Ръководство за въпроси за интервюта в 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