Выпуск#11: ITренировка — актуальные вопросы и задачи от ведущих компаний

Мы отобрали для Вас несколько интересных вопросов и алгоритмических задач, задаваемых на собеседованиях в Luxoft.

КДПВ

При устройстве на работу в Luxoft, соискателям чаще задаются вопросы технического характера, например, для проверки уровня владения технологией. Но тем не менее, встречаются и вопросы, связанные с логикой, и алгоритмические задачи. Ниже приведены наиболее интересные из них, среди которых мы постарались выбрать вопросы различного уровня сложности.

Вопросы

  1. 3 Travellers crossing the river

    Three travellers need to cross a river. Each traveller has certain amount of gold coins kept in his bag.
    Traveller A has 1000 gold coins
    Traveller B has 700 gold coins
    Traveller 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 travellers can cross the river or a traveller with a bag can cross the river. The problem is that in this process of crossing the river if a traveller is left with an amount of coins more than his own then he will run away with that. The same rule applies for two travellers, 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 ?

    Перевод

    Трём путешественникам нужно пересечь реку. У каждого из них определенное количество золотых монет в рюкзаке.
    Путешественник А имеет 1000 монет
    Путешественник B имеет 700 монет
    Путешественник C имеет 300 монет

    Для пересечения реки есть лодка, которая может вместить максимум 2 объекта — двух путешественников или путешественника с рюкзаком. Проблема заключается в том, что если оставить любого путешественника с количеством золота, превышающим его собственное — он сбежит, прихватив все деньги. То же касается и двух путешественников, если они останутся с золотом, превышающим их суммарные запасы — они убегут с золотом.
    Какая стратегия позволит всем пересечь реку и остаться при деньгах?

  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?

    Перевод

    Вы находитесь в гребной лодке посреди озера. В лодке также лежит тяжёлый камень. Вы с усилием поднимаете камень и выбрасываете за борт, в результате чего, камень уходит на дно озера. Что произойдёт с уровнем воды в озере? Он поднимется, опустится или останется таким же?

Задачи

  1. Multiple of 3

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

    Перевод

    Напишите эффективную программу для проверки, является ли число произведением тройки.

  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).

    Перевод

    Напишите куайн — программу, которая печатает на вывод свой исходный код. Куайн не принимает никаких входных данных. Вам не разрешено использовать файл, а потом выводить его содержимое. Куйан назван в честь американского математика и логика Уилларда Ван Ормана Куайна (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.

    Перевод

    На некоторых машинах, где ветвление является дорогим, следующий подход для нахождения минимума будет медленным:

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

    Напишите программу для нахождения минимума из двух чисел, не используя ветвление.

Ответы будут даны в течение следующей недели — успейте решить. Удачи!

Решения

  1. Вопрос 1

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

  2. Вопрос 2

    Объём воды понизится. Верный ответ нашли в комментариях, объяснение можно посмотреть например в этом комментарии.

  3. Задача 1

    Суммирование цифр числа и проверка делимости на 3 — не саммый эффективный подход.
    В комментарии был предложен верный паттерн: если разница между суммой четных и нечетных битов делится на три. Сумму считаем примерно как в классическом примере о подсчёте битов.

    Исходный вариант решения:

    // 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. Задача 2

    В комментариях были предложены решения.

    Исходный вариант на С++:

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

  5. Задача 3

    В комментариях предложено несколько корректных решений. Исходное:

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

FavoriteLoadingДобавить в избранное

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *