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

It's time to publish the following selection of tasks that are set at interviews at leading IT-companies.



We selected the tasks and questions on the logic that can ask applicants for the position of developer in Microsoft. Tasks have a different level of complexity (even if they all seem at first glance very simple :).
')
The purpose of the compilation is to prepare the applicant for successful interviewing, by training the ability to find algorithms that are optimal for solving and building logical chains, rather than by banal memorization of answers.

We hope that we have achieved this goal.

Questions

1. Duck in the pond
   

   The fox saves the chrome by the fox saves by itself. Cant fly from land but not fly from the water. Furthermore, the fox cant swim. The fox is four times faster than the duck. It is possible that it is possible to reach the distance from the ground.

   
   
   Transfer

   A duck, pursued by a fox, is saved in the center of a round pond of radius r. The duck can take off from the ground, but not from the water. Fox does not know how to swim. Also, a fox is 4 times faster than a duck. Assuming that the duck and the fox are absolutely reasonable, is it possible for the duck to reach the shore and fly away?
   
2. Fruit Crates (and Labels)
   

   In front of you are three boxes. One contains only apples, one contains only a mix of apples and oranges. Each box is incorrectly labeled, like this:
   Box 1: “apples”
   Box 2: “oranges”
   Box 3: “apples & oranges”
   
   Question: You get to choose one, and one box only. It will remove your skin from the box. After that, you will be able to relabel all three boxes.
   

   
   
   Transfer

   There are 3 boxes in front of you. One contains only apples, the second - only oranges, and the third - and apples and oranges. Each box has an incorrectly labeled label, like:
   Box 1: "apples"
   Box 2: "Oranges"
   Box 3: "apples and oranges"
   
   Question: You need to choose only one box, after which I will pull out one fruit from the selected box and show you (so that you can determine whether it is an apple or an orange). You need to correctly outweigh the labels on the boxes.
   

Tasks

1. Multiply without multiplication operator
   

   The integers without the multiplication operation. O (log (n) or better)
   

   
   
   Transfer

   Write a function that returns the product of 2 integers without using the multiplication operator. Try to implement with maximum performance (O (log (n) or better).
   I also saw a variation of this problem, where it was required to implement multiplication without multiplication, division operators, cycles and bitwise operators.
   
2. Nth prime number
   

   Write a function that returns the nth prime number. For example, nthPrime (1) should return 2, since this is the first prime number, nthPrime (2) should return 3, and so on.

   
   
   Transfer

   Write a function that returns the nth prime number. For example:
   nthPrime (1) => 2 (since 2 is the first prime number),
   nthPrime (2) => 3
   etc.
   
3. Find the next number with the same numbers.
   

   It is not necessary to set the number of digits for the digits, and it is “not possible”.
   Ex:
   N = "218765" => "251678"
   N = "1234" => "1243"
   N = "4321" => "Not Possible"
   N = "534976" => "536479"
   

   
   
   Transfer

   Given the number N, you need to find the next number that has the same set of numbers and is greater than N. If N is the largest possible combination, output “not possible”.
   Example:
   N = "218765" => "251678"
   N = "1234" => "1243"
   N = "4321" => "Not Possible"
   N = "534976" => "536479"
   

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

Solutions

1. Question 1

   Indeed, the movement in a straight line to the bank for a duck is not advantageous, since the fox is 4 times faster, it will be at the exit point earlier: (π * r) <(4 * r).
   
   A duck can swim in circles, and if the radius of the circle is <r / 4, then it will swim this circle faster than the fox, and in several circles it will be able to stand opposite the fox so that there will be a pond center between them. Suppose that a duck began to swim at a distance of r / 4-x (where x is an infinitely small value), then to the exit point:
   - for duck 3 / 4r + x
   - for fox π * r
   
   Obviously, π * r <4 (3/4 r + x), and the duck can fly away.
   
   
   
2. Question 2

   It is necessary to choose 1 item from the box with the sign “Apples + Oranges”.
   Since the plate is wrong, in this box are either only apples or only Oranges.
   Suppose we got an apple. The correct label for this box is "Apples."
   
   On the remaining two boxes there are the plates “Apples” and “Oranges”, among them there is one box with oranges and one box with a mixture.
   The plates on the condition on them are wrong, meaning oranges are in a box with a sign "Apples", and the mixture - in a box with a sign "Oranges".
   If you got an orange from the first box, the solution would be the same.
   
   
   
3. Task 1

   One solution is recursion:
   
   

   #include<stdio.h> /* function to multiply two numbers x and y*/ int multiply(int x, int y) { /* 0 multiplied with anything gives 0 */ if(y == 0) return 0; /* Add x one by one */ if(y > 0 ) return (x + multiply(x, y-1)); /* the case where y is negative */ if(y < 0 ) return -multiply(x, -y); } int main() { printf("\n %d", multiply(5, -11)); getchar(); return 0; } 

   
   
   
   
4. Task 2

   Possible answer:
   

    #include <stdio.h> #include <stdlib.h> #include <math.h> #define MAX 100000000 void prime(int n, int *primes) { int i,j,count=0; primes[count++] = 2; if (count == n) return; for(i=3;i<=MAX;i+=2) { int isPrime=1; int jMax = sqrt(i); for(j=3;j<=jMax;j+=2) { if(i%j==0) { isPrime=0; break; } } if(isPrime) { primes[count++] = i; if(count==n) return; } } } int main() { int n,i; scanf("%d",&n); int arr[n]; int maxPrime = 0; for(i=0;i<n;i++) { scanf("%d",&arr[i]); if (arr[i] > maxPrime) maxPrime = arr[i]; } int primes[maxPrime]; prime(maxPrime, primes); for (i=0;i<n;i++) { printf("%d\n", primes[arr[i]-1]); } return 0; 

   
   
   
   
5. Task 3

   Original solution:
   

    #include <iostream> #include <cstring> #include <algorithm> using namespace std; // Utility function to swap two digits void swap(char *a, char *b) { char temp = *a; *a = *b; *b = temp; } // Given a number as a char array number[], this function finds the // next greater number. It modifies the same array to store the result void findNext(char number[], int n) { int i, j; // I) Start from the right most digit and find the first digit that is // smaller than the digit next to it. for (i = n-1; i > 0; i--) if (number[i] > number[i-1]) break; // If no such digit is found, then all digits are in descending order // means there cannot be a greater number with same set of digits if (i==0) { cout << "Next number is not possible"; return; } // II) Find the smallest digit on right side of (i-1)'th digit that is // greater than number[i-1] int x = number[i-1], smallest = i; for (j = i+1; j < n; j++) if (number[j] > x && number[j] < number[smallest]) smallest = j; // III) Swap the above found smallest digit with number[i-1] swap(&number[smallest], &number[i-1]); // IV) Sort the digits after (i-1) in ascending order sort(number + i, number + n); cout << "Next number with same set of digits is " << number; return; } // Driver program to test above function int main() { char digits[] = "534976"; int n = strlen(digits); findNext(digits, n); return 0; }