Swifty Finch

Собеседование, работа над ошибками

swift
interview
story
04.03.2018
5 мин

Совсем недавно я проходил собеседование в одну IT компанию на должность iOS разработчика и столкнулся с интересными проблемами. В этой статье я хотел бы поделиться своей работой над ошибками.

Для кого эта статья?

Статья может быть интересна в первую очередь тем, кто планирует проходить собеседование на языке Swift с решением практических задач.

Фальстарт 🏃🏻

Собеседование проходило по скайпу и было необходимо решить задачу и запрограммировать решение в онлайн редакторе без подсветки кода. Сейчас многие компании проводят такие собеседования, например в редакторе collabedit.

Звонок, быстрое знакомство. Выбрал язык Swift, так как сейчас это мой основной язык. Затем рассказали простое задание.

Написать функцию проверяющую является ли строка палиндромом.

Я очень обрадовался, когда услышал это описание. Простое задание и я уже писал код решения на С++ несколько раз. Почти сразу приступил к написанию функции, но внезапно интервьюер меня остановил. Оказалось, он объяснил только первую часть задания.

bool isPalindrom(const string&; input) {
    for (int index = 0; index < input.size() / 2; ++index) {
        if (input[index] != input[input.size() - index - 1]) {
            return false;
        }
    }
    return true;
}

Полное задание

Написать функцию проверяющую является ли строка палиндромом. Строка может содержать любые символы. Нужно учитывать только числа и латинские буквы. Регистр не важен. Решение должно работать за константную память и линейное время.
Пример палиндрома: Madam I’m Adam.

И опять я выдохнул спокойно. Похожая задача мне уже встречалась на С++. Нужно было написать тесты для такой функции, а затем система перебирала разные реализации и проверяла покрыты ли все случаи. Хотя, погодите. Я не писал саму реализацию функции.

Предложили рассказать решение устно. С ходу сказал, что заведу два курсора: один на начало, а второй на конец. Затем буду идти к центру и проверять каждый символ. Если символ не нужно учитывать, то пропускаем его, иначе сравниваем символы. Если символы различны, то это не палиндром. Иначе двигаемся дальше до центра и если добрались, значит это палиндром.

Решение казалось стройным и логичным. Интервьюер сказал, что похоже на хороший план и пора его реализовать. Я, абсолютно уверенный в своих силах, принялся писать код. На самом деле я допустил одну очень неприятную ошибку уже в теории.

От теории к практике 👨🏻‍💻

Через несколько минут вспомнил, что строки в Swift не так просты как в С++. Если коротко, то в Swift символы строки не фиксированной длины и поэтому нельзя обращаться к символу по целочисленному индексу. Для того чтобы обратится к символу необходимо высчитать размер всех символов до него. Подробнее об этом можно почитать в этой замечательной статье.

let test = "Madam I'm Adam"
print(test[test.startIndex]) // M
print(test[test.index(before: test.endIndex)]) // m
print(test[test.index(test.endIndex, offsetBy: -1)]) // m
print(test[test.index(test.endIndex, offsetBy: -2)]) // a

После этого задумался как бы проверить, что символ является числом или латинской буквой. В C++ это делается очень просто, можно смело задать диапазон с помощью операторов сравнения. В Swift обычно используют CharacterSet. Проверяют символ на вхождение в определенное множество.

extension Character {
    var isLetterOrNumber: Bool {
        return !["a"..."z", "A"..."Z", "0"..."9"]
            .filter { $0 ~= self }
            .isEmpty
    }
}

Рокировка 🐴

Внимание! Рокировка никак не связанна с конем

Я знал синтаксис примерно, хотя в Swift он немного меняется с выходом новых версий. Объяснил интервьюеру, не уверен что это решение будет компилироваться и он усомнился в моих знаниях. Тогда я предложил переписать всё на С++, и мы сошлись на этом.

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

Фиаско 🙄

Да, я благополучно провалил это собеседование. Подумал, а почему в Swift нет итераторов? С ними было бы проще.

Решил написать простую реализацию, разместил всё на Github. Также развернулось небольшое обсуждение на форуме SwiftBook. Добавил тесты и альтернативное решение одного из читателей. А ниже только решение этой задачи. На мой взгляд получилось очень просто.

func isPalindrom(_ input: String) -> Bool {
    guard !input.isEmpty else { return true }
    let left = input.iterator(input.startIndex)
    let right = input.iterator(input.endIndex)
    --right
    
    while (left < right) {
        while left < right && !left.character.isLetterOrNumber {
            ++left
        }
        while left < right && !right.character.isLetterOrNumber {
            --right
        }
        
        if left >= right { break }
        if !left.character.isCaseInsensitiveEqual(right.character) {
            return false
        }
        ++left
        --right
    }
    return true
}

Выводы 💁🏻‍♂️

  • Очень советую потратить пару минут в начале и записать условие задачи. Я каждый раз жалею, что не делаю этого. Думаю это поможет сконцентрироваться на решении, а не на запоминании всех деталей. Если вы начинаете уточнять детали, о которых забыли, в процессе написания кода — это ещё один аргумент за этот пункт;
  • Выбирайте язык под задачу, если у вас есть такая возможность. Swift замечательный язык, но некоторые простые задачи требуют более углубленных знаний и запоминания более сложного синтаксиса. К тому же, я не упоминал об этом, но перебор строк по индексам нужно делать аккуратно. Иначе получите сверхлинейное время работы общего решения;
  • Перед тем как приступать к реализации, убедитесь что вы не допустили ошибок в теории. Изначально я полагал, что палиндром нужно перебирать до центра. Это кажется логичным в первом простом решении. На самом деле это не так. В более общем решении нужно перебирать пока курсоры не встретяться. Пример палиндрома: AA]/;/;/,. Во время реализации я старался придерживаться идеи, в которой был уверен;
  • Подбирайте тестовые данные для вашего теоретического и практического решения. Хорошо подобранные тесты помогают понять задачу до конца. Также решать её быстрее, без множественного переписывания решения;
  • Был ещё один небольшой, но очень неприятный момент. В редакторе, в котором я писал код, глючил курсор. Ввод происходил не на месте курсора, а где-то рядом. И то же самое с удалением. Ощущение, что вы просто нахреначились. Или если играли в игры с инвертированным управлением, то это очень похоже. На это тоже ушло время и нервы. Своего рода экстрим. Лучше сразу договариваться о смене редактора.

Можно поспорить на сколько показательны такие собеседования, но статья совсем не об этом. Я не включил это в выводы, но лично для меня самое сложное — просто не нервничать.

На этом всё, спасибо за внимание. Надеюсь статья будет вам полезна и вы не допустите моих ошибок. Используйте выводы и всё у вас будет просто отлично! Но, это не точно. Удачных вам собеседований!

Если вы начинающий iOS разработчик или вам интересны алгоритмы и структуры данных, возможно вам могут быть интересны мои другие статьи. Также вы можете подписаться в Twitter и получать уведомления о новых статьях.