Bəzi ümumi qovşaqları olan iki Sıralanmış Bağlı Siyahıdan Maksimum Cəm Bağlı Siyahı yaradın

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.

İ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;
}

 

 

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