Snehasish Barman
BAN USERCorrect.
- Snehasish Barman February 29, 2012Duplicate posts.
- Snehasish Barman February 14, 2012As this is an interview question, i would say first use this approach -
Have a doubly-linked list to hold the items.
Have a Map(use a red-black tree) where key = item, value = location of the item in the linked-list.
Whenever you want to access an element, get the location from the Map, insert the item at the beginning of the linked-list and update the location in the Map.
Whenever you want to delete the least recently used item, delete it from the end of the linked-list and remove it from the Map.
There can be ’N’ number of improvements on caching mechanism but those are best kept for research.
Use Hashing with open-addressing mechanism. This will definitely work.
Take an array of size M = 100. Make your hash function extremely inefficient so that long clusters are formed and your array becomes full. Now try to insert the next item (which hashes to the same bucket). As the table is full, it will keep searching for an empty entry, but won’t find any and falls in an infinite loop!
We can use hashing with chaining(linked-list).
For this we have to choose an array of size M = 1113 (larger than the number of keys).
We choose a large array so that average number of keys per linked-list remains almost ~1. Let’s say no. is 997, so 997 % 1113 = 997.
997 will be my array index, Key = 997, Value = 997.
Going by this way out search hit, search miss, insert, delete, and finding any random number will be executed in constant-time.
We have to choose the load-factor very wisely such that list sizes are small and number of comparisons if needed be (no. of keys in the arrays / size of the array)
Hi Tanvi Reddy,
Can you be a bit more elaborate on this? What are you trying to achieve by using a boolean array ?
Going by the question, i assume that the array is already sorted and the interviewer doesn’t bother about the running time of the program(it is not mentioned).
Running time: Worst-case is linear O(n).
private function findDuplicate(a:Array):void {
for ( var i:Number = 1 ; i< a.length; i++ ){
if ( a[i] == a[i-1] ){
trace(“Duplicate number is: “ + a[i]);
break;
}
}
Hi Srikant,
You can have a N-way Heap and by doing that i assume you want to achieve constant-time performance and add more complexity. But the catch is that a “Binary Heap” will give you logarithmic performance for most operations. Most of the time you will perform insert and delete operations on the heap which are very efficient using binary. If we can sacrifice small performance for complexity/maintainability, its better for all of us.
Maybe you can, but there is a major flaw here as you are hashing by manager name. Here “key” is the “name”, so you might land up with lots of duplicate keys. Duplicate keys are always bad.
You may want to hash it by using a unique number such as employee id...
I don’t know much about the first question, but you can use a Binary Search Tree.
For second question, one can definitely use a “Binary Heap”( a heap-ordered complete binary tree ). Whenever you add a new member into the organization, you move up the member, so that the member(parent) is larger than its children. Whenever you delete a member, you move down. At any point you move up/down to restore the heap ordering - (organizational hierarchy)
He he he… Good question king!
- Snehasish Barman March 19, 2012