## Chih.Chiu.19

BAN USERDo you mean to say that you want to generate random samples with a given distribution?

- Chih.Chiu.19 February 26, 2013How about "finding the node with largest depth such that it is the root of a subtree that contains both of the specified nodes"?

- Chih.Chiu.19 February 22, 2013Besides the insertion still need to be done on the heaps too, otherwise the new "min" may only exist in the hash table. But as we realized by the top post that O(1) time is impossible, I still think your solution is so-far the best choice, well, in which case the hash table is unnecessary, and all operations take O(lg n) time.

- Chih.Chiu.19 February 22, 2013This 'solution' is wrong.

- Chih.Chiu.19 February 22, 2013Hey, do you understand what's been asked?

- Chih.Chiu.19 February 22, 2013No... this is not right. Suppose you want to delete the min then ask what's the new "min", then your hashtable tells you that the value suggested by your min stack is not in the hashtable, then you needs to find the next next one in the min stack, what if that value is again not in the hashtable? I am not sure this is an O(1) operation.

- Chih.Chiu.19 February 21, 2013This is a really nice piece of code and I agree with your algorithm --- swiping! Thanks for taking effort preparing such a nice program and please ignore those ill jokes.

- Chih.Chiu.19 February 21, 2013He said "wait for the parents to report the eventual sums", the final value will be flushed top-to-bottom so all the nodes will have the sum of all the values.

- Chih.Chiu.19 February 20, 2013The subset sum problem is NP-complete, right? How can it be solved in polynomial time?

- Chih.Chiu.19 February 19, 2013It is said that "no rollback provision". The product id idea works I think upon modification, to "transaction id" :)

- Chih.Chiu.19 February 14, 2013Does the POS knows that there are $90 left in the card? I don't think this is practical because this leaves so many security issues... What I'm thinking is that each transaction can contain a "transaction number" which, only changes *if* ack arrives (say, ack_id++). The server can use this id to check if it is the same transaction or not.

- Chih.Chiu.19 February 14, 2013Nice!

- Chih.Chiu.19 February 08, 2013This algorithm is not right, is it?

- Chih.Chiu.19 February 08, 2013This does not work --- try it yourself

- Chih.Chiu.19 February 07, 2013But isn't this what he did?

- Chih.Chiu.19 February 07, 2013Yes you are right, thanks!

- Chih.Chiu.19 February 07, 2013This is where the confusion begins: we have to agree on a convension whether the monkey moves *before* or *after* the shot --- here I assume the monkey moves first though I cannot see it. Then my solution is correct.

- Chih.Chiu.19 February 07, 2013Thanks for the clarification, now I am clear and a solution I can think of is the following, and by step I mean if the monkey is not killed by previous attempts.

1) Shoot at 4 twice. Then monkey can only be currently in 1, 2, and 3.

2) Shoot at 3 once. Then monkey can only be currently in 1, 2, and 4.

3) Shoot at 2 once. Then monkey can only be currently in 1, 3, and 5.

4) Shoot at 4 once. Then monkey can only be in 2.

5) Kill the monkey whatever way you want.

Thanks.

- Chih.Chiu.19 February 07, 2013Nice! But what do I need this "color" array for?

- Chih.Chiu.19 February 07, 2013I see, thanks. Use adjacency list to represent the graph then run a topological sort on it, get it. And using adjacency list is better because it is dynamic --- as opposed to using adjacency matrix representation which is better to be pre-allocated, am I right?

- Chih.Chiu.19 February 07, 2013Hi USTChucat, again I am confused: we know that certain recursive algorithms (merge sort etc) work on array, and of course there are other algorithms (tree walker etc) using stacks. So what exactly does "best" mean here, and what's your reason to pick stack over, say, array? Thanks.

- Chih.Chiu.19 February 07, 2013Thanks for both explanations. I see, now I understand the suggestion based on performing a topological sort. But could you please elaborate more on using "adjacency list"? Thanks in advance.

- Chih.Chiu.19 February 07, 2013(Only) The first answer is correct:

if n is odd:

ans = 2^(n-1)

else:

ans = 2^(n-1)-[nC(n/2)]/2

And this can be verified using the test case n=4.

I think the question is to reverse the order of indices, for example, if it is a 2-dimensional array then "reverse" means to transpose the matrix. For a multi-dimensional array to "reverse" it means to reoder the indices backwards. This is my understanding.

- Chih.Chiu.19 February 07, 2013**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

A good piece of code is self-explanatory --- *IF* it is properly commented.

- Chih.Chiu.19 February 27, 2013