perguntas da entrevista Ruby: listas vinculadas e tabelas Hash

passei algum tempo neste outono entrevistando em vários lugares da indústria. Como praticamente qualquer um que está planejando fazer isso sabe, todas as empresas fazem, basicamente, o mesmo sabor de perguntas. No entanto, eles tendem a variar em dificuldade e escopo. No centro da experiência de entrevista estão algoritmos e estruturas de dados, ou seja, material padrão, de primeiro ano, de graduação. Embora possamos passar o dia todo determinando se essa é uma boa medida de capacidade de programador (quase certamente não é, especialmente para empresas cujo negócio principal é construir aplicativos para iPhone bastante simples), o negócio é que aprender a jogar o jogo é melhor (e certamente mais lucrativo) do que evitá-lo.

a maioria dos materiais de preparação para entrevistas parece estar em Java ou C++, principalmente devido à sua onipresença, bem como ao fato de que eles não “fazem muito”, ou seja, a maioria das abstrações é bem fina. Mas, não há nenhuma razão para que um Rubiista não pode trabalhar o seu caminho através de entrevistas com a nossa ferramenta de escolha. Neste artigo, vamos passar por alguns problemas de entrevista de dificuldade razoavelmente fáceis de média usando Ruby. Na maioria das vezes, perguntas de entrevista mais difíceis não são difíceis porque envolvem código realmente complicado; em vez disso, eles só exigem mais pensamento e alguma visão. Então, ao descobrir como fazer as coisas fáceis em Ruby, você deve estar pronto para resolver os problemas difíceis também.

uma nota sobre estilo

este artigo não é sobre como escrever o Ruby mais inteligente possível. A ideia é escrever um código claro que seja fácil de entender, o que geralmente é mais importante (especialmente em uma configuração de entrevista) do que usar todos os truques possíveis disponíveis na gramática Ruby. Portanto, o código apresentado é feito para ser o mais simples e direto possível.

listas vinculadas

as listas vinculadas são provavelmente as estruturas mais comuns testadas em entrevistas (com forte concorrência pelo primeiro lugar nas tabelas hash.) Como tal, estar intimamente familiarizado com listas vinculadas é uma boa ideia. Embora existam muitas outras fontes para descrever o conceito por trás de uma lista vinculada, a ideia básica é que uma lista vinculada consiste em um monte de nós (ou seja, pedaços de dados) e cada nó contém um link para o próximo nó. Às vezes, temos que usar listas duplamente vinculadas nas quais cada nó contém um link para o próximo nó, bem como o anterior.

vamos descobrir como implementar a estrutura de dados da lista vinculada antes de trabalharmos no primeiro problema. É muito simples:

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

tudo o que estamos fazendo é manter o valor de cada nó e uma referência ao próximo nó. Vamos abordar a coisa mais simples que podemos primeiro:

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

isto é muito fácil. Iniciamos o nó atual no nó que nos foi dado, imprimimos o valor (ou o adicionamos a uma string) e, em seguida, movemos nosso nó atual para o atributo @next_node desse nó. Aqui está em Ruby:

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

não é o código mais bonito, mas funciona. Podemos testá-lo:

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

o Que nos dá . OK, vamos fazer algo um pouco mais complicado:

Reverse a linked list given its head.

Este é um problema que é tão popular que praticamente ninguém usa mais. A solução não é imediatamente óbvia, mas torna-se assim uma vez que você já ouviu isso um milhão de vezes. Basicamente, resolvemos esse problema recursivamente. Dado um nó, primeiro verificamos se o nó é ou não o último da lista. Se for, então voltamos imediatamente (ou seja, o reverso de é apenas ). Caso contrário, passe o próximo nó para nossa função reversa. Isso reverterá a lista e colocará o nó que passamos no final da lista invertida. Em seguida, coloque nosso nó atual no “próximo” desta lista. É um pouco confuso por causa do truque de que o próximo do nó atual realmente acaba no final da lista invertida, então o próximo do próximo do nó atual é onde queremos colocar o nó atual. Confira no código:

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

o código é muito simples. O “truque” vem em next_node.next_node = curr. Como sabemos que o próximo nó de curr estará no final da lista invertida, apenas colocamos currno final do próximo nó de curr. Vamos dar uma olhada em outro problema.

Implement a stack using a linked list.

em primeiro lugar, vamos esclarecer o que queremos dizer com uma pilha. Basicamente, é como uma pilha de livros sentados em sua mesa. Você pode colocar coisas no topo (isso é chamado push) e você pode tirar o último livro que você colocou lá (isso é chamado pop). Existem várias maneiras de implementar uma pilha com uma lista vinculada e escolheremos uma delas.

vamos acompanhar o topo da pilha como o chefe de uma lista vinculada. Então, queremos empurrar as coisas para o topo da pilha, simplesmente mudaremos o cabeçalho da lista e apontaremos o próximo nó da nova cabeça para a cabeça antiga. Se quisermos estourar as coisas, apenas movemos a cabeça (deixaremos o coletor de lixo lidar com a desalocação da cabeça antiga). Vamos dar uma olhada:

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

como você pode ver, tudo o que estamos fazendo é criar uma cabeça no push e mover a cabeça para o próximo nó no pop. Nós podemos testá-lo:

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

há algumas coisas cruciais que omitimos aqui. O que acontece se você chamar pop em uma pilha vazia? Você deve discutir casos extremos como este com seu entrevistador e encontrar uma maneira de lidar com eles (por exemplo, lançar uma exceção).

tabelas Hash

tabelas Hash são outra estrutura de dados que você precisa ter pat para ace essas entrevistas. Em Ruby, tabelas hash são instâncias de Hash. Embora você provavelmente possa se safar com uma compreensão fraca dos internos das tabelas de hash (por exemplo, hash universal, encadeamento, etc.), entender essas coisas pode ser útil em algum momento. Praticamente qualquer livro didático de algoritmos fornecerá essas informações.

ao contrário das listas vinculadas, não precisamos de nossa própria implementação de tabelas hash, pois elas fazem parte da biblioteca Ruby e também apenas algumas pessoas se importam se você puder implementar uma tabela hash do zero. Vejamos um problema fácil:

Remove duplicates in an array of numbers.

aqui está o que fazemos. Colocamos cada número na tabela hash como uma chave e, em seguida, retornamos as chaves no final. Se encontrarmos um número que já vimos, isso não é grande coisa, porque isso significa que já o colocamos na tabela de hash.

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

Então, qual é o ponto de usar a tabela hash aqui? A tabela nos permite verificar em tempo constante se já vimos ou não um elemento antes. Isso permite que este código seja executado em tempo linear. OK, em algo um pouco mais envolvido:

duas cordas são consideradas anagramas se forem compostas das mesmas letras (com as mesmas frequências de cada letra), embora possam estar em uma ordem diferente. Escreva uma função para determinar se uma string é um anagrama de outra.

outra maneira de enquadrar esta questão é que estamos tentando determinar se as frequências de cada letra em duas strings são as mesmas. Podemos calcular frequências com uma tabela hash com bastante facilidade. Nós apenas iteramos sobre a string e adicionamos o valor para cada letra. Então, comparamos e vemos se as duas frequências são as mesmas. Aqui está em 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

o único ponto incomum aqui é Hash.new(0). Isso cria um hash onde o valor “padrão” para qualquer chave é 0. Isso pode parecer um pouco trivial e sem importância, mas isso é extremamente útil para praticamente qualquer problema de entrevista relacionado à tabela de hash, já que você costuma usar tabelas de hash para contar frequências.

encerrando

é isso para esta pequena peça sobre entrevista com Ruby. Embora as coisas que discutimos até agora sejam bastante simples, é bastante surpreendente como é fácil estragar as coisas mais básicas quando você tem um entrevistador respirando pelo pescoço. Na próxima parcela, cobriremos árvores binárias e a implementação de um cache LRU.