C**3 (Coveo Coding Challenge)

I’m at (what seems to be) the last step of the interview process at Coveo. The order was Phone interview –> Live interview with logic puzzles –> Personality + Aptitude tests –> Coding Challenge. I have to say I’ve never enjoyed an interview process quite as much as this one. Although it’s long and quite extensive, it does feel like both sides benefit by finding the right fit. Every once in a while while browsing Hacker News, you’ll come across a blog post from some experienced coder who describes in great detail his disdain for a certain part of interviews. Often mentioned is the take home coding challenge which some people see as a waste of time and sometimes even an insult to their abilities. Usually the way to resolve this is to compensate people for the time spent doing the challenge by hiring them on a freelance basis. It’s a sensible thing to do considering that most people don’t apply to only one company while job hunting and the time of a experienced dev is valuable.

In my case after passing the logic puzzles and the online tests, I was given a coding challenge to round off the interview process. As a side note, I was happy with my performance in the logic puzzles except for the way to implement a solution to detect a loop in a linked list. I was presented with the logic puzzles with the mention that they do not involve coding and tried to deduce the solution with lists and hash tables knowingly suboptimally considering the time needed when expressed in Big O notation. I blanked out on some basic notions (dictionary usage) and spent the next few days groaning at my lack of ingenuity. However it lead me to finding the best ways to do it. The most common approach is implemented by using Floyd’s Cycle-Finding Algorithm, also called the Tortoise and Hare Algorithm. Basically you have to use two pointers going through the list, one (hare) twice as fast as the other (tortoise).

Tortoise and Hare Algorithm

I’ll spare you the version I drew in OneNote and use the gif above instead as a quick explanation. Here’s a breakdown.

  1. Start both pointers at the first node of the list.
  2. Move Tortoise 1 step forward, Hare 2 steps forward every iteration until they both reach the same value.
  3. Send Tortoise back to the first node.
  4. Advance both pointers at same speed (1 step) until they once again reach the same value - This is first repetition of the cycle.
  5. Move Hare to the Node following the Tortoise and move it forward one step at at a time until finding another match.
  6. We now know the length of the loop and we can map it to a list if needed.

N.B. If the Hare reaches the end of the list before meeting up with the Tortoise, the list has no loop.

There is a more efficient version which also uses two pointers but introduces a ‘teleporting’ tortoise/turtle called Brent’s Algorithm. I’m not going to explain it in detail but you can read about both on Wikipedia. Overall it’s between 24-36% more efficient than Floyd’s.

C**3

Back to my main point, I have a coding challenge to complete before the next step of my interview. The basic premise is to write a shell script which helps analyze AWS S3 data. There is a minimum set of required criteria and suggestions for additional options which would make the script more useful. It can be written in the language of my choosing and it will be evaluated on its performance against buckets containing millions of files. I started off wanting to do it in Go for fun but the AWS SDK for Go is relatively new and lacking compared to others. My second choice was Java since it seems to have the most complete and well documented SDK but I settled on Python since I had previous experience with Boto3 while managing hundreds of EC2 instances to mine CPU based cryptocurrencies during the altcoin boom. Contrary to the point I made in my intro, I’m actually excited about the challenge and willing to put in the time to make it great. Maybe with a bit more experience I’ll become disgruntled like the rest though!