22.05.2018 12:18
reci 43 4500 Источник
Мы подготовили для Вас новый выпуск, ставшей уже традиционной, ITренировки — подборки задач с собеседований в IT-компании мира.
КДПВ
В отобранные задачи попали задачи с собеседований Samsung. Соискателю также могут задать вопрос про шифр и Шерлока Холмса (нет, не пляшушие человечки, как можно было подумать). Уровень сложности мы постарались варьировать — от простых до серьезных.

Вопросы


  1. Faulty machine
    We have 10 machines that produce screws, each weighing 1 gram. One of the machines, however, produces screws weighing 0.9 grams only. We are allowed only one weighing and need to determine which machine is faulty.

    Перевод
    У нас есть 10 машин, производящих винты, каждый весом в 1 грамм. Правда, одна из машин производит винты весом 0,9 грамм. Нам разрешено произвествие только одно взвешивание (прим. винтов), чтобы найти машину, производящую бракованные винты.
  2. Holmes and cipher
    Sherlock Holmes was decoding an encrypted message. If in the encryption, DISTANCE is written as IDTUBECN and DOCUMENT is written as ODDVNTNE.

    Can you help him decipher HTTQYAD?

    Перевод
    Шерлок Холмс разгадывает зашифрованное сообщение. В шифре, DISTANCE обозначено как IDTUBECN, а DOCUMENT — как ODDVNTNE.

    Сможете ли Вы помочь ему расшифровать HTTQYAD?

Задачи


  1. Research center and rare elements
    A Research team want to establish a research center in a region where they found some rare-elements.They want to make it closest to all the rare-elements as close as possible so that they can reduce overall cost of research over there.It is given that all the rare-element’s location is connected by roads.It is also given that Research Center can only be build on road.Team decided to assign this task to a coder.If you feel you have that much potential..Here is the Task :- Find the optimal position of research center from given locations of rare-elements.

    Locations are given in the matrix cell form where 1 represents roads and 0 no road. Number of rare-element and their location was also given(number<=5) and order of square matrix was less than equal to (20).

    Перевод
    Исследовательская команда хочет основать центр исследований в регионе, где найдены некоторые редкие элементы. Они хотят расположить его максимально близко ко всем источникам элементов, чтобы снизить общие затраты. Источники элементов соединены дорогами. Также, исследовательский центр может быть построен только возле дороги. Команда решает поручить задачу разработчику, и, если Вы чувствуете свой потециал — найдите оптимальное расположение центра, исходя из локаций элементов.

    Локации даны в виде матрицы, где 1 в ячейке означает наличие дороги, а 0 — её отсутствие.
    Также даны локации элментов (числом <= 5). Порядок квадратной матрицы <= 20.
  2. Stack down or up
    In a typical process, a stack segment of program contains local variables along with information that is saved each time a function is called. Each time a function is called, the address of where to return to and certain information about the caller’s environment, such as some of the machine registers, are saved on the stack. The newly called function then allocates room on the stack for its automatic and temporary variables.

    Stack may grow downward or upward depending on environment for which code is compiled, i.e., depends on compiler. Write down the program to determine whether stack grows downward or upward?

    Перевод
    Обычно, сегмент стека программы содержит локальные переменные с информацией, сохраняемой при каждом вызове функции. Когда вызывается функция, в стек сохраняется адрес возврата и информация об окружении — например, некоторые регистры. Затем вызываемая функция занимает место в стеке для своих автоматических и временных переменных.

    Стек может расти вниз или вверх в зависимости от среды, для которой скомпилирован код, т. е. зависит от компилятора. Реализуйте программу для определения, растет ли стек вниз или вверх.
  3. Next greater element
    Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

    Examples:
    a) For any array, rightmost element always has next greater element as -1.
    b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
    c) For the input array [4, 5, 2, 25], the next greater elements for each element are as follows.
    Element       NGE
   4      -->   5
   5      -->   25
   2      -->   25
   25     -->   -1

    d) For the input array [13, 7, 6, 12], the next greater elements for each element are as follows.
      Element        NGE
   13      -->    -1
   7       -->     12
   6       -->     12
   12     -->     -1


    Перевод
    Дан массив, напечатайте следующий больший элемент (NGE) для каждого из элементов. Следующим большим элементом для x является первый больший элемент с правой стороны от x в массиве. Если такого элемента не существует — NGE считается -1.
    Примеры:
    a) Для любого массива, крайний правый элемент всегда имеет NGE = -1.
    b) Для любого массива, отсортированного по убыванию, все элементы имеют NGE = -1.
    c) Для элементов массива [4, 5, 2, 25] NGE будет следующим:
    Элемент       NGE
   4      -->   5
   5      -->   25
   2      -->   25
   25     -->   -1

    d) Для элементов массива [13, 7, 6, 12] NGE будет следующим:
     Элемент         NGE
   13      -->    -1
   7       -->     12
   6       -->     12
   12     -->     -1


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

Комментарии (43)


  1. KYKYH
    22.05.2018 16:18
    #11367180
    +1

    А почему во втором вопросе ответ

    2
    thurday


    1. StanislavMikheyev
      22.05.2018 16:36
      #11367212
      +1

      Я точно не знаю, но я получил ответ так — первые две буквы надо поменять местами, последние 3 записать в обратном порядке, а каждую букву в центре заменить на следующую в алфавите.


      1. mird
        22.05.2018 17:37
        #11367304

        вот только в вопросе каждая буква в центре заменяется на предыдущую. Кажется, в задаче ошибка… Ну либо правильный ответ Thursday, а алгоритм сложнее.


        1. ProstoUser
          22.05.2018 18:53
          #11367474
          +1

          На Thursday букв не хватает. В задаче их 7, а не 8.

          У меня THSPDAY получилось


          1. mird
            23.05.2018 12:55
            #11368752

            Дело в том, что предыдущие слова все по 8 символов. Так что, скорее всего, тут ошибка в условии (даже две).


      1. unknown_geo
        22.05.2018 18:06
        #11367364

        По идее для расшифровки буквы в центре надо заменять на предыдущие в алфавите: в шифре IDTUBECN в центре это будут DISTANCE. Поэтому в зашифрованном HTTQYAD это должны быть THSPDAY. Похоже на ошибку в вопросе


      1. paratagas
        23.05.2018 10:31
        #11368348

        У меня получилось THURDAY, а для того, чтобы было THURSDAY, в вопросе должно было быть слово HTTQRYAD.


      1. smer44
        25.05.2018 04:42
        #11371528

        я тож в уме прикинул, если так сделать будет th???day а единственное слово в английском которое подходит это thursday,, буквы в центре рандомные для запутывания?


    1. iva666ka
      22.05.2018 18:06
      #11367366
      +1

      написавший был русским шпионом, поэтому сделал ошибку в слове. Но ответ такой, да.


  1. jmdorian
    22.05.2018 18:11
    #11367376
    +1

    1
    Взвесить для каждой машины число болтов равное ее номеру.


    1. jmdorian
      22.05.2018 18:21
      #11367404
      +1

      Задача 2
      Поправьте, если я не прав: каждая локальная переменная помещается в стек. Так почему не сделать например так
      void checkStack() {
 int a;
 int b;
 if (&a < &b) {
   cout << "Up" << endl;
 } else {
   cout << "Down" << endl;
 }
}


      1. ProstoUser
        22.05.2018 19:17
        #11367510
        +2

        Думаю, не верно. В рамках одного вызова ни кто не гарантирует (даже не упоминает) порядок расположения локальных переменных в стеке.

        Ну и сравнение указателей так просто не сработает. Надо к интам закастить.

        Примерно так:

        bool CheckStack(int *p)
{
	int var;
	if ((int)p == 0)
		return CheckStack(&var);
	return (int)(&var) < (int)p;
}


        Вызвать исходно с нулем. Если вернет 1, значит стек растет сверху вниз.

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


        1. jmdorian
          23.05.2018 11:12
          #11368444

          Согласно этому указатели таки можно сравнивать as is.


          1. ProstoUser
            23.05.2018 16:22
            #11369148

            Да. Я не прав. С какой стати это мне пришло в голову — понятия не имею.

            Действительно, указатели одного типа можно сравнивать на больше/меньше непосредственно.


  1. creat0r
    22.05.2018 20:22
    #11367606

    А если нет никаких уточнений про механизм «weighing», почему бы не

    1
    сделать весы в виде сбалансированного горизонтального диска на центральном подвесе с равномерно расположенными по внешнему краю отверстиями для шурупов?


    1. Kanut79
      23.05.2018 09:11
      #11368170

      Потому что в этом нет необходимости и всё решается с обычными весами :)


    1. AndyPike
      23.05.2018 09:58
      #11368264
      +1

      Весы одни. Взвешивание одно.

      1
      Берём 1 шуруп с 1-й, 2 шурупа со второй… 10 с 10-й.
      Сваливаем всё в кучу и идем взвешивать.
      Ответ: 10 — (wight % 1) * 10.


      1. creat0r
        23.05.2018 10:39
        #11368376
        +1

        Ну это тривиальное решение которое я заведомо знал подсмотрел бы в комментариях выше. Моё — альтернативное и с инженерной точки зрения по некоторым критериям даже более подходящее.


        1. Kanut79
          23.05.2018 11:06
          #11368424
          +1

          Я если честно немного сомневаюсь что люди, задающие такие задачи на собеседованиях, придерживаются такого же мнения :)


          1. AndyPike
            23.05.2018 14:39
            #11368956

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

            В реальной жизни — почти любую задачу можно решить не одним, а 3-мя вариантами как минимум. В результате:
            1) В уме: «Это ответ не правильный, у меня такого в вариантах нет», вербально: «Не правильно».
            2) В уме: «Я тут начальник, не понял, слишком умный что-ли?», вербально: «Вы нам не подходите».
            3) В уме: «Хм… интересно, как я до этого не додумался...»


            1. Kanut79
              23.05.2018 15:00
              #11369006

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

              Это если вас берут на должность где требуется необычный подход. А вот если вас берут на должность программиста, а вы каждый раз вместо того чтобы использовать существующие решения/программы/фреймворки, начинаете придумывать свои «альтернативные», то не думаю что это обрадует вашего работодателя :)

              В реальной жизни — почти любую задачу можно решить не одним, а 3-мя вариантами как минимум. В результате:

              А в результате всех интересует тот, который наиболее эффективен(при учёте всех необходимых требований естественно). А ваш способ эффективным назвать сложно.

              П.С. И поймите меня правильно, я не говорю что ваша идея глупа или не нужна в принципе. Я сам иногда тендирую к поиску «нестандартных решений». Но в контексте задач для собеседований такой подход не особо правильный.


              1. AndyPike
                23.05.2018 16:53
                #11369222

                У нас тоже довольно большая команда, давно уже.
                И перехожу уже с темы набора — от претендентов на реальную работу.
                По претендентам максимальный плюс может выдать только TL или кто там главный в проекте. Но до него не дойдёт, отсеют по формальным признакам. Шлак. Тест не прошёл.

                Мы отказались от этого.


                1. Kanut79
                  23.05.2018 17:00
                  #11369232

                  Ну если переходить на конкретику, то мы от подобных задач на собсеседованиях отказались. Потому что умение их решать на мой взгляд ничего не говорит ни о том как человек может работать в команде, ни о том насколько хорошо и грамотно он умеет программировать.
                  Максимум что мы делаем это даём потенциальным сениорам пример «кривого» на наш взгляд кода и спрашиваем что человек в нём поменял бы и почему. А потом просто смотрим куда приведёт обсуждение.


        1. AndyPike
          23.05.2018 14:27
          #11368928

          Полностью согласен. Эта первая задачка тривиальна — для затравки, наверно.
          Да, ваше решение действительно красивое и креативное, если понятие «весы» не определено.


  1. maslyaev
    22.05.2018 20:25
    #11367618

    Не знаю, какой хитрый алгоритм подразумевался в 3-й задаче, но через моё дерево двоичного поиска делается легко и красиво:

    Python
    import collections
import aa_sbst # Дерево, можно поиметь через "pip install aa_sbst"

def NGEs(arr):
    ans = [-1]*len(arr) # Здесь накопим результат
    t_el = collections.namedtuple('t_el', 'v, pos')
    t = aa_sbst.sbst()
    for pos, v in enumerate(arr):
        # Цикл по ранее встреченным меньшим элементам
        for el in t.backward_from(t_el(v, 0), False):
            ans[el.pos] = v
            t.remove(el) # Второй раз обрабатывать не будем
        t.add(t_el(v, pos))
    return ans


    1. Asyroc
      22.05.2018 23:06
      #11367846

      Хитрость в том,

      Спойлер
      что начинать надо с конца.
      def nge(arr):
    result = [-1] * len(arr)
    current_greater = arr[-1]
    for i in range(len(arr) - 2, -1, -1):
        if arr[i] < current_greater:
            result[i] = current_greater
        else:
            current_greater = arr[i]
    return result


      1. maslyaev
        22.05.2018 23:35
        #11367886

        Валится на первом тесткейсе:

        >>> nge([4, 5, 2, 25])
[25, 25, 25, -1]
        А должно быть [5, 25, 25, -1]


      1. qw1
        22.05.2018 23:38
        #11367890

        Тоже рассматривал в точности такой вариант. Решение простое, но неверное.
        Для массива [1,2,3] оно выдаст [3,3,-1], а надо [2,3,-1].


      1. Asyroc
        23.05.2018 01:28
        #11367986

        Упс. Ошибочка вышла

        Спойлер
        def nge(arr):
    result = [-1] * len(arr)
    current_greater = arr[-1]
    for i in range(len(arr) - 2, -1, -1):
        if arr[i] < arr[i+1]:
            current_greater = arr[i+1]
        if arr[i] < current_greater:
            result[i] = current_greater
        else:
            current_greater = arr[i]
    return result


        1. mbait
          23.05.2018 03:14
          #11368042

          WA на тесте [3, 1, 2, 4]


          1. domix32
            23.05.2018 11:11
            #11368442

            [-1, 2, 4, -1]
            да вроде все верно выдало


            1. reci Автор
              23.05.2018 11:13
              #11368446

              Должно быть [4, 2, 4, -1]


        1. amidaleet
          23.05.2018 12:52
          #11368750

          Ошибка в том, что идти нужно с конца, но сравнивать необходимо не с одним числом (максимумом), а проверять все возможные числа идущие следом в исходом массиве (или уже отобранные greaterNumbers).
          Под спойлером код на Swift c комментариями, достаточно простой чтобы понять суть алгоритма.
          Ошибка

          Код на Swift
          func nextGreaterElement(forEachIn input: [Int] ) -> [Int] {
    guard !input.isEmpty else { return [Int]() }     //Если введенный массив пуст – вернём пустой
    if input.count == 1 { return [-1] }    //Если всего 1 элемент – вернём [-1]
    
    var greaterElementsReversed = [-1] //greaterElement в обратном порядке
    
    for index in stride(from: input.count - 2, through: 0, by: -1) {
        let currentNumber = input[index]
        if currentNumber < input[index + 1] { //Проверяем следующее число в исходном массиве
            greaterElementsReversed.append(input[index + 1])
        } else {//Вынуждены поискать среди greaterElementsReversed
            guard greaterElementsReversed.last! != -1 else { //Если не было greaterElement у следующего числа, то и искать нечего, оно ведь меньше и даже для него не нашлось большего
                greaterElementsReversed.append(-1)
                continue
            }
            
            var greaterElementFound = false
            for searchIndex in stride(from: greaterElementsReversed.count - 1, through: 0, by: -1) {
                if currentNumber < greaterElementsReversed[searchIndex] {
                    greaterElementsReversed.append(greaterElementsReversed[searchIndex])
                    greaterElementFound = true
                    break
                }
            }
            if !greaterElementFound { greaterElementsReversed.append(-1) }
        }
    }
    return greaterElementsReversed.reversed()
}


          1. qw1
            23.05.2018 14:08
            #11368892

            Идея идти с конца появилась, чтобы получить линейную сложность.
            Если сложность решения всё равно O(n^2), зачем что-то запутывать?

            Можно решить самым простым и наглядным способом, тоже за O(n^2): идти от начала вперёд, и от каждого элемента снова вперёд, пока не найдёшь больший, чем текущий.


            1. amidaleet
              25.05.2018 01:49
              #11371486

              Да, действительно, я написал очень плохую реализацию, не использующую преимуществ обхода с конца и с лишними проверками.
              А смысл был в том, чтобы на каждой итерации получать некоторую ценную информацию позволяющую в будущем не сравнивать элемент с заведомо меньшими числами.
              Например в отрывке [10, 8, 6, 5, 4, 3, 2, 7, 9, 12] мы не хотим для 10 лишний раз пробегаться по [6, 5, 4, 3, 2, 7] потому что они заведомо меньше 8, что мы уже знаем совершив поиски NGE для 8. Саму 8 проверять таки придётся, потому что ища NGE для 8 мы не знаем ещё о стоящем слева числе и заведомо вышвырнуть не можем.

              Исправленный алгоритм
              Заведём дополнительный массив (стек, так как пополняется внесением элементов из исходного в конец и уменьшается в ходе последовательного перебора с конца) searchArea под потенциальные NGE, из которого такие бесполезные числа нужно исключать.
              Будем искать NGE с конца по элементам исходного массива.
              Если searchArea не пуст, сверяем последнее число в searchArea с элементом, если оно меньше или равно, то выкидываем его из searchArea (для следующих элементов в исходном массиве выкинутый элемент не может оказаться NGE, так как текущий для них и больше и ближе). Так пока searchArea не опустеет или пока не наткнёмся на большее число в нём – наш NGE.
              Наткнулись на NGE – запишем в результирующий массив NGEs.
              Обязательно добавляем текущий элемент в searchArea, ведь наш текущий элемент может стать NGE для отстоящих слева.


  1. qw1
    22.05.2018 22:46
    #11367814

    Задача про стек
    www.onlinegdb.com/HJuG7efkX


  1. mbait
    23.05.2018 02:39
    #11368018

    Это вопросы из корейского самсунга что ли, или почему английский такой корявый? Или вы сами придумываете задачи, потом их коряво переводите и выдаёте за оригинал?


    1. reci Автор
      23.05.2018 08:57
      #11368146

      Что Вы имеет против корейского Самсунга? )
      Английский вариант обычно публикуем без изменений, если ошибки не влияют на смысл.

      ps. Кстати, большая часть вопросов — из азиатского сегмента (Индия, Китай, Япония, Корея)


      1. mbait
        23.05.2018 09:06
        #11368158

        Ничего не имею. Просто если так, то понятно, а от американского Сансунга (а именно там много software и R&D отделов) странно было бы такое получить.


  1. nickolaym
    23.05.2018 18:42
    #11369446

    в1 - дефект массы

    1 винт от 1 машины, 2 винта от 2 машины и т.д.
    найти дефект массы и поделить на единичный дефект, получим номер машины


  1. nickolaym
    23.05.2018 18:56
    #11369476
    +1

    задача 1. как-то очень криво сформулирована.
    Приходится домысливать за топикстартера! Всё по-взрослому, вот тебе хотелки, сам себе сделай ТЗ!
    Поэтому под кат не прячу. Пусть будет спойлер, а авторам пусть будет стыдно.


    Допустим, так. Локации пронумерованы. Дана матрица смежности. Если локации смежные, то расстояние между ними 1. В некоторых локациях есть источники (потому что локаций — до 20 — по размеру матрицы, а источников — до 5).


    Тупое решение, благо, размер матрицы позволяет.


    1. Получаем матрицу расстояний из матрицы смежности. Это — тупо, возвести матрицу смежности в 20 степень, где (умножение) — это сложение, а (сложение) — это минимум. А единичка смежности считается 1 расстояния, нолик смежности считается бесконечностью, а на диагонали стоят 0. (расстояние до самих себя, естественно, нулевое).


    2. Для каждой локации посчитать сумму расстояний до всех источников.


    3. Найти минимум.


  1. nickolaym
    23.05.2018 19:01
    #11369494

    Задача 2 про стек

    элементарно ватсон!


    ptrdiff_t delta(char* caller) {
  char inside;
  return &inside - caller;
}

bool stack_grows_up() {
    char caller;
    return delta(caller) > 0;
}


  1. nickolaym
    23.05.2018 19:29
    #11369554

    Задача 3 про NGE, наивное решение за квадратное время
    def NGEs(xs):
  return [
    next(  # первая итерация
      (y for y in xs[i+1:] if y > x),  # итератор по следующим бОльшим элементам
      -1)  # дефолт первой итерации
    for n in (len(xs),)  # трюк с переменной внутри генератора
    for i in range(n)
    for x in (xs[i],)  # трюк с переменной внутри генератора
  ]