# Issue # 11: IT training - current issues and challenges from leading companies

We have selected for you several interesting questions and algorithmic problems asked during interviews at Luxoft.

When applying for a job at Luxoft, applicants are often asked technical questions, for example, to check the level of technology ownership. Nevertheless, there are questions related to logic, and algorithmic problems. Below are the most interesting of them, among which we tried to choose questions of various difficulty levels.

#### Questions

1. 3 Travelers crossing the river
Three travelers travelers need to cross a river. Each traveler has certain amount of gold coins kept in his bag.
Traveler A has 1000 gold coins
Traveler B has 700 gold coins
Traveler C has 300 gold coins

To cross the river there is a boat which can carry a maximum of two objects at a time that means either a maximum of two travelers can cross the river or a traveler with a bag can cross the river. The problem is that in this process of crossing the river if a traveler is left with an amount of coins more than his own then he will run away with that. The same rule applies for two travelers, if they are left with a total of more than their cumulative gold coins then they will run away with that money.
What strategy will ensure that they all cross the river properly?
Transfer
Three travelers need to cross the river. Each of them has a certain amount of gold coins in a backpack.
Traveler A has 1000 coins
Traveler B has 700 coins
Traveler C has 300 coins

To cross the river there is a boat that can accommodate a maximum of 2 objects - two travelers or a traveler with a backpack. The problem is that if you leave any traveler with more gold than his own, he will run away, grabbing all the money. The same applies to two travelers, if they stay with gold in excess of their total reserves - they will run away with gold.
What strategy will allow everyone to cross the river and stay with the money?

2. Heavy rock in the boat
You are in a rowing boat on a lake. A large heavy rock is also in the boat. You heave the rock overboard. It sinks to the bottom of the lake. What happens to the water level in the lake? Does it rise, fall or stay the same?
Transfer
You are in a rowing boat in the middle of the lake. There is also a heavy stone in the boat. You lift the stone with force and throw it overboard, as a result of which the stone goes to the bottom of the lake. What will happen to the water level in the lake? Will it rise, fall or remain the same?

1. Multiple of 3
Write an efficient method to check if a number is multiple of 3.
Transfer
Write an effective program to check if a number is a product of a triple.

2. Write a quine
A quine is a program which prints a copy of its own as the only output. A quine takes no input. You are not allowed to use, open and then print file of the program. Quines are named after the American mathematician and logician Willard Van Orman Quine (1908–2000).
Transfer
Write quine, a program that prints its source code. Quine does not accept any input. You are not allowed to use the file and then display its contents. Kuyang is named after the American mathematician and logician Willard Van Orman Quine (1908-2000).

3. Min / Max without branching
On some rare machines where branching is expensive, the below obvious approach to find minimum can be slow as it uses branching.

``````/* The obvious approach to find minimum (involves branching) */
int min(int x, int y)
{
return (x < y) ? x : y
}
``````

Write a program to find the minimum of two integers without branching.
Transfer
On some machines where branching is expensive, the following approach to finding the minimum will be slow:

``````/* The obvious approach to find minimum (involves branching) */
int min(int x, int y)
{
return (x < y) ? x : y
}
``````

Write a program to find the minimum of two numbers without using branching.

Answers will be given within the next week - have time to decide. Good luck

#### Solutions

1. Question 1
```0. (1000) (700) (300) ABC ----
1. (1000) (300) AC ---- (700) B
2. (1000) (300) ABC ---- (700)
3. (1000) BC ---- (700) (300) A
4. (1000) ABC ---- (700) (300)
5. (1000) A ---- (700) (300) BC
6. (1000) (300) AC ---- (700) B
7. (300) C ---- (700) (1000) AB
8. (700) (300) BC ---- (1000) A
9. (700) (300) ---- (1000) ABC
10. (700) (300) A ---- (1000) BC
11. (700) ---- (300) (1000) ABC
12. (700) B ---- (300) (1000) AC
13. ---- (300) (1000) (700) ABC
```

2. Question 2
The volume of water will decrease. The correct answer was found in the comments, an explanation can be found, for example, in this comment .

Summing the digits of a number and checking for divisibility by 3 is not the most effective approach.
The correct pattern was suggested in the comment : if the difference between the sum of the even and odd bits is divided by three. We consider the sum approximately as in the classical example of counting bits.

Initial solution:

``````// CPP program to check if n is a multiple of 3
#include
using namespace std;
/* Function to check if n is a multiple of 3*/
int isMultipleOf3(int n)
{
int odd_count = 0;
int even_count = 0;
/* Make no positive if +n is multiple of 3
then is -n. We are doing this to avoid
stack overflow in recursion*/
if(n < 0) n = -n;
if(n == 0) return 1;
if(n == 1) return 0;
while(n)
{
/* If odd bit is set then
increment odd counter */
if(n & 1)
odd_count++;
n = n>>1;
/* If even bit is set then
increment even counter */
if(n & 1)
even_count++;
n = n>>1;
}
return isMultipleOf3(abs(odd_count - even_count));
}
/* Program to test function isMultipleOf3 */
int main()
{
int num = 24;
if (isMultipleOf3(num))
printf("%d is multiple of 3", num);
else
printf("%d is not a multiple of 3", num);
return 0;
}
``````

``main(a){printf(a="main(a){printf(a=%c%s%c,34,a,34);}",34,a,34);}``
``y ^ ((x ^ y) & -(x < y))``