시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
"BST 수정이 허용되지 않는 경우 BST에서 K 번째로 큰 요소"는 이진 검색 트리가 제공되고 k 번째로 큰 요소를 찾아야 함을 나타냅니다. 이것은 이진 검색 트리의 모든 요소가 내림차순으로 배열 될 때를 의미합니다. 그런 다음 시퀀스에서 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 개의 이진 트리 노드를 저장하고 있기 때문입니다.
