Ziq-Zaqda əlaqəli siyahını yenidən düzəldin

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.

Bağlı bir siyahını a, b, c, d, e, f düyünlü əlaqəli siyahı üçün a <b> c <d> e <f> şəklində olmalıdır.

misal

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

Alqoritm

a. Bağlı siyahını başdan keçin.

b. Dəyişən bir bayraq yaradın (Boolean dəyəri).

1. Əgər bayraq doğrudursa, cərəyanın növbəti düyünü daha böyük olmalıdır. Əgər onları dəyişdirməsəniz.

2. Əgər bayraq yalnışdırsa, cərəyanın növbəti düyünü daha kiçik olmalıdır. Əgər onları dəyişdirməsəniz.

c. Keçərkən, hər dəfə bir mövqe irəlilədikdə bayrağın dəyərini dəyişdirin.

d. Son siyahı istədiyiniz siyahıdır.

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;
    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 ZigZag(struct LLNode *head)
{
    bool flag = true;
 
    // Traverse linked.
    struct LLNode* curr = head;//start from head
    while (curr->next != NULL)
    {
        //Condition is X > Y > Z swap Y and Z
        //convert to X > Z < Y or Z < Y with no X
        if(flag)
        {
            if (curr->data > curr->next->data)
            {
                swap(curr->data, curr->next->data);
            }
        }
        //Condition is X < Y < Z swap Y and Z
        //convert to X < Z > Y or Z > Y with no X
        else
        {
            if (curr->data < curr->next->data)
            {
                swap(curr->data, curr->next->data);
            }
        }
        //Move forward by reversing flag
        curr = curr->next;
        flag = !flag;
    }
    //O(number of nodes)
}
  
//Main function
int main(void)
{
    struct LLNode* head = NULL;
    insertAtBeginning(&head, 1);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 4);
 
    cout<<"Input linked list is: ";
    display(&head);
    ZigZag(head);
    cout<<"'\nOutput linked list is: ";
    display(&head);
 
    return (0);
}

 

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