Комментарии 44
А почему во втором вопросе ответ
2
?thurday
Я точно не знаю, но я получил ответ так — первые две буквы надо поменять местами, последние 3 записать в обратном порядке, а каждую букву в центре заменить на следующую в алфавите.
вот только в вопросе каждая буква в центре заменяется на предыдущую. Кажется, в задаче ошибка… Ну либо правильный ответ Thursday, а алгоритм сложнее.
По идее для расшифровки буквы в центре надо заменять на предыдущие в алфавите: в шифре IDTUBECN в центре это будут DISTANCE. Поэтому в зашифрованном HTTQYAD это должны быть THSPDAY. Похоже на ошибку в вопросе
У меня получилось THURDAY, а для того, чтобы было THURSDAY, в вопросе должно было быть слово HTTQRYAD.
я тож в уме прикинул, если так сделать будет th???day а единственное слово в английском которое подходит это thursday,, буквы в центре рандомные для запутывания?
написавший был русским шпионом, поэтому сделал ошибку в слове. Но ответ такой, да.
1
Взвесить для каждой машины число болтов равное ее номеру.
2
THSPDAY тоже вышло, вероятно ошибка
Задача 2
Поправьте, если я не прав: каждая локальная переменная помещается в стек. Так почему не сделать например так
void checkStack() {
int a;
int b;
if (&a < &b) {
cout << "Up" << endl;
} else {
cout << "Down" << endl;
}
}
Думаю, не верно. В рамках одного вызова ни кто не гарантирует (даже не упоминает) порядок расположения локальных переменных в стеке.
Ну и сравнение указателей так просто не сработает. Надо к интам закастить.
Примерно так:
Вызвать исходно с нулем. Если вернет 1, значит стек растет сверху вниз.
Тут рекурсия — последовательный вызов, так что гарантировано локальная переменная из первого экземпляра раньше по стеку, чем та же переменная из второго экземпляра.
Ну и сравнение указателей так просто не сработает. Надо к интам закастить.
Примерно так:
bool CheckStack(int *p)
{
int var;
if ((int)p == 0)
return CheckStack(&var);
return (int)(&var) < (int)p;
}
Вызвать исходно с нулем. Если вернет 1, значит стек растет сверху вниз.
Тут рекурсия — последовательный вызов, так что гарантировано локальная переменная из первого экземпляра раньше по стеку, чем та же переменная из второго экземпляра.
Согласно этому указатели таки можно сравнивать as is.
А если нет никаких уточнений про механизм «weighing», почему бы не
1
сделать весы в виде сбалансированного горизонтального диска на центральном подвесе с равномерно расположенными по внешнему краю отверстиями для шурупов?
Весы одни. Взвешивание одно.
1
Берём 1 шуруп с 1-й, 2 шурупа со второй… 10 с 10-й.
Сваливаем всё в кучу и идем взвешивать.
Ответ: 10 — (wight % 1) * 10.
Сваливаем всё в кучу и идем взвешивать.
Ответ: 10 — (wight % 1) * 10.
Ну это тривиальное решение которое я заведомо знал подсмотрел бы в комментариях выше. Моё — альтернативное и с инженерной точки зрения по некоторым критериям даже более подходящее.
Я тоже сомневаюсь, что у них там есть несколько вариантов решения, скорее всего одно. В чём и проблема для таких тестов — только да/нет. Если же общаешься с реальным заинтересованным человеком — его может весьма заинтересовать необычный подход к проблеме.
В реальной жизни — почти любую задачу можно решить не одним, а 3-мя вариантами как минимум. В результате:
1) В уме: «Это ответ не правильный, у меня такого в вариантах нет», вербально: «Не правильно».
2) В уме: «Я тут начальник, не понял, слишком умный что-ли?», вербально: «Вы нам не подходите».
3) В уме: «Хм… интересно, как я до этого не додумался...»
В реальной жизни — почти любую задачу можно решить не одним, а 3-мя вариантами как минимум. В результате:
1) В уме: «Это ответ не правильный, у меня такого в вариантах нет», вербально: «Не правильно».
2) В уме: «Я тут начальник, не понял, слишком умный что-ли?», вербально: «Вы нам не подходите».
3) В уме: «Хм… интересно, как я до этого не додумался...»
У нас тоже довольно большая команда, давно уже.
И перехожу уже с темы набора — от претендентов на реальную работу.
По претендентам максимальный плюс может выдать только TL или кто там главный в проекте. Но до него не дойдёт, отсеют по формальным признакам. Шлак. Тест не прошёл.
Мы отказались от этого.
И перехожу уже с темы набора — от претендентов на реальную работу.
По претендентам максимальный плюс может выдать только TL или кто там главный в проекте. Но до него не дойдёт, отсеют по формальным признакам. Шлак. Тест не прошёл.
Мы отказались от этого.
Полностью согласен. Эта первая задачка тривиальна — для затравки, наверно.
Да, ваше решение действительно красивое и креативное, если понятие «весы» не определено.
Да, ваше решение действительно красивое и креативное, если понятие «весы» не определено.
Не знаю, какой хитрый алгоритм подразумевался в 3-й задаче, но через моё дерево двоичного поиска делается легко и красиво:
По скорости: 100000 за секунду с О(n*ln(n)) в худшем случае.
Python
import collections
import aa_sbst # Дерево, можно поиметь через "pip install aa_sbst"
def NGEs(arr):
ans = [-1]*len(arr) # Здесь накопим результат
t_el = collections.namedtuple('t_el', 'v, pos')
t = aa_sbst.sbst()
for pos, v in enumerate(arr):
# Цикл по ранее встреченным меньшим элементам
for el in t.backward_from(t_el(v, 0), False):
ans[el.pos] = v
t.remove(el) # Второй раз обрабатывать не будем
t.add(t_el(v, pos))
return ans
По скорости: 100000 за секунду с О(n*ln(n)) в худшем случае.
Хитрость в том,
4000000 за секунду. O(n).
Спойлер
что начинать надо с конца.
def nge(arr):
result = [-1] * len(arr)
current_greater = arr[-1]
for i in range(len(arr) - 2, -1, -1):
if arr[i] < current_greater:
result[i] = current_greater
else:
current_greater = arr[i]
return result
4000000 за секунду. O(n).
Валится на первом тесткейсе:
>>> nge([4, 5, 2, 25])
[25, 25, 25, -1]
Тоже рассматривал в точности такой вариант. Решение простое, но неверное.
Для массива [1,2,3] оно выдаст [3,3,-1], а надо [2,3,-1].
Для массива [1,2,3] оно выдаст [3,3,-1], а надо [2,3,-1].
Упс. Ошибочка вышла
Так, вроде, работает правильно.
Спойлер
def nge(arr):
result = [-1] * len(arr)
current_greater = arr[-1]
for i in range(len(arr) - 2, -1, -1):
if arr[i] < arr[i+1]:
current_greater = arr[i+1]
if arr[i] < current_greater:
result[i] = current_greater
else:
current_greater = arr[i]
return result
Так, вроде, работает правильно.
WA на тесте [3, 1, 2, 4]
Это вопросы из корейского самсунга что ли, или почему английский такой корявый? Или вы сами придумываете задачи, потом их коряво переводите и выдаёте за оригинал?
в1 - дефект массы
1 винт от 1 машины, 2 винта от 2 машины и т.д.
найти дефект массы и поделить на единичный дефект, получим номер машины
в2 - ой холмс, у вас буква отклеилась!
D I . S T A . N C E
x + + + X
I D . T U B . E C N
D O . C U M . E N T
x + + + X
O D . D V N . T N E
H T . T Q . Y A D
x - - X
T H . S P . D A Yхз как расшифровывать 7-буквенные слова. Но допустим, что в конце DAY. А в начале может быть всё что угодно и как попало.
задача 1. как-то очень криво сформулирована.
Приходится домысливать за топикстартера! Всё по-взрослому, вот тебе хотелки, сам себе сделай ТЗ!
Поэтому под кат не прячу. Пусть будет спойлер, а авторам пусть будет стыдно.
Допустим, так. Локации пронумерованы. Дана матрица смежности. Если локации смежные, то расстояние между ними 1. В некоторых локациях есть источники (потому что локаций — до 20 — по размеру матрицы, а источников — до 5).
Тупое решение, благо, размер матрицы позволяет.
Получаем матрицу расстояний из матрицы смежности. Это — тупо, возвести матрицу смежности в 20 степень, где (умножение) — это сложение, а (сложение) — это минимум. А единичка смежности считается 1 расстояния, нолик смежности считается бесконечностью, а на диагонали стоят 0. (расстояние до самих себя, естественно, нулевое).
Для каждой локации посчитать сумму расстояний до всех источников.
- Найти минимум.
Задача 2 про стек
элементарно ватсон!
ptrdiff_t delta(char* caller) {
char inside;
return &inside - caller;
}
bool stack_grows_up() {
char caller;
return delta(caller) > 0;
}Задача 3 про NGE, наивное решение за квадратное время
def NGEs(xs):
return [
next( # первая итерация
(y for y in xs[i+1:] if y > x), # итератор по следующим бОльшим элементам
-1) # дефолт первой итерации
for n in (len(xs),) # трюк с переменной внутри генератора
for i in range(n)
for x in (xs[i],) # трюк с переменной внутри генератора
]Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Выпуск#22: ITренировка — актуальные вопросы и задачи от ведущих компаний