- PVSM.RU - https://www.pvsm.ru -
Публикуем очередную подборку задач и вопросов с собеседований в крупных IT-компаниях (для тех, кому мало задач из предыдущего сета [1] :)
Ниже приведены вопросы и задачи для соискателей в Google, с различным уровнем сложности. Набор получился с лингвистическим уклоном, но знание языков не обязательно — задачи можно решить руководствуясь логикой и рассуждая последовательно. Надеемся, что решение этих задач принесёт интеллектуальное удовольствие и практическую пользу на собеседовании :).
There are 3 ants sitting on three corners of a triangle. All ants randomly pick a direction and start moving along edge of the triangle. What is the probability that any two ants collide?
A team of three people decide on a strategy for playing the following game. Each player walks into a room. On the way in, a fair coin is tossed for each player, deciding that player’s hat color, either red or blue. Each player can see the hat colors of the other two players, but cannot see her own hat color. After inspecting each other’s hat colors, each player decides on a response which are one of the following:
— “I have a red hat”
— “I had a blue hat”
— “I pass”The player’s responses are recorded, but the responses are not shared until every player has recorded her response. The team wins if at least one player responds with a color and every color response correctly describes the hat color of the player making the response. In other words, the team loses if either everyone responds with “I pass” or someone responds with a color that is different from her hat color. What strategy should one use to maximize the team’s expected chance of winning?
For example, one possible strategy is to single out one of the three players. This player will respond “I have a red hat” and the others will respond “I pass”. The expected chance of winning with this strategy is 50%. Can you do better?
Например, одним из возможных вариантов является ответ только избранного игрока. Этот игрок отвечает «У меня красная шляпа» или «У меня синяя шляпа», остальные пасуют. Ожидаемая вероятность победить при такой стратегии — 50%. Сможете ли Вы предложить лучшее решение?
Imagine you have a special keyboard with the following keys:
A Ctrl+A Ctrl+C Ctrl+Vwhere CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.
If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.
That is to say, the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce).Ex:
Input: N = 3
Output: 3
We can at most get 3 A's on screen by pressing following key sequence.
A, A, AInput: N = 7
Output: 9
We can at most get 9 A's on screen by pressing following key sequence.
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl VInput: N = 11
Output: 27
We can at most get 27 A's on screen by pressing following key sequence.
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V, Ctrl A, Ctrl C, Ctrl V, Ctrl V
A Ctrl+A Ctrl+C Ctrl+V
где CTRL+A, CTRL+C, CTRL+V работают как «Выбрать всё», «Скопировать», «Вставить» соответственно.
Вы можете нажать на клавиатуру N раз (только на указанные клавиши). Напишите программу, дающую максимальное количество «A» с помощью этих операций. Если возможно, выведите также последовательность нажатий. Иначе говоря, вход — N (количество нажатий), вывод — M (количество «А», которые можно получить).
Примеры:
Вход: N = 3
Выход: 3
Можем получить максимум 3 A следующей последовательностью нажатий: A, A, A
Вход: N = 7
Выход: 9
Максимум — 9 А, последовательность: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
Вход: N = 11
Выход: 27
Максимум — 27 А, последовательность: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V, Ctrl A, Ctrl C, Ctrl V, Ctrl V
Given a boolean expression with following symbols.
Symbols
'T' ---> true
'F' ---> falseAnd following operators filled between symbols
Operators
& ---> boolean AND
| ---> boolean OR
^ ---> boolean XORCount the number of ways we can parenthesize the expression so that the value of expression evaluates to true.
Let the input be in form of two arrays one contains the symbols (T and F) in order and other contains operators (&, | and ^}
Examples:
Input: symbol[] = {T, F, T}
operator[] = {^, &}
Output: 2
The given expression is «T ^ F & T», it evaluates true in two ways "((T ^ F) & T)" and "(T ^ (F & T))"Input: symbol[] = {T, F, F}
operator[] = {^, |}
Output: 2
The given expression is «T ^ F | F», it evaluates true in two ways "( (T ^ F) | F )" and "( T ^ (F | F) )".Input: symbol[] = {T, T, F, T}
operator[] = {|, &, ^}
Output: 4
The given expression is «T | T & F ^ T», it evaluates true in 4 ways ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T)).
Символы
'T' ---> true
'F' ---> false
И следующие операторы, вставляемые между символами:
Операторы
& ---> логическое И
| ---> логическое ИЛИ
^ ---> исключающее ИЛИ
Подсчитайте количество вариантов расстановки скобок, чтобы значение выражения стало равным true.
Допустим, вводные данные представлены в виде 2-х массивов — символов (T и F) и операторов (&, | и ^).
Примеры:
Вход: symbol[] = {T, F, T}
operator[] = {^, &}
Выход: 2
Выражение «T ^ F & T», становится равным true в 2-х случаях: "((T ^ F) & T)" и"(T ^ (F & T))"
Вход: symbol[] = {T, F, F}
operator[] = {^, |}
Выход: 2
Выражение «T ^ F | F», становится равным true в 2-х случаях "( (T ^ F) | F )" и "( T ^ (F | F) )".
Вход: symbol[] = {T, T, F, T}
operator[] = {|, &, ^}
Выход: 4
Выражение «T | T & F ^ T», становится равным true в 4-х случаях: ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T)).
Given a sorted dictionary (array of words) of an alien language, find order of characters in the alien alphabet.
Examples:
Input: words[] = {«baa», «abcd», «abca», «cab», «cad»}
Output: Order of characters is 'b', 'd', 'a', 'c'
Note that words are sorted and in the given language «baa» comes before «abcd», therefore 'b' is before 'a' in output. Similarly we can find other orders.Input: words[] = {«caa», «aaa», «aab»}
Output: Order of characters is 'c', 'a', 'b'
Примеры:
Вход: words[] = {«baa», «abcd», «abca», «cab», «cad»}
Выход: Порядок букв 'b', 'd', 'a', 'c'
Заметим, что 'baa' идёт перед 'abcd', следовательно в алфавите 'b' стоит перед 'a'. Аналогичным образом узнаем порядок других букв.
Input: words[] = {«caa», «aaa», «aab»}
Выход: Порядок букв 'c', 'a', 'b'.
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Автор: reci
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/276572
Ссылки в тексте:
[1] предыдущего сета: https://habrahabr.ru/company/spice/blog/351896/
[2] правильной монеты: https://en.wikipedia.org/wiki/Fair_coin
[3] Источник: https://habrahabr.ru/post/352454/?utm_campaign=352454
Нажмите здесь для печати.