Microsoft Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
3
of 3 vote

For operations like insert and delete an element we can use HashMap<T,Integer> where T is the element that we need to insert or delete.Along with this we also need to use a random access structure such as an ArrayList.Now do we make it random ? because in the HashMap we store the location of the element in the ArrayList.Have a class variable such as count to keep track of the number of elements added.

Pseudo code:

Private int index=0;

void insertElement( Object element)  --Complexity <O(n)
{
	if (hashmap.contains(element)) then do not add
        else
	hashmap.put(element,index) ;
	arraylist.add(index,element);
	index++;
}

void deleteElement(Object element)--Complexity < O(n)
{
	if (hashmap.contains(element)
		{
			//first get location of the element in the arraylist
				int location=hashmap.get(element);
			//delete from element
				hashmap.remove(element);
			//reduce the count parameter
						index--;
//Logical deletion in arraylist is as follows.. instead of deleting the element in the arraylist replace the element at that location with the last element in the arraylist and delete the last element in the arraylist
	if( location != arrayList.size()-1){
		arraylist.put(location,arrayList.get(arraylist.size()-1));
		
		arraylist.remove(arraylist.size()-1);}

	else
		//simple remove last element
	 arraylist.remove(location);
}

Element getRandom()
{
	randomindex= Math.random(0,arrayList.size()-1);
	return ( arrayList.get(randomindex);
}

- Anonymous February 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

- Mr. Lathif December 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi December 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 December 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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).

- eugene.yarovoi December 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Or, generate a random number < n. Do an inorder traversal and return the nth element?

- Shan December 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- eugene.yarovoi December 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

- Dhass April 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hash table plus array will work. the hash is keyed on the number and contains the index of the array where the number is stored as its value.

- alex September 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- IntwPrep December 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you elaborate?

- Andi December 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

-1: It's not possible to search for an arbitrary value in a heap in less than O(n). Such searching would probably be needed to implement deleteElement() (if deleteElement deletes an element with a specified value).

- eugene.yarovoi December 13, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More