Interviewstreet Challenges have some excellent programming problems, and solving them has been a great learning experience for me so far. Even for the few problems I have solved, the solutions often involved a non-trivial component, like a data structure, or a paradigm, that I was not already aware of, or had no clue about. And I have no shame in accepting the fact that on many occasions, I Googled for hints, sometimes at length, (after trying to solve it myself for long enough, of course) to figure out the right approach. However, I made sure that I wrote all the code myself, and trust me when I say that this part is not necessarily as easy as it seems. I'm still stuck on many problems despite having figured out the right approach.
In the next few posts (including this one), I will post hints for the problems I have solved so far. I will add to this list as I solve more problems. Ideally, you should look at these hints only after having spent enough time on the questions. If you haven't thought about the question for long enough, then you probably won't understand the hints anyway.
Billboards :
1. Dynamic programming
2. It is easier if you consider which boards are removed (and try to minimize the loss), rather than considering which boards are not removed.
Did you get the recurrence for the above case? A naive implementation of the recurrence, in which you calculate the minimum in each iteration in O(K), will result in O(N * K) running time, which will time out.
3. The minimum can be found in O(log K), but it will require some data structure. (does it ring a bell?).
4. Better still, the minimum can be found in O(1), with very little extra work (think about how often you need to actually calculate the minimum, instead of blindly doing it in each iteration).
Equations :
1. Rewrite as A * B = C
2. Think primes.
Permutation Game :
1. N is very small. You can examine all possibilities. See this.
2. Bit-masking will help you avoid a lot of unnecessary work.
In the next few posts (including this one), I will post hints for the problems I have solved so far. I will add to this list as I solve more problems. Ideally, you should look at these hints only after having spent enough time on the questions. If you haven't thought about the question for long enough, then you probably won't understand the hints anyway.
Billboards :
1. Dynamic programming
2. It is easier if you consider which boards are removed (and try to minimize the loss), rather than considering which boards are not removed.
Did you get the recurrence for the above case? A naive implementation of the recurrence, in which you calculate the minimum in each iteration in O(K), will result in O(N * K) running time, which will time out.
3. The minimum can be found in O(log K), but it will require some data structure. (does it ring a bell?).
4. Better still, the minimum can be found in O(1), with very little extra work (think about how often you need to actually calculate the minimum, instead of blindly doing it in each iteration).
Equations :
1. Rewrite as A * B = C
2. Think primes.
Permutation Game :
1. N is very small. You can examine all possibilities. See this.
2. Bit-masking will help you avoid a lot of unnecessary work.
No comments:
Post a Comment