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)

Frog 1

Problem Statement : https://atcoder.jp/contests/dp/tasks/dp_a

This problem consists to minimise the answer at each step. Here I'm explaning my C++ code on the following example:

6
30 10 60 10 60 50

ret : [Ø, 20, 30, 20, 30, 40]

ret[0] = Ø
ret[1] = ret[0] + abs(v[0] - v[1])
ret[2] = ret[1] + max( abs(v[0] - v[2]), abs(v[1] - v[2]) )
 (In this case, it's ret[1])
.......

C++ code

#include <iostream>

#include <climits>

#include <vector>

using namespace std;

int main(){

ios::sync_with_stdio(0);

cin.tie(0);

int n,K;

cin >> n >> K;

vector<int> v(n+3),ret(n+3,INT_MAX);

for (int i=0; i<n; ++i) cin >> v[i];

ret[0]=0;

for (int i=0; i<n; ++i){

for (int k=1; k<=K; ++k) ret[i+k] = min(ret[i+k],abs(v[i]-v[i+k])+ret[i]);

}

cout << ret[n-1];

return 0;

}

Frog 2

So here I'm going to solve a AtCoder problem from the AtCoder Educational Contest
Problem Statement : https://atcoder.jp/contests/dp/tasks/dp_b

When you got the idea of Frog 1. Frog 2 is trivial : do one more for loop.

Time complexity : O(n^2)
Space complexity : O(n)

This question again is a very trivial dp problem.

C++ code :

#include <iostream>

#include <climits>

#include <vector>

using namespace std;

int main(){

ios::sync_with_stdio(0);

cin.tie(0);

int n,K;

cin >> n >> K;

vector<int> v(n+3),ret(n+3,INT_MAX);

for (int i=0; i<n; ++i) cin >> v[i];

ret[0]=0;

for (int i=0; i<n; ++i){

for (int k=1; k<=K; ++k) ret[i+k] = min(ret[i+k],abs(v[i]-v[i+k])+ret[i]);

}

cout << ret[n-1];

return 0;

}

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

Dynamic Programming Course

This course (the math course is still running) is about DP (Dynamic Programming). It will cover 26 questions from the AtCoder Educational DP contest and all the other DP classical (edit distance) and non classical DP questions.

This course does not have a specific starting and ending time.

Fishing Problem ! - Algorithm

Problem

             f

  f       f      f    f

       f      f    f

  ----------------------

x .  .  .   .  .    .

f represents a fish and . represents a person who does fishing. These people are on a line that we call x. A fisherman can only capture a fish at a k distance of the fish or less (distance, Mahattan distance). Exemple :

Input

4 5 10

3 1 2 4 5

1 2

2 3

1 1

2 5

Output

4 4 4 4 4

Explanation of exemple

The first integer represents the number of fish, the second integer represents the number of fisherman and the third number is k. Then we have the position of the fishman. After you have the coordinates of the fish.

Constraints

Time : 0.5 second

Memory : 50000 ko 

The x coordinate of a fish is always <= 1000, no matter the subtask.

The y coordinate of a fish is always <= 1000, no matter the subtask.

Subtasks (in total 100 pts):

- number of fish < 100 and number of fishman < 100 - 20 pts

- number of fish < 1000 and number of fishman < 1000 - 20 pts
- number of fish < 1000 and number of fishman < 10000 - 20 pts
- number of fish < 1000000 and number of fishman < 1000 - 20 pts
- number of fish < 1000000 and number of fishman < 10000 - 20 pts

Analyse

This problem can be easily solved in O(nbFish*nbFishman) by looping on all the fisherman and all the fish. There exists a solution much faster in almost O(nbFish * log(nbFish)) + a sort. Here is the C++ code :

#include <iostream>

#include <algorithm>

#include <deque>

#include <queue>

#include <vector>

#include <map>

using namespace std;

int main(){

ios::sync_with_stdio(false);

cin.tie(nullptr);

int n,m,l;

cin >> n >> m >> l;

deque<pair<int,int>> v;

for (int i=0; i<n; ++i){

int a,b;

cin >> a >> b;

if (b > l) continue;

v.emplace_back(a-(l-b),a+(l-b));

}

sort(v.begin(),v.end());

deque<int> pecheurs(m);

for (int i=0; i<m; ++i) cin >> pecheurs[i];

deque<int> ordre_init=pecheurs;

sort(pecheurs.begin(),pecheurs.end());

priority_queue<int,vector<int>,greater<int>> q;

map<int,int> print;

int ret=0;

while (!v.empty() and !pecheurs.empty()){

while (!pecheurs.empty() and v[0].first > pecheurs[0]){

while (!q.empty() and q.top() < pecheurs[0]){

q.pop();

--ret;

}

print[pecheurs[0]]=ret;

pecheurs.pop_front();

}

q.emplace(v[0].second);

++ret;

v.pop_front();

}

while (!pecheurs.empty()){

while (!q.empty() and q.top() < pecheurs[0]){

q.pop();

--ret;

}

print[pecheurs[0]]=ret;

pecheurs.pop_front();

}

for (auto& i:ordre_init) cout << print[i] << '\n';

return 0;

}

Basic Operators

Today we will be talking about operations. There are many different types of operations :

• & - You can use it to check if a number is divisible by 2.
• ^ - This is the XOR operator. XOR has property : the same number XOR the same number equal to zero.
• 2 power n can be done in constant time with bit operation <<. Ex. (1<<n)
• Multiplication and division are slower then bit operations. (n >>= 1) is equivalent as n /= 2.     (n <<= 1) is equivalent as n *= 2.
• the or bit operation
• n++ - increment n by 1
• n-- - subtracts n by 1
• ++n - increment n by 1
• --n - subtracts n by 1
• n%m = r - r is the remainder of the division n and m
• *, -,  /, + - basic arithmetic operators