Кодкамп - практическое программирование на python

2021-09-23 11:01:18 Задача 33
(Собеседование в Microsoft)

Вычислите бегущую медиану последовательности чисел при заданном списке чисел. Бегущей медианой списка является медиана от первого элемента до текущего элемента списка.

Напомним, что медиана четного списка - это среднее значение двух средних чисел.

Например, учитывая последовательность [2, 1, 5, 7, 2, 0, 5], ваш алгоритм должен напечатать:

2 # медиана 2
1.5 # медиана [2, 1]
2 # медиана [2, 1, 5]
3.5 # медиана [2, 1, 5, 7]
2 # медиана [2, 1, 5, 7, 2]
2 # медиана [2, 1, 5, 7, 2, 0]
2 # медиана [2, 1, 5, 7, 2, 0, 5] Открыть/Комментировать

2021-09-19 08:39:51 Задача 32 (Собеседование в Jane Street)

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

Нет транзакционных издержек, и Вы можете торговать дробными количествами. Открыть/Комментировать

2021-09-19 08:34:55 Открыть/Комментировать

2021-09-15 14:56:05 Задача 31 (Собеседование в Google)

Расстояние Левенштейна (или редакционное расстояние) между двумя строками относится к минимальному количеству вставок, удалений и замен символов, необходимых для изменения одной строки на другую. Например, редакционное расстояние между "kitten" и "sitting" равно трем: замените «k» на «s», замените «e» на «i» и добавьте «g».

Вычислите редакционное расстояние двух заданных строк. Открыть/Комментировать

2021-09-15 14:24:45 Открыть/Комментировать

2021-09-11 17:32:56 Открыть/Комментировать

2021-09-11 14:23:32 Задача 30
Вам предоставляется массив неотрицательных целых чисел, представляющий двумерную карту высот, где каждый элемент представляет собой стену единичной ширины, а целое число - это высота. Предположим, пойдет дождь и все места между двумя стенами будут засыпаны.

Вычислите, сколько единиц воды остается в ловушке на карте за O(N) времени и O(1) место.

Например, учитывая вход [2, 1, 2], мы можем держать 1 единицу воды посередине.

Учитывая входные данные [3, 0, 1, 3, 0, 5], мы можем удерживать 3 единицы в первом индексе, 2 во втором и 3 в четвертом индексе (мы не можем удерживать 5, так как они переместятся влево), так что мы можем уловить 8 единиц воды. Открыть/Комментировать

2021-09-11 14:11:24 Открыть/Комментировать

2021-09-10 14:09:58 Задача 29 (Собеседование Amazon)
Кодирование длин серий - это быстрый и простой метод кодирования строк. Основная идея состоит в том, чтобы представить повторяющиеся последовательные символы как один счетчик и символ. Например, строка «AAAABBBCCDAA» будет закодирована как «4A3B2C1D2A».

Реализуйте кодирование и декодирование длин серий. Вы можете предположить, что кодируемая строка не содержит цифр и состоит исключительно из буквенных символов. Вы можете предположить, что декодируемая строка действительна. Открыть/Комментировать

2021-09-10 14:08:52 Открыть/Комментировать