Zəncir cütlərinin maksimum uzunluğu

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Bloomberg Über
Dinamik proqramlaşdırma GörməmişBaxılıb 338

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Zəncir cütləri probleminin maksimum uzunluğunda n cüt cüt verdik, b <c olduqda (c, d) (a, b) təqib edə biləcəyi ən uzun zənciri tapın. Verilən cütlərdə birinci element həmişə ikincidən kiçikdir.

 misal

Input

[{12, 14}, {23, 29}, {18, 41}, {30,34}]

Buraxılış

3

Izahat

Burada zəncir {12, 14}, {23, 29}, {30, 34}

Zəncir cütlərinin maksimum uzunluğuna yanaşma

Burada ən uzun artan ardıcıllıq alqoritminin dəyişdirilmiş yolundan istifadə edirik. Birincisi, elementləri elə sıralamalıyıq ki, birinci element daim artan sırada olsun. İndi vektorun cari cütlüyünə ən uzun artan ardıcıllığı tətbiq edirik. İndi yaradılan zəncirin cari və ikinci elementinin birinci elementini müqayisə edin. Zəncirdə heç bir cüt ilk cütü əlavə etmirsə. Birinci element> zəncirdə sonuncu ikinci element bir element əlavə edərsə. Başqa, dəyişdirin. İndi daha çox anlayış üçün məntiqin addım-addım icrasına baxın -

arr [] = {{12, 14}, {23, 29}, {18, 41}, {30,34}};

Əvvəlcə serialı birinci element əsasında sıralayırıq.

arr [] = {{12,14}, {18,41}, {23,29}, {30,34}}

İndi elementləri zəncirə əlavə edin və uzunluq saylarını artırın.

zəncir = {{12,14}}; //addım 1;

zəncir = {{12,14}, {23,29}}; // addım 2;

zəncir = {{12,14}, {23,29}, {30,34}}; // addım 3;

Alqoritm

a. Verilən cütləri birinci element artan sıraya görə sıralayın.

b. Burada dəyişdirilmiş istifadə edirik LİS,

  • Yaradılan zəncirin cari və ikinci elementini müqayisə edin.
  • Zəncirdə heç bir cüt ilk cütü əlavə etmirsə.
  • Birinci element> zəncirdə sonuncu ikinci element bir element əlavə edərsə.
  • Başqa, dəyişdirin.

c. Nəhayət, yaradılan zəncirin uzunluğunu qaytarın.

Həyata keçirilməsi

Maksimum Zəncir Cütlükləri üçün C ++ Proqramı

#include <stdio.h>
#include <stdlib.h>
//pair structure
struct pair
{
  int a;
  int b;
};
 
int MaxChainLen(struct pair array[], int n)
{
   int i, j, maximum_len = 0;
   int *length_array = (int*) malloc ( sizeof( int ) * n );
   //initilize length array
   for ( i = 0; i < n; i++ )
   {
      length_array[i] = 1;
   }
   //algorithm
   for(i = 1; i < n; i++ ){
      for(j = 0; j < i; j++ )
      {
         if(array[i].a > array[j].b && length_array[i] < length_array[j] + 1)
         {
            length_array[i] = length_array[j] + 1;
         }
        }
   }
   for(i = 0; i < n; i++ )
   {
      if(maximum_len < length_array[i] )
       { 
         maximum_len = length_array[i];
       }
   }
   free( length_array );
   return maximum_len;
}
 
/* Driver program to test above function */
int main()
{
    struct pair input_array[] = {{12, 14}, {18, 41}, {23, 29}, {30, 34}};
    int size = sizeof(input_array)/sizeof(input_array[0]);
    printf("length of longest chain is: %d",MaxChainLen(input_array,size));
    return 0;
}

Maksimum Zəncir Cütlükləri üçün Java Proqramı

import java.util.Scanner;
class sum
{
    public static int MaxChainLen(int array[][], int n)
    {
       int i, j, maximum_len = 0;
       int length_array[] = new int[n];
       //initilize length array
       for ( i = 0; i < n; i++ )
       {
          length_array[i] = 1;
       }
       //algorithm
       for(i = 1; i < n; i++ ){
          for(j = 0; j < i; j++ )
          {
             if((array[i][0] > array[j][1]) && (length_array[i] < (length_array[j] + 1)))
             {
                length_array[i] = length_array[j] + 1;
             }
            }
       }
       for(i = 0; i < n; i++ )
       {
          if(maximum_len < length_array[i] )
           { 
             maximum_len = length_array[i];
           }
       }
       return maximum_len;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[][] = new int[n][2];
        for(int i=0;i<n;i++)
        {
            arr[i][0] = sr.nextInt();
            arr[i][1] = sr.nextInt();
        } 
        int ans = MaxChainLen(arr,n);
        System.out.println("length of longest chain is: " + ans);
    } 
}
4
12 14 
18 41 
23 29 
30 34
length of longest chain is: 3

Zəncir Cütlərinin Maksimum Uzunluğu üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (nlogn) burada n verilən cütlərin sayıdır. Burada zaman mürəkkəbliyini n ^ 2-yə aparan loop üçün ikisini yuyuruq.

Kosmik Mürəkkəblik

O (1) çünki köməkçi məkan olaraq yalnız bir neçə dəyişəndən istifadə edirik.

References

Crack Sistemi Dizayn Müsahibələri
Translate »