11.05.2017 16:18
SpiceIT 28 2800 Источник
Многие наслышаны о каверзных вопросах и задачах, которые дают на собеседованиях в Google, Microsoft, Apple, Intel, IBM, Amazon, SpaceX, Yahoo, Facebook, etc., а также российских Яндекс и Mail.ru. Они нацелены на оценку технических навыков или проверку университетских знаний, логики, мышления.

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

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

На этой неделе мы публикуем 5 интересных задач, которые недавно предлагал решить разработчикам Google.

1. Создайте случайное 4-значное четное число. Две смежные цифры должны быть разными. 

public int getNumber(){ 
}

2. Для введенного слова найдите следующее в лексикографическом порядке из представленных в массиве.

Пример:

Список слов:
[Cat, dog, cow, donkey, zebra, monkey],
input
duck
output
monkey

Input
dog
output
donkey

Можете ли вы использовать для решения дерево? 

public String findNextWord(List<String> words, String input){ 
}

3. Учитывая массив целых чисел, распечатайте все числа, удовлетворяющие следующему требованию:

когда число больше каждого числа слева и меньше каждого числа справа.

4. Для строковой химической формулы типа «C6H2 (NO2) 3CH3» выведите карту с ключом в качестве элемента и значением в качестве его числа. Элемент может иметь два символа, например Fe2(SO4)3 

public HashMap<Character, Integer> getCount(String chemicals){ 
}

5. В школе студент получает вознаграждение, если имеет не более 1 пропуска и 3 опозданий. Учитывая запись посещаемости студента, представленную строкой с тремя возможными символами «L» («Опоздал»), «A» (Отсутствовал), «O» («Пришел вовремя»).

Проверьте, имеет ли студент право на вознаграждение. Пример:

@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False

Студент не может претендовать на вознаграждение, потому что «LLA» означает, что он опоздал 3 раза подряд.

@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True

Дополнительно:

Если известно, что длина строки посещаемости — n, сколько есть способов посещения с получением вознаграждения.

NB

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

1. Generate a random 4-digit even number: the adjacent 2 digits must be different. 
public int getNumber(){ 
}

2. Find the Lexicographic next word of the input word from a list of words
Example
Words list
[Cat, dog, cow, donkey, zebra, monkey],
input
duck
output
monkey

Input
dog
output
donkey
Can you use trie to solve it? 

public String findNextWord(List<String> words, String input){ 
}

3. Given an array of integers, print all the numbers that meet the following requirement — when the number is greater than every number on its left and smaller than every number on the right.

4. For a string chemical formula like “C6H2(NO2)3CH3”, and output a map with key as element and value as its count.

element can have two chars, for example Fe2(SO4)3 

public HashMap<Character, Integer> getCount(String chemicals){ 
}

5. In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),
check whether the student qualifies for the reward.

e.g. 
@INPUT (String) "OLLAOOOLLO" 
@RETURN (Boolean) False

The student does not qualify for reward because «LLA» means he was late for 3 times in a row. 

@INPUT (String) "OLLOAOLLO" 
@RETURN (Boolean) True

Follow-up:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.
Поделиться с друзьями
-->

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


  1. xandox
    12.05.2017 00:28
    #10212544

    Я не силён в химии. Что значит 3 после скобок? Должно ли это число помножатся на числа при элементах в скобках?
    И в задачи с прогулами. Из примеров следует, что опоздания играют роль только если три подряд. В условии этого не сказано.


    1. alexeykuzmin0
      12.05.2017 13:38
      #10213312

      Да, должно умножаться


  1. cranium256
    12.05.2017 00:40
    #10212548
    +3

    Странные задачи. Если вы ничего не перепутали, то от Гугла такого не ожидал.

    1. Некорректная постановка задачи. Тупо return 1352; формально удовлетворяет условию задачи.

    2. Примитивное решение: отсортировать массив и простейший поиск. Можно и деревом, но возни больше. Вообще оптимальный алгоритм зависит от размера массива. Для десятка элементов — любая сортировка из библиотеки и линейный поиск.

    3. Решение в один цикл и один условный оператор. Даже не интересно.

    И что значит «Учитывая массив целых чисел,»? Погрешности гуглопереводчика?

    4. Единственная задача, требующая некоторых размышлений.

    5. Банальное сканирование строки с подсчётом вхождения символов. И возврат значения логического выражения. Однако смущают примеры и комментарий.

    Из первого примера следует, что студент не получает конфетку, поскольку опоздал больше 3 раз. В комментарии же написано: «потому что «LLA» означает, что он опоздал 3 раза подряд». Отсутствие == опоздание?? И где в условии сказано, что нельзя опаздывать 3 раза подряд?

    Во втором примере тоже должно быть False, поскольку студент опаздывал более 3 раз.

    Подозреваю, что условие задачи дано (или переведено с английского?) некорректно.

    Пункт «дополнительно» n*(n-1)*(n-2)*(n-3), если следовать условию задачи из первого абзаца.


    1. Aivean
      12.05.2017 07:53
      #10212682

      2. Отсортировать и простейший бинарный поиск. А для большого количества длинных слов оптимально использовать Trie.

      3. Неверно. Решение в два прохода и O(N) дополнительной памяти.

      4. Если честно, я не понял условие. Объясните?
      Если требуется посчитать количество атомов каждого элемента в формуле, то как, например, «Fe» влезет в ключ типа `Character`?

      5. Из контекста очевидно, что «прогул» также считается «опозданием», и что учитываются только три опоздания подряд.
      Интерес представляет дополнительная часть при таком условии. Может быть, можно придумать аналитическую формулу, но я бы решал ее динамикой.


      1. cranium256
        12.05.2017 16:52
        #10213810

        2. До 10 элементов, скорее всего, можно не заморачиваться с бинарным поиском.

        3. Откуда два прохода и дополнительная память?

        for (size_t i = 1; i < ARR_LENGTH; ++i) {
    if (arr[i] > arr[i-1] && arr[i] < arr[i+1])
        std::cout << arr[i] << ' ';
    }


        Ну ещё добавить проверку, что длина массива больше 3. И вроде как всё. Или я что-то упустил?

        5. Из контекста русского перевода как раз вообще ничего такого не следует. А вот в английском варианте, который сейчас добавили, написано: «being absent for more than once or being late for 3 times continuously». Здесь уже примеры выглядят логично: они поясняют, что подряд два опоздания и прогул тоже не допускаются. При переводе пропустили всего одно слово, и смысл задачи полностью изменился.


        1. cranium256
          12.05.2017 16:56
          #10213824

          3. А ведь упустил. Слово «каждого». Прошу прощения.


      1. sverhnovaia
        12.05.2017 17:19
        #10213858

        Aivean Спасибо за исправления. При переводе допустили ошибку, заменив «trie» на «tree», что несколько меняет смысл.
        По поводу задачи 4: возможно, оригинал условия поможет вам, мы добавили его в статью.


      1. nickolaym
        12.05.2017 17:22
        #10213864

        Ниже я показал, как можно обойтись существующей памятью.

        Если очень-очень постараться, то можно и в один проход уложиться.
        Правда, потребуется второй проход уже чисто по найденной подпоследовательности, чтобы вывести её.
        Но если нам достаточно просто оставить в массиве только эту подпоследовательность, — то второй проход не потребуется.


    1. sverhnovaia
      12.05.2017 17:12
      #10213846

      cranium256 Спасибо за такой подробный комментарий.
      Задачи действительно от Google, их давали различным специалистам на собеседованиях, поэтому уровень сложности может отличаться.
      Возможно, наш перевод исказил суть, поэтому мы добавили оригинальный текст в теле статьи. Надеемся, что теперь задачи будут выглядеть немного интереснее, а условие станет понятнее :)!


  1. mbait
    12.05.2017 00:48
    #10212552

    1. Создайте случайное 4-значное четное число.
      public int getNumber() {}

    image


    1. sverhnovaia
      12.05.2017 17:45
      #10213932

      mbait Здорово, что даже ночью у вас есть желание решать задачки :)


  1. longclaps
    12.05.2017 07:50
    #10212680

    1, увы не однострочник:

    def getNumber():
    l = [randint(0, 4) * 2]
    for i in 0, 0, 1:
        d = randint(i, 8)
        l.append(d + (l[-1] <= d))
    return int(''.join(map(str, l[::-1])))


    1. sverhnovaia
      12.05.2017 17:48
      #10213942

      longclaps чем больше вариантов решений, тем интереснее :)


  1. ngalayko
    12.05.2017 08:16
    #10212696
    +1

    откуда вы это скопировали? условия половины задач некорректны / плохо переведены / непонятны, нет даже простейшей обертки кода в ```
    и ради чего тогда вообще статья? ссылки на недельный курс "войтивайти" под ответами через неделю?


    1. sverhnovaia
      12.05.2017 17:32
      #10213882

      ngalayko Задачи скопированы с ресурса https://careercup.com/, где их постят разработчики со всего мира :)
      Мы добавили оригиналы задач, т.к. перевод оказался частично неверным.
      Статья чисто ознакомительного характера, чтобы все могли увидеть, что предлагают решать на собеседованиях в крупных компаниях.


  1. alexeykuzmin0
    12.05.2017 13:42
    #10213328

    Почему-то ни одна из приведенных задач brain teaser'ом не является. Хоть бы посмотрели сначала определение термина, чтобы не позориться.


    1. sverhnovaia
      12.05.2017 17:37
      #10213902

      alexeykuzmin0 Да, вы правы, классическим brain teaser'ом ни одна из задач не является..)
      Заголовок рассчитан на рубрику в целом, но в этот раз это, скорее, технические задачи.


  1. nickolaym
    12.05.2017 16:43
    #10213782

    Задачки какие-то сомнительные.

    1. Если нам можно препроцессинг, то проще всего создать набор всех четырёхзначных чисел, удовлетворяющих критерию (всего-то их 7290 штук, можно хоть внешним генератором нарожать сишный или шарповый файл), а затем мгновенно выбирать из массива по случайному числу в диапазоне [0..7290).
    Если нам лень препроцессинг и плевать на равномерное распределение, то генерировать [0..10000) и брать ближайшее к случайному правильное число. Как в ЧГК ближе к концу игры.
    Если нам и это лень и много свободного времени, то тупо долбить случайные числа, пока не налетим на правильное.
    Если нам вообще адски не лень, то можем сочинить мега-формулу, отображающую [0..7290) на [0..10000)

    2. Два совершенно разных случая — однократная и пакетная обработка.
    Для однократного вызова «следующее(список, ключ)» никакие деревья нафиг не нужны. Бежим по списку и находим «минимум(фильтр(список, _ > ключ))».
    Для пакетного вызова «следующие(список, ключи)» нужно построить дерево. Желательно — префиксное дерево. Но опять же, баланс между количеством писанины и скоростью работы. Обычный упорядоченный std::set с функцией upper_bound из плюсов — бесплатное решение, а есть ли что-то хорошее в дотнете — тут я не знаю. Возможно, что именно провал в стандартных библиотеках дотнета и заставил людей придумать такую задачу.

    using namesace std; // чтобы не шуметь
vector<string> nexts(vector<string> words, vector<string> keys) {
  set<string> sorted_words(begin(words), end(words));
  vector<string> solutions; solutions.reserve(keys.size());
  for (const string& key : keys) {
    set<string>::const_iterator next = sorted_words.upper_bound(key);
    if (next != sorted_words.end())
      solutions.push_back(*next);
  }
  return solutions;
}


  1. nickolaym
    12.05.2017 17:19
    #10213860

    3. Больше всех слева и меньше всех справа — это больше максимума слева и меньше минимума справа.
    Дополнительный булев массив и ровно два забега.
    Либо права на запись в текущий массив и константная доп.память, и опять два забега

    int numbers[n];

const int BAD = numbers[0]-1;  // число, заведомо не могущее быть хорошим (ибо меньше левого максимума)

int treshold = numbers[n-1]+1;
for (int i=n-1; i>=0; --i) {
  if (numbers[i] < treshold)
    treshold = numbers[i];
  else
    numbers[i] = BAD;
}
treshold = numbers[0]-1;
for (int i=0; i<n; ++i) {
  if (numbers[i] == BAD) continue;
  if (numbers[i] > treshold) {
    output(numbres[i]);
    treshold = numbers[i];
  }
}


  1. nickolaym
    12.05.2017 17:26
    #10213870

    В четвёртой задаче надо получить брутто-формулу из структурной? Т.е. раскрыть скобки и свалить всё в кучу, да?
    Fe2(SO4)3 = Fe2S3O6?

    Простенький рекурсивный парсер. Много рутинной писанины.


    1. sverhnovaia
      12.05.2017 17:42
      #10213918

      nickolaym Спасибо большое за ваши ответы!
      Мы опубликуем варианты решений немного позже. Возможно, они помогут ответить на ваши вопросы.
      Или станут поводом для новых..))


  1. nickolaym
    12.05.2017 17:46
    #10213934

    5 — конечный автомат решает.
    Состояние — это пара (количество опозданий подряд, количество пропусков всего).

    (L,A), «O» -> (0,A) — посещение обнуляет счётчик опозданий
    (L,A), «L» -> (L+1,A) — опоздание увеличивает счётчик
    (L,A), «A» -> (L+1,A+1)
    состояния остановки — (3,A) и (L,2)

    5* — немножко марковских цепей и матричных вычислений надо.
    Всего у нас рабочих состояний — шесть штук. (0,0), (0,1), (1,0), (1,1), (2,0), (2,1).
    Вектор состояния S в момент t показывает, сколькими способами мы попали в то или иное состояние.
    Для момента 0, очевидно, он равен (1,0,0,0,0,0) — мы находимся в состоянии 00.
    Для момента t+1 вектор S' состоит из компонент:
    S'00 = S00, — ровно один способ, не накосячить в этот раз
    S'01 = S01 + S11 + S21 — надо придти во время, при условии, что уже однажды прогулял
    S'10 = S00 — опоздать
    S'11 = S01 — опоздать после старого прогула
    S'20 = S10 — опоздать второй раз подряд
    S'21 = S11 — опоздать второй раз подряд после старого прогула
    Получается матрица M.
    1 0 0 0 0 0
    0 1 0 1 0 1
    1 0 0 0 0 0
    0 1 0 0 0 0
    0 0 1 0 0 0
    0 0 0 1 0 0
    и вектор нового состояния — это умножение матрицы на вектор старого состояния S(t+1) = M*S(t)
    А финальный вектор — это, соответственно, S(n) = M^(n-1) * S(t)

    Ну и итоговый ответ — это надо просуммировать все компоненты S(n), т.е. умножить на вектор со всеми единицами E.
    total = E * M^(n-1) * S(0).

    Возведение матрицы в степень делается за логарифмическое время. Ну или, если это влом реализовывать, то за линейное безо всяких матриц.


  1. sverhnovaia
    18.05.2017 18:27
    #10224108

    Всем привет!
    Как и обещали, публикуем по одному варианту решения каждой задачи. Код взят с тех же ресурсов, что и задачи. Синтаксис сохранен, комментарии к решениям также оригинальные.

    Atention! Spoiler!

    1. Generate a random 4-digit even number: the adjacent 2 digits must be different.
    public int getNumber(){
    }

    Solution:
    It can boil down to getting the list of integers between 1000 and 9999 (including) that have adjacent digits as different.
    To do that we can apply memoization on the following function

    List(d, s)
    Lists = []

    if d = 1
    for i = 0 to 9 and i != s
    Lists.add(i)
    return Lists
    for i in 0 to 9 and i != s
    Lists.addAll(List(d-1, i))
    for i in 0 to Lists.length
    Lists[i] = (10 ^ d * s) + Lists[i]
    return Lists

    Call Lists(4, 1..9)
    Then its about figure out
    Lists[random() * (Lists.length — 1)]


    1. sverhnovaia
      18.05.2017 18:49
      #10224140

      2. Atention! Spoiler!

      Find the Lexicographic next word of the input word from a list of words
      Example
      Words list
      [Cat, dog, cow, donkey, zebra, monkey],
      input
      duck
      output
      monkey

      Input
      dog
      output
      donkey
      Can you use trie to solve it?

      public String findNextWord(List words, String input){
      }>

      Solution:

      public class FindNextLexogWord {


	public static void main(String[] args) {

		String[] wordList = {"Cat", "dog", "cow", "donkey", "zebra", "monkey"};
		String input = "duck";
		int nextLex = Integer.MIN_VALUE;
		int value = 0;
		String word = null;
		for( int i = 0 ; i < wordList.length ; i ++ ) {
			if(( value =  input.compareTo(wordList[i]))  <  0 ) {
				System.out.println(value);
				if( nextLex < value){ 
				nextLex = value;
				word = wordList[i];
				}
			}
		}


	}


  1. vak0
    18.05.2017 18:33
    #10224114

    Я вообще не программист и, возможно, вопрос глупый:
    2. Зачем вообще что-то сортировать, когда можно идти по списку и считать лексикографическое «расстояние» от введенного слова до текущего в просматриваемом массиве, сохраняя где-то текущий неотрицательный минимум? Функция расстояния, например, СУММА(Аi — Bi)*k^i, где i — позиция буквы в слове, Вi и Аi — буквы в введенном слове и текущем слове массива соответственно. k — константа, большая или равная длине алфавита.


  1. sverhnovaia
    18.05.2017 18:51
    #10224150

    3. Atention! Spoiler!

    Given an array of integers, print all the numbers that meet the following requirement — when the number is greater than every number on its left and smaller than every number on the right.

    Solution:

    void order(int * num, int size){
  int max = 0;

  stack<int> s;
  for(unsigned int i = 0; i < size; i++){
    if(num[i] > max){
      max = num[i];
      s.push(max);
    }
    while(!s.empty() && num[i] < s.top()){
      s.pop();
    }
  }

  while(!s.empty()){
    printf("%d ", s.top()) ;
    s.pop();
  }
  printf("\n");

}


int main(){
  int  a[] = {6, 5, 4, 3, 9, 100, 87, 64, 34, 101};
  int  b[] = {3, 4, 7, 1, 8, 12};
  order(a, 10) ;
  order(b, 6) ;

  return 0;
}


  1. sverhnovaia
    18.05.2017 18:53
    #10224158

    4. Atention! Spoiler!

    For a string chemical formula like “C6H2(NO2)3CH3”, and output a map with key as element and value as its count.
    element can have two chars, for example Fe2(SO4)3 

    public HashMap<Character, Integer> getCount(String chemicals){ 
}


    Solution:

     class Data{
	Map<Character,Integer> elems;
	int idx;
	int mult;
	
	Data(Map<Character,Integer> mp, int i, int m){
		elems = mp;
		idx = i;
		mult = m;
	}
}

public Map<Character,Integer> elemCounts(String str){

	Data d = elemHelp(str, 0);
	if(d.mult != 1){
		for(Map.Entry<Character,Integer> e: d.elems.entrySet()){
			e.getValue() *= d.mult;
		}
	
	}
	return d.elems;
}

private Data elemHelp(String str, int i){
	Map<Character,Integer> mp = new HashMap<Character,Integer>();
	int mult = 1;
	while(i< str.length()){
		if(str.charAt(i) >= 'A' && str.charAt(i) <= 'Z'){
			char elem = str.charAt(i);
			int ct = 1;
			if(i + 1 < str.length() && str.charAt(i + 1) >= '0' && str.charAt(i + 1) <= '9'){
				int j = i + 1;
				while(j < str.length() && str.charAt(j) >= '0' && str.charAt(j) <= '9'){
					j++;
				}
				ct = Integer.parseInt(str.substring(i + 1, j));
				i = j;
			}else{
				i++;
			}
			if(mp.containsKey(elem)){
				ct += mp.get(elem);
			}
			mp.put(elem,ct);
		}else if(str.charAt(i) == '('){
			Data d = elemHelp(str, i + 1);
			for(Map.Entry<Character,Integer> e : d.elems.entrySet()){
				e.getValue() *= d.mult;
				if(mp.containsKey(e.getKey())){
					e.getValue() += mp.get(e.getKey());
				}
				mp.put(e.getKey(),e.getValue());
			}
			i = d.idx;
		}else{
			if(i + 1 < str.length() && str.charAt(i + 1) >= '0' && str.charAt(i + 1) <= '9'){
				int j = i + 1;
				while(j < str.length() && str.charAt(j) >= '0' && str.charAt(j) <= '9'){
					j++;
				}
				mult = Integer.parseInt(str.substring(i + 1, j));
				i = j;
			}else{
				i++;
			}
			break;
		}
		
	}
	return new Data(mp,mult,i);
}



  1. sverhnovaia
    18.05.2017 18:57
    #10224166

    5. Atention! Spoiler!

    In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
    Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),
    check whether the student qualifies for the reward. 

    e.g. 
@INPUT (String) "OLLAOOOLLO" 
@RETURN (Boolean) False


    The student does not qualify for reward because «LLA» means he was late for 3 times in a row. 

    @INPUT (String) "OLLOAOLLO" 
@RETURN (Boolean) True


    Follow-up:
    If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.


    Solution:
    We can figure out this by keeping two variable one is WasAbsent and ContinousLateCount, and if WasAbsent is true when we found a new Absent, return false, or if ContinousLateCount is 2 when he/she is Late, return false.
    Here is how we will write the code

    
public static boolean ShouldbeRewarded(string attendance)
{
	if(String.IsNullOrWhiteSpace(attendance))
	{
		return true;
	}
	boolean wasAbsent = false;
	int continousLateCount = 0;
	boolean WasLateLastDate = false;
	for(int i = 0 ; i < attendance.Length;i++)
	{
		if(attendance[i] == 'A')
		{
			if(wasAbsent || continousLateCount >= 2)
			{
				return false;
			}
			wasAbsent = true;
			continousLateCount++;
		}
		else if(attendance[i] == 'L')
		{
			if(continousLateCount >= 2)
			{
				return false;
			}
			continousLateCount++;
		}
		else
		{
			continousLateCount = 0;
		}
	}
	return true;
}
	}