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

Fibonacci Numbers

One famous question about Fibonacci numbers is about rabbits. Say rabbits are able to mate at the age of one month, and pregnancy takes one month. Thus, at the end of its second month, a female can produce another pair of rabbits. Rabbits never die, and a mating pair always produces one new pair (one male, one female) every month from the second month on. The puzzle that Fibonacci posed was if we start with a new pair from birth, how many pairs will there be in one year ?

To solve this problem we are using the following formula : f(n-1)+f(n-2)=f(n). This can be done in recursive and iterative. I prefer the iterative version because in iterative we can do in O(1) memory and O(n) time.

Here is the C++ code to calcute the fibonnacci numbers to the nth term:

int prev1=1,prev2=1;

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

   swap(prev1,prev2);

   prev2=prev1+prev2;

}

cout << prev2;

Another way to calculate Fibonnacci number. If Fn is the nth Fibonacci number then :

This is Binet's formula

Distances

There are many different distances but today we will be talking about Manhattan distance and Euclidean distance. Mahattan distance is based on the gridlike street geography of the New York borough of Mahattan.
For 2D : Manhattan Distance's formula is abs(x1-x2)+abs(y1-y2). Euclidean distance's formula is sqrt((x1-x2)^2+(y1-y2)^2). This is equivalent to the Pythagorean theorem.
This chapter is an easy, short and fundamental chapter. (in fact the whole math chapter is easy, short and fundamental)

In the picture, in red, blue and yellow, you have Manhattan distance. And in green is the Euclidean distance.

Big Number Addition

This is a very basic problem : Given two numbers up to 1 million, N and M.
And given N digits representing the first number. Then another M digits representing the second number.

ex :

INPUT

4 5
1 2 3 4
5 4 3 2 1

OUTPUT

66661

If you use Python then it is a very very very easy problem because Python supports numbers in a infinity of digits. But if you are a Java, C++ programmer then you can't do it like simple two number addition. So to do that, you just need to know how to addition big numbers at primary school. So you do :

remainder : nothing
                   1112
                  +  34
                  -------
                   1146

So now I think you can implement it yourself (each time do addition then modulo 10), if anyone needs a C++ code, you can ask me.

Info (1) Cup 2019

This is one of the not interactive question. (2 out of 4 questions are interactive questions). You can try it !

InfO(1) CUP 2019 Third edition International Round

COSTINLAND

Costin is the dictator of Costinland, a country located on a very small island in the middle of Pacific Ocean. One day, Costin started feeling depressed because his island was very small. In order to stop his own depression, he decided to conquer other countries, so that the territory of Costinland and his influence as a dictator

will be even bigger! In order to do that, he needs an army! But no citizen of Costinland fits the dictator’s requirements... So what army would be better than an army of Costins? Thus, being the smartest person living in Costinland, he invented cloning on a Saturday evening. Being a very playful person (the most playful person in Costinland), he wanted to play with his clones while creating them.

Maximum time of execution: 0.5seconds/test. Maximum available memory: 64 MB

For that, Costin chose a piece of land consisting of N x M cells. There are 4 types of cells:“X” (if a Costin steps on this cell, he clones himself; one of the Costins goes right and the other one goes down), “r” (if a Costin steps on this cell, he will go right, regardless of his initial direction), “d” (if a Costin steps on this cell, he will go down, regardless of his initial direction),“.” (if a Costin steps on this cell, he will not change his initial direction and will move to the next cell indicated by his direction).
Costin leaves from (1,1) and wants to reach (N,M), along with all of the created clones. Costin is also very lazy (the laziest person in Costinland), so he asks you “nicely” to help him build such a matrix, such that exactly K clones will reach (N,M). Clones cannot be “lost” on their way (read the constraints carefully).

TASK

Given K, help Costin generate such a (small) matrix that will bring to (N,M) exactly KCostins.

INPUT FORMAT

The first line contains one integer: K.

OUTPUT FORMAT

The first line will contain to integers: N, M (the size of the matrix). The following N lines will contain M characters, describing the matrix.

Page 1 of 3

CONSTRAINTS

•   The character situated on (1,1) must be different from “.”, in order to give a direction
  to the first Costin. (It can be “X”, “d” or “r”)
•   None of the Costins stops until he reaches (N,M).
•   In order not to waste Costins or to lose them somehow during their path, the last line
  of the matrix will consist only of “r” and the last column will consist only of “d”. By exception, the character situated on (N,M) will be “.” (There is no need to give the Costins a direction since they reached their destination)
•   In order to get 100 points, you need to generate a matrix with both of its sides smaller than or equal to 5, for the first subtask, and one with both of its sides smaller than or equal to 49, for the second subtask (more details below in the SCORING section).

Subtask	Score	Restrictions
1	20 points	3 <= K <= 19
2	Another 80 points	19 < K <= 1018

The scoring is very hard to read on the blog, sorry.

SCORING:
Let CxD be the contestant’s matrix size. Subtask 1:

•   If max{C,D} <= 5, you will receive 100% of the points on that test case.
•   If max{C,D} = 6, you will receive 60% of the points on that test case.

                                                                                         If 6 < max{C,D} <= 500, you will receive 60*𝟓𝟎𝟎−𝒎𝒂𝒙{𝑪,𝑫}/500/6 % of the points on

that test case. If max{C,D} > 500, you will receive 0% of the points on that test case.

Subtask 2: If max{C,D} <= 49, you will receive 100% of the points on that test case.

 If 49 < max{C,D} < 62, you will receive 60+40*1.262−max {𝐶,𝐷}/1.262−49 % of the points

on that test case. If max{C,D} = 62, you will receive 60% of the points on that test case.

𝟓𝟎𝟎−𝒎𝒂𝒙{𝑪,𝑫} If 62 < max{C,D} <= 500, you will receive 60* 𝟓𝟎𝟎−𝟔𝟐 % of the points on

that test case. If max{C,D}>500, you will receive 0% of the points on that test case.

Page 2 of 3

COMPILER MESSAGES:

•   "The output does not fit the requirements": You will get this message if your
  matrix does not respect the CONSTRAINTS or the OUTPUT FORMAT.
•   "Matrix size too big": You will get this message if max{C,D}>500.
•   "The matrix does not generate the required number of Costins": You will get
  this message if, in the end, there won’t be exactly K Costins in (N,M).
•   If you don’t get any of these messages, you will receive a score according to the formulas from above and a message which specifies the size of your generated matrix for that test case.

EXAMPLE:

Input:
11
Output:
4 4
XXXd
.XXd
.XXd
rrr.

Prime numbers

Prime numbers are numbers that can only be divided by itself and one. A prime number has two divisors so one is not a prime number. Prime numbers have been proved that there are a infinity of them by Euclid in Euclid's Element. Two numbers are said to be coprime if the only divisor that divides both of them is one (gcd(a,b) = 1). Here, we are going to tell you different ways to check if a number is a prime number. One technique is to do a brute force algorithm, this algorithm will see if there is a number from 2 to n-1 that can divide n.

Brute force

Pseudo-code :

for i=2 to i=n-1 i += 1 {
    if n % i == 0 {
        print : n is composite
        break
    }
}

C++ code :

for (int i=2; i<=n-1; ++i){
    if (n%i == 0){
        cout << n " is composite\n";
        break;
    }
}

Optimisation : you might have already seen that n can not be divided by sqrt(n)+1 so in the above for loop you could replace n-1 and put sqrt(n). This algorithm can be inefficient if we have two thousand integers to check.

Sieve of Eratosthenes

This solution consists to take the next  number let's say n that has not been marked as true and every number that have n as divisor and have not been marked are marked as true.

Pseudo-code for finding prime numbers from 2 to 100000 :

for i=2 to i=100000 i += 1 {
    if not vu[i] {
        for j=2*i to j=100000 j += i vu[j]=true;
    }
}
// all numbers where vu[i] = false are prime numbers

C++ code for finding prime numbers from 2 to 100000 :

for (int i=2; i<100001; ++i){
    if (!vu[i]){
        for (int j=2*i; j<100001; ++j) vu[j]=true;
    }
}
// all numbers where vu[i] = false are prime numbers

Optimisation : In the first loop, we can see that we only need to do the loop to sqrt(100000) or sqrt(n). In this case n=100000. Also it is possible to do this algorithm in O(n).

Different Integer

In C++, you have a huge amount of varieties of numbers. When you add unsigned in front of a type like int (except : bool, char) then the type will no longer support negative numbers.

• Bool  0 or 1
• Char  0 to 9
• Short  - 2^16 to 2^16
• Int (32 bits) -2^32 to 2^32
• Long or long long -2^63 to 2^63
• Unsigned long long 0 to 2^64

You also have complex numbers in C++ if you include the following line : #include <complex>
When you have included that line, you can :

• initialise a complex table like this : complex<double> mycomplex(10.0,0.01);
• print the real part with real()
• print the imaginary part with imag()
• print the phase angle of a complex number with arg()
• print the complex projection with proj()
• print the complex conjugate with conj()
• print the norm of a complex  number with norm()
• print absolute value of a complex number with abs()
• ......

Programming Competitions and Training 1

Competitions

International competitions

IOI

Most people who are less than 18 years old are aiming for the IOI. IOI is also called International Olympiad of Informatics. The IOI contest is taking place at a different country each year. Here is the IOI website : https://ioinformatics.org

Google Code Jam

Google Code Jam is a competition organised by Google each year. To participate the next round, you need to be qualified from the previous round. Participants are automatically qualified for Round A. By doing well in this contest, you can get contacted by Google. Top participants can get a T-shirt and top 25 participants can go to the on site final. Some of the finalist can get a prize. The Google Code Jam website : https://codingcompetitions.withgoogle.com/codejam

Kickstart

Kickstart is another Google competition organised almost every month. By doing well in this contest, you can get contacted by Google. There are no finals and you don't need to be qualified to attend the next round. Here is the Kickstart website : https://codingcompetitions.withgoogle.com/kickstart

Hash Code

Hash Code is also a Google competition organised each year. The difference between other contests and this one is that : you need to have your own team ! Hash Code has got on site finals ... The Hash Code website : https://codingcompetitions.withgoogle.com/hashcode/about

Top Coder

Top Coder offers regular (almost every week) competitions and a on site final. Here is the Top Coder website : https://www.topcoder.com/community/competitive-programming

ICPC

The International Collegiate Programming Contest is an algorithmic programming contest for college students. Teams of three, representing their university, work to solve the most real-world problems, fostering collaboration, creativity, innovation, and the ability to perform under pressure. Through training and competition, teams challenge each other to raise the bar on the possible. Quite simply, it is one of the oldest, largest, and most prestigious programming contest in the world just like the IOI. Here is the ICPC website : https://icpc.baylor.edu


Fario

This is a France and Australien competition. This competition is held every year, and the team leaders from the two teams pick some people via the two training sites : France IOI and Orac. Here is the Fario site : http://orac.amt.edu.au/fario/

European competitions

If you are a bit younger, you can aim for the eJOI (Europe only) who is another competition much easier then the IOI. eJOI just like the IOI is taking place every year in a different country. eJOI is the initials for European Junior Olympiad of Informatics. Here is the 2018 eJOI website : http://ejoi2018.org

Training

CodinGame

This is a french coding website. The thing is that you learn while you are playing. So, check it out : https://www.codingame.com/start

Codewars

You can sharpen your skills with Codewars ! The Codewars website : https://www.codewars.com

Kattis

Kattis is a great training website. Here is the link : https://open.kattis.com

NOI

NOI is a chinese training website. The link to the website : http://www.noi.cn

USACO Training

USACO also has a training gateway website to prepare for the USACO contests. Here is the USACO website : https://train.usaco.org/usacogate?a=oxuybwibj5z

Orac

Orac is a australien training website.
The link to the website : http://orac.amt.edu.au/cgi-bin/train/hub.pl

Luo Gu

Luo Gu is another chinese training website. Here is the link : https://www.luogu.org

Leetcode

Leetcode is not a competitive programming website (more a interview website) but it has a lot of exercises. It also organises weekly constests. Here is the website : https://leetcode.com

UVA

UVA is one of the best programming website. Here is the link : https://uva.onlinejudge.org

Hacker Rank

Hacker Rank is a great training website. Here is the Hacker Rank website : https://www.hackerrank.com/dashboard

SPOJ

SPOJ is another great training website. Here is the link : https://www.spoj.com/problems/

Codeforces and Codechef

They have some great problems ! Here's the link to codechef : https://www.codechef.com/contests/
And for codeforces : https://codeforces.com/

Project Euler

Last but not the least is Project Euler ! This website is a mathematical and programming website :  https://projecteuler.net

GCD and LCM

GCD also called Greatest Commun Divisor is a basic algorithm created by Euclid (Mid 4th century BC - Mid 3rd century BC). LCM also called Lowest Commun Multiple is a basic algorithm also created bu Euclid and it's formula depends on GCD. Here's the formula : a*b/GCD(a,b).
Theoreme (Euclide's lemma) : Consider A and B two integers; if R is the rest of the euclideen division of A and B then GCD(A,B)=GCD(B,R).

Pseudo-code

GCD can be implemented in two different ways : recursive and iterative. I recommand the recursive solution because it is shorter.

GCD(a,b) {
    if b == 0 return a
    return GCD(b,a%b)
}

GCD(a,b) {
   while a != b {
      if a > b a -= b;
      else b -= a;
   }
   return a;
}

C++ code

In C++ there is a gcd() function and a lcm function (for those who are tired to do a multiplication and a division) in numeric. There is also a new gcd function but it requires C++17, it is called __gcd().

#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;

inline int GCD_1(int a, int b){
 if (b == 0) return a;
 return GCD_1(b,a%b);
}

inline int GCD_2(int a, int b){
 while (a != b){
  if (a > b) a -= b;
  else b -= a;
 }
 return a;
}

inline int GCD_3(int a, int b){
 return gcd(a,b);
}

int main(){
 ios::sync_with_stdio(0);
 cin.tie(0);
 int a,b;
 cin >> a >> b;
 cout << "GCD 1,2,3 result : " << GCD_1(a,b);
 cout << ' ' << GCD_2(a,b) << ' ' << GCD_3(a,b) << '\n';
 cout << "LCM result : ";
        cout << a*b/GCD_1(a,b) << ' ' << lcm(a,b) << '\n';
 return 0;
}

Another technique is to use tie :

//Greatest common divisor, the way Euclid intended :

int gcd(int a, int b){

    while (b != 0){

        tie(a,b) = make_tuple(b , a%b);

    }

    return a;

}

Math - Course 2

Math is a subject that everyone has learned at school so this chapter should be a bit easier for everyone to understand. This chapter will contain all the fundemental or easier knowledge. We will provide a more advanced chapter on math in the future. In this course we will provide one article per day (if possible). Also in Big Number Addition, we will also provide code and explanations for Big Number Substraction.

Start : Saturday 2nd March 2019

End (likely) : Wednesday 13th March 2019

Here are the main subjects :

1. GCD and LCM
2. Distances
3. Different Integer
4. Prime Numbers
5. Fibonacci Numbers
6. Venn Diagram
7. Base
8. Bitset
9. Factorials
10. Basic operators
11. Triangles
12. Permutations
13. Cmath Library
14. Big Number Addition