Посібник із питань інтерв’ю Google: Видаліть повторювані символи за допомогою Python

В наш час інтерв’ю в Google - це велика мода. Але іноді співбесіди можуть отримати найкраще від нас. Особливо якщо це на посаду, яку ми дуже хочемо.

Я мав задоволення брати інтерв'ю у кількох провідних компаніях ще студентом і влаштуватися на роботу в Силіконову долину інженером-програмістом.

Моя мета - допомогти вам отримати ту мрійну роботу, яку ви завжди бажали!

Ми розглянемо класичне запитання, яке може з’явитися у вашому наступному інтерв’ю Google.

Попередження: якщо ви ветеран кодування, ви, напевно, вже знаєте, як вирішити це питання!

Якщо ви намагаєтеся влаштуватися на стажування або на повну робочу посаду в наступному році, то вам неодмінно виграє ця стаття. ???

ЗАПИТАННЯ: Якщо вам вказано рядок, видаліть будь-який повторюваний символ і поверніть новий рядок.

Якщо ви віддаєте перевагу відео для пояснення питання, я зробив його тут.

Як ми можемо бачити з наведеного вище прикладу, результат є "abc", оскільки ми видаляємо другі "a", "b" і "c".

Перш за все, давайте налаштуємо нашу функцію в Python 2.7.

def deleteReoccurringCharacters(string):

Для вирішення цього питання ми будемо використовувати специфічну структуру даних, яка називається HashSet.

Ви можете вважати набір подібним до масиву, за двома основними винятками.

  1. Це абсолютно невпорядковано
  2. Він не може містити дублікатів

Оскільки це невпорядковано, нам також знадобиться порожній рядок для зберігання символів, які ми додали до набору по порядку. Це буде рядок, який ми повертаємо.

Давайте налаштуємо обидві ці речі.

def deleteReoccurringCharacters(string): seenCharacters = set() outputString = ''

Тепер, коли ми створили потрібні нам структури даних, давайте поговоримо про наш алгоритм.

Через те, як набір працює в пам'яті, він має складність часу пошуку 0 (1).

Це означає, що ми можемо використовувати його для перевірки того, чи ми вже відвідували персонажа чи ні!

Наш алгоритм

Прокрутіть усі символи у початковому рядку та виконайте наступне:

Крок 1: Перевірте, чи символ вже є в наборі. Крок 2: Якщо його немає в наборі, додайте його до набору та додайте до рядка

Давайте подивимося, як це буде виглядати в коді ???

for char in string: if char not in seenCharacters: seenCharacters.add(char) outputString += char

Нам не потрібно турбуватися про випадок “інакше”, оскільки ми нічого не робимо з самим повторюваним символом.

Тепер залишилося лише повернути outputString.

Ось як виглядає готовий код:

def deleteReoccurringCharacters(string): seenCharacters = set() outputString = '' for char in string: if char not in seenCharacters: seenCharacters.add(char) outputString += char return outputString

І ось вам!

Тепер, якби це було співбесіда, ваш рекрутер запитав би вас про складність часу та простору.

Давайте зробимо невеликий аналіз.

Складність часу

Ітерація по всьому рядку має часову складність O (n), оскільки в самому рядку є n символів.

Для кожного з цих символів ми повинні перевірити, чи не бачили ми ... Однак, оскільки HashSet має час пошуку O (1), наша складність часу це не впливає.

Залишаючи нас з останньою часовою складністю O (n).

Складність простору

У гіршому випадку ми отримуємо рядок з усіма унікальними символами. Наприклад, “abcdef”.

У цьому випадку ми зберігали б усі n елементів у нашому рядку та наборі.

Однак ми також обмежуємося розміром англійського алфавіту.

Це хороший шанс запитати у нашого інтерв’юера, який тип символів вважається унікальним у рядку (великі / малі / цифри / символи).

Припускаючи, що початковий рядок міститиме малі літери з алфавіту, оскільки алфавіт скінченний, наш набір і вихідний рядок ніколи не може бути більшим за 26 символів.

Залишаючи нас із найгіршим сценарієм складності простору O (1).

Ви тепер знаєте, як вирішити питання інтерв’ю в Google!

Це питання, швидше за все, постане на ранніх стадіях співбесіди через його прямолінійність ... Як онлайн-тест або перший телефонний дзвінок.

Якщо ви вивчаєте візуальний світ, як я, перегляньте це відео, яке я зробив, пояснюючи далі рішення. Я створюю нове відео-посібник, яке щодня обертається навколо початку вашої кар'єри в галузі програмного забезпечення.

Я також розмістив готовий код на Github тут.

Дякуємо за перегляд, і удачі!

.a # 33