Interview Question
Country: United States
This is actually kind of an interesting problem. You need to make several levels of arrays, each one having one element that is the minimum of two elements in a lower level.
If you have 1 2 3 4 5 6 7 8
Your first summary level will be 1 3 5 7
The next will be 1 5
and the final just 1
I'll leave it to you to determine how to use this to find the minimum of any range in logN time. Hint: a range like 3-7 can be broken into 4-7 (which is one lookup in the second summary level), and 3. You can break any range into just logN pieces that can be looked up in the summary arrays.
This looks like homework (or you are just trying to challenge the folks here).
- Anonymous August 26, 2012Which company was this asked in? Which location? Phone screen? Onsite?