Выпуск#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))


    Spice IT Recruitment 95,12
    ИТ специализированное кадровое агентство
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 42
    • 0

      Вопрос N2:


      Ответ и решение

      Ответ: Уровень воды уменьшится.


      1) Как легко понять, неважно, где камень, в лодке на дне или привязан за веревку и находится полностью в воде. Ну, заменим камень песком или тяжелой жидкостью...


      2) Т.е. если утопить камень (или перерезать веревку) сумма объема воды в озере плюс объем камня не изменится.


      3) Но лодка всплывет.


      4) Значит уровень воды упадет.


      Честно говоря, я сначала формулы в Maple написал, удивился результату, а уже потом через некоторое время понял, как без них объяснить.

      • +2
        Я бы сказал ваше объяснение для меня не совсем ясное. Я понимаю это так:
        Ход мысли
        — воду вытесняемую человеком и лодкой не трогаем, т.к. эта составляющая неизменна;
        — камень в лодке на плаву, значит вытеснен объем воды по массе равный массе камня;
        — камень на дне, значит вытеснен объем самого камня.
        Из того, что плотность камня больше плотности воды (камень тонет), следует, что при одинаковой массе вода имеет больший объем чем камень.
        Те. V_озера+V_воды_массой_камня > V_озера+V_камня.
        • 0
          Ну, конечная формула, очевидно, та же самая, что у меня. Только я совсем без формул и упоминания закона Архимеда в объяснении обошелся.

          P.S. У меня может быть не совсем понятен только первый пункт. Ну, могу подробнее. Считаем лодку плоскодонкой. Далее давайте условно расплавим камень, потом, сделаем поверх новое дно лодки а низ отрежем — пусть тонет. Понятно, что мы имеем право считать дно лодки невесомым — неважно, где вес сосредоточен.
      • 0
        Задача 1

        Путешественник А перевозит все деньги на другой берег. Далее перевозит путешественника Б, но на обратном пути забирает свою тысячу. Забирает путешественника C, оставив свою тысячу на изначальном берегу, после возвращается за ними.
        • 0
          Путешественник А перевозит все деньги на другой берег.

          И сбегает с ними…
          • 0
            с какого перепуга? согласно условий он сбегает если сумма чужих денег выше чем у него, а в данном случае получится сумма равна
            • 0
              Все деньги, это 1000+700+300? Или таки только свои?
              • 0
                да, все две тысячи постепенно перевезти на другую сторону, согласно условия задачи
                с количеством золота, превышающим его собственное

                он не сбежит, так как количество чужого золота не превышает его собственное
                • 0
                  Про «постепенно»… Я спрашивал про первый ход.
                  • –1
                    согласно условиЮ
                • 0
                  Нет. См. условие задачи. Он сбегает, как только он остается наедине с суммой, большей, чем у него было изначально:

                  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.
            • +1
              Multiple of 3

              Не совсем понятно условие.
              Если число представлено в десятичной записи, то достаточно проверить сумму его цифр на делимость на 3.
              • 0
                Да, число вводится в десятичной записи.
                • 0
                  Как строка?
                  • 0
                    Думаю, как int
                    • 0
                      Тогда оно окажется в системе счисления компьютера, и школьное правило окажется неэффективным, поскольку потребует предварительного перевода N-ричного числа в десятичную систему счисления.
                    • +1
                      да, как строка, и тогда можно работать с ооооооооооооооооооочень длинной арифметикой )
                • 0
                  Задача N3:

                  Если число десятичное, то школьное правило, если троичное, то ноль в конце, если шестнадцатеричное, то поскольку 16^N mod 3 == 1, то тоже самое школьное правило, для прочих систем счисления тоже можно найти подобные правила (типа как для двоичной — см. google):

                  На самом деле последовательность вида M^k mod 3, k=1,2,3… где M — основание системы счисления бывает, вроде бы, всего лишь трех типов:

                  0, 0, 0, 0,…
                  1, 1, 1, 1…
                  1, 2, 1, 2,… (или с двойки начинается).

                  Если первый вариант, то систем «троичная» и надо, чтобы был ноль в конце. Если второй — то «школьное» правило, а вот если третий вариант, то тот же способ, что и для двоичной системы — надо, что бы сумма цифр, стоящих на четных местах, минус сумма, стоящих на нечетных, делилась на три.

                  A вот если N число задано, например, последовательностью из N единиц, а потом нулем, и неизвестно, на какой системе счисления основан компьютер (или даже просто неизвестно про систему счисления — ну, типа в римских числах), то все становится интереснее.
                  • 0
                    первая задача:
                    Обозначение: берег — {лодка} --> берег

                    B,C, 1000 — {A,1000} --->> 0
                    B,C, 1000 << — {A} — 1000
                    A, 1000 — { B,C} --->> 1000
                    A, 1000 << — {C, 300} — B, 700
                    C, 300 — {A,1000} -->> B, 700
                    C, 300 << — {B, 700} — A, 1000
                    1000 — {B,C} --->> A, 1000
                    1000 << — {A} — B,C, 1000
                    0 — {A, 1000} -->> B,C, 1000

                    Минимум без условий:
                    min = (a + b – (a – b) & 0x7FFFFFFF) / 2

                    Задача про деление на три: если разница между суммой четных и нечетных битов делится на три. Сумму считаем примерно как в классическом примере о подсчёте битов.
                    Разница может быть только меньше 16 для x32 числа и меньше 32 для x64 числа, поэтому для неё можно сделать лукап- таблицу.
                    попозже может мину исходники: дерево решений для первой и код для других задач.
                    • 0
                      #define yMIN(a,b) (b- ((a-b) & 0x7FFFFFFF) +a )>>1
                      #define yMAX(a,b) (b+ ((a-b) & 0x7FFFFFFF) +a )>>1
                      
                      #define SWAP_NO_IF(a,b,type) { type t = (a^b) & -(a > b); a = a^t; b = b^t;}
                      
                      
                      uint32_t lookupDiv3[] = {1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0};
                      
                      
                      int div3(uint32_t x){
                      
                      	uint32_t evens = (x & 0xAAAAAAAA) >> 1;
                      
                      	evens = ((evens>>2) & 0x33333333) + (evens & 0x33333333);
                      	evens = ((evens>>4)+evens) & 0x0F0F0F0F;
                      	evens = ((evens>>8)+evens) & 0x00FF00FF;
                      	evens = ((evens>>16)+evens) & 0xFF;
                      
                      	uint32_t odds = x & 0x55555555;
                      	odds = ((odds>>2) & 0x33333333) + (odds & 0x33333333);
                      	odds = ((odds>>4)+odds) & 0x0F0F0F0F;
                      	odds = ((odds>>8)+odds) & 0x00FF00FF;
                      	odds = ((odds>>16)+odds)& 0xFF;
                      
                      	SWAP_NO_IF(evens, odds, uint32_t);
                      
                      
                      	return lookupDiv3[odds - evens]; //lookupDiv3[odds - evens];
                      }
                      • 0
                        В этом случае А едет с двумя мешками на первом или на последнем ходу. То есть в лодку не влезет.
                      • 0
                        Вопрос 1
                        1. Туда: A + 1000, обратно: А
                        2. Туда: B + C, обратно B + 700
                        3. Туда: A + 1000, обратно C + 300
                        4. Туда: B + C, обратно A
                        5. Туда: A + 1000

                        Вопрос 2
                        Пока камень находится в лодке, она вытесняет объём воды, равный по массе лодке + человеку + камню.
                        Когда камень опустился на дно озера, то лодка вытесняет объём воды, равный по массе лодке + человеку, а погрузившийся камень вытесняет меньше, чем раньше, иначе он бы не утонул.
                        Таким образом, уровень воды снизится.

                        Задача 1
                        bool isMultiplyOf3(int number) {
                          int sum = 0;
                          while (number) {
                            sum += (number & 1);
                            number >>= 1;
                            sum -=  (number & 1);
                            number >>= 1;
                          }
                          return !sum;
                        }

                        • 0
                          Multiple of 3 решена неверно )
                          • 0
                            Да, пока модерация шла, я уже сам понял.
                            Надо заменить return !sum; на
                            if ($sum < 0) {
                                  $sum = -$sum;
                              }
                              return !$sum || ($sum > 2 && isMultiplyOf3($sum));

                            }
                            • 0
                              Подумайте ещё )
                              • 0
                                Пардон, не разглядел приведение модуля, вот теперь похоже не правду )
                          • 0
                            Задачка 3

                            r = (a+b-abs(a-b))/2;
                            надеюсь взятие модуля числа и деление на 2 сдвигом недороги на неуказанной абстрактной платформе, где будет исполняться кот

                            • +1
                              в предполагаемой платтформе, взятие модуля числа будет либо операцией с условием либо каким то числовым трюком как в моём ответе
                              • 0

                                зависит от представления отрицательных чисел — в обратном, дополнительном до 1 или дополнительном до 2 коде. где-то достаточно просто занулить знаковый бит по И по маске, где-то просто прибавить максимальное число разрядной сетки умноженное на знаковый бит, сдвинутый вправо на ту же величину разрядной сетки — получается мы прибавляем макс_сигнед_инт умноженный на 1 если число отрицательное и на 0 если положительное — и получаем модуль числа.


                                но это уже детали реализации. стравлю 200 денег, что составители задачи хотели увидеть именно такое решение, как написано выше

                                • +1
                                  а как же через сигн и массив
                                  можно еще разложить входные данные в массив, потом взять sign от разницы чисел и использовать его для адресации по массиву.
                                  примерно так:
                                  int[3] a={y,y,x};
                                  int i=sign(x-y);
                                  return a[i+1];
                                  • 0

                                    Отлично. Сигн по знаковому биту, выделенному маской и сдвинутому в 0 позицию даже проще чем модуль.

                            • 0

                              del

                              • +2

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

                                • 0
                                  Варианты когда плотность камня меньше плотности воды или воздуха рассматривать лень


                                  Камень плотность которого меньше воздуха — взлетит), камень плотность которого меньше воды — всплывет)). За условием задачи камень упал на дно — значит его плотность больше плотности воды.
                                  • 0

                                    Его можно силой затащить на дно, привязав веревкой к коряге )) И тогда уровень воды поднимется — по той же логике крайних значений — представьте что вы везли в лодке огромный воздушный шар )) И это стройно укладывается в модель — при плотности камня больше плотности воды уровень опустится, при меньше — поднимется. А если камень деревянный, и не затаскивать его на дно, а позволить плавать свободно после выкидывания за борт — то вангую что уровень не изменится — но надо аккуратнее разобрать этот вариант для уверенности )

                                    • 0
                                      В исходной ситуации суммарный вес камня и лодки скомпенсирован весом вытесненной ими воды. После потопления камня — нет. То есть вес вытесненной воды стал меньше суммарного веса лодки и камня. Так как трудно себе представить, что при потоплении камня удельный вес воды изменяется, то уменьшение веса вытесненной воды может произойти только за счёт уменьшения её объёма. Следовательно, уровень упадёт.
                                      А если камень плавучий, то действительно не изменится.
                                • 0

                                  Квайн:
                                  1
                                  проверяется в любом РЕПЛе


                                  я не думаю, что составители задачи будут в восторге от такого ответа, но квайнопись сильно зависит от языка — а он не был озвучен. Или это интервью в ту компанию, где кроме С языков не знают? ))

                                  • 0
                                    Для интерпретируемых языков самый простой квайн — пустой файл.
                                  • 0
                                    #! /bin/more
                                    Дальше что угодно.
                                    • +1
                                      переправа
                                      Назовём пустников 1,2,3, у 1 — 300 у 3 — 1000.
                                      -2 уезжает со своими 700 и оставляет там, возвращаясь
                                      -3 берёт 300 и отвозит на тот берег, возвращается (ведь у него и своих столько же)
                                      -отбывают 1 и 2, кто-то из них возвращается со своим, чтобы его место на том берегу занял 3 (со своим)
                                      -отбывает второй со своим, теперь оба переезжают без мешков, все три путника на другом берегу
                                      -3 плывёт назад за 700 и возвращается
                                      -1 плывёт назад за 300 и возвращается


                                      уровень воды
                                      понизится

                                      делимость на 3
                                      короче, логика такая: два соседних разряда это х+2х, значит 11 везде в тексте кода делится на 3. Теперь если мы из болльшего четного числа еденичек вычтем четные единички (например 1001) всё равно будет делиться на три, т.к. вычитаемое и уменьшаемое по отдельности делится. Значит чтобы не писать много лишнего кода с проверками, просто заменим одну за другой все пары последовательных ноликов 00 на 11, а затем все 11 на 00. если получился ноль, значит делится, если не ноль — не делится. Единственное что надо проверить — это что вначале не ноль.

                                      min
                                      a xor b — исследуем пошагово побитово, начиная со старших. Там где первая 1 попалась, говорим что это индекс k. Выводим a*(!a_k)+b*(!b_k)

                                      Начал писать квайн, исправлял ошибки методом дописывания. Это было ошибкой. Посмотрел на сайте квайнов на пайтоне, и понял, какой же я лох. Тем не менее, квайн рабочий
                                      a = []
                                      a.append("a")
                                      a.append(" = []")
                                      a.append(".append")
                                      a.append("(")
                                      a.append("\"")
                                      a.append(")")
                                      a.append("\\")
                                      a.append("a")
                                      a.append("print(a[0] + a[1])")
                                      a.append("for i in range(13):")
                                      a.append("    print(a[0] + a[2] + a[3] + a[4] + a[6] + a[i] + a[4] + a[5] if (i==4 or i ==6) else a[0] + a[2] + a[3] + a[4] + a[i] + a[4] + a[5])")
                                      a.append("for i in range(8, 13):")
                                      a.append("    print(a[i])")
                                      print(a[0] + a[1])
                                      for i in range(13):
                                          print(a[0] + a[2] + a[3] + a[4] + a[6] + a[i] + a[4] + a[5] if (i==4 or i ==6) else a[0] + a[2] + a[3] + a[4] + a[i] + a[4] + a[5])
                                      for i in range(8, 13):
                                          print(a[i])

                                      • 0

                                        Немного перемудрили с min. Достаточно (x+y-abs(x-y))/2. Функция abs реализована через зануление sign-bit.

                                        • 0
                                          Сейчас нет современных архитектур, где изменение одного знакового бита в X даёт (-X), т.к. это не эффективно при сложении-вычитании.

                                          -1 — это в двоичном коде все единицы (11111111), чтобы при прибавлении 1 получить 0 (00000000) обычным суммированием с переполнением старшего разряда.

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое