Microsoft Interview Question
Country: United States
We can Achieve this, by using BST (Binary Search Tree)
search for Binary_search_tree Wiki page.
It will provide the following Time Complexity
Time complexity
in big O notation
Average Worst case
Space O(n) O(n)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
What's your algorithm for implementing get_random()? It can be done, but you haven't explained how you will fulfill this rather critical requirement.
lathif is correct bst will solve the case.
for random number case generate a number less than n,
now do a tree traversal according to the bits.
1- left, 0 - right.
let say random number generated is 10.
i.e 1010
so starting from root you go left right left right.
return the value.
which is O(logn).
:)
@huha: that's only correct if the tree is a complete binary tree, in the sense that every leaf node is at the same level, and every node is either a leaf node or has two children. There's no reason to assume that would be the case since you're forming the tree dynamically (in fact, it's not even possible to have a complete binary tree unless the number of nodes can be expressed as 2^k - 1 for some positive integer k).
@Shan: That's an algorithm that potentially takes O(n). The problem statement asked us to do better. It can definitely be done. I was only commenting that no one here has given a correct sublinear algorithm for it so far.
Binary Search Trees that are augmented with special information to help them find the k-th element in O(log n) time are called "order statistic trees". You can read more about these on Wikipedia. If you make the tree a balanced order statistic tree all the operations this problem asks for can be done in O(log n) time.
Binary Search tree can be used here as the Insert and Delete can be achieved in O(log n).For get random element,we could have a extra field in the tree size and populate the size of left+right childs + 1. So getting Kth smallest element can be achieved in O(log n).
Code for finding Kth element in log(n):
public int calculateSize(BinaryTree root) {
if (root == null)
return 0;
root.size = calculateSize(root.left) + calculateSize(root.right) + 1;
return root.size;
}
public BinaryTree getKthSmallestElmt(BinaryTree root, int K) {
int s = (root.left == null ? 0 : root.left.size) + 1;
if (s == K)
return root;
if (K > s)
return getKthSmallestElmt(root.left, K);
else
return getKthSmallestElmt(root.right, K - s);
}
All three operations (insert, delete and getRandom) can be done in constant time O(1), if the order of the elements is irrelevant
Data structure: Array, and HashTable which holds the value as key and index as value
Insert (X):
- push X as the last element in the array, update hashTable
- increment array size
Delete (X):
- get index of X
- swap it with last element in the array, say Y
- update index of Y in hash table to index(X)
- delete X from array and hash table
- decrement array size
getRandom:
generate a random index less than array size, and return value in that index
- Anonymous February 14, 2013