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.
Mündəricat
İki sıralanmış əlaqəli siyahı nəzərə alınaraq, başdan sona qədər maksimum cəm yolu olan bir siyahı hazırlayın.
Nəticə siyahısında hər iki giriş siyahısından qovşaqlar ola bilər. nəticə siyahısını qurarkən digər giriş siyahısına yalnız kəsişmə nöqtəsində keçə bilərik (eyni dəyərə malik düyün).
misal
INPUT
siyahısı1
2->8->34->50->71->75
siyahı2:
1->8->10->45->50->80
ÇIXDI
2 -> 8 -> 10 -> 45 -> 50 -> 71 -> 75 -> XNUMX
Yuxarıdakı nümunədə 8-in ilk ümumi düyün, 2-nin 8-ə qədər ən böyük cəm olduğunu görə bilərik.
8-dən sonra 50, növbəti ümumi qovşaqdır və 55, 50-ə qədər ən böyük cəmdir. Beləliklə, 10, 45 nəticədəki elementlərdir. 50-dən sonra 146 ən böyük cəm olduğundan 71, 75 nəticə siyahısındakı elementlərdir
Zaman Mürəkkəbliyi: O (n)
Alqoritm
Temp1, curr1 - list1 və temp2, curr2 - list2 başladın
1. Hər iki siyahıdan keçin və ilk ümumi nodu tapın ("curr" göstəricisindən istifadə edərək), yəni yuxarıdakı nümunədə 8
2. Həm də hər iki siyahıda daha çox cəmi izləyin. Daha çox cəmi olan siyahının rəhbəri nəticə siyahısının başıdır (yəni “temp” göstəricisindən istifadə etməklə). yəni yuxarıdakı nümunədə 2 (list1)
3. Bundan sonra, hər iki siyahının göstəriciləri NULL olmayana qədər. daha çox cəmi əsas götürərək növbəti temp göstəricilərini dəyişdirməliyik
Yuxarıda göstərilən alqoritm aşağıdakı diaqramda açıq şəkildə izah olunur
C ++ Proqram
#include <bits/stdc++.h>
using namespace std;
struct LLNode{
int data;
LLNode *next;
};
LLNode* maxSumList(LLNode* list1, LLNode* list2)
{
LLNode *result = NULL;
// Assigning temp and curr to the head of the linked list
LLNode *temp1 = list1, *curr1 = list1;
LLNode *temp2 = list2, *curr2 = list2;
// Till either of the current pointers is not
// NULL execute the loop
while (curr1 != NULL || curr2 != NULL)
{
//variables sum1, sum2 to keep track of sum between
//temp and curr in both lists
int sum1 = 0, sum2 = 0;
//calculating sum till the common node
while (curr1!=NULL && curr2!=NULL && curr1->data!=curr2->data)
{
if (curr1->data < curr2->data)
{
sum1 += curr1->data;
curr1 = curr1->next;
}
else // (curr2->data < curr1->data)
{
sum2 += curr2->data;
curr2 = curr2->next;
}
}
// If either of current pointers becomes NULL
// carry on the sum calculation for other one.
if (curr1 == NULL)
{
while (curr2 != NULL)
{
sum2 += curr2->data;
curr2 = curr2->next;
}
}
if (curr2 == NULL)
{
while (curr1 != NULL)
{
sum1 += curr1->data;
curr1 = curr1->next;
}
}
//For the first common node
//To know the head of the result list
if (temp1 == list1 && temp2 == list2)
result = (sum1 > sum2)? temp1 : temp2;
//If temp1 and temp2 are not the heads, then update next pointers
else
{
if (sum1 > sum2)
temp2->next = temp1->next;
else
temp1->next = temp2->next;
}
// updating temp pointers
temp1 = curr1, temp2 = curr2;
// If curr1 is not NULL move to the next.
if (curr1)
curr1 = curr1->next;
// If curr2 is not NULL move to the next.
if (curr2)
curr2 = curr2->next;
}
return result;
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
LLNode*curr=new LLNode;
//make a new LLNode with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;
if(*head==NULL) //if list is empty then set the current formed LLNode as head of list
*head=curr;
else //make the next of the current LLNode point to the present head and make the current LLNode as the new head
{
curr->next=*head;
*head=curr;
}
//O(1) constant time
}
void display(LLNode**head)
{
LLNode*temp=*head;
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;
temp=temp->next; //move to next LLNode
}
//O(number of nodes)
cout<<endl;
}
int main()
{
LLNode *result = NULL;
LLNode *list1 = NULL; //initial list has no elements
insertAtBeginning(&list1,75);
insertAtBeginning(&list1,71);
insertAtBeginning(&list1,50);
insertAtBeginning(&list1,34);
insertAtBeginning(&list1,8);
insertAtBeginning(&list1,2);
LLNode *list2 = NULL;
insertAtBeginning(&list2,80);
insertAtBeginning(&list2,50);
insertAtBeginning(&list2,45);
insertAtBeginning(&list2,10);
insertAtBeginning(&list2,8);
insertAtBeginning(&list2,1);
cout<<"\n Two lists are :-\n";
display(&list1);
display(&list2);
result = maxSumList(list1,list2);
cout<<"Max Sum List is"<<endl;
display(&result);
return 0;
}
