ITренировка — актуальные brain teaser'ы ведущих компаний

Многие наслышаны о каверзных вопросах и задачах, которые дают на собеседованиях в 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.