Algorithm questions. See if you can get these!

[BrownTown]

Olog(k)? what are you talking about, k is a constant, log(k) is the same as k in this case. But the answer isn't either, its Olog(n), you just take the top of the heap and percolate up

 

[Matthias99]

Originally posted by: BrownTown
Olog(k)? what are you talking about, k is a constant, log(k) is the same as k in this case. But the answer isn't either, its Olog(n), you just take the top of the heap and percolate up

Like I said:

Using proper algorithms for the heap/tree, this works out to O(log_2 k) time amortized for each element you process, and requires O(k) storage.

It is most definitely not O(log(n)) time; it is O(log(k) * n) to merge n elements from k sorted streams into a single sorted stream.

 

[spranks]

which position these question are for ?

have a first google interview call next week ( after sending my CV and setting up a time to talk)

any idea wht to expect ?