CareerCup

i agree

Could you explain your solution a little more

Here by I am writing the code for implementing the segment from the series of number...

Suppose I have int[] arr = {1, 2, 3,4, 5, 6, 7, 8};
I will take one more array of size int[] tree = new int[3 * arr.length];

And I have to keep track of maximum\ value from each node forming the segment trees,

public void buildSegementTree(int n, int startRange, int endRange)   {
    if (startRange > endRange) return;
    if (startRange == endRange) {
        tree[n] = arr[startRange]; // n the index in tree keeps track of the maximum value. (when range is 1 .. ::)
        buildSegementTree(n, startRange, (startRange + endRange) >> 1);
        buildSegementTree(n,  (startRange + endRange)  / 2 + 1,
        endRange);
        tree[n] = Math.max(tree[2 * n], tree[2 * n + 1]);
    }
}

This way each node is keeping track of the maximum value in the down tree... Similary do for minimum value. And querying which will happen in log(n).

this is close to what the interviewer was hinting on...
btw do u know any book for trees and different type of trees and problems on trees?

Ya CLRS , Introduction to Algorithm covers these stuffs. And geeksforgeeks.org also has some materials about this.

good stuff esp the geeks for geeks site

i found this very informative
ardendertat .c om/2012/01/09/programming-interview-questions/

but with segment trees, after every addition and deletion, the segment tree will have to be updated.
So these 2 operations will be O(n)
What am I missing here?
How can we update the segment tree after insertion/ deletion?

If you are updating a value (updating at particular index) in given array). this adjustment can be done in O(log(n)) in the segement tree .. Same is the case for deletion of single element.

public void updateSegementTree(int n, int start, int end, int index, int val) {
	if (start > end || start > index || end < index ) return;
	 if (start==end) //at leaf node
	 {
	  tree[n] = val;
	  return;
	 }

	 updateSegementTree( n*2 , start , (start + end ) / 2 , index, val );
	 updateSegementTree( n*2 + 1 , (start + end) / 2 + 1 , end , index, val );
	 tree[n] = max( tree[n*2] , tree[n*2 + 1] );
}

scorpion king is a f***ing moron. No wonder he didn't get an offer. After being repeatedly asked for clarification, he still does not give any.

@Anonymous: True that. The movie sucks too.

I don't think it's clear if it was stated as the original poster phrased it:

"optimum addition removal, querying and priority." is broken english at best.

One might suspect he was "trying" to say: "optimal (addition removal), (querying), and (priority)" or:
optimal (addition removal)
optimal (querying)
optimal (priority)

Only the second makes sense. Optimal "addition removal" doesn't mean anything in this context nor optimal "priority."

When you state a problem, it should be VERY clear if you want a meaningful answer.

I think he means add, delete, search, and find the min or max. A balanced BST can do all of these in logN time, if we maintain two pointers to the left-most leaf node (min) and the right-most leaf node.

yeah ..pls elaborate the question ....

maybe a doubly linked list?

hmm OK after a long list of offensive comments which tried to justify my rejection, let me try to explain again:
1. It was an open ended question at the end, He was not having a special case..
He precisely asked me this:

I want a data structure which gives me efficient lookup, insert and querying by priority (i want the second biggest element, 5th biggest,etc)
He also mentioned that I am free to use my creativity and not limit to the standard data strucutres.

First i said hash, he said hash will not give efficient priority lookup

Then i said linked Hash, which too he rejected
BST also rejected.
Then i suggested Heap. He said heap will just give efficient lookup for the most prioritized node, not the 2nd most or 5th most

My issue was I did not read abt anything else than the basic data-structures.

He hinted that I could solve it using changes to basic BST. And the time was up, he was in hurry to leave for home as my interview was the last.

After calling off, he told me the solution which is the same as cksharma.skt suggested and only he could solve properly in this forum :)

My advise for other interviewees would be to atleast read a one liner about datastructures other than the basic ones.

@scorpionking.

You are not explaining _again_. This is a _new_ explanation which was missing all along. The people asking for clarification (multiple times) are justified in being annoyed. Name calling is another matter.

Also, priority is a completely wrong word to use (especially when you give no more details than addition, removal, query and priority).

Was it so hard to explain it a bit more?

Also, if you don't understand why the question you wrote was unclear, well...