01.05.2018 07:03
reci 24 5300 Источник
Продолжаем публиковать интересные задачи и вопросы с собеседований в различные IT-компании мира.

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

Вопросы


  1. Counterfeit сoins
    A box contains n coins, of which 7 of them are counterfeit with tails on both sides and the rest are fair coins. If one coin is selected from the bag and tossed, the probability of getting a tail is 17/20. Find the value of ‘n’.

    Перевод
    В коробке n монет, 7 из которых поддельные — с решкой на обеих сторонах, а остальные монеты — правильные. Если выбрать и подбросить монету из коробки — шанс выпадения решки 17/20. Найдите n.

  2. The largest unavailable number
    At McDonald’s you can order Chicken McNuggets in boxes of 6,9, and 20. What is the largest number of nuggets that you cannot order using any combination of the above?

    Перевод
    В Макдональдс Вы можете заказать куриные наггетсы в коробке на 6, 9 и 20 шт. Каким является максимальное число наггетсов, которое нельзя заказать любыми комбинациями этих коробок,
    Прим. Нет, рекламу нам не оплачивали :)


Задачи


  1. Find all combinations
    Given a set of characters and a positive integer k, print all possible strings of length from 1 to k that can be formed from the given set.

    Examples:

    Input:
    set[] = {'a', 'b'}, k = 3

    Output:
    a
    b
    aa
    ab
    ba
    bb
    aaa
    aab
    aba
    abb
    baa
    bab
    bba
    bbb

    Input:
    set[] = {'a', 'b', 'c', 'd'}, k = 1
    Output:
    a
    b
    c
    d

    Перевод
    Дан набор символов и положительное число k. Выведите все возможные строковые комбинации длиной от 1 до k, которые можно получить из этого набора.

    Примеры:

    Вход:
    set[] = {'a', 'b'}, k = 3

    Выход:
    a
    b
    aa
    ab
    ba
    bb
    aaa
    aab
    aba
    abb
    baa
    bab
    bba
    bbb

    Вход:
    set[] = {'a', 'b', 'c', 'd'}, k = 1
    Выход:
    a
    b
    c
    d

  2. Delete a node in a single-linked list
    Given a pointer to a node to be deleted in a singly linked list, delete the node. Note that we don’t have pointer to head node. Write a program to accomplish the task, pseudocode is accepted.

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

  3. Comment remover
    Write a program to remove comments from given C/C++ code.

    Перевод
    Напишите программу, удаляющую комментарии из С/C++ кода.

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

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


  1. qw1
    01.05.2018 11:39
    #10784330
    +2

    Ответ к задаче про McDonalds
    Сначала определим, существует ли такое число.
    Понятно, что если мы найдём 6 подряд идущих чисел, которые можно заказать: N0=N, N1=N+1, N2=N+2,..., N5=N+5, то любое следующее за ними M можно представить как M=Ni+6*k. То есть добавив к заказу Ni k коробок по 6, получим заказ M.

    Также понятно, что начиная с 6, можно заказать любое число, кратное трём (N=6x+9y=3(2x+3y), можно найти x,y чтобы получить любое число 2x+3y>1)

    Дальше я нарисовал таблицу 9x9, аналогичную таблице умножения, и расположил в ней числа от 0 до 99. Буду зачёркивать числа, которые можно заказать. Сразу зачеркнул все числа, кратные 3 и число 0. Делаем что-то типа решета Эратосфена. Идём подряд по всем зачёркнутым, начиная от 0, и зачёркиваем все числа, через 6, 9 и 20, начиная от зачёркнутого. В итоге у меня появился зачёркнутый ряд из 6 чисел 44-49, и незачёркнутое число 43 перед ним, что и является ответом.


    1. qw1
      01.05.2018 22:23
      #10784810

      Таблицу 10x10*


    1. Deosis
      03.05.2018 08:26
      #10786254
      +1

      Также понятно, что начиная с 6, можно заказать любое число, кратное трём (N=6x+9y=3(2x+3y), можно найти x,y чтобы получить любое число 2x+3y>1)

      Тогда, начиная с 26, можно заказать число, равное 0 или 2 по модулю 3.
      С 46 можно заказать любое число.
      Поэтому 43 — наибольшее число.


      ПС. Попробуйте решить задачу для чисел 165, 210, 231, 315.


      1. qw1
        03.05.2018 21:06
        #10787790

        Чертовски сильная мысль, никогда бы не подумал в таком ключе, что 20 mod 3 = 1, поэтому, добавляя 20, можно сдвигать остатки от деления на 3 на единицу.

        ПС. Попробуйте решить задачу для чисел 165, 210, 231, 315.

        165 = 3·5·11
        210 = 2·3·5·7
        231 = 3·7·11
        315 = 3·3·5·7
        Комбинируя только числа 165 и 231, я могу получить
        N = 165·x+231·y = 33·(5x+7y), т.е., начиная с 33·24 можно получить все числа, кратные 33.
        Если бы вместо 33 было 11 (т.к. 210 mod 11 = 1), то, добавляя 210·z можно получить любое число, начиная с 23·24+11·210. Но увы, 210 mod 33 = 12, добавляя 12, я не получу все остатки от деления на 33 (33 — не простое число).
        Как тут поможет ещё одно не использованное число 315, у меня нет идей.


      1. qw1
        03.05.2018 21:13
        #10787806

        ПС. Попробуйте решить задачу для чисел 165, 210, 231, 315.
        Тут нет решения. Все числа делятся на 3. Значит, любое 3x+1 нельзя заказать :D


    1. blindmen
      03.05.2018 15:00
      #10787112

      а разве правильный ответ не «все имеющиеся нагетсы + 1 любая коробка»?


      1. qw1
        03.05.2018 20:30
        #10787758

        Неправильный ответ, т.к. надо выбрать наибольшее, а решение «все имеющиеся нагетсы + 2 любых коробки» заведомо больше вашего )))


  1. qw1
    01.05.2018 11:45
    #10784334

    Задача на удаление ноды простая, но не всегда имеет решение.
    В случае, когда список состоит из 1 ноды, её удаление должно обнулить указатель Head, а его, по условями задачи, у нас нет.


  1. Andy_U
    01.05.2018 12:04
    #10784348

    Вопрос N1 — 10.

    Без комментариев…

    Вопрос N2 — 43:

    44 = 1*20+4*6
    45 = 5*9
    46 = 2*20+1*6
    47 = 1*20+3*9
    48 = 8*6
    49 = 2*20+1*9

    Дальше — по кругу с шагом 6:

    50=44+6
    51=45+6
    …

    Задача N2:

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


    1. speciman
      01.05.2018 21:59
      #10784782

      Правим ссылку?
      Это нужно ?


      1. Andy_U
        02.05.2018 02:42
        #10784898

        О! Нет, конечно. Спасибо за уточнение.


    1. mickvav
      02.05.2018 11:16
      #10785124

      Но вылезание задачи про односвязный список в продакшене вызовет серьезные вопросы к архитектуре…


  1. Andy_U
    01.05.2018 13:03
    #10784384

    Задача N 3:

    # -*- coding: utf-8 -*-

import itertools


if __name__ == '__main__':

    k = 3
    symbols = 'ab'
    
    for i in range(1, k+1):
        for j in itertools.product(symbols, repeat=i):
            print(''.join(j))


  1. Koneru
    01.05.2018 17:45
    #10784614

    Ну что проверит 3 задача…

    2 строки кода
    Умение написать примитивную регулярку?

    var fileContent = fs.readFileSync("hello.cpp", "utf8");
fileContent.replace(/\/\*.*\*\/|\/\/.*\n/g,"");


    1. RiaD
      01.05.2018 18:41
      #10784676

      string path = "//path";


      1. Koneru
        01.05.2018 20:13
        #10784736

        Ваша правда, ну буду модифицировать регулярку(уже дело принципа)).


        1. qw1
          01.05.2018 22:02
          #10784786
          +1

          да там ещё и другие проблемы:
          1) жадная звёздочка \/\/.*\n скушает всё от первого коммента // до конца файла.
          2) жадная звёздочка \/\*.*\*\/ скушает всё между первым и последним комментом:

          int /* hello */ test = 1; /* world */
          после замены останется: int

          3) Нужно учесть смешивание стилей комментирования:
          // /*
int x;
// */

          Ваш regex зачистит всё.


          1. qw1
            01.05.2018 22:18
            #10784806

            Ну и, такая замена fileContent.replace(/\/\/.*?\n/g,"");
            из 

            #include <stdio.h> // hello
#include <stdlib.h> // world

            сделает некорректный код 
            #include <stdio.h> #include <stdlib.h>


            1. Koneru
              02.05.2018 16:59
              #10785448

              Кармы не хватает, но +


  1. IIvana
    02.05.2018 03:30
    #10784910

    Вопрос 1 — n=10. Решал по-честному, с уравнением (14+k)/(14+2k) = 17/20


    Задача 1 как всегда решается в одну строчку на неземном и волшебном


    f l k = concat . take k . tail . iterate (liftM2 (:) l) $ [[]]

main = print $ [f "ab" 3, f "abcd" 1]

[["a","b","aa","ab","ba","bb","aaa","aab","aba","abb","baa","bab","bba","bbb"],["a","b","c","d"]]


  1. naething
    02.05.2018 07:46
    #10784996

    Про наггетсы было на Numberphile: www.youtube.com/watch?v=vNTSugyS038


  1. SkyL1ne
    02.05.2018 09:51
    #10785048

    Наггетсы: что не так с числом 37?


    1. Andy_U
      02.05.2018 13:03
      #10785246

      Все так, его тоже нельзя «набрать» указанными числами, но оно не максимальное. 43 больше.


    1. johnklymenko
      02.05.2018 13:35
      #10785272

      Нужно наибольшее число.