Если вы когда-либо искали работу в качестве разработчика, вы, несомненно, столкнетесь с «собеседованием по программированию».
Тот ужасающий момент, когда кто-то сообщает вам о проблеме, о которой вы не слышали со второго семестра в колледже, и ожидает, что вы решите ее быстро и правильно без автозаполнения, переполнения стека или компилятора.
Scaaary ... Я знаю.
Но основная проблема с собеседованием по кодированию - это не условия, в которых вам приходится работать, или суждение ваших коллег, или что-либо из того, что мы связываем со стрессом, отказом и неудачей во время собеседования.
Дело в том, что, поскольку мы сталкиваемся с основными проблемами, мы склонны предлагать базовые решения, которые являются грязными, сложными и созданы для работы только для этих конкретных случаев использования.
И я бы сказал, что для того, чтобы по-настоящему оценить, насколько кто-то хороший инженер, вы должны увидеть, насколько хорошо они могут изобретать свое решение проблемы.
Потому что, если вы еще не решаете запутанные воображаемые проблемы, касающиеся повторного использования, обслуживания и масштабирования, в своей голове; ты вообще проблему решаешь? Я прав?
Так что, пожалуйста, присоединяйтесь ко мне, поскольку я делаю именно это! Ради забавы! (Да, мне так скучно.)
FizzBuzz
Итак, давайте рассмотрим одну из самых простых задач: «FizzBuzz». Идея состоит в следующем: если число делится на 3, вы распечатываете «Fizz», если оно делится на 5 «Buzz», если оно делится на оба: вы догадались, «FizzBuzz». Если ничего из этого не подходит, просто распечатайте номер.
Итак, базовая игра будет выглядеть так:
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16
Большинство программистов, столкнувшихся с этой проблемой, напишут что-то вроде этого (конечно, на Java):
for (int i = 1; i <= n; i++) {
String output = "";
if (i % 3 == 0) output += "Fizz";
if (i % 5 == 0) output += "Buzz";
if (output == "") output += i;
System.out.println(output);
}
Но, допустим, вы похожи на меня и ненавидите Java. Что ж, у меня лично есть моральные возражения против циклов, и я решил использовать вместо них функциональный язык программирования.
Так что с этого момента я буду использовать OCaml: французский язык функционального программирования, известный как менее известный, но более очаровательный кузен Haskell.
Моделирование нашей проблемы
Поскольку мы собираемся переусердствовать с этой проблемой, мы не будем напрямую работать с правилами FizzBuzz до самого конца. А пока мы будем иметь дело с абстрактным набором правил, которые можно передать волшебной функции, которая сообщит нам результат.
Какие правила?
Представьте себе правило как оператор if в приведенном выше коде Java. Правила сообщают нашей программе, что писать с указанием чисел. Мы определим их в виде наборов условий и строк.
Если условие выполнено, мы добавим строку к выводу функции. Например, Правило в FizzBuzz будет таким:
let rule = (fun n -> n % 3 = 0), "Fizz";;
Это означает, что если вход делится на 3, добавьте к выходу «Fizz».
Понятно? В порядке. Вот так!
Время реализации!
Первый! Поскольку я не хочу импортировать какие-либо модули в свой код, я буду реализовывать две довольно распространенные функции: map и reduce.
let rec reduce l f a = match l with
| x::xs -> reduce xs f (f a x)
| [] -> a;;
let rec map l f = match l with
| x::xs -> (f x)::(map xs f)
| [] -> [];;
Следующий! Нам нужно подумать о последней проверке пустой строки.
Поскольку мы работаем с абстрактными правилами, мы не знаем, хочет ли одно из них вывести пустую строку. Таким образом, мы не можем полагаться на пустую строку, означающую, что правило не применяется. Поэтому лучше было бы вместо этого абстрагироваться от этого случая как Необязательного. Что уже определено в OCaml как:
type 'a optional = Some of 'a | None
Теперь, чтобы правильно работать с Optionals, нам потребуются следующие функции:
1. Оператор Элвиса:
let ($) a b = match a with
| Some(a) -> a
| None -> b;;
Эта функция просто проверяет, определено ли a. В этом случае возвращается a. В противном случае будет возвращено значение по умолчанию b.
Примечание. Оператор Элвис обычно пишется с помощью (? :). Однако из-за ограничений OCaml на инфиксные операторы использование (? :) невозможно. Поэтому я решил использовать ($). Просто потому, что!
2. Карта по желанию:
let mapOptional i f = match i with
| Some(i) -> Some(f i)
| None -> None;;
При этом значение i будет передано в f, если оно присутствует, и в противном случае будет возвращено значение Нет.
3. Объединение строки поверх необязательной строки:
let (^?) a b = (mapOptional a (fun a -> a ^ b)) $ b;;
Последний имеет очень простую цель. Если a имеет значение, верните ab. В противном случае выведите b.
Теперь, когда у нас есть опции, мы можем приступить к написанию нашей волшебной функции.
Начнем с вспомогательной функции:
let helper a n (f, s) =
if (f n) then
Some(a ^? s)
else
a;;
Что проверит условие f на n и, если оно соблюдается, вернет аккумулятор a, объединенный со строкой s . В противном случае только a.
И теперь мы можем назвать это:
let output n r f =
(reduce r
(fun a x -> helper a n x)
None) $ (f n);;
Мы сократим все правила r с помощью нашего помощника: начиная со значения None и соберем все Strings. Если никакие условия не выполняются, результатом будет Нет. В этом случае мы вернем значение по умолчанию, полученное при вызове f на n. (В случае fizzbuzz f будет преобразовывать целое число n в String..)
И это все, что нам нужно. Теперь нам нужно только скормить этим функциям правильные входные данные.
Для этого давайте начнем с того, что сможем сгенерировать ряд чисел:
let rec range a b =
if a < b then
a::(range (a + 1) b)
else
[b];;
И возможность вычислить mod целого числа a с учетом базы b (, поскольку она не определена в OCaml):
let rec (%) a b =
if a < b then
a
else
(a - b) % b;;
Теперь нам нужны правила, которыми мы будем кормить нашу функцию:
let rules = map [3, "Fizz"; 5, "Buzz"] (fun (a, b) ->
(fun n -> n % a = 0), b
);;
И, наконец, мы определяем функцию fizzbuzz, которая будет выводить все результаты до n:
let fizzbuzz n =
map (range 1 n) (fun x -> output x rules string_of_int);;
Готово!
Если вы вызовете fizzbuzz с 15, вы получите результат:
["1"; "2"; "Fizz"; "4"; "Buzz"; "Fizz"; "7"; "8"; "Fizz"; "Buzz"; "11"; "Fizz"; "13"; "14"; "FizzBuzz"]
Так? Что мы узнали?
Ну не очень. Здесь нет уроков по стилю или системному дизайну.
Некоторые из вас наняли бы меня после прочтения этого. Другие (откровенно говоря, большинство), вероятно, хотели бы убить меня за то, что я даже осмелился написать такой код. Но скажу так:
У вас гораздо более информированное мнение о том, как я кодирую, основываясь на этом, чем на небольшом фрагменте Java, который любой может написать. И разве это не более полезно, чем любое «Интервью по программированию»?
Так что я оставлю вас с этим. Если вы когда-нибудь кого-нибудь берете на интервью. Может быть, просто попросите их переосмыслить свое решение и посмотреть, что на самом деле происходит под капотом.
Вы можете быть удивлены ...
