K-Qrupda Əks Düyünlər

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Çiy kərpic Amazon alma ByteDance Facebook microsoft
Bağlı siyahıBaxılıb 71

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.

Problem

In K-Qrupda Əks Düyünlər problem verdik əlaqəli siyahıBağlı siyahını k qrupunda tərs edin və dəyişdirilmiş siyahını qaytarın.

Düyünlər k-dən çox deyilsə, qalan düyünləri tərs çevirin. K-nin dəyəri hər zaman əlaqəli siyahının uzunluğuna bərabərdir və ya həmişə 0-dan böyükdür.

misal

Input

[1, 2, 3, 4, 5] K = 3

Buraxılış

[3, 2, 1, 5, 4]

Izahat

K-Qrupda Əks DüyünlərPin

K qrupunda qovşaqları tərs çevirəcəyik. K = 3 dəyəri olaraq. Beləliklə, ilk k düyünlərini tərs edəcəyik. Düyünlər k-in çoxu deyil, ona görə də 2 qovşaqda qalırıq. Qalan iki nodu geri qaytaracağıq, bu bizim cavabımızdır.

K-Qrupdakı Ters Düyünlər üçün yanaşma

Biz istifadə edəcəyik rekursiv k qrupunda verilmiş əlaqəli siyahını geri çevirmək üçün yanaşma.

  • Bağlı siyahının ilk k düyünlərini tərsinə çevirin. Siyahının ilk k qovşaqlarını geri qaytararkən əvvəlki və sonrakı göstəricini qoruyur. Əvvəlki göstərici geri döndüyümüz k qrup qruplarının ilk qovşağına işarə edəcəkdir. Növbəti göstərici geri döndüyümüz k qrupu düyünündən sonra növbəti düyünü göstərəcəkdir.
  • K qrupu tərs döndükdən sonra rekursivdir funksiyası k qrupunun başını tərs node qaytaracaq. Beləliklə baş-> next = təyin edəcəyiktərs (sonrakı, k).
  • bundan sonra k + 1-ci düyünü göstərir. Rekursiv olaraq siyahını cari vaxtdan başlayaraq çağıracağıq və siyahının qalan hissəsini ilk düyünün yanında edəcəyik.
  • Bütün rekursiv əməliyyatlardan sonra bir qrup qovşaqda əks əməliyyatı yerinə yetirdikdən sonra əlaqəli bir siyahı əldə edəcəyik.

K-Qrupdakı Ters Düyünlər üçün tətbiqetmə

K-Group'dakı Reverse Nodes üçün C ++ kodu

// CPP program to reverse a linked list 
// in groups of given size 
#include <bits/stdc++.h> 
using namespace std; 

/* Link list node */
class Node 
{ 
  public: 
  int data; 
  Node* next; 
}; 

/* Reverses the linked list in groups 
of size k and returns the pointer 
to the new head node. */
Node *reverse (Node *head, int k) 
{ 
  Node* current = head; 
  Node* next = NULL; 
  Node* prev = NULL; 
  int count = 0; 
  
  /*reverse first k nodes of the linked list */
  while (current != NULL && count < k) 
  { 
    next = current->next; 
    current->next = prev; 
    prev = current; 
    current = next; 
    count++; 
  } 
  
  /* next is now a pointer to (k+1)th node 
  Recursively call for the list starting from current. 
  And make rest of the list as next of first node */
  if (next != NULL) 
  head->next = reverse(next, k); 

  /* prev is new head of the input list */
  return prev; 
} 

/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(Node** head_ref, int new_data) 
{ 
  /* allocate node */
  Node* new_node = new Node(); 

  /* put in the data */
  new_node->data = new_data; 

  /* link the old list off the new node */
  new_node->next = (*head_ref);	 

  /* move the head to point to the new node */
  (*head_ref) = new_node; 
} 

/* Function to print linked list */
void printList(Node *node) 
{ 
  while (node != NULL) 
  { 
    cout<<node->data<<" "; 
    node = node->next; 
  } 
} 

int main() 
{
  Node* head = NULL; 

  /* Created Linked list is 1->2->3->4->5->6->7->8->9 */
  push(&head, 9); 
  push(&head, 8); 
  push(&head, 7); 
  push(&head, 6); 
  push(&head, 5); 
  push(&head, 4); 
  push(&head, 3); 
  push(&head, 2); 
  push(&head, 1);	 

  cout<<"Given linked list \n"; 
  printList(head); 
  head = reverse(head, 3); 

  cout<<"\nReversed Linked list \n"; 
  printList(head); 

  return(0); 
}
Given Linked List
1 2 3 4 5 6 7 8 9 
Reversed list
3 2 1 6 5 4 9 8 7

K-Group'dakı Reverse Nodes üçün Java kodu

// Java program to reverse a linked list in groups of 
// given size 
class LinkedList 
{ 
  Node head; // head of list 

  /* Linked list Node*/
  class Node 
  { 
    int data; 
    Node next; 
    Node(int d) {data = d; next = null; } 
  } 

  Node reverse(Node head, int k) 
  { 
  Node current = head; 
  Node next = null; 
  Node prev = null; 
    
  int count = 0; 

  /* Reverse first k nodes of linked list */
  while (count < k && current != null) 
  { 
    next = current.next; 
    current.next = prev; 
    prev = current; 
    current = next; 
    count++; 
  } 

  /* next is now a pointer to (k+1)th node 
    Recursively call for the list starting from current. 
    And make rest of the list as next of first node */
  if (next != null) 
    head.next = reverse(next, k); 

  // prev is now head of input list 
  return prev; 
  }					 

          
  /* Utility functions */

  /* Inserts a new Node at front of the list. */
  public void push(int new_data) 
  { 
    /* 1 & 2: Allocate the Node & 
        Put in the data*/
    Node new_node = new Node(new_data); 

    /* 3. Make next of new Node as head */
    new_node.next = head; 

    /* 4. Move the head to point to new Node */
    head = new_node; 
  } 

  /* Function to print linked list */
  void printList() 
  { 
    Node temp = head; 
    while (temp != null) 
    { 
    System.out.print(temp.data+" "); 
    temp = temp.next; 
    } 
    System.out.println(); 
  } 

  /* Driver program to test above functions */
  public static void main(String args[]) 
  { 
    LinkedList llist = new LinkedList(); 
    
    /* Constructed Linked List is 1->2->3->4->5->6-> 
    7->8->8->9->null */
    llist.push(9); 
    llist.push(8); 
    llist.push(7); 
    llist.push(6); 
    llist.push(5); 
    llist.push(4); 
    llist.push(3); 
    llist.push(2); 
    llist.push(1); 
    
    System.out.println("Given Linked List"); 
    llist.printList(); 
    
    llist.head = llist.reverse(llist.head, 3); 

    System.out.println("Reversed list"); 
    llist.printList(); 
  } 
}
Given Linked List
1 2 3 4 5 6 7 8 9 
Reversed list
3 2 1 6 5 4 9 8 7

Zaman mürəkkəbliyi

O (n)  hər qovşaq yalnız bir dəfə keçdiyi üçün.

Kosmik mürəkkəblik

O (1) əvvəlki və sonrakı qovşaqların ünvanını saxlamaq üçün yalnız dəyişənlərdən istifadə etdiyimiz üçün.

References

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