10.02.2018 08:12
reci 33 6500 Источник
Ставшая уже традиционной, новая подборка вопросов и задач от SpiceIT.

КДПВ

Среди отобранных задач — вопросы и алогоритмические задачи, задаваемые соискателям на должность разработчика в Samsung. Предлагаем Вам попробовать решить их самостоятельно и оценить, готовы ли Вы подавать резюме в Samsung :)

Вопросы


  1. 100 open/closed doors
    There are 100 doors in a row, all doors are initially closed. A person walks through all doors multiple times and toggle (if open then close, if close then open) them in following way:

    In first walk, the person toggles every door.

    In second walk, the person toggles every second door, i.e., 2nd, 4th, 6th, 8th, …

    In third walk, the person toggles every third door, i.e. 3rd, 6th, 9th, …

    ……….

    In 100th walk, the person toggles 100th door.

    Which doors are open in the end?
    Перевод
    В ряду находятся 100 закрытых дверей. Человек, проходит через двери множество раз, меняя их состояние (если открыта — закрывает, если закрыта — открывает), следующим образом:
    За первый проход посещает каждую дверь.
    За второй проход — каждую вторую дверь (2-ю, 4-ю, 6-ю, ...).
    За третий проход — каждую третью дверь.
    …
    За сотый проход — сотую дверь.

    Какие двери в конце будут открытыми?
  2. Light bulbs and switches
    There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can’t change them. Identify each switch with its bulb.
    Перевод
    В комнате есть три лампы, дверь в комнату закрыта. Перед комнатой три выключателя, соединенные с лампами. Вы можете ставить выключатели в любое положение, но после того как откроете дверь — положение выключателей менять нельзя. Сопоставьте каждый выключатель с лампой.

    Подсказка
    (Прим. в задаче используется физика в т.ч.)

Задачи


  1. Power of 2
    Write a program to test if a number is power of 2 or not in one line code.
    Перевод
    Напишите программу-однострочник, которая будет проверять, является ли число степенью двойки.
  2. Find an element in a sorted and rotated array
    An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.
    Перевод
    В отсортированном массиве элемент можно найти за O(log n) времени, используя двоичный поиск. Предположим, что мы повернули массив в произвольной точке, которая Вам заранее неизвестна. Так, например, 1 2 3 4 5 может стать 3 4 5 1 2. Предложите способ поиска элемента в таком массиве за O(log n) времени.
  3. Find a Number X whose sum with its digits is equal to N
    Given a positive number N. We need to find number(s) such that sum of digits of those numbers to themselves is equal to N. If no such number is possible print -1.
    N <= 1000000000.

    Examples:
    Input: N = 21
    Output: X = 15
    Explanation: X + its digit sum
    = 15 + 1 + 5
    = 21

    Input: N = 5
    Output: -1

    Input: N = 100000001
    Output: X = 99999937
    X = 100000000
    Перевод
    Дано положительное целое число N. Нам необходимо найти такое число (числа), чтобы сумма самого числа и его цифр равнялась N. Если таких чисел нет — вывести -1.

    Примеры:

    Вход: N = 21
    Выход: X = 15
    Объяснение: X + сумма его цифр
    = 15 + 1 + 5
    = 21

    Вход: N = 5
    Выход: -1

    Вход: N = 100000001
    Выход: X = 99999937
    X = 100000000

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

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


  1. Rsa97
    10.02.2018 13:24
    #10661858
    +1

    Первая задача
    Дверь будет менять состояние, если её номер (D) нацело делится на номер прохода. Все такие номера проходов можно получить, если разложить номер двери на простые множители (p1...pk) и взять все различные их комбинации
    D = p1n1 ? p2n2 ?… ? pknk
    Количество различных комбинаций этих множителей даст количество проходов, на которых дверь сменит состояние. Его можно получить как
    N = (n1 + 1) ? (n2 + 1) ?… ? (nk + 1)
    Для того, чтобы дверь в конце осталась открытой она должна сменить своё состояние нечётное количество раз. Такое возможно только если все множители (ni + 1) будут нечётными, то есть все ni будут чётными.
    Но, раз все ni — чётные, то мы можем записать изначальное разложение как
    D = (p1n1/2)2 ? (p2n2/2)2 ?… ? (pknk/2)2 = (p1n1/2 ? p2n2/2 ?… ? pknk/2)2
    Таким образом, открытыми останутся только двери, чьи номера представляют собой квадраты целых чисел, то есть 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.


    1. zhussupov
      11.02.2018 10:44
      #10662714

      На самом деле дверь номер 8 тоже в итоге будет открыта, но она не является квадратом целого числа


      1. Rsa97
        11.02.2018 10:50
        #10662720

        Давайте посчитаем: проход 1 — открыта, 2 — закрыта, 4 — открыта, 8 — закрыта. Какие ещё проходы меняют состояние этой двери?


  1. IgnisDeus
    10.02.2018 13:24
    #10661860

    Power of 2
    public bool IsPowerOfTwo(int Number) { return ((Number & 1) == 0) ? IsPowerOfTwo(Number >> 1) : Number == 1; }


    1. IgnisDeus
      10.02.2018 13:37
      #10661868

      Find a Number X whose sum with its digits is equal to N
      Тут идет простой перебор, но перебор начинается с числа N-((порядок числа N)*9) и идет до N-1
              static int[] GetNumbers(int N)
        {
            List<int> res = new List<int>();
            int Order = 1;
            int tmp = N;
            while (tmp/10 != 0)
            {
                Order++;
                tmp /= 10;
            }
            int start = N - Order * 9;
            if (start < 0) start = 0;
            for (int i = start; i < N; i++)
            {
                if (i+ GetSumOfDigits(i) == N)
                {
                    res.Add(i);
                }
            }
            return res.ToArray();
        }
        static int GetSumOfDigits(int N)
        {
            int res = 0;
            while (N / 10 != 0)
            {
                res += N%10;
                N /= 10;
            }
            res += N;
            return res;
        }


    1. SeptiM
      11.02.2018 05:05
      #10662622

      Я думаю, что про power of 2 скорее было

      это.
      x > 0 && ((x — 1) & x) == 0


  1. ultrinfaern
    10.02.2018 13:24
    #10661862

    По первому вопросу: посещение двери равно её порядковому номеру.
    По второму вопросу: так как там лампы, можно попытаться определить по нагреву — горячая, теплая, бе нагрева — только причем тут программирование…
    По первой задаче: в одну строку можно посчитать количество бит в числе — если равно 1 то степень двойки.
    По второй задаче: глядя на первый и последний элементы возможно можно узнать точку поворота.


    1. Andy_U
      10.02.2018 17:08
      #10662060

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


      Однако, тоже за логарифмическое время (см. задачу за прошлую неделю). А потом второй проход по одному из двух подмассивов. Если сохранить значения из первого прохода, можно, наверное, немного сэкономить на втором.


      1. NoRegrets
        10.02.2018 19:35
        #10662206

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


    1. qw1
      10.02.2018 17:43
      #10662110

      По второму вопросу: так как там лампы, можно попытаться определить по нагреву — горячая, теплая, бе нагрева — только причем тут программирование…
      В этом случае, условие задачи не полное, т.к. не исключает вариант, что лампы висят на высоте 5 метров и нет никаких подручных средств, чтобы их достать.


      1. Rsa97
        10.02.2018 18:15
        #10662132
        +1

        А условие и так не полное. Сказано, что выключатели подключены к лампам, но не сказано, подключен ли каждый выключатель только к одной лампе, подключен ли к каждой лампе только один выключатель, подано ли питание к лампам через выключатели, можно ли закрыть дверь и снова переключить выключатели, и т.д, и т.п., и пр.


    1. LizardVojd
      11.02.2018 10:45
      #10662718

      По первому вопросу: посещение двери равно её порядковому номеру.

      Сколько раз посещали двери под номерами 3,5,7,11,13....?


  1. Rsa97
    10.02.2018 15:49
    #10661978
    +2

    Power of 2
    bool function isPowerOf2(int number) { return !(number & (number - 1)); }


    1. xi-tauw
      10.02.2018 20:11
      #10662246

      Чутка не хватает.
      Проверяем


      1. Rsa97
        10.02.2018 20:40
        #10662278

        Согласен, ноль не учёл. Хотя,… 0 = 2??


        1. Habra-Mikhail
          11.02.2018 12:04
          #10662758

          Отнюдь! У вас тут должен быть предел, т.к ? — не число.


  1. ads83
    10.02.2018 19:01
    #10662180
    +2

    IMHO, на задачу о лампочке лучше всего ответил (бы) Фейнман blogs.msdn.microsoft.com/ruericlippert/2011/02/28/983

    TL;DR

    И почему решение, к которому вы меня подталкиваете, основывается на недокументированных и ненадежных побочных явлениях? Неужели ваша команда пишет код, корректность которого основывается на недокументированных и ненадежных взаимосвязях, которые могут на порядок отличаться в зависимости от деталей реализации?


  1. xi-tauw
    10.02.2018 20:08
    #10662244

    Что-то сегодня простые задачи.

    Power of 2
    v && !(v & (v — 1))


  1. kardan2
    10.02.2018 20:39
    #10662276

    Заголовок спойлера
    1 вопрос. Открытыми будут только двери, чьи номера образуют квадрат, т.е. 1,4,9,16,25,...100
    2 вопрос. Баян, и вообще вопрос многими считается не корректным.
    1. Задача. Отнимаем от числа 1, и побитово умножаем с исходным числом.
    2. Задача. Опять повороты массивов. Смысл давать похожие задачи между 2-мя выпусками?
    Над последней задачей ещё думаю.


  1. IIvana
    11.02.2018 02:52
    #10662596

    Ради интереса - чуть менее тривиальное решение последней задачи
    f 0 a 0 = [a]
f 0 _ _ = []
f d a n | c >  9    = []
        | c == 0    = [c] >>= f'
        | otherwise = [c, c-1] >>= f' where
    d1 = d + 1
    c  = div n d1
    d' = div d 10
    f' v = f d' (v:a) (n-v*d1)

toi = foldr (\x a -> a*10 + x) 0

g n = map toi . f (10^(length $ show n)) [] $ n

main = do
    mapM (\x -> putStrLn $ show x ++ "   " ++ show (g x)) [10000000000000..10000000000010]


    1. reci Автор
      11.02.2018 13:13
      #10662822

      Что это за язык?


      1. IIvana
        11.02.2018 14:16
        #10662892

        Должно быть, Эльфийский


        1. IIvana
          11.02.2018 14:26
          #10662898

          Хотя не, вот кажется ключ к разгадке

          image


  1. Karpion
    11.02.2018 03:15
    #10662600

    del


  1. aslepov78
    11.02.2018 06:21
    #10662630

    Порция унижения. 1й вопрос — даже готовое решение с трудом понимаю. Это тест на мат эрудию? Или что, действительно вот так приходят и выкладывают решение в приятной беседе?


    1. ptyrss
      11.02.2018 10:44
      #10662716

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


  1. longclaps
    11.02.2018 11:07
    #10662732

    Find a Number X whose sum with its digits is equal to N

    def f(N):
    res = []
    for x in range(max(N - 9 * len(str(N)), 1), N):
        if x + sum(map(int, str(x))) == N:
            res.append(x)
    print(f'N = {N}, X : {res or [-1]}')


f(21)
f(5)
f(100000001)

    вывод
    N = 21, X : [15]
    N = 5, X : [-1]
    N = 100000001, X : [99999937, 100000000]


  1. IIvana
    11.02.2018 14:47
    #10662910

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


    на неземном волшебном
    f n = n==1 || r==0 && f q where (q,r) = quotRem n 2


  1. Deosis
    12.02.2018 07:52
    #10663768

    Не знаю, была ли подобная задача тут или нет.


    В комнате находится шахматная доска, на каждой клетке которой лежит по одной монете.
    Первый участник заходит в комнату и узнает "ключевую" клетку.
    Он может перевернуть не более одной любой монеты.
    Задача второго участника найти "ключевую" клетку.


    ПС

    Попытка передать информацию с помощью сдвига монеты к краю, поворота, царапин и т.п. недопустима.


    1. ptyrss
      12.02.2018 09:37
      #10663886

      Была. Даже статья отдельная на хабре была. habrahabr.ru/post/250585


  1. Nick_mentat
    12.02.2018 11:50
    #10664162

    прячу ответы
    1) остануться открытыми полные квадраты и 1. 1,4,16,64,9,81,25,36,49,100
    2) уже видел когда-то. Один выключатель нужно включить на время и выключить, чтобы найти соответствие по температуре.
    1. if (sumarray(char a[] = (string(binary(x)))) == 1) then println(«power of two!»)
    2. ищем пивот как в прошлонедельной задаче. Дальше переопределяем начало кольца этим пивотом. Всё, массив вернули в исходное состояние, для которого уже было готовое решение за такое время.
    3. Положим, на входе 7 значное число. Максимум, который могут дать цифры в сумме — это 6 девяток и первая цифра числа — 1. Отступим от числа на 6*9+первая_цифра-1, и переберём небольшое число вариантов. Количество проверяемых чисел — пропорционален логарифму от входного числа. Проверка суммы цифр так же пропорциональна длине чисел, так что всего получаем быстроту O((log(N))^2).


    1. Nick_mentat
      12.02.2018 12:45
      #10664282

      Дополнение про двери: интересно, что в задаче упомянуто, что двери стоят в ряд, а не в кольцо. В этом смысле задача напоминает задачу о заключённом, и мы должны следить за положением человека — каждый раз доходя до конца ряда он будет вынужден проходить его в противоположном направлении. То есть каждую дверь он открыл, затем, идя в обратную сторону, закрыл каждую вторую — и это все нечётные двери, а не чётные. Точно так же в последнюю ходку он меняет состояние 1 двери, а не последней. Открытыми останутся 1,2,3,4,8,9,16,18,25,29,32,36,49,50,51,64,69,72,81,83,93,98,99,100.
      Глядя на этот ряд у меня возникает два вопроса: существует ли аналитический способ получить его? И почему он всё ещё содержит весь правильный ряд, как если бы мы делали прогоны в одну сторону? Если поменять количество дверей (я пробовал 101, чётные, нечйтные, полные квадраты и простые) то можно избавится от последней сотни, но на дальней перспективе, уже к 81, все меньшие полные квадраты сохраняются… Так странно… Очень не похоже на совпадение.


  1. kimisa
    13.02.2018 09:50
    #10665994

    Я наверное в своей прошлой работе перерешала задач, что сейчас уже не хочу решать ничего из этого. Тем более на работе с такими задачами каждый день процентов 90 находящихся здесь не сталкиваются.
    Но решить задачу это не показатель. На их решения обычно натаскивают. Не тривиальных задач довольно мало. Остальные решаются по известным алгоритмам. Поэтому основная проблема — отнести задачу к соответствующему типу задач.
    P.S. Утверждаю это как бывший преподаватель высшей математики, готовила и к олимпиадным задачам и к ЕГЭ.