Предисловие
Кто из iOS разработчиков не мечтал о работе в престижном месте вроде Yandex или Avito. К сожалению, про мечты на собеседованиях спрашивает только hr, а вот интервьюеры из числа разработчиков задают вопросы немного другого характера. Чем отличается reference type от value type или bounds от frame? Вопросы, который каждый из нас слышал не раз на собеседованиях. Если ваше интервью начинается с вопроса про отличия значимого и ссылочного типов или в духе “расскажите ка нам про SOLID”, то вы явно на пути трудоустройства в ООО “Так себе перспективы“.
В приличной компании у вас такую ерунду не спросят. Готовьтесь к вопросам про диспетчеризацию, side table и underlying queue. Знания подобных нюансов никоем образом не помогут добиться 60 FPS при скролле, нагруженных элементами ячеек и не сделают вас почетным девелопером России. Они помогут распознать в вас человека, который не просто 4 года менял констрейнты в xib-ах и теперь считает себя Senior iOS Developer, а действительно интересуется платформой. Для меня всегда останется загадкой, в какой момент человек решает, что он достиг уровня Middle или Senior. Наверное участвует в общероссийских соревнованиях, на которых РОС-ГОС-iOS присуждает разряды и звания за выполнение нормативов и призовые места.
Вернемся к собеседованиям. Мало того, что престижный работодатель обязательно задаст заковыристые вопросы по платформе, так еще обязательно спросит про архитектуру. Ждите вопроса: “Почему на прошлом месте вы использовали именно VIPER, а не MVVM?“. Могут поинтересоваться: “Чем плох MVC?“. Ну и последним гвоздем в крышку гроба будут алгоритмы. Даже если вы блестяще разбираетесь в iOS и архитектуре мобильных приложений, но не знаете слабые стороны массивов и не можете оптимизировать поиск элемента, то после собеседования ждите на почту ответ:
На просторах русскоязычного интернета полным-полно статей про алгоритмы и структуры данных. Единственный недостаток, который может омрачить изучение — скудность примеров и реализаций на Swift. Достаточно сложно разбираться в этой теме, когда тебе подсовывают много непонятных слов и еще больше непонятных примеров на C++.
Для всех, кто хочет каждый день пить смузи в шикарных офисах и на встречах выпускников рассказывать как он один тащит на себе всю мобильную разработку Сбера, я подготовил пару статей по структурам данных. Статьи рассчитаны на разработчиков, которые уже знакомы с дженериками, работали с массивами/множествами/словарями, разбираются в отличиях классов от структур и делают вид, что понимают рекурсию. Я не буду расписывать теорию. Это уже сделано до меня и уверен, что достаточно информативно. Сосредоточимся на примерах.
Связаный список
С теорией поможет википедия. Начнем с создания того самого узла.
*обязательно смените свою цветовую схему Xcode на темную иначе не видать вам работы в Mail
Внимательный читатель должен задаться вопросом: «Почему мамкин девелопер решил реализовать узел как класс, а не структуру? Статья же про структуры данных!». Обсудить это решение предлагаю в комментариях. Перейдем к самому связаному списку. Начальная реализация будет выглядеть так:
Каждый уважающий себя эксперт-зануда отметит, что WeakReference какой-то неведомый тип и справедливо потребует реализацию.
Добавим в реализацию методы, отвечающие за наполнение нашего списка:
* Complexity O(1) справедлива только в случае, если нет необходимости копировать структуру. В противном случае у нас будет сложность O(n). Это относится ко всем mutating методам
Добавим методы, отвечающие за удаление из списка:
*@discardableResult избавит нас от необходимости писать "_ = " перед вызовом функции, когда возвращаемое значение нам не интересно
Наша поделка уже выглядит как рабочий связаный список. Попробуем сделать ее максимально Swift-ориентированной. Для этого нам осталось реализовать всего две вещи: BidirectionalCollection протокол и copy-on-write технику. Начнем с протокола. Методов в нем совсем мало и самое сложное это понять и реализовать Index.
Замечательно! Теперь нашему списку доступны все плюшки коллекций. Можем применить к нему map, compactMap, filter, contains и тд. Настала очередь copy-on-write. Реализуем метод copyIfNeeded() из-за отсутствия которого у вас сейчас компилятор намекает на то, что код писал не Д'Артаньян:
Желающих задать умный вопрос или указать на недочеты жду в комментариях.
P.S. Благодарю ivlevAstef за помощь в устранении недочетов. Рабочей реализации без weak обёрток пока никто не предложил.
Код на GitHub
Комментарии (23)
DevlabStudio
01.08.2019 00:49Очкнь интересный стиль подачи материала. Прочлось на одном дыхании. Спасибо!
snamef
01.08.2019 11:07Статьи рассчитаны на разработчиков, которые уже знакомы с дженериками, работали с массивами/множествами/словарями, разбираются в отличиях классов от структур и делают вид, что понимают рекурсию.
неа, основные непонятки с этим странным SWIFT и употреблением weak или с утверждением
копирование необходимо если сильных ссылок больше одной
и почему вы пытаетесь копировать если надо после каждого действия со списком и думаете что там будет O(1)?
и почему сразу двойной связный список
и вообще почему вы представляете в обьектном виде, а не связный список из индексов (int) на обычный массив…
mamkin_developer Автор
01.08.2019 11:22Спасибо за замечание о сложности операций. Copy-on-write я реализовывал в последнюю очередь и забыл оставить пометку об изменениях.
По поводу необходимости копирования: если на первый контейнер нашего списка ссылается кто-то еще (копии нашей структуры), то нам необходимо создать новый экземпляр списка и работать с ним иначе изменения нашего списка отразятся на всех его копиях. Контейнеры же ссылочный тип.
Сразу двойной связанный список, потому что мы здесь не в игрушки играемся! Простых примеров в интернете полно.
ivlevAstef
01.08.2019 18:15На самом деле у меня к реализации есть замечание:
Меня смутил WeakReference а ровном месте. То есть протокол принуждаем людей сразуже использовать weak ссылку, а не просто получить первый элемент — что обычно и хочется.
Все это ради Copy-on-write?.. ну а я сделаю вот так:let node = list.first.nodeто есть решение еще и не назовешь надежным. А потом так:let node = list.first.node.nextи поведение резко изменится.
Но давайте учить людей правильно — внешний интерфейс всегда важнее технических проблем. А в данном случае техническая проблема решается легко, да и делает использование надежней:
struct LinkedList<T> { private class Reference { } private var ref = Reference() ... }
И вот этой переменной уже можно пользоваться, для получения количества копий именно структуры. При изменении смотрим количество ссылок, и если больше одной, то делаем тоже самое + пересоздаем переменную (дабы каждый раз не копировать).
P.S. ну и я закрываю глаза, на тот факт, что никто не мешает получить node и поиграться таким образом, что весь лист будет сломан — у Node то нет полей доступа, аля
private(set)
P.P.S. не знаю почему, но ваша статья меня привлекла — рассказано в самом деле хорошо. Да и LinkedList я тоже люблю — на нем много какие особенности языка всплывают.
mamkin_developer Автор
02.08.2019 21:44Умные вещи говорите. Решая проблему, которая ломала реализацию списка в книге за 60$, я и не мог подумать, что решение может быть таким простым. Снимаю шляпу перед вашей внимательностью. Это я про ссылку на пустой приватный класс вместо ссылки на первый контейнер.
Может быть посоветуете как можно элегантно закрыть доступ к модификации содержимого контейнеров, но так чтобы внутри класса LinkedList логика не изменилась? Всем классом сидим голову ломаем и никаких результатов.mamkin_developer Автор
03.08.2019 10:24Пока перенесу Node класс в файл к LinkedList и закрою все сеттеры fileprivate доступом.
ivlevAstef
01.08.2019 12:26Начало статьи породило куча вопрос:
1. Почему Avito и Yandex? Я ничего против них не имею, но полно и других.
2. Когда я собеседовался в Yandex на iOS, то меня почему-то спрашивали именно те вопросы которые попали в категорию «так себе перспективы»
3. Почему вдруг эти вопросы плохие? Мне на собеседованиях один кандидат из 20 способен не только сказать заученную фразу, но и на практике доказать, что он понимает её… остальные не способны без компилятора сказать, что напишет код из 5 простых строчек и как поведение меняется в зависимости от типа.
Про Solid промолчу — не люблю этот вопрос, и не обращаю внимание если человек не знает что это, но когда люди говорят, что знаю… см начало пункта.
А ну и замечание по коду — писать ‘guard a != b else’ это кощунство над людьми которые будут читать — два отрицания за место обычного: ‘if a==b’.
P.S. с тем что знание алгоритмов полезно я соглашусь. Правда стоит начать с более важных вещей, например что такое словарь, массив, множество — сложность операций, как реализовано в iOS. Вроде бы этим пользуются каждый день, но как устроено мало кто знает.mamkin_developer Автор
01.08.2019 14:19- Я ждал вопроса «почему яндекс?!». Выбор пал на эти компании, потому что они известны своими «сложными» и долгими отборочными этапами. Разговоры о престижности и тд это все очень субъективно.
- «Так себе перспективы» это не всегда о компании в целом. Даже в яндексе найдутся команды, где работать скучно и платят меньше.
- То-то и оно! Если у Вас в сторе 20 проектов, 5 лет опыта работы над проектами с многомиллионной аудиторией, а у Вас спрашивают вопросы для отсева полных новичков, то тут два варианта. Первый — вам не верят, второй — вас собеседуют по вопросам из интернета.
- Про if и guard это все субъективная вкусовщина.
ivlevAstef
01.08.2019 17:483) Ну… я лично бы не верил. Я даже себе на собеседовании бы не верил :).
И встречал людей с N проектами N лет опыта, но которые не понимаю разницы между этими всеми вещями, даже на базовом уровне.
Хотя меня тоже бы расстроили подобные вопросы на собеседовании, но только если не было бы развития вопроса в глубь. Например вопрос "отличие reference type от value type" — хороший. На него ответит junior и senior по разному, и сломаются они на разных стадиях развития этого вопроса. Ибо к нему потом сверху идут weak/unowned/strong, захват, замыкания, аналоги в obj-c. Короче тема хорошо развивается, и если человек на самом деле крут, то доходит до разговора — а как это внутри устроено.
4) Ну в общем счете да, и я даже не настаиваю как писать. Но люди так пишут до тех пор пока не ошибутся в этом условии по несколько раз, хотя кто-то продолжает так писать.
guard letчитается легко и это его назначение — разворот области видимости, аguard без letимеет по факту отрицание в себе, и если условие с отрицанием, да еще и не одно условие, то начинаются серьезные проблемы.
В прочем если отстранится от swift то
guard без letпо стилю мышления похож наassert.
Не знаю как кто, но я еще не видел людей которые бы assert-ы всегда писали с первого раза верно — в них часто условие при написании инвертят, и позже исправляют.
Хотя разговор в этом плане похож на табы vs пробелы :) Так как есть человек с самого первого дня пишет на swift с guard, то ему будет одинаково легко читать как guard так и if.
lenina15i25
02.08.2019 21:44«Про if и guard это все субъективная вкусовщина.»
Такой код становится не очевидным и менее читабельным, но если ты сам на проекте, можно писать хоть ногой. Например, через switch.
domix32
01.08.2019 13:45А где же тесты?
mamkin_developer Автор
01.08.2019 13:52Тесты в проекте на github
domix32
01.08.2019 19:53В
main.swiftвижу только использование. Ни папки test c кейсами ниassertов, ни фикстур сXCTestCaseни каких либо еще вариантов тестов в упор не вижу.
sm4tlm
02.08.2019 21:44так почему мамкин девелопер решил реализовать узел как класс, а не структуру?)
mamkin_developer Автор
03.08.2019 13:05Контейнеры должны ссылаться друг на друга, а не копировать значения. Value Type для контейнера не подходит. Вот здесь можно ознакомиться более детально, правда на заморском языке.
omaksim
03.08.2019 14:52-1Такие статьи только вредят. Смысл структуры данных скрыт за нагромождением костылей вместо нормального использования языка.
Bhudh
Странно, ссылка на Википедию правильная, а в статье везде связанный
свитерсписок…mamkin_developer Автор
Русский язык слишком сложный! Спасибо
Bhudh
Настолько сложный, что до сих пор не исправлено нормально…
Воспользуйтесь Ctrl-C, Ctrl-V из Википедии, что ли.
mamkin_developer Автор
Могли бы не занудствовать, а сообщить о всех опечатках через Ctrl+Enter. Раз вы так переживаете за орфографию.