Bağlı bir siyahını qruplara çevirin

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.

Verilən əlaqəli siyahıda, hər k düyünlərini tərsinə çevirmək üçün bir funksiya yazın.
(K giriş dəyəridir)

misal

Alqoritm

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

a. K ölçülü alt siyahılar dəstindəki əlaqəli siyahını tərsinə çevirmək üçün ReverseInGroups funksiyası yaradın.

b. Bu funksiyada biz rekursiv metoddan istifadə edirik

      1) Əvvəlcə k ölçüsünün ilk alt siyahısını tərsinə çevirin.

      2) Növbəti düyünü (növbəti) və əvvəlki düyünləri (əvvəlki) izləyin.

      3) Funksiya əvvəlki qayıdır, bu da siyahının rəhbəri olur.

      4) Siyahının qalan hissəsi üçün rekursiv funksiyanı çağırın və iki alt siyahını birləşdirin.

C ++ Proqramı

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};


struct LLNode *reverse(struct LLNode *head, int k)
{
    struct LLNode* curr = head;
    //Initialize next and previous as null
    struct LLNode* next = NULL;
    struct LLNode* previous = NULL;
    int count = 0;   
     
    //reverse first k nodes
    while (curr != NULL && count < k)
    {
        next  = curr->next;
        curr->next = previous;
        previous = curr;
        curr = next;
        count = count + 1;
    }
    if (next !=  NULL)
    {
       head->next = reverse(next, k); 
    }
 
    //previous will be new head of the linked list
    return previous;
}
 
/* 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;
}
//Main function
int main(void)
{

    struct LLNode* head = NULL;//initial list has no elements
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 4);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);           
    
    cout<<"The list initially is :-\n";
    display(&head);
    int k = 3;
    cout<<"value of k: "<<k<<endl;
    head = reverse(head, k);//call function on head
    
    cout<<"\nFinal list after reversing is:-\n";
    display(&head);

    return(0);
}

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