Киты! - Я имею в виду Уэльс!

Недавно я готовился к собеседованиям по жесткому программированию с ведущими технологическими компаниями. Два месяца назад я опубликовал статью, в которой высмеивал эти типы вопросов по кодированию, но затем меня почти сразу же спросили о них в интервью, так что я все еще считаю, что они бесполезны и необходимы, учитывая потребность программистов в доказательстве друг другу, что они СМЕРТ.

В последнее время я взламывал эти проблемы на таких сайтах, как LeetCode и HackerRank, хотя оба сайта недавно сделали часть своего контента более премиальной, чтобы доить деньги от нас, мало работающих бездельников. Но если (и давайте будем честными: когда) я застряну в вопросе, я пойду посмотреть видео этого чувака, Кевина Нотона-младшего, который помогает мне решить проблему.

Затем я перевожу его код, который он пишет на Java, на JavaScript, который обычно очень простой, если не идентичный (помогает мне осознать их сходство!), И пишу комментарии для всех строк проблемы, так что я знаю, что понимаю это.

Наконец, если возможно, я тестирую его на LeetCode и смотрю, работает ли он, или пишу мои собственные тесты, а затем, если я ошибаюсь, отчаянно прошу друга о помощи, как у ужасного синдрома самозванца n00b, которым я иногда являюсь.

Однако недавно я столкнулся с проблемой, что не было ни видео, ни доступной общедоступной информации. Проблема выглядит так:

Given the Welsh Alphabet, which is slightly different than the English one, design a function that sorts a list of words by that alphabet:
"a b c ch d dd e f ff g ng h i j l ll m n o p ph r rh s t th u w y"
Note: "double" letters supersede single letters so "ng" would be considered in its current order and not as an "n g".

Это звуки из Великобритании! Можно даже сказать, что это будет «Ночной трудный день», пытающийся решить эту проблему.

В любом случае, поскольку для этого не было LeetCode и видео, давайте сделаем это!

Во-первых, давайте просто сделаем этот валлийский алфавит хорошей переменной, скопировав его.

const welshAlphabet = 'a b c ch d dd e f ff g ng h i j l ll m n o p ph r rh s t th u w y'

Затем мы знаем, что нам нужна функция, которая будет принимать список или массив слов, которые будут оцениваться нашей функцией. Кроме того, давайте также превратим эту большую старую строку в массив, пока мы работаем над этим! Легче иметь дело!

const welshSort = (welshWordsArray) => {
 //turn the string into an array of welsh letters.
 let welshArray = welshAlphabet.split(' ')

Мне нравится называть вещи как можно более описательными, чтобы не запутаться!

Теперь давайте создадим словарь! В JavaScript мы называем их картой hash-map или объектом. Это будет способ максимально быстро отследить порядок алфавита, поскольку поиск значений в объекте занимает O (1) раз! Итак, чтобы создать этот словарь, мы просто инициализируем его переменной и используем цикл JavaScript forEach, чтобы получить index или порядок букв и установить их как значения к ключам валлийских букв.

//create a map/dicitonary for the welsh letters with O(1) lookup.
const welshDict = {}
//add each letter as a key in the dictionary with its value based on order.
welshArray.forEach((letter,i) => welshDict[letter] = i)

А теперь, что очень важно, я хотел бы абстрагировать часть логики до вспомогательной функции. У меня уже есть идея, что мы будем просматривать каждое слово в поисках этих валлийских двойных букв, и я хочу создать функцию, которая сообщит мне, является ли буква одной из них.

Итак, я собираюсь использовать метод String.slice (), чтобы посмотреть на два элемента строки одновременно, чтобы увидеть, являются ли они потенциально валлийскими, и если да, мы хотим, чтобы они оценивались по их двухбуквенному значению. В противном случае мы просто возьмем одну букву в любой позиции в строке, в которой мы находимся.

//helper function to see if the letter we're checking is a two letter Welsh character or not.
const isItWelsh = (word, position) => {
  //if it is a welsh letter, this slice of the word will be the letter.
 let potentiallyWelsh = word.slice(position, position +2)
  //if we're not at the end of the word and the two-letter character is in the welsh alphabet, return it
  if(position < word.length-1 && potentiallyWelsh in welshDict) return potentiallyWelsh;
  //otherwise return the single character letter
  return word[position]
}

Отлично, мы сделали действительно сложную часть работы. Теперь нам просто нужно выполнить настоящую сортировку. Теперь в JavaScript мы можем либо вызвать Array.sort (), либо добавить параметр function для сортировки, учитывая два значения в массиве и то, что мы собираемся делать.

Это будет значение return нашей функции, поскольку оно будет отсортировано, и мы также можем инициализировать нашу позицию первым элементом слова, которое в JavaScript имеет индекс 0.

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

//we need to sort these words by a custom method
return welshWordsArray.sort((a,b) => {
//edge-case, if they're the same word, no need to manipulate the array!
if(a === b) return 0;
//initializing the position at the start of the word.
let position = 0

Хорошо! А теперь давайте начнем веселье.

Мы собираемся просмотреть каждую букву этого массива итеративно, что означает, что мы будем использовать цикл. Для простоты я просто использовал цикл while (true), который будет работать бесконечно, если не будет сказано остановиться, поэтому мне придется останавливать его вручную с помощью return или операторы break.

Вдобавок, если слово остается неизменным до точки, но одно длиннее (т. Е. Способный, эйллист), мы захотим поставить любое из самых коротких слов после того, которое длиннее. Так что мы тоже с этим разберемся.

//using a loop to loop through the whole word with no condition so we can use custom returns.
while(true){
  //if we've reached the end of the first word and it's been equal thus far but shorter, it goes before.
  if(position >= a.length) return -1;
  //if we've reached the second word and it's been equal but shorter it goes before.
  if(position >= b.length) return 1;

Теперь легкая часть! Нам нужно проверить каждую букву и двухбуквенный блок, чтобы убедиться, что это валлийский! Обычно для этого требуется много логики, но поскольку мы создали вспомогательную функцию, это очень просто:

//initializing what the letters are at the current position using our helper function
let letterA = isItWelsh(a, position)
let letterB = isItWelsh(b, position)

Наконец, у нас есть последнее условие. Если у нас есть одна и та же буква в той же позиции, одно- или двухсимвольная буква, мы хотим перейти к следующей позиции и продолжить наш цикл. В противном случае мы можем просто отсортировать по этой букве с синтаксисом сортировки a-b, который дает нам возрастающий порядок, и вернуть это значение для нашей сортировки.

//if they're letters are equal, go to the next letter, either 1 or 2 away!
if(letterA === letterB){
  position += letterA.length
} else {
  //otherwise sort them by their welsh values comparing the first and second word.
  return welshDict[letterA] - welshDict[letterB]
}

Готово! Окончательный код выглядит примерно так:

Теперь, наконец, давайте поговорим о временной и пространственной сложности, поскольку это вопрос собеседования, и вас, скорее всего, об этом спросят.

Сложность пространства довольно проста, поскольку мы создаем только один массив и один объект независимо от длины функции, поэтому это означает, что если он никогда не меняется, он остается постоянным. пробел или O (1).

Временная сложность немного сложнее. Насколько я понимаю, мы получаем в среднем O (n log n) времени для нашего алгоритма sort, подробнее об этом здесь, что на самом деле довольно круто.

Но, насколько я понимаю, поскольку нам нужно не только сортировать каждое слово, но и перебирать его, чтобы убедиться, является ли буква валлийской или нет, временная сложность (в худшем случае) равна O (длина самого длинного слова. * N log n).

Вуш. Гав. Arf.

Так вот оно! У меня нет для вас фактов об Уэльсе, хотя я полагаю, что это хорошее место! Я просто не хотел, чтобы кто-то еще остался в беде, что, вероятно, тоже не по-уэльски.

Хотя это было сложно, и у меня нет остроумного перехода, так что вот милая собачка!

Это Тень, самый добрый мальчик. Он полуночный милашка. Он супер-умный и знает, когда тебя тянет, чтобы перестать тянуть, как по волшебству. Он также эмоционально умен, облизывает и наклоняется. Я уверен, что как только он появится у Шона Кейси, его усыновят.

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

Хоть он и собачий.

Тем более, что он пёсик.

Бай пока,

ник