Monkeys and Bananas ! - Interview

Time : 1h30 of interview.


This Interview question contains sereval parts (follow ups) :

Question

- Part 1 -

A monkey loves bananas. Given the pos of monkey and the pos of a banana. Find how many units does he need to walk (min).

Input

Monkey : 3,5

Banana : 5,7

Output :

4

- Part 2 -

Now there are obstacles. Same question.

Input :

Obstacle : 1,1

Monkey : 3,5

Banana : 5,7

Output :

4

- Part 3 -

Now there are more monkeys. Same question but output for each monkey.

Input :

Obstacle : 1,1

Monkey : 3,5

Monkey : 3,6

- Part 4 -

Now there are more bananas. Same question but output for each monkey as begin and for each banana as end.

- Part 5 -

Now the bananas have one more integer : their taste. The monkeys also have one more integer : their favourite specie of banana. Same question.

- Part 6 -

Now the monkeys want to taste all the bananas. For each monkey : print the min path that he needs to take in order to taste every single banana.

Analyse

Part 1 is simple Mahattan distance. Part 2 is dfs or bfs. Part 3 is dfs for each monkey. Part 4 is dfs for each monkey and each ~ O(n*n*n). Part 5 is almost same complexity and algorithm as part 4. Part 6, minimum spanning tree and/or backtracking. If you have better algorithms, please send a comment.

(if you have better solutions, please leave a comment)