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

Questions

1. 3 Travelers crossing the river
   

   Three travelers need to cross a river. Each traveler has a 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
   ')
   It can be seen that there is a boat on the boat. If you are a traveler, then you’ll run away from there. It is a rule that it applies to travelers.
   What strategy will ensure that?

   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, taking all the money. The same applies to two travelers, if they remain 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 effortlessly pick up a stone and throw it overboard, with the result that the stone goes to the bottom of the lake. What happens to the water level in the lake? Will it rise, fall or remain the same?
   
   
   

Tasks

1. Multiple of 3
   

   Write a method to check if there is a number of multiple of 3.

   Transfer

   Write an effective program to check if a number is a product of a triple.
   
   
   
2. Write a quine
   

   A copy of it is a program. A quine takes no input. File of the program. Quines are named after the American mathematician and logician Willard Van Orman Quine (1908–2000).
   

   Transfer

   Write a quine program that prints its source code to output. Quine does not accept any input. You are not allowed to use the file, and then display its contents. Quian is named after Willard Van Orman Quine (1908-2000).
   
   
   
3. Min / Max without branching
   

   It can be slowed down.
   
   

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

   
   Write a program to find out the minimum of two integers without branching.
   

   Transfer

   On some machines where branching is expensive, the following approach for 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 a minimum of two numbers without using branching.
   

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 go down. The correct answer was found in the comments, an explanation can be found for example in this comment .
   
   
   
3. Task 1

   Summing digits of numbers and checking divisibility by 3 is not the most effective approach.
   The commentary suggested the correct pattern: if the difference between the sum of even and odd bits is divided into three. We consider the sum approximately as in a classical example about the counting of bits.
   
   Initial solution:
   
   

    // CPP program to check if n is a multiple of 3 #include<bits/stdc++.h> 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; } 

   
   
   
   
4. Task 2

   In the comments were proposed solutions.
   
   The original version of C ++:
   

    main(a){printf(a="main(a){printf(a=%c%s%c,34,a,34);}",34,a,34);} 

   
   
   
   
5. Task 3

   The comments suggested several correct solutions. Original:
   

    y ^ ((x ^ y) & -(x < y))