These days I am reviewing Algorithm couse in Coursera, which is taught by Prof.Robert Sedgewick and Prof. Kevin Wayne. I found some interview questions are interesting and really worthy to be explored.
Union-find with specific canonical element. Add a method find() to the union-find data type so that find(i) returns the largest element in the connected component containing i. The operations, union(), connected() and find() should all take logarithmic time or better.
If you try to figure out how to implement weighted quick-union, then you will find add another array will be useful. For each element i, the array will store the maximum node under the root i.
Successor with delete.
Make use of last question Union-find with specific canonical element. For example, if we have S = {0,1,2,3,4,5,6,7,8}. And we do:
- remove 5, that means we do union(5,6)
- remove 7, that means we do union(7,8)
- remove 6, that means we do union(6,7)
We can get the success of 5 is 8, for 8 is the largest number in the connected component which contains 5.
Analysis of Algorithms interview questions
3-SUM in quadratic time
It is similar to 2-SUM in O(N). In the 2-SUM, two pointers can be used, which point the begin and end of a sorted array. If the sum of two pointers are bigger than 0, then the end pointer should move backward.
For 3-SUM problem, here is a solution:
1 |
for every x in array: |
Search in a bitonic array.
1.Standard Version.(~3lgn)
Use binary search to find out the maximum number m in the array, then split the array. Use binary search twice for splitted array. In sum, we use binary search for three times, thus it’s ~3lgn.
2.Signing bonus.
We don’t need to find out the maximum integer, for binary search could be used in a bitonic array.
1 |
if key > a[mid]: |
Notice that the search function above is always binary search, which means we will solve this problem using recursion. At the end of the recursion, segment of the array will be monotonous. Thus we can use binary search in bitonic array.
Egg drop. Suppose that you have an n-story building (with floors 1 through n) and plenty of eggs. An egg breaks if it is dropped from floor T or higher and does not break otherwise. Your goal is to devise a strategy to determine the value of T given the following limitations on the number of eggs and tosses:
- Version 0: 1 egg, $leq$ T tosses.
- Version 1: ~1lg$n$ eggs and ~1 lg$n$ tosses.
- Version 2: ~lg $T$ eggs and ~2lg $T$ tosses.
- Version 3: 2 eggs and ~2$sqrt{n}$ tosses.
- Version 4: 2 eggs and $leq c sqrt{T}$ tosses for some fixed constant $c$
I will analysize one by one.
Version 0
To determine T with one egg, there is only one way: sequential search. First drop it on the first floor, if the egg is not broken, then drop it one the second floor…
Version 1
ln $n$ has already gives the hint: do it with binary search.
Version 2
Drop the egg on 1,2,4,8,16,… th floor. Suppose egg breaks at floor $2^k$, then binary search between $2^{k-1}$ and $2^k$
Version 3
Drop the egg on $sqrt{N}$,$2sqrt{N}$,$3sqrt{N}$,… th floor. Suppose egg breaks at floor $ksqrt{N}$, then increse floor from $(k-1)sqrt{N}$ to $ksqrt{N}$
Version 3 (~$sqrt{2N}$ tosses)
I recommend to go to this website to see the details.
Version 4
We drop the egg at floor 1, 3(1+2), 6(1+2+3), 10(1+2+3+4), … Note that $1+ 2+ 3+ 4 + … k = frac{k(k+1)}{2}$~$frac{1}{2}k^2$. Now that $T = frac{1}{2}k^2$, $k = sqrt{2T}$.
From $frac{k(k-1)}{2}$ to $frac{k(k+1)}{2}$, we toss egg one by one, then we toss $frac{1}{2}k^2$ times.
In total, we toss $2sqrt{2T}$ times, thus $c = 2sqrt{2}$
近期评论