bad_robot1

The traveling robot problem

I am currently between contracts and for first time in many years, I am requested to write some complex code from home so I took the liberties to share my result on my blog.

A startup based in London sent me this problem:

Problem:
A robot can be programmed to run 1, 2, 3, 5 and 10 kilometers and it takes 10, 5, 3, 2 and 1 minutes, respectively. Once it runs to programmed kilometers, it must be turned off for 2 minutes. After 2 minutes it can again be programmed to run for a further 1, 2, 3, 5 or 10 kilometers. How would you program this robot to go exactly 43 kilometers in minimum amount of time.

Please write a java program that solves the problem by finding the minimum time required to travel 43 kilometers. Your solution should print out the correct sequence of distances to be programmed into the robot: for example (10,5,10 and so on…)
When coding your solution please pay special attention to design, data structures, dynamic programming, faster execution time and creating generic solutions. (it should be fairly easy to change the parameters) Compute and provide Big O notation for main piece of your solution too.


END-OF-QUESTION

Before you look at my answers, it will be cool for you to try the exercise too so that we can share feedback in the comments section.

The question brought back memory of my Computer Sciences days, especially Data Structure and Algorithm lectures. At first glance, this looks like a simple problem but it goes deeper than that. Like artists, there are multiple ways to write code but once you look at someone else code, then it becomes difficult to be original ( IP patent law suit anyone?). Any experience developer can write code that would work perfectly for this problem, looking closely to what is being requested and you will notice that there is an extra requirement; dynamic
programming
. For those who needs more information about what dynamic programming is, I suggest the following wikipedia article. I had to spend sometimes reading the article to refresh my memories and off-I-went-hacking-away. Bear in mind that you could solve this problem by rewriting a recursive application but that is not a dynamic programming approach.

Anyway, here are my results ( the algorithm was inspired by a similar problem set).

I hope this helps someone in the future in any ways.

Happy Coding

You can download the source code this github https://github.com/armelnene/the-traveling-robot-problem

670px-Cope-With-a-Double-Parachute-Failure-Step-31

Parachutist Dilemma – a parallel programming problem

Here is a little mental problem solving exercise for you to try to do in 30 seconds; that was the time I was allowed. So I had a telephone interview from a company today and this guy asked me this question utilizing a parrallel programming algorithm. Here are the details:

Two parachutist (A and B: A is in front of B) land on single line; one behind the other. Their parachutes also lands behind them respectively. 
We have a set of instructions which are as follow (all instructions are executed, meaning A and B will executed instructions at the same time).

  1. move forward 1 step
  2. move back 1 step
  3. if standing on a parachute go to (1 | 2)

Question:

We need our parachutist to somehow meet each other, what are the sets of instructions that can make that happen?


Please try to answer before reading my answer below

My answer:

  1. execute 2
  2. execute 3

Explanation:

  • When both parachutist move back 1 step, they will both be on their parachutes
    • when parachutist A stands on his parachute, he will move back 1 step therefore go to 1
    • when parachutist B lands on his parachute, he will move forward 1 step 

Therefore our two parachutist will meet in B original position.

NB I had to change the original questions as the interviewer explanations led to the parachutist to never meet.