Недавно я прошел испытание кода для стажировки в крупной технологической компании. Мне понравились вопросы, я делал по ним заметки, а ограничение по времени и набор тестов на их платформе позволили мне уточнить свой ответ, пока он мне не понравился. Вот первый вопрос, мой процесс, включая первоначальные попытки, и мой окончательный ответ. Я надеюсь, что они не возражают против того, что я это пишу - я не смог найти другого языка, который бы противоречил этому правилу.
Вопрос
Они написали небольшую предысторию, похожую на словесную проблему: «О, у нас есть билетное агентство yadda yadda и множество цен yadda yadda», - я точно не помню. Дело было в следующем: Напишите функцию, которая принимает массив целых чисел и дает длину самого длинного ряда последовательных целых чисел, включая повторения. Так, например, для ввода [5,1,6,8 , 5,2,2,1,6,4] он должен вернуть 5 для [4,5,5,6,6].
Я решил решать на Ruby.
Первая попытка
Мой первоначальный мыслительный процесс был следующим: мы можем подобрать это, проверив размер прогонов, которые вы можете получить, начиная с каждого элемента. Итак, в нашем примере, отметьте 1, вы получите 1,1,2,2 и остановитесь на этом. Сделайте это для каждого элемента, выберите самый длинный. Это наиболее наивный метод, но лучше всего начинать с получения результатов на бумаге.
def someTicketsFunction(ticketsArray)
sortedTix = ticketsArray.sort
m = 0
sortedTix.each{|price|
currentprice = price
innerm = 0
while sortedTix.include?(currentprice)
innerm += sortedTix.count(currentprice)
currentprice += 1
end
m = [innerm, m].max
}
p m
end
Это прекрасно работает, но очень неэффективно по времени. Вы можете видеть, что у него есть вложенная итерация (while внутри each), которую вы хотите исключить.
Что здесь происходит, так это то, что мы сначала сортируем входной массив с помощью удобного .sort рубина, превращая наш предыдущий пример [5,1,6,8,5,2,2,1,6,4] в [1,1,2,2,4,5,5,6,6,8]. Затем мы начинаем просматривать каждый элемент и проверять, является ли он началом цикла, и если да, мы находим размер цикла, сравниваем его с ранее сохраненным размером (m - почему Я называю его m?), А если он больше, замените на него m.
Считаем пробежку с помощью этого:
innerm = 0 while sortedTix.include?(currentprice) innerm += sortedTix.count(currentprice) currentprice += 1 end
Мы проверяем, содержит ли массив следующее целое число, затем следующее, а затем следующее. Это работает, но программе нужно утомиться.
Вторая попытка
При разработке этого метода первого прохода я понял, что нам не нужно проверять длину прогона для каждого элемента, а только тех, которые являются его началом. Другими словами, если во входном массиве есть 1 и 2, нет причин проверять запуск, начинающийся с 2 - мы точно знаем, что тот, который начинается с 1, будет длиннее. Итак, с деталями проработаны:
def someTicketsFunction(ticketsArray)
sortedTix = ticketsArray.sort
m = 0
sortedTix.each{|price|
if sortedTix.include?(price - 1)
nil
else
currentprice = price
innerm = 0
while sortedTix.include?(currentprice)
innerm += sortedTix.count(currentprice)
currentprice += 1
end
m = [innerm, m].max
end
}
p m
end
Мы проверяем, является ли это началом пробега, с помощью этого:
sortedTix.include?(price - 1)
Это проверяет, существует ли значение, на единицу меньшее, чем значение, которое мы сейчас проверяем, как запись в массиве. Если это так, значит, запись, которую мы сейчас проверяем, не является первой из прогона, поэтому нас это не волнует и мы можем перейти к следующему.
Это улучшение, поскольку теперь мы проверяем намного меньше значений, но это не решает нашу основную проблему итерации внутри итератора. Мы все еще слишком медлительны, и нам нужно найти способ обойти это.
Третья попытка (лучшее решение)
def someTicketsFunction(ticketsArray)
tixFrequencyHash = ticketsArray.sort.reverse.each_with_object(Hash.new(0)){|key,hash| hash[key] += 1}
m = 0
tixFrequencyHash.each{|price, frequency|
tixFrequencyHash[price] = frequency + tixFrequencyHash[price + 1]
m = [tixFrequencyHash, m].max
}
p m
end
Впечатленный? Я, по крайней мере. Medium не любит эти длинные строки, по крайней мере, на моем экране, так что меня это беспокоит.
Идея здесь - частотный хеш. На самом деле, это не первый раз, когда я сталкиваюсь с подобным улучшением времени в тесте кода, поэтому, если вы проводите собеседование, я бы порекомендовал посмотреть и подумать о частотных хэшах. Частотный хеш для нашего предыдущего примера массива будет выглядеть так:
# the array
[5,1,6,8,5,2,2,1,6,4]
# frequency hash
{5=>2, 1=>2, 6=>2, 8=>1, 2=>2, 4=>1}
Вот первый фрагмент неразберихи в нашей функции:
tixFrequencyHash = ticketsArray.sort.reverse.each_with_object(Hash.new(0)){|key,hash| hash[key] += 1}
Он состоит из двух частей. Во-первых, шаблонный (но модный!) Ruby-способ создания частотного хэша из массива:
tixFrequencyHash = ticketsArray.each_with_object(Hash.new(0)){|key,hash| hash[key] += 1}
А затем наше небольшое изменение: сначала мы сортируем и меняем местами массив, чтобы хэш частоты шел в порядке от наибольшего к наименьшему значению (цена билета или что-то еще. должно быть). Итак, для нашего примера:
{8=>1, 6=>2, 5=>2, 4=>1, 2=>2, 1=>2}
Это главный трюк в нашем рукаве. Теперь мы можем читать это слева направо, чтобы найти прогоны, вложенная итерация не требуется. Вы видите это?
tixFrequencyHash.each{|price, frequency|
tixFrequencyHash[price] = frequency + tixFrequencyHash[price + 1]
}
К каждому значению в хэше мы добавляем значение, назначенное ключу, который на единицу больше текущего ключа. Посмотрим, как это выглядит на нашем примере:
#initial state
{8=>1, 6=>2, 5=>2, 4=>1, 2=>2, 1=>2}
# tixFrequencyHash[8] = tixFrequencyHash[8] + tixFrequencyHash[9]
{8=>1, 6=>2, 5=>2, 4=>1, 2=>2, 1=>2}
# tixFrequencyHash[6] = tixFrequencyHash[6] + tixFrequencyHash[7]
{8=>1, 6=>2, 5=>2, 4=>1, 2=>2, 1=>2}
# tixFrequencyHash[5] = tixFrequencyHash[5] + tixFrequencyHash[6]
{8=>1, 6=>2, 5=>4, 4=>1, 2=>2, 1=>2}
# tixFrequencyHash[4] = tixFrequencyHash[4] + tixFrequencyHash[5]
{8=>1, 6=>2, 5=>4, 4=>5, 2=>2, 1=>2}
# tixFrequencyHash[2] = tixFrequencyHash[2] + tixFrequencyHash[3]
{8=>1, 6=>2, 5=>4, 4=>5, 2=>2, 1=>2}
# tixFrequencyHash[1] = tixFrequencyHash[1] + tixFrequencyHash[2]
{8=>1, 6=>2, 5=>4, 4=>5, 2=>2, 1=>3}
По мере прохождения он собирает длину каждого прогона в значении, присвоенном ключу начала прогона! Шестерки, пятерки и четверки складываются в 4 = ›5.
Нет вложенной итерации - намного быстрее.
Прокомментируйте свои улучшения, и на следующей неделе я расскажу о второй проблеме из того же теста кода.
edit 13 января 2021 г. - (1) абзац продублирован не в том месте, не имеет смысла; (2) демонстрация частотного хеширования с ошибками
