reci January 11, 2018 at 12:45

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

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

KDPV

We selected tasks and questions on the logic that can ask applicants for the position of developer at Microsoft. Tasks have a different level of difficulty (even if everything seems very simple at first glance :).

The purpose of the selection is to prepare the applicant for a successful interview, by training the ability to find optimal algorithms for solving and build logical chains, rather than banal memorization of answers.

We hope that we have achieved this goal.

Questions

Duck in the pond
A duck that is being chased by a fox saves itself by sitting at the center of circular pond of radius r. The duck can fly from land but cannot fly from the water. Furthermore, the fox cannot swim. The fox is four times faster than the duck. Assuming that the duck and fox are perfectly smart, is it possible for the duck to ever reach the edge of the pond and fly away to its escape from the ground?

Transfer
A duck chased by a fox rescues in the center of a circular pond of radius r. A duck can take off from the ground, but not from the water. The fox does not know how to swim. Also, a fox is 4 times faster than a duck. Assuming the duck and the fox are perfectly intelligent, is it possible for the duck to reach the shore and fly away?
Fruit Crates (and Labels)
In front of you are three boxes. One contains only apples, one contains only oranges and one contains 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 only one, box. I will remove a randomly selected piece of fruit from your chosen box and show it to you (so you can tell if it's an apple or an orange). After that, you will be able to accurately and definitively relabel all three boxes

Transfer
Before you 3 drawers. One contains only apples, the second contains only oranges, and the third contains apples and oranges. Each box has an incorrectly hung label, like:
Box 1: “apples”
Box 2: “oranges”
Box 3: “apples and oranges”

Question: You only need to select one box, after which I will pull one fruit out of the selected box and show you (so that you can determine whether it is an apple or an orange). You need to accurately outweigh the labels on the drawers.

Tasks

Multiply without a multiplication operator
Write a function that takes the produce of two given integers without using the multiplication operation. Try to do this as fast as you can (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 necessary to implement multiplication without the operators of multiplication, division, loops and bitwise operators.
Nth prime
Write a function that returns the nth prime number. For example, nthPrime (1) should return 2 since 2 is the first prime number, nthPrime (2) should return 3, and so on.

Transfer
Write a function that returns the nth prime. For example:
nthPrime (1) => 2 (since 2 is the first prime),
nthPrime (2) => 3
, etc.
Find the next number with the same numbers
Given a number N, find the next number that has the same set of digits as n and is greater than N. If N is the greatest possible number with its set of digits, then print “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 digits and is greater than N. If N is the largest of the possible combinations, print "not possible".
Example:
N = “218765” => “251678”
N = “1234” => “1243”
N = “4321” => “Not Possible”
N = “534976” => “536479”

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

Solutions

Question 1
Indeed, the straight-to-shore movement for the duck is not beneficial, 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 for several circles it can stand in front of the fox so that between them will be the center of the pond. 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 a duck 3 / 4r + x
- for a fox π * r

Obviously, π * r <4 ( 3/4 r + x), and the duck can fly away.
Question 2
You must select 1 item from a box labeled "Apples + Oranges."
Since the plate is incorrect, in this box there 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 tablets “Apples” and “Oranges”, among them one box with oranges and one box with the mixture.
The tablets are incorrect according to their condition, so the oranges are in the box with the label “Apples”, and the mixture is in the box with the label “Oranges”.
If an orange were taken from the first box, the solution would be similar.

Task 1

One solution is recursion:

#include
/* 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;
}

Task 2

Possible answer:


#include 
#include 
#include 
#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 maxPrime)
           maxPrime = arr[i];
   }
   int primes[maxPrime];
   prime(maxPrime, primes);
   for (i=0;i

Задача 3Оригинальное решение: 

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

Теги:
spiceit
itренировка
microsoft
задачи для собеседований

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

Questions

Tasks

Solutions

Also popular now: