Facebook Hacker Cup - Qualification Round 2019

The 48h qualification round consisits of 4 algorithmic problems to do on the facebook interface. You shall do 1 question to advance in Round 1.

The first two questions were the easisiest ones. The solution is just some simple implementations, most people were able to do them. The 30th July will start Round 1 !

Now, is the time for Round 1 ! Good Luck to all !

Google Code Jam 2019 - Qualification Round

This weekend, I have participated at the Google Code Jam contest. You only needed to get 30 pts to attend the next round !

For the first question : Because each number always has a the number 4 in it, we can just :

create (initialise) string A and string B
for each digit in the number :
     if the digit is a 4 :
          put '1' in string B
          put '3' in string A
     else :
          put the digit in string A

For the second question : It is a pretty easy question. The idea is just to replace 'E' by 'S' and 'S' by 'E':

read the string s
for each character c in s :
     if c == 'E' :
         print 'S'
     else :
         print 'E'

For the third question : just use Euclid's gcd !

Have a look at the official editorial for question 3 and 4 :

https://codejam.withgoogle.com/2018/challenges/0000000000051705/analysis/000000000008830b
https://codejam.withgoogle.com/2018/challenges/0000000000051705/analysis/00000000000881de

Here is my youtube video (doing A and B) : https://youtu.be/0k4q1SMSYSo

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.