시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
“바이너리 트리가 BST인지 확인하는 프로그램”은 바이너리 트리를 부여 받았으며 바이너리 트리가 바이너리 검색 트리의 속성을 만족하는지 확인해야한다고 말합니다. 따라서 이진 트리에는 다음과 같은 속성이 있습니다.
- 왼쪽 하위 트리에는 루트보다 값이 작은 노드가 있어야합니다.
- 오른쪽 하위 트리에는 루트보다 큰 데이터가있는 노드가 포함되어야합니다.
- 왼쪽 및 오른쪽 하위 트리 자체는 이진 검색 트리 여야합니다. 즉, 이진 검색 트리의 속성을 따라야합니다.
예
입력
YES
설명 : 주어진 트리는 이진 검색 트리의 모든 속성을 따릅니다. 왼쪽 하위 트리의 모든 노드는 루트 값보다 작습니다. 오른쪽 하위 트리도 마찬가지입니다. 노드의 값은 루트보다 큽니다. 그리고 왼쪽 하위 트리와 오른쪽 하위 트리 자체는 BST의 속성을 따릅니다.
입력
NO
설명 : 트리는 다음 속성을 따르지 않습니다. BST여기서 왼쪽 하위 트리의 모든 노드는 루트보다 작은 값을 가져야합니다.
이진 트리가 BST인지 여부를 확인하는 프로그램 접근 방식
순진한 접근 (잘못된 접근)
여기서 우리는 왼쪽 서브 트리의 루트가 루트 값보다 작은 값을 가지고 있는지 확인하는 프로그램을 작성합니다. 그리고 오른쪽 하위 트리의 루트는 루트보다 큰 값을 갖습니다. 그런 다음 왼쪽 및 오른쪽 하위 트리를 재귀 적으로 확인합니다. 그러나이 방법은 왼쪽 하위 트리 루트가 루트보다 작기 때문에 잘못되었습니다. 왼쪽 하위 트리에 루트에 비해 더 큰 값을 가진 일부 노드가있을 수 있습니다. 오른쪽 하위 트리도 마찬가지입니다. 따라서이 경우이 접근 방식은 실패합니다.
주어진 트리 (이미지)에서 알고리즘을 실행합니다. 알고리즘이 주어진 이진 트리가 BST임을 반환하더라도 알 수 있습니다. 그러나 오른쪽 하위 트리의 1이 2보다 작기 때문에 다른 방법을 찾아야합니다.
효율적인 접근 (올바른 접근 방식)
왼쪽 및 오른쪽 하위 트리의 범위를 정의하기 위해 최소 및 최대 두 개의 변수를 사용합니다. 이것은 왼쪽 하위 트리의 요소가 특정 범위에 있는지 여부를 알려줍니다. 이 범위는 하위 트리를 계속 변경함에 따라 계속 변경됩니다. 이 방법은 순진한 접근 방식에서 직면하는 결함을 제거하는 데 사용됩니다. 왼쪽 하위 트리의 모든 요소가 루트보다 작다는 것을 보장 할 수 없습니다. 그리고 오른쪽 하위 트리의 모든 요소는 루트보다 큽니다. 처음에는 최소값을 정수의 최소값으로, 최대 값을 정수의 최대 값으로 설정 한 BST 검사기를 호출합니다. 그것이 루트의 값을 만족해야하는 범위이기 때문입니다. 이제 왼쪽 하위 트리의 최대 값을 루트의 값 -1로 업데이트하고 오른쪽 하위 트리의 경우 최소값을 루트의 값으로 설정합니다. 이제 최소 및 최대 값을 적절하게 설정하고 왼쪽 및 오른쪽 하위 트리에 대한 함수를 반복적으로 호출합니다.
암호
바이너리 트리가 BST인지 확인하는 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;
}
bool isThisBST(node* root, int minimum, int maximum)
{
// if there is no tree
if(!root)
return true;
// the root should be in the range defined by [minimum, maximum]
if(root->data < minimum || root->data > maximum)
return false;
// if the root satisfies the value then we recursively check the same for left and right subtree
// we set the minimum and maximum for left and right subtrees accordingly.
return isThisBST(root->left, minimum, root->data-1) && isThisBST(root->right, root->data+1, maximum);
}
int main()
{
node *root = create(2);
root->left = create(1);
root->right = create(4);
root->right->left = create(3);
root->right->right = create(5);
bool isBST = isThisBST(root, INT_MIN, INT_MAX);
cout<<((isBST == true) ? "YES" : "NO");
return 0;
}
YES
바이너리 트리가 BST인지 확인하는 Java 프로그램
// Class that denote a node of the tree
class Node
{
int data;
Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
}
class Tree
{
static Node root;
// return true if the tree is BST else return false
static boolean isThisBST(Node root, int minimum, int maximum)
{
// if there is no tree
if(root == null)
return true;
// the root should be in the range defined by [minimum, maximum]
if(root.data < minimum || root.data > maximum)
return false;
// if the root satisfies the value then we recursively check the same for left and right subtree
// we set the minimum and maximum for left and right subtrees accordingly.
return isThisBST(root.left, minimum, root.data-1) && isThisBST(root.right, root.data+1, maximum);
}
public static void main(String args[])
{
Tree tree = new Tree();
tree.root = new Node(2);
tree.root.left = new Node(1);
tree.root.right = new Node(4);
tree.root.right.left = new Node(3);
tree.root.right.right = new Node(5);
boolean isBST = isThisBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
System.out.print((isBST == true) ? "YES" : "NO");
}
}
YES
복잡성 분석
시간 복잡성
의 위에), 우리는 나무를 통해서만 횡단했기 때문입니다. 그리고 단일 순회는 선형 시간 복잡성을 필요로합니다.
공간 복잡성
O (1) 일정한 수의 변수 만 사용했기 때문에 상수 공간이지만 트리에 N 개의 노드가 있기 때문에 프로그램 전체는 O (N)을 사용합니다.
