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

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?
   
   
   

Tasks

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.
   

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 .
   
   
   
3. Task 1

   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;
   }
   

   
   
   
   
4. Task 2

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

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

   
   
   
   
5. Task 3

   The comments suggest several correct solutions. Source:
   

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