На прошлой неделе у меня было собеседование, я сделал несколько технических тестов и начал наш последний проект в последней команде, в которой я буду работать в Makers. Вот краткое изложение того, что произошло.
Большая часть работы, которую мы делаем в Makers, выполняется во время парного программирования или в наших командных проектах. Как следствие, есть только несколько частей курса, когда основное внимание уделяется исключительно индивидуальной работе. Одно упражнение по кодированию в Неделе 2, Gilded Rose, о котором я писал ранее. Другой раз, когда мы сосредотачиваемся на индивидуальной работе, - это неделя 10, также известная как неделя качества кода или, чаще, неделя технических тестов.
Для непосвященных технический тест обычно представляет собой небольшое упражнение по кодированию, которое компания проводит во время процесса найма, которое дополняет обычный способ оценки кандидата в компании - техническое собеседование.
У Makers есть набор технических тестов, над которыми мы будем работать на этой неделе, в том числе наиболее часто назначаемый для начала «банковский технический тест». Кандидатам предлагается написать простое приложение командной строки, моделирующее банковский счет, с депозитами, снятием средств и выписками из банка на любом языке по их выбору.
На данный момент мне удобнее всего начинать новый проект на JavaScript, в основном из-за знакомства. Кроме того, я недавно подал заявку на работу в фирме облачных вычислений / финансовых услуг в лондонском Сити, и, видя, что они ищут кого-то с опытом JavaScript, я чувствую, что это помогло мне сделать правильный выбор. Тест банковских технологий прошел очень хорошо. Затем пришло неожиданное сообщение: я получил настоящий технический тест, на сдачу которого оставалось чуть более 36 часов. Мое приложение было включено в короткий список, и теперь пришло время показать им, что я могу писать код в срок.
Задача: написать приложение из командной строки, решающее анаграммы. Более конкретно, если дать слово для проверки, называемое subject, и файл, содержащий список слов в качестве входных данных, вычислить, какие из слов являются анаграммами темы, и вернуть новый список найденных анаграммы.
Мое решение можно найти здесь. Не самое лучшее.
Я сдал его за несколько часов до крайнего срока, о чем сразу пожалел, и в последующие дни почувствовал себя все хуже и хуже. Почему? Потому что я заметил очень глупый изъян в своем методе, и было уже поздно забирать его обратно!
Вот немного контекста. Представьте, что у вас есть подлежащее слово «безмолвный».
silent
Допустим, у вас также есть список слов, все из которых могут быть анаграммами слова «безмолвный».
enlist inlets listen silent tinsel
Один из способов сделать программу проверки анаграмм (но не так, как это сделал я) - это расположить в алфавитном порядке все слова, которые нужно сравнить.
Сначала вы должны расположить подлежащее слово в алфавитном порядке.
Затем, возможно, вы пройдете по списку слов и для каждого слова расположите слово в алфавитном порядке, а затем сравните его.
let subject = 'silent';
let sorted = subject.split('').sort().join(); // => 'eilnst'
let list = 'enlist\ninlets\nlisten\nsilent\ntinsel';
list = list.split('\n').filter((word) => {
word = word.split('').sort().join();
return word == sorted;
}).join('\n'); // => 'enlist\ninlets\nlisten\nsilent\ntinsel'
Это довольно простой подход. Это можно сделать с помощью некоторых оптимизаций, таких как сначала проверка длины слова, чтобы отсеять слова, которые не могут быть анаграммами, но это хороший способ начать.
Я так не делал.
Я рассуждал следующим образом: это был технический тест для компании, работающей с большими объемами данных. Можно даже назвать это большими данными. Худшее, что я мог сделать, по крайней мере, я так думал, - это сдать технический тест, который плохо масштабировался. Я с самого начала думал о масштабируемости. Что произойдет, если список входных слов состоит из 100 слов? А что, если он состоит из 1 000 000 слов? Что, если бы это была немного другая проблема и нам разрешили слова длиной 100 символов? Это все еще эффективный с точки зрения вычислений подход? Конечно, перебирая весь несортированный список, а затем выполняя сортировку по каждому слову, выполняются сразу две вещи, которые могут оказаться ненужными ... если мы найдем другой способ.
Компьютеры могут делать очень много, но о том, чтобы требовать меньше от вашего процессора, можно многое сказать. То есть, вместо того, чтобы заставлять компьютер выполнять всю эту сортировку, что, если бы мы заставили его выполнять умножение? Каждый символ имеет уникальный код символа, связанный с ним (целое число). Так почему бы нам просто не преобразовать каждое слово в его числовой эквивалент, а затем сравнить произведение слова?
Простой.
Я ушел, торопясь воплотить в жизнь то, что я считал проблеском умеренного гения. Не осознавая очевидного: даже если анаграмму можно проверить по двум словам, имеющим одинаковый код символа продукта, это не означает, что этот продукт уникален.
Тупой.
Я сдал свой технический тест, все тесты для крайних случаев прошли, прежде чем я осознал свою ошибку. Теоретически должно быть достаточно легко построить критические примеры. Все, что нужно было сделать, - это найти слово, которое имеет тот же код символа, что и другое слово, но не тот же набор символов. Если все эти коды не являются простыми числами, а это не так, их произведение не будет уникальным.
let subject = 'silent';
let charCodeProduct = subject.split('').map((value, index) => {
return subject.charCodeAt(index);
}).reduce((a, b) => a * b); // => 1680671916000
К счастью для меня, в примере предметного слова ‘silent’ charCodeProduct равнялось 1680671916000. Чем длиннее слово, тем меньше вероятность того, что произойдет коллизия, то есть алгоритм сработает при ложном срабатывании.
Урок усвоен? Ну, кроме «бездумно гуглить, а потом начинать писать код», которое применимо практически в любой ситуации, урок состоит в том, что если вы собираетесь выполнить нестандартную реализацию простой задачи, вы Лучше сделай это правильно. Стоит потратить несколько минут на то, чтобы все записать и подумать, прежде чем спешить, чтобы приступить к реализации! Даже в техническом тесте.
Фактический способ сделать это эффективно, и что бы я сделал, если бы я начал это снова завтра, - это использовать простое разложение. Сначала вы присваиваете каждой букве от «a» до «z» простое число, начиная с 2 для «a» и, наконец, со 101 для «z». Вы должны определить таблицу поиска где-нибудь в своей программе. Затем вместо преобразования каждого символа в его уникальный код символа вы должны преобразовать его в его уникальное простое представление. Затем при вычислении продукта у вас будет произведение простых множителей. Этот продукт будет уникальным, и поэтому вы сможете избежать любых потенциальных столкновений, описанных в другом методе.
// not shown: some JavaScript monkeying around
console.log(LOOKUP_TABLE); // => { a: 2,
b: 3,
c: 5,
d: 7,
e: 11,
f: 13,
g: 17,
h: 19,
i: 23,
j: 29,
k: 31,
l: 37,
m: 41,
n: 43,
o: 47,
p: 53,
q: 59,
r: 61,
s: 67,
t: 71,
u: 73,
v: 79,
w: 83,
x: 89,
y: 97,
z: 101 }
Теперь мы можем преобразовать тему слушать в ее уникальный целочисленный эквивалент: 1 914 801 911. Как мы узнаем, что этот продукт уникален? Что ж, это одна из тех фундаментальных вещей в математике, которая пришла от греков. Вздох.
Я взглянул на своих интервьюеров, пытаясь пробормотать объяснение, почему я прошел технический тест таким ошибочным способом. Мой код был показан на экране телевизора. Мое резюме лежало на столе передо мной, с выделенными различными разделами. Три дружелюбных, но суровых лица смотрели на меня, ожидая ответа.
Мне пришлось объяснить не только простую факторизацию, но и мы быстро обнаружили другую проблему с моей реализацией, о которой я даже не думал до того момента. В JavaScript есть максимальный размер для целых чисел! Хорошо, конечно, это 2⁵³, или 9007199254740991, но со всеми этими продуктами, плавающими в моем коде, было бы немыслимо быстро выйти на этот предел. Чтобы представить действительно большие числа в JavaScript, вы должны работать с большой целочисленной библиотекой, использовать встроенный typeBigInt или, в качестве альтернативы, вы могли бы просто каким-то образом представить число в виде строки.
Моих полуобъяснений несколько убедило моих интервьюеров. Я дошел до самой интересной части. Я должен был рассказать о своем опыте в Makers, о проектах, которые прошли хорошо или не очень хорошо, и о навыках, которые я приобрел в процессе. После нескольких собственных вопросов я провел экскурсию по офисам, а затем меня поблагодарили за потраченное время и показали дверь. Я понятия не имел, плохо я справился или нет, и всю оставшуюся неделю мне оставалось мало что делать, кроме как закончить некоторые подготовительные работы для финальных проектов и дождаться вердикта.
Сегодня понедельник, и мы начали наш последний проект. Наша команда решила работать над веб-приложением с данными о местоположении и темой карт, а наш продукт имеет благотворительную тему: объединение нуждающихся с услугами и людьми, которые могут им помочь. В течение следующих двух недель я буду работать изо всех сил, чтобы закончить наш продукт, вместе с новой командой людей, с большинством из которых мне еще предстоит работать. Захватывающе!
Я также услышал о моем собеседовании.
Я прошел в следующий раунд! На этой неделе у меня собеседование с персоналом, и тогда я должен точно узнать, есть ли у меня работа. Кажется, всей этой суеты по поводу простой факторизации было недостаточно, чтобы их оттолкнуть.
Следите за обновлениями ... и помните, всегда рисуйте схему.
