Coding
Minimum Index Distance Between Person and Cake in a Ternary Array
Given a 1D array A of length n where each element is in {0,1,2}:
0 means empty
1 means person
2 means cake
Compute the minimum distance between any person and any cake.
Follow up: assume the input guarantees that at every step there is a unique nearest person and cake, greedily assign each cake to a person at every step, and compute the total distance.
The second part threw me. It took me a long time to understand what the question was asking. It is not the kind of thing where you do DP or find a global optimum.
System Design
TinyURL was simpler than I expected. The slightly tricky part is that the same long URL has to always map to the same unique short URL.
That brings up some questions: if you did not need to guarantee that, each long URL could have its own expiration date. Once you do guarantee it, do you update the expiration date, or how do you handle it?
There is also a concurrency issue: two people create a short URL for the same long URL at the same time. A unique constraint in the database should solve that.
Discussion
Loading comments…