Мы подготовили для Вас новый выпуск ITренировки — с задачами от Amazon.
Ниже приведены вопросы и задачи для соискателей на должность инженера-разработчика в Amazon, сложность традиционно варьируется от низкой до высокой. А некоторые вопросы под силу решить только самым пытливым умам :) Предлагаем решить их и тем, кто готовится к собеседованию в компанию подобного уровня и просто для проверки собственных сил.
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Ниже приведены вопросы и задачи для соискателей на должность инженера-разработчика в Amazon, сложность традиционно варьируется от низкой до высокой. А некоторые вопросы под силу решить только самым пытливым умам :) Предлагаем решить их и тем, кто готовится к собеседованию в компанию подобного уровня и просто для проверки собственных сил.
Вопросы
- Find missing int
We are given an Excel sheet which contains integers from 1 to 50, including both. However, the numbers are in a jumbled form and there is 1 integer missing. You have to identify the missing integer. Only the logic is required.
ПереводДана таблица Excel, содержащая числа от 1 до 50 включительно. Числа неупорядочены, а одно число — пропущено. Необходимо найти это число. Для решения задачи достаточно логики.
- Robots and parachutes
Two robots land with their parachutes on an infinite one-dimensional number line. They both release their parachutes as soon as they land and start moving. They are allowed only to make use of the following functions.
I. moveLeft() // robot moves to left by 1 unit in 1 unit time
II. moveRight() // robot moves to right by 1 unit in 1 unit time
III. noOperation() // robot does not move and takes 1 unit time
IV. onTopOfParachute() // returns true if the robot is standing on top of either of the parachute, else false
V. didWeMeet() // returns true if the robot meets to the other robot, else false
Write a function in order to make the robots meet each other. Robots will be executing the same copy of this function. Pseudocode is accepted.
ПереводДва робота с парашютами приземляются на бесконечную плоскую ленту. Оба отстёгивают парашюты и начинают двигаться. Роботы могут выполнять следующие инструкции:
I. moveLeft() // робот двигается влево на 1 единицу за 1 единицу времени
II. moveRight() // робот двигается вправо на 1 единицу за 1 единицу времени
III. noOperation() // робот выжидает на месте 1 единицу времени
IV. onTopOfParachute() // возвращает true если робот стоит на парашюте, иначе — возвращает false
V. didWeMeet() // возвращает true, если робот встретил другого робота, иначе — false.
Напишите функцию, обеспечивающую встречу роботов. Роботы выполняют одинаковые копии этой функции. Псевдокод приемлем.
Задачи
- Run length encoding
Given an input string, write a function that returns the Run Length Encoded string for the input string.
For example, if the input string is “wwwwaaadexxxxxx”, then the function should return “w4a3d1e1x6”.
ПереводДана входная строка, напишите функцию, которая возвращает кодирование длин серий входной строки.
Например, входная строка “wwwwaaadexxxxxx” должна быть преобразована к “w4a3d1e1x6”.
- Students and chocolates
Given n boxes containing some chocolates arranged in a row. There are k number of students. The problem is to distribute maximum number of chocolates equally among k students by selecting a consecutive sequence of boxes from the given lot. Consider the boxes are arranged in a row with numbers from 1 to n from left to right. We have to select a group of boxes which are in consecutive order that could provide maximum number of chocolates equally to all the k students. An array arr[] is given representing the row arrangement of the boxes and arr[i] represents number of chocolates in that box at position ‘i’.
Examples:
Input: arr[] = {2, 7, 6, 1, 4, 5}, k = 3
Output: 6
The subarray is {7, 6, 1, 4} with sum 18.
Equal distribution of 18 chocolates among
3 students is 6.
Note that the selected boxes are in consecutive order
with indexes {1, 2, 3, 4}.
ПереводДано n ящиков с шоколадом, уложенных в ряд. Также присутствует k студентов. Задача — разделить максимально возможное количество шоколада поровну между студентами, выбрав подпоследовательность ящиков в ряду. Предположим, ящики пронумерованы от 1 до n слева направо. Мы должны последовательно выбрать группу ящиков, расположенных рядом, которые содержат максимальное количество шоколада, делимого поровну между студентами. Массив arr[] представляет собой ящики, расположенные в ряд, а значение arr[i] представляет количество шоколада в ящике 'i'.
Например:
Вход: arr[] = {2, 7, 6, 1, 4, 5}, k = 3
Выход: 6 (количество шоколада, которое достанется одному студенту)
Подмассив {7, 6, 1, 4} с суммой 18. Распределение 18 шоколадок между студентами даст 6 шок/чел. Выбранные индексы ящиков — {1, 2, 3, 4}.
- Print all anagrams together
Given an array of words, print all anagrams together. For example, if the given array is {“cat”, “dog”, “tac”, “god”, “act”}, then output may be “cat tac act dog god”.
ПереводДан массив слов, напечатайте все анаграммы вместе. Например, в массиве {“cat”, “dog”, “tac”, “god”, “act”} вывод может быть «cat tac act dog god».
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Rsa97
Detlev
И встретятся они через 4*s единиц времени, где s — расстояние между парашютистами сразу после приземления.
reci Автор
Оба будут двигаться влево бесконечно.
reci Автор
Хотя, если парашюты остаются на месте приземления (а они остаются по условию задачи), то — все ок.
trantor1
а так не проще?
Mikluho
ну так выше же и дана формула суммы ряда.
IIvana
1 вопрос — Гаусс, Карл! (С). Который решал ее в детстве безо всяких экселей.
andyudol
1 вопр. В екселе это номер строки, начиная с которой номер строки не равен числу.
Rsa97
Это только если числа отсортированы, находятся в одной колонке и записаны начиная с первой строки. В задаче же, как минимум, явно указано, что числа неупорядочены.
andyudol
Разьве в екселе нет сортировки?
Rsa97
Попробуйте отсортировать числа, находящиеся в разных колонках на разных страницах.
andyudol
Но ведь при вычислении через разность сумм их ведь тоже не ручками предлагается переносить?
Rsa97
Для суммирования можно просто выделять диапазоны ячеек, в том числе и на разных страницах.
andyudol
Почему в одном случае можно, а в другом нельзя?
Rsa97
Попробуйте сами. Выделите в Excel несколько колонок на разных страницах и попробуйте их отсортировать для сравнения с номерами строк.
andyudol
Почему в моём случае это сложно, а в вашем — посто?
Rsa97
Вы не спрашивайте, вы откройте Excel и попробуйте. Запишите в колонку A все нечётные от 1 до 49, в колонку B — все чётные от 2 до 50. А теперь отсортируйте эти значения так, чтобы они были в строках с соответствующими номерами.
andyudol
Ещё раз. Почему в поём случае это проблема, а в вашем — нет? Вы как будете вычислят пропущенное число? Макрос напишете или на калькуляторе? Эти числа ведь не сами найдутся и впрыгнут в калькулятр. В любом случае вам точно так же придётся эти числа найти, выделить, скопировать, куда-то вставить. Подозреваю, что у меня-то как раз ручных действий требуется меньше.
Rsa97
Ставите курсор в свободную ячейку. Набираете '=(1+50)/2*50-СУММ('. Зажав Ctrl, мышкой выбираете все нужные ячейки и/или диапазоны ячеек. Набираете ')'. Нажимаете Enter. Всё, пропущенное число найдено. Ничего копировать, вставлять и т.п. не надо.
andyudol
То есть все те же действия ручками совершить надо.
Ну ладно, что-то трёп затянулся. Я же не опровергаю вычислительное решение.
Ну и на закуску. "… одно число — пропущено. Необходимо найти это число.". Найти, а не вычислить! Но как можно найти то, чего нет? Оно же пропущено!
Вот. Вы как хотите, а я на этом закончил.
Detlev
На мой взгляд не совсем корректно поставлена задача. Непонятно зачем приплели Excel. В Excel можно решить эту задачу большим количеством способов, вплоть до того что можно написать макрос. Я бы переформулировал бы задачу так. Дан массив размерностью 49, в котором находятся в неупорядоченном виде числа от 1 до 50, за исключением одного. Как за один проход найти пропущенное число? Ограничение по памяти О(1). И тогда решение от Rsa97 станет очевидным и самым простым.
Detlev
Или даже так: вообще не использовать дополнительно память))
reci Автор
Я думаю, что Rsa97 имеет в виду, что-то вроде
SUM(Sheet1!A1:C10,Sheet2!A1:C10)
andyudol
А Sheet1!A1:C10 и Sheet2!A1:C10 точно в одной таблице находятся?
Rsa97
По условию задачи — в одной.
andyudol
Я читал условия задачи.
В екселе разные листы — это точно одна и та же таблица?
jmdorian
steps = 1;
do {
for (i=0;i < steps; i++) { moveLeft(); }
if (onTopOfParachute()) { noOperation(); }
else {
for (i=0;i < steps; i++) { moveRight();}
steps++;
}
} while(!didWeMeet())
Rsa97
Встретятся через s2 единиц времени, где s — расстояние между парашютистами сразу после приземления.
Rsa97
Поправка. Роботы не встретятся. После того, как один из роботов дойдёт до чужого парашюта, он пойдёт влево на s шагов, в то время, как второй робот будет двигаться мимо него вправо.
zalp
jmdorian
Да, облажался.
Vlad130198
ilya06
Такой вариант задачи:
Rsa97