SDE - 1

You will be given a stream of numbers, and you need to find the 'kth' largest number in the stream at any given time.

As the stream of numbers can not be given during compile time, so you need to design a data structure which can accept infinite numbers and can return the 'kth' largest number at any given time.

The stream of numbers is nothing but a large collection of numbers from which integers are read at runtime, such as the user will never know the upper limit on the number of integers that will be read.

The implemented data structure must support the following operations:

1. add(DATA) :
   This function should take one argument of type and store it in its pool and returns the 'kth' largest number from the current pool of integers.

You will be given 'q' queries:

val - For this query, insert the integer into your current pool of integers and return the 'kth' largest integer from the existing pool of integers.

Note

 1. The maximum number of integers that will be given will always be under memory limits.

 2. You will also be given an initial pool of integers whose size equals k.

 3. The maximum number of queries will be less than 10^5.

 4. The 'kth' largest element is not the 'kth' distinct element but the 'kth' largest element in the sorted order.

 5. There will be at least one query of type 2.

What is a semaphore?
What is race condition?
Describe all the joins in SQL with a Venn diagram.
 

There is a Binary Search Tree (BST) consisting of ‘N’ nodes. Each node of this BST has some integer data.

You are given the root node of this BST, and an integer ‘X’. Return true if there is a node in BST having data equal to ‘X’, otherwise return false.

A binary search tree (BST) is a binary tree data structure that has the following properties:

1. The left subtree of a node contains only nodes with data less than the node’s data.

2. The right subtree of a node contains only nodes with data greater than the node’s data.

3. The left and right subtrees must also be binary search trees.

Note:

It is guaranteed that all nodes have distinct data.

Ninja is playing with numbers but hates when he gets duplicate numbers. Ninja is provided an array, and he wants to remove all duplicate elements and return the array, but he has to maintain the order in which the elements were supplied to him.