After performing less than excellent at a technical interview today (expected since I haven’t covered half the coding interview materials and forgot the other half) I found myself with renewed energy to solve hackerrank problems.
An interesting problem I had to ponder over for a long time is the New Year Chaos Problem. Doesn’t help my confidence that it was marked “Problem Solving (Basic)”. Anyhow, the problem goes as follows:
You have a bunch of partygoers cutting queue, the original arrived and were given stickers to mark their position in the queue so: [1,2,3,4,5]
but some people decided to bribe their way ahead so after awhile the queue looked like [3,1,2,5,4]. The challenge is to count the minimum number of bribes that were made to reach the new configuration. If anyone made more than 2 bribes, we can print(‘Too chaotic’) and exit the problem.
My first impression looking at this is that we can loop through the queue and for each person i in the queue, count the number of people with smaller stickers than person i behind him. However, this leads to 2 for loops as we are also looping from queue[i:]. This would lead to the dreaded timeout error. It was not at all obvious to me how to make this 1 loop. After reading through some of the comments on the discussion forum I found this solution to be extremely similar to my original intuition yet it only uses 1 loop by keeping track of the two smallest stickers behind person i. This can be done by iterating through the queue from the back instead of from the front.
Here is the python code:
My takeaway? If you can’t crack it from the front door try the back door…
