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)

Optimise this function ! - Interview

Time : 30 minutes

Question

Optimise this function :

f(int n){

if (n == 0) return 1;

if (n == 1) return 2;

return f(n-1)+f(n-1);

}

Analyse :

Normally, people will easily optimise this O(n*n) algorithm to O(n) by doing return fun(n-1)*2. Usually, people then will understand that this function does 2 power n so people uses pow from the cmath library. Then people might find that we can do 2 power n, simply by bit operation : (1<<n).

Source : Geeks for geeks