İki əlaqəli siyahının birləşməsi və kəsişməsi

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 əlaqəli siyahı verildikdə, iki əlaqəli siyahıda elementlərin birləşməsini və kəsişməsini tapın.

misal

İki siyahı bunlardır: -
list1 = 8 -> 4 -> 5
list2 = 8 -> 2 -> 5

İki siyahının birliyi
2 -> 5 -> 4 -> 8

İki siyahının kəsişməsi
5 -> 8

QEYD : Həm birləşmə, həm də kəsişmə siyahılarında elementlərin qaydasında olmasına ehtiyac yoxdur.

Zamanın mürəkkəbliyi: O (mn),

burada m - list1-dəki elementlərin sayı və n - list2-dəki elementlərin sayı

Alqoritm

Ittifaq

1. List1-dən keçin və list1-dəki bütün elementləri siyahıya çıxarmaq üçün daxil edin

2. List2-yə keçin və elementin list1-də olub olmadığını yoxlayın. Təqdim edilmədikdə elementi siyahıya daxil edin.

Kəsişmə:

1. List1-dən keçin və elementin list2-də olub olmadığını yoxlayın. Mövcud olduqda elementi siyahıya daxil edin.

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;

struct LLNode{
	int data;
	LLNode *next;	
};
void insertAtBeginning(LLNode**head,int dataToBeInserted);
//search function, says whether the element is present in that list or not
int search(LLNode *head, int data) 
{
  LLNode* temp = head;
    while (temp != NULL) {
        if (temp->data == data){
            return 1;
        }
        temp = temp->next;
    }
    return 0;
}
//Finding the union of elements in two linked lists
//By checking whether the element in list2 is present in list1 or not
LLNode* findUnion(LLNode* list1, LLNode* list2)
{
  LLNode* unionLL = NULL;
  LLNode* temp1 = list1;
  LLNode* temp2 = list2;
  //Inserting all the elements in list1 to unionLL list
  while(temp1 != NULL) {
      insertAtBeginning(&unionLL, temp1->data);
      temp1 = temp1->next;
  }
  //If element in list2 is not present in list1
  //then inserting the element to unionLL list
  while(temp2 != NULL) {
      if (!search(list1, temp2->data))
      {
        insertAtBeginning(&unionLL, temp2->data);
      }
      temp2 = temp2->next;
  }
  return unionLL;
}
//Finding the Intersection of elements in two linked lists
//By checking whether the element in list1 is present in list2 or not
LLNode* findIntersection(LLNode* list1, LLNode* list2)
{
  LLNode* intersectionLL = NULL;
  LLNode* temp1 = list1;
  //If element in list1 is present in list2
  //then inserting the element to intersectionLL list
  while(temp1 != NULL) {
      if (search(list2, temp1->data))
      {
        insertAtBeginning(&intersectionLL, temp1->data);
      }
      temp1 = temp1->next;
  }
  return intersectionLL;
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
	LLNode*curr=new LLNode;
	//make a new node 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 node as head of list
			*head=curr;
		
	else //make the next of the current node point to the present head and make the current node 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 node
		}
		//O(number of nodes)
	cout<<endl;
}

int main() 
{    
	LLNode *result = NULL;
  LLNode *unionLL = NULL;
  LLNode *intersectionLL = NULL;

	LLNode *list1 = NULL; //initial list has no elements
	insertAtBeginning(&list1,5);
	insertAtBeginning(&list1,4);
  insertAtBeginning(&list1,8);

  LLNode *list2 = NULL;
  insertAtBeginning(&list2,5);
  insertAtBeginning(&list2,2);
  insertAtBeginning(&list2,8);


	
	cout<<"\nTwo Lists are :-\n";
	display(&list1);
  display(&list2);
	unionLL = findUnion(list1,list2);
	cout<<"Union of two lists"<<endl;
	display(&unionLL);

  intersectionLL = findIntersection(list1,list2);
  cout<<"Intersection of two lists"<<endl;
  display(&intersectionLL);

	return 0;
}

 

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