BST 수정이 허용되지 않는 경우 BST에서 K '번째로 큰 요소

난이도 중급
자주 묻는 질문 아마존 시스코 구글 UHG 옵텀
이진 검색 트리 이진 트리 나무조회수 80

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

"BST 수정이 허용되지 않는 경우 BST에서 K 번째로 큰 요소"는 이진 검색 트리가 제공되고 k 번째로 큰 요소를 찾아야 함을 나타냅니다. 이것은 이진 검색 트리의 모든 요소가 내림차순으로 배열 될 때를 의미합니다. 그런 다음 시퀀스에서 k 번째 요소를 반환해야합니다.

입력

BST 수정이 허용되지 않는 경우 BST에서 K '번째로 큰 요소

k = 4

3

설명 : 나무의 이미지는 위에 표시됩니다. 그리고 우리는 4 번째로 큰 요소를 찾아야합니다. 따라서 오름차순으로 정렬하면 {1, 2, 3, 4, 5, 6}이됩니다. 따라서 네 번째로 큰 요소는 세 번째로 작은 요소입니다. 따라서 4을 출력으로 반환합니다.

BST 수정이 허용되지 않는 경우 BST에서 K '번째로 큰 요소를 찾는 방법

우리는 이미 비슷한 질문을했습니다. k 번째로 작은 요소 BST에서. 문제는 그것에 대한 수정일뿐입니다. 이전 게시물에서 해당 질문에 대한 솔루션에 대해 논의했습니다. 첫 번째 방법은 트리 데이터 구조를 수정하는 것이 었습니다. 다른 하나는 이진 검색 트리에 대해 순서대로 순회를 실행하고 노드를 계속 계산하는 것입니다. 이전 질문은 k 번째 작은 값을 반환하는 것이 었습니다. 우리는 단순히 노드 수를 세고 그 수가 k와 같으면 해당 노드의 값을 반환했습니다.

순진한 접근

여기 상황이 조금 다릅니다. k 번째로 큰 요소를 찾아야합니다. 먼저 트리에서 총 노드 수를 찾은 다음 총 노드 수에서 k-1을 뺍니다. 이제 n-k + 1 가장 작은 노드를 찾습니다. 여기서 n은 이진 검색 트리의 총 노드 수입니다. 하지만이 방법은 두 번 또는 두 번 순회 나무 위에.

효율적인 접근

내림차순으로 노드를 찾을 수 있다면 효율적으로 문제를 해결할 수 있습니다. 이렇게하면 트리에서 총 노드 수를 찾을 필요가 없습니다. 효율적인 접근 방식은 트리를 역 순회하는 것입니다. 이진 검색 트리의 역 순회는 트리를 내림차순으로 순회합니다. 따라서 역순으로 수행하는 동안 노드 수를 계속 계산합니다. 카운트가 k가되면 해당 노드의 값을 반환합니다.

암호

BST 수정이 허용되지 않는 경우 BST에서 K 번째로 큰 요소를 찾는 C ++ 코드

#include <bits/stdc++.h>
using namespace std;
struct node{
    int data;
    node *left;
    node *right;
} ;
node* create(int data){
    node * tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}
// normally insert the node in BST
node* insert(node* root, int x)
{
    if (root == NULL)
        return create(x);
    if(x<root->data)
        root->left = insert(root->left, x);
    else if(x>root->data)
        root->right = insert(root->right, x);
    return root;
}
node* findKthLargest(node* root, int& k)
{
    // base case
    if(!root)
        return NULL;
    node *right = findKthLargest(root->right, k);
    if(right)
        return right;
    // if current element is kth largest
    if(k==1)
        return root;
    // if the kth largest is not found in the left subtree
    // search in left subtree
    k--;
    return findKthLargest(root->left, k);
}
int main()
{
    node *root = NULL;
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int element;cin>>element;
        root = insert(root, element);
    }
    int k;cin>>k;
    node* res = findKthLargest(root, k);
    if(res == NULL)
        cout<<"No kth largest found";
    else
        cout<<"Kth largest element is "<<res->data;
}
6
3 2 1 5 4 6
4
Kth largest element is 3

BST 수정이 허용되지 않을 때 BST에서 K'th 가장 큰 요소를 찾는 Java 코드

import java.util.*;
import java.lang.*;
import java.io.*;
 
class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  static node root;
  static int count;
  static node create(int data){
      node tmp = new node();
      tmp.data = data;
      tmp.left = null;
      tmp.right = null;
      return tmp;
  }
 
  static node insert(node root, int x)
  {
      if (root == null)
          return create(x);
      if(x<root.data)
          root.left = insert(root.left, x);
      else if(x>root.data)
          root.right = insert(root.right, x);
      return root;
  }
 
  static node findKthLargest(node root, int k)
  {
      // base case
      if(root == null)
          return null;
      node right = findKthLargest(root.right, k);
      if(right != null)
          return right;
      count++;
      // if current element is kth largest
      if(k==count)
          return root;
      // if the kth largest is not found in the left subtree
      // search in left subtree
      return findKthLargest(root.left, k);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      for(int i=0;i<n;i++){
          int element = sc.nextInt();
          root = insert(root, element);
      }
      int k = sc.nextInt();
      count = 0;
      node res = findKthLargest(root, k);
      if(res == null)
          System.out.println("No kth largest found");
      else
          System.out.println("Kth largest element is "+res.data);
  }
}
6
3 2 1 5 4 6
4
Kth largest element is 3

복잡성 분석

시간 복잡성

의 위에), 우리는 단순히 BST, BST에는 N 개의 노드 만 있기 때문에. 우리는 O (N)의 선형 시간 복잡도를 달성했습니다.

공간 복잡성

O (1), 우리는 일정한 여분의 공간만을 사용했습니다. 따라서이 알고리즘 만 일정한 공간 복잡성을 갖지만 프로그램 전체는 선형 공간 복잡성을가집니다. N 개의 이진 트리 노드를 저장하고 있기 때문입니다.

균열 시스템 설계 인터뷰
Translate »