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
A və B əlaqəli iki siyahını nəzərə alaraq, A siyahısının alternativ mövqelərində B qovşaqlarını A-ya daxil etməliyik.
misal
Zamanın mürəkkəbliyi: O (n),
n - ilk siyahıdakı qovşaq sayı.
Alqoritm
a. ListA-da mövcud mövqelər olmayana qədər keçin.
b. ListB-də dövr edin və ListB-nin qovşaqlarını ListA-ya daxil edin
c. Göstəriciləri dəyişdirərək əlavə edin.
d. Həm A həm də B növbəti göstəricilərini saxlayın.
e. B işarəsini A göstəricisinin yanında, B göstəricisinin sonrakı hissəsini A göstəricisinin yanında edin, bunu etməklə ListA-ya ListB düyünü əlavə edirik.
f. ListA və ListB göstəricilərini hərəkət etdirin.
Alqoritm işləyir
C ++ Proqramı
#include <bits/stdc++.h>
using namespace std;
struct LLNode
{
int data;
struct LLNode* next;
};
/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
struct LLNode* curr = new LLNode;
curr->data = dataToBeInserted;
curr->next = NULL;
if(*head == NULL)
*head=curr; //if this is first node make this as head of list
else
{
curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
*head=curr;
}
//O(1) constant time
}
//display linked list
void display(struct LLNode**node)
{
struct LLNode *temp= *node;
if (temp==NULL)
{
cout<<"Empty linked list"<<endl;
}
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
void Merge(struct LLNode *A, struct LLNode **B)
{
struct LLNode *current_inA = A, *current_inB = *B;
struct LLNode *next_inA, *next_inB;
while (current_inA != NULL && current_inB != NULL)
{
//store next pointers of current pointers
next_inA = current_inA->next;
next_inB = current_inB->next;
//adding node from B to A by changing:
//next of node in B to next in A
//move pointers
current_inB->next = next_inA;
current_inA->next = current_inB;
current_inA = next_inA;
current_inB = next_inB;
}
//change pointer of head of list B
//remaining nodes
*B = current_inB;
}
// Driver program to test above functions
int main()
{
struct LLNode *ListA = NULL, *ListB = NULL;
insertAtBeginning(&ListA, 8);
insertAtBeginning(&ListA, 7);
insertAtBeginning(&ListA, 6);
insertAtBeginning(&ListB, 5);
insertAtBeginning(&ListB, 4);
insertAtBeginning(&ListB, 3);
insertAtBeginning(&ListB, 2);
insertAtBeginning(&ListB, 1);
cout<<"Linked List A: ";
display(&ListA);
cout<<"Linked List B: ";
display(&ListB);
cout<<"Merging List B into List A at alternate positions in A";
Merge(ListA,&ListB);
cout<<"\nOutput Linked List A: ";
display(&ListA);
cout<<"Output Linked List B: ";
display(&ListB);
return 0;
}
