27.02.2018 05:27
reci 38 5000 Источник
Мы подобрали новую порцию вопросов и задач, встречающихся соискателям на собеседованиях в ведущие ИТ-компании мира.

КДПВ

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

Вопросы


  1. Black and white balls
    You have 20 white and 13 black balls in a bag. You pull out 2 balls one after another. If the balls are of same color, then you replace them with a white ball – but if they are of different color, you replace them with a black ball. Once you take out the balls, you do not put them back in the bag – so the balls keep reducing. What would be the color of the last ball remaining in the bag?

    Перевод
    У Вас в мешке 20 белых и 13 черных шаров. Вы последовательно вытягиваете по 2 шара. Если они одного цвета — тогда вы заменяете их белым шаром, если же они разных цветов — вы заменяете их черным шаром. Шары в мешок не возвращаются, поэтому их количество там убывает. Каким будет цвет последнего оставшего в мешке шара?

  2. Count the eggs
    The man who delivers eggs to my home everyday, did not turn up one day. So when he came the next morning I demanded an explanation from him. He told me the following story:
    The previous morning when he just came out of the house carrying a basket full of eggs on his head to start his daily rounds and stepped on to the street, a car going full speed brushed against him and knocked down his basket destroying all the eggs. The driver, however, a thorough gentleman admitted his responsibility and offered to compensate him for damages. But peddler could not remember the exact number of eggs he had, but he estimated the number at between 50 and 100. He was also able to tell the gentleman that if the eggs were counted by 2’s and 3’s at a time, none would be left, but if counted by 5’s at a time, 3 would remain, and that he sold the eggs at 10 cent a piece. The gentleman made some quick calculations and paid peddler adequately.
    How much did the gentleman pay for eggs?

    Перевод
    Однажды разносчик, который приносит ежедневно мне свежие яйца, не пришёл. Он появился на следующий день и я попросил его объяснить причину отсутствия. Он рассказал следующую историю:
    Накануне утром он вышел из дома с корзиной, полной яиц, чтобы сделать ежедневный обход улицы. Рядом с ним промчалась на полной скорости машина и задела корзину, так, что все яйца разбились. Водитель, однако, оказался джентельменом и предложил оплатить ущерб. Разносчик не мог вспомнить точное количество яиц в корзине, только то, что их было от 50 до 100. Он также припомнил, что если выбрать по 2 или по 3 яйца, то яиц в корзине бы не осталось, а если по 5, то должно было остаться 3 яйца. Он продавал яйца по 10 центов за штуку. Автомобилист быстро посчитал в уме и отдал разносчику точную сумму за разбитые яйца. Сколько он заплатил?


Задачи


  1. Find median in row wise sorted matrix
    We are given a row wise sorted matrix of size r*c, we need to find the median of the matrix given. It is assumed that r*c is always odd.

    Examples:

    Input:
    1 3 5
    2 6 9
    3 6 9
    Output: Median is 5
    If we put all the values in a sorted array A[] = 1 2 3 3 5 6 6 9 9

    Input:
    1 3 4
    2 5 6
    7 8 9
    Output: Median is 5

    Перевод
    Дана матрица с элементами, отсортированными построчно, размера r*c. Нам необходимо найти медиану матрицы. Предполагается, что r*c всегда нечётное.
    Примеры

    Вход:
    1 3 5
    2 6 9
    3 6 9
    Выход: Медиана — 5
    В виде отсортированного массива: A[] = 1 2 3 3 5 6 6 9 9

    Input:
    1 3 4
    2 5 6
    7 8 9
    Output: Медиана — 5

  2. Smallest single digit expression
    Given a number N and a digit D, we have to form an expression or equation that contains only D and that expression evaluates to N. Allowed operators in expression are +, -, *, and /. Find the minimum length expression that satisfy the condition above and D can only appear in the expression at most 10(limit) times.

    Examples:

    Input: N = 7, D = 3
    Output: 3/3+ 3 + 3
    Explanation: 3/3 = 1, and 1+3+3 = 7
    This is the minimum expression.

    Input: N = 7, D = 4
    Output: (4+4+4)/4 + 4
    Explanation: (4+4+4) = 12, and 12/4 = 3 and 3+4 = 7
    Also this is the minimum expression. Although
    you may find another expression but that
    expression can have only five 4's

    Input: N = 200, D = 9
    Output: Expression not found!
    Explanation: Not possible within 10 digits.

    Перевод
    Дано число N и цифра D. Небходимо составить выражение, дающее в результате N и содержащее только D. Допустимы операции +, -, *, /. Необходимо найти выражение минимальной длины, удовлетворяющее условия, с учётом того, что D может встречаться в выражении не более 10 раз.

    Ввод: N = 7, D = 3
    Вывод: 3/3+ 3 + 3
    Объяснение: 3/3 = 1, and 1+3+3 = 7

    Ввод: N = 7, D = 4
    Вывод: (4+4+4)/4 + 4
    Объяснение: (4+4+4) = 12, and 12/4 = 3 and 3+4 = 7

    Ввод: N = 200, D = 9
    Вывод: Expression not found!
    Объяснение: Невозможно выполнить с ограничением в 10 цифр.

    Прим.: третий пример выглядит как вызов

  3. Minimum swaps to bring them all together
    Given an array of n positive integers and a number k. Find the minimum number of swaps required to bring all the numbers less than or equal to k together.

    Input: arr[] = {2, 1, 5, 6, 3}, k = 3
    Output: 1

    Explanation:
    To bring elements 2, 1, 3 together, swap element '5' with '3' such that final array will be:
    arr[] = {2, 1, 3, 6, 5}

    Input: arr[] = {2, 7, 9, 5, 8, 7, 4}, k = 5
    Output: 2

    Перевод
    Дан массив n целых положительных чисел и число k. Найти количество перестановок, необходимое, чтобы собрать все элементны, меньшие или равные k, рядом.

    Вход: arr[] = {2, 1, 5, 6, 3}, k = 3
    Выход: 1

    Объяснение:
    Достаточно поменять 5 и 3 местами:
    arr[] = {2, 1, 3, 6, 5}

    Вход: arr[] = {2, 7, 9, 5, 8, 7, 4}, k = 5
    Выход: 2


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

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


  1. niklisto
    27.02.2018 08:56
    #10688106

    Вопрос 1 не совсем понятен. Заменяются пары на 1 шар. Этот один шар откуда? Из мешка тоже? Или отдельно?

    Вопрос 2 - простым показался
    78 яиц = $7.80


    1. reci Автор
      27.02.2018 10:44
      #10688238

      Да, шар на замену достаётся из мешка, потом пара добирается оттуда же.


      1. sena
        27.02.2018 11:36
        #10688322

        А если только чёрные шары остались, то чем заменять?


        1. phs233
          27.02.2018 11:40
          #10688334

          2 черных меняются на 1 белый.


          1. sena
            27.02.2018 12:23
            #10688404

            Откуда брать белый, если остались только чёрные?


      1. ozvenya
        27.02.2018 15:10
        #10688750

        А разве, не наоборот — 2 достаются, шар-замена кладется обратно в мешок?


        1. sena
          28.02.2018 17:39
          #10690500

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


          1. ozvenya
            01.03.2018 15:09
            #10691386

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

            Once you take out the balls, you do not put them back in the bag


    1. se-chemodanov
      27.02.2018 11:50
      #10688346

      Вопрос 2 еще вариант
      18


      1. phs233
        27.02.2018 11:52
        #10688352

        в условиях от 50 до 100


        1. se-chemodanov
          27.02.2018 11:55
          #10688358

          Точно, упустил этот нюанс.


    1. ThisMan
      27.02.2018 12:53
      #10688476

      Решается в один цикл


      Код на js
      let result;

for(let i = 50; i <= 100; i++) {
    if(
        (i % 2 === 0) &&
        (i % 3 === 0) &&
        (i % 5 === 3)
    ) {
        result = i
    }
}

console.log(result)


  1. vesper-bot
    27.02.2018 09:16
    #10688126

    > Input: N = 200, D = 9

    Ответ
    (999-99)/9*(9+9)/9


    1. phs233
      27.02.2018 11:00
      #10688270

      > Input: N = 200, D = 9

      увы 999 и 99 не 9


      1. alexluk86
        27.02.2018 12:22
        #10688396

        Так ведь сказано, что нужно использовать цифру 9, а не число 9. В числе 99, используется только цифра 9, и ни какая другая, так что заданным условиям удовлетворяет. Но, возможно, придется объяснять интервьюеру разницу в понятиях.


    1. brain_tyrin
      27.02.2018 12:22
      #10688400
      +1

      > Input: N = 200, D = 9

      Ответ
      ((9 + (9 / 9)) + (9 + (9 / 9))) * ((9 / 9) + (9 / 9))


      1. vesper-bot
        27.02.2018 13:03
        #10688494

        Левый плюс на первом уровне вложенности надо поменять на «умножить», иначе получится (10+10)*2 = 40. Равно как и правую часть на (9+9)/9 (экономим одну девятку), иначе «минимальное» выражение не получается.

        Респект :)


        1. brain_tyrin
          27.02.2018 14:18
          #10688636

          Да, конечно, опечатался :)


    1. vesper-bot
      27.02.2018 13:06
      #10688504

      Хм, кстати, не минимальное получается. (99+9/9)*(9+9)/9 использует меньше девяток.


  1. nasl
    27.02.2018 12:22
    #10688402
    +2

    Input: N = 200, D = 9: (9*9+9+9+9/9)*(9+9)/9


  1. ThisMan
    27.02.2018 13:54
    #10688602

    Если я правильно понял задание с массивом, то нам нужно просто посчитать индексы значений, которые меньше k, получим массив (пример) [0, 1, 3, 4], а потом пройдем циклом по элементам и если следующий индекс больше предыдущего на 2 и больше, значит нужна перестановка.


    Код на js
    const array = [2, 7, 9, 5, 8, 7, 4]
const k = 5

const groupNearK = function (arr, k) {
    const length = arr.length
    const idx = []
    let moveCount = 0

    for(let i = 0; i < length; i++) {
        if(arr[i] <= k) idx.push(i)
    }

    for(let i = 1; i < idx.length; i++) {
        if((idx[i] - idx[i - 1]) > 1) moveCount++
    }

    return moveCount
}

console.log(groupNearK(array, k))


    1. Phaker
      27.02.2018 14:07
      #10688624

      Одной перестановкой на каждый пропуск не отделаешься, за ней целый паровоз перестановок поползёт. Надо просто сначала посчитать количество "хороших" значений <= k, а потом пройтись окном размера k по всему массиву, считая количество попаданий "плохих" значений в каждое окно. Минимум и будет ответом — это значит, что в данном окне нужно перестановками заменить "плохие" значения "хорошими" снаружи окна.


      1. phs233
        27.02.2018 16:01
        #10688892

        Ну да, лучше такого алгоритма придумать не смог.

        Код на java
        private int GetTranspositions(int[] array, int k)
  {
	int count = 0;
	for (int i = 0; i < array.length; i++)
	{
	  if (array[i] <= k)
	  {
		count++;
	  }
	}
	int result = array.length;
	for (int i = 0; i<= array.length - count; i++)
	{
	  int iteration = 0;
	  for (int j = 0; j<= count; j++)
	  {
		if (array[i+j] > k)
		{
		  iteration++;
		}
	  }
	  if (iteration < result)
	  {
		result = iteration;
	  }
	}
	return result;
  }


        1. Phaker
          28.02.2018 15:23
          #10690346

          Только пробегать заново по каждому окну не эффективно. Достаточно просто при сдвиге окна делать +1/0/-1 к текущему каунту в зависимости от того, добавилось ли новое "хорошее" значение к окну справа или, наоборот, ушло из окна слева. Ниже уже и реализацию соответствующую привели.


  1. iBojarin
    27.02.2018 14:03
    #10688622

    3-вопрос
    (9+9+9/9+9/9+9/9+9/9)*9+9/9+9/9


  1. Nick_mentat
    27.02.2018 15:12
    #10688754

    Шары
    Белый шар останется. Есть комбинации где извлекая пары чёрных можно потратить все белые, но тогда не может остаться одного шара (всегда минимум 2 чёрных останется, а надо ответить про цвет последнего шара). Вывод — чёрные необходимо исчерпать раньше белых, чтобы была возможность оставить только один шар. Соответственно, шар будет белым.


    1. vesper-bot
      27.02.2018 17:16
      #10689018

      Шары

      А ничего, что в начале есть 13 черных, а извлечь их можно только попарно?


      1. Nick_mentat
        27.02.2018 18:47
        #10689178

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


        1. vesper-bot
          28.02.2018 09:21
          #10689808

          Читаем внимательно.


          but if they are of different color, you replace them with a black ball

          Ушли черный и белый — пришел черный, т.е. в сухом остатке ушел белый.


          1. Nick_mentat
            01.03.2018 11:37
            #10691044

            А… Я подумал что их заменяют не в коробке, а в руке. Мол, взяли два, а потом положили назад в коробку и взяли оттуда чёрный или белый, в зависимости от комбинации.


  1. utor
    27.02.2018 20:25
    #10689310

    200
    поскольку () в допустимых операциях нет:
    99+99+9/9+9/9


    1. vesper-bot
      28.02.2018 09:23
      #10689812

      С учетом наличия в ответах (4+4+4)/4, скобки разрешены.


  1. Rsa97
    27.02.2018 20:25
    #10689312

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


  1. kardan2
    27.02.2018 20:25
    #10689314
    +1

    Задачи понравились.
    Мои решения:

    1 Вопрос
    При всех вариантах сохраняется четность черных шаров. Значит, черных шаров не может из 13 стать 0. Последним будет черный шар.


    1. kardan2
      28.02.2018 19:28
      #10690576

      Решение задачи 1. Пока без кода
      Можно отсортировать весь массив и взять центральный элемент. Это означает r*c*Log(r*c).
      Можно постараться найти решение за r*c. Но r*c — это предел для данных без структуры. У нас же есть порядок по строкам, поэтому можно искать решения вида r*Log( c), или что-то типа того.
      Если коротко, как в бинарном поиске храним верхнюю и нижнюю границы по значению. Кроме того, храним правую и левую границы для каждой строки. Каждый раз берем медиану по каждой строке (с учетом границ), находим среди этих медиан новую медиану и пробуем её, как искомое значение. Находим для каждой строчки положение этого значения бинарным поиском (с учетом границ). Для левой границы ищем положение значения меньше или равно, а для правой больше или равно. Если сумма по каждой строке больше половины всех элементов массива с обоих сторон, значит значение и есть искомое. Если нет, то в каждой строке передвигаем границу.
      Нам нужно, чтобы за каждую итерацию отсеивать некий процент (у меня он =25%) оставшихся элементов. Поэтому медиану медиан нужно искать с учётом весов, где вес медианы равен кол-ву оставшихся значений в строке.
      Т.е. пусть у нас остались следующие строки (16) (11, 15, 20) (17, 21,33,48,50,77,78) и соотвественно медианы 16, 15, 48 с весами 1-3-7. Если мы возмем просто медиану медиан, т.е. число 16, то отсеем малое значение элементов, т.к. оно произойдет в строках с малым количеством. Это нам не нужно. с другой стороны 3+1+7=11, и медиана приходится на значение 7, т.е. медиану, которая равна 48.
      Поиск такой медианы можно делать через сортировку медиан с последующим проходом.
      Сложность поиска такой медианы с весом равна r*Log( r). Внутри строк нужен бинарный поиск, и так как зона бинарного поиска сокращается на 25%, то Log( c)+Log(0.75*c)+Log(0.75*0.75*c)+… = O(Log( c)*Log( c)), как сумма арифметической прогрессии.
      Итого, сложность всего алгоритма это O(r*Log( r)*Log( c)^2)


  1. lenon
    27.02.2018 20:25
    #10689316

    #3 — вроде как, тоже простой (решение за O(n)):
    counter = 0

    for i =0; i < array.size; i++
    if array[i] <= k


    1. lenon
      27.02.2018 20:50
      #10689390

      Удалите мои комментарии, пожалуйста. Я случайно Enter, не дописав нажал.


      1. reci Автор
        27.02.2018 21:07
        #10689408

        Увы, это не так просто. Только редактировать и писать новые :)