pytania do Ruby Interview: połączone listy i tabele hashowania

tej jesieni spędziłem trochę czasu na wywiadach w różnych miejscach w branży. Każdy, kto planuje to zrobić, wie, że wszystkie firmy zadają te same pytania. Mają one jednak tendencję do zróżnicowania trudności i zakresu. U podstaw doświadczenia Wywiad leżą algorytmy i struktury danych, czyli standardowe, pierwszego roku, undergrad rzeczy. Chociaż możemy spędzić cały dzień na ustalaniu, czy jest to dobra miara umiejętności programisty (prawie na pewno nie jest, zwłaszcza dla firm, których podstawową działalnością jest budowanie dość prostych aplikacji na iPhone ’ a), umowa polega na tym, że nauka gry jest lepsza (i na pewno bardziej lukratywna) niż jej unikanie.

większość materiałów przygotowujących do wywiadów wydaje się być albo w Javie, albo w c++, głównie ze względu na ich wszechobecność, a także fakt, że nie „robią zbyt wiele”, tzn. większość abstrakcji jest dość cienka. Ale nie ma powodu, dla którego Rubyista nie może przebrnąć przez wywiady z naszym wybranym narzędziem. W tym artykule omówimy kilka łatwych do średniej trudności problemów z wywiadem używając Ruby. W większości przypadków trudniejsze pytania na rozmowę kwalifikacyjną nie są trudne, ponieważ wiążą się z naprawdę skomplikowanym kodem; zamiast tego wymagają więcej przemyśleń i wglądu. Tak więc, zastanawiając się, jak robić łatwe rzeczy w Rubim, powinieneś być ustawiony na radzenie sobie z trudnymi problemami.

notka o stylu

ten artykuł nie jest o tym, jak napisać najbardziej sprytny Ruby. Chodzi o to, aby napisać jasny kod, który jest łatwy do zrozumienia, co jest często ważniejsze (szczególnie w kontekście rozmowy kwalifikacyjnej) niż użycie każdej możliwej sztuczki dostępnej w gramatyce Ruby. Tak więc przedstawiony kod jest tak prosty i zrozumiały, jak to tylko możliwe.

listy łączone

listy łączone są prawdopodobnie najczęściej testowanymi strukturami w wywiadach (z dużą konkurencją o pierwsze miejsce z tabel mieszanych.) W związku z tym dobrym pomysłem jest dogłębne zaznajomienie się z listami powiązanymi. Chociaż istnieje wiele innych źródeł opisujących koncepcję listy połączonej, podstawową ideą jest to, że lista połączona składa się z kilku węzłów (tj. fragmentów danych), a każdy węzeł zawiera łącze do następnego węzła. Czasami musimy użyć podwójnie połączonych list, w których każdy węzeł zawiera link do następnego węzła, jak również do poprzedniego.

zastanówmy się, jak zaimplementować strukturę danych listy połączonej, zanim zajmiemy się pierwszym problemem. To całkiem proste:

class Node attr_accessor :value, :next_node def initialize(value, next_node) @value = value @next_node = next_node endend

wszystko, co robimy, to utrzymywanie wartości każdego węzła i odniesienie do następnego węzła. Zajmijmy się najpierw najprostszą rzeczą, jaką możemy:

Given a node, print the linked list that begins with that node.

to całkiem proste. Uruchamiamy bieżący węzeł w podanym nam węźle, wypisujemy wartość (lub dodajemy ją do łańcucha), a następnie przenosimy nasz bieżący węzeł do atrybutu @next_node tego węzła. Tutaj to jest w Ruby:

 class Node ... def to_s curr_node = self res = "" ... end

nie najpiękniejszy kod, ale działa. Możemy to przetestować:

 head = Node.new 8, nil snd = Node.new 7, nil head.next_node = snd puts head

co daje nam . OK, zróbmy coś trochę bardziej skomplikowanego:

Reverse a linked list given its head.

jest to problem, który jest tak popularny, że prawie nikt go już nie używa. Rozwiązanie nie jest od razu oczywiste, ale staje się tak, gdy usłyszysz je milion razy. Zasadniczo rozwiązujemy ten problem rekurencyjnie. Biorąc pod uwagę węzeł, najpierw sprawdzamy, czy węzeł jest ostatnim z listy. Jeśli jest, to po prostu zwracamy natychmiast (tzn. odwrotność jest po prostu ). Jeśli nie, przekaż następny węzeł do naszej funkcji odwrotnej. Spowoduje to odwrócenie listy i umieszczenie węzła, który przekazaliśmy na końcu odwróconej listy. Następnie umieść nasz aktualny węzeł na „następnym” tej listy. Jest to nieco mylące ze względu na sztuczkę, że następny z bieżącego węzła faktycznie kończy się na końcu odwróconej listy, więc następny z następnego bieżącego węzła jest miejscem, w którym chcemy umieścić bieżący węzeł. Sprawdź to w kodzie:

def reverse_list(curr) return curr if curr == nil or curr.next_node == nil next_node = curr.next_node new_head = reverse_list(curr.next_node) next_node.next_node = curr curr.next_node = nil return new_headend

kod jest bardzo prosty. „Trick” przychodzi next_node.next_node = curr. Ponieważ wiemy, że następny węzeł curr będzie na końcu odwróconej listy, po prostu przyczepiamy currdo końca następnego węzła curr. Spójrzmy na inny problem.

Implement a stack using a linked list.

przede wszystkim wyjaśnijmy, co rozumiemy przez stos. Zasadniczo, to jest jak stos książek siedzących na biurku. Możesz umieścić rzeczy na górze (nazywa się to push) i możesz zdjąć ostatnią książkę, którą tam umieściłeś (nazywa się to pop). Istnieje wiele sposobów na zaimplementowanie stosu z połączoną listą i wybierzemy jeden z nich.

będziemy śledzić górę stosu jako początek połączonej listy. Następnie, chcemy wcisnąć rzeczy na górę stosu, po prostu zmienimy nagłówek listy i wskażemy następny węzeł nowej głowicy na starą. Jeśli chcemy coś zdjąć, po prostu przesuwamy głowicę (pozwolimy, aby zbieracz śmieci zajął się dealokacją starej głowy). Rzućmy okiem:

class Stack attr_reader :head def initialize @head = nil end def push(value) new_head = Node.new value, @head @head = new_head end def pop @head = @head.next_node endend

jak widać, wszystko co robimy to tworzenie głowy na push i przesuwanie głowy do następnego węzła na pop. Możemy to przetestować:

stack = Stack.newstack.push 3stack.push 5stack.push 7stack.popstack.push 8print stack.head

jest jednak kilka istotnych rzeczy, które pominęliśmy. Co się stanie, jeśli wywołasz pop na pustym stosie? Powinieneś omówić takie przypadki z ankieterem i wymyślić sposób ich obsługi (np. rzucić wyjątek).

tabele skrótu

tabele skrótu są kolejną strukturą danych, którą musisz mieć w dół, aby zaliczyć te wywiady. W Ruby, tabele skrótów są instancjami Hash. Chociaż prawdopodobnie możesz ujść na sucho ze słabym zrozumieniem wewnętrznych elementów tabel hashowych (np. uniwersalnego hashowania, łańcuchowania itp.), rozumiejąc, że rzeczy mogą się w pewnym momencie przydać. Prawie każdy podręcznik algorytmów da ci tę informację.

w przeciwieństwie do list połączonych, nie potrzebujemy własnej implementacji tabel hashowych, ponieważ są one częścią biblioteki Ruby i tylko kilku osobom zależy na tym, czy możesz zaimplementować tabelę hashową od zera. Przyjrzyjmy się łatwemu problemowi:

Remove duplicates in an array of numbers.

oto co zrobimy. Umieszczamy każdą liczbę w tabeli hash jako klucz, a następnie zwracamy klucze na samym końcu. Jeśli napotkamy liczbę, którą już widzieliśmy, to nic wielkiego, ponieważ oznacza to, że już umieściliśmy ją w tabeli hash.

def remove_duplicates(list) set = {} list.each do |el| set = 1 end set.keysend

więc jaki jest sens używania tutaj tabeli hash? Tabela pozwala nam w stałym czasie sprawdzać, czy dany element już widzieliśmy, czy nie. To pozwala na uruchomienie tego kodu w czasie liniowym. OK, na coś trochę bardziej zaangażowanego:

dwa ciągi są uważane za anagramy, jeśli składają się z tych samych liter (z tą samą częstotliwością każdej litery), chociaż mogą być w innej kolejności. Napisz funkcję, aby określić, czy łańcuch jest anagramem innego.

innym sposobem na sformułowanie tego pytania jest to, że próbujemy ustalić, czy częstotliwości każdej litery w dwóch ciągach są takie same. Możemy obliczyć częstotliwości za pomocą tabeli skrótów dość łatwo. Po prostu iterujemy nad ciągiem znaków i dodajemy wartość dla każdej litery. Następnie porównujemy i sprawdzamy, czy te dwie częstotliwości są takie same. Tutaj jest w Ruby:

def get_freq(str) freq = Hash.new(0) str.each_char do |chr| freq += 1 end freqenddef check_anagram(str1, str2) return get_freq(str1) == get_freq(str2)end

jedyny niezwykły punkt to Hash.new(0). Tworzy to hash, w którym” domyślną ” wartością dla dowolnego klucza jest 0. Może się to wydawać nieco trywialne i nieistotne, ale jest to niezwykle przydatne w przypadku prawie każdego problemu związanego z tabelą mieszania, ponieważ często używasz tabel mieszania do liczenia częstotliwości.

to tyle za ten krótki kawałek o rozmowie z Ruby. Chociaż rzeczy, które omówiliśmy do tej pory, są dość proste, zaskakujące jest, jak łatwo jest spieprzyć najbardziej podstawowe rzeczy, gdy masz rozmówcę oddychającego przez szyję. W kolejnej odsłonie zajmiemy się drzewami binarnymi i implementacją bufora LRU.