Ruby Interview Questions: Linked Lists and Hash Tables

I spent some time this fall interviewing at various places across the industry. As pretty much anyone who’s planning to do this knows, all companies ask, basically, the same flavor of questions. However, they do tend to vary in difficulty and scope. At the core of the interview experience lie algorithms and data structures, i.e. standard, first-year, undergrad stuff. Although we can spend all day determining whether this is a good measure of programmer ability (it almost certainly isn’t, especially for companies whose primary business is building pretty simple iPhone apps), the deal is that learning to play the game is better (and certainly more lucrative) than avoiding it.

Most interview prep material seems to be either in Java or C++, primarily due to their ubiquity, as well as the fact that they don’t “do too much,” i.e. most abstractions are pretty thin. But, there’s no reason why a Rubyist can’t work his/her way through interviews with our tool of choice. In this article, we’ll go through some reasonably easy to average difficulty interview problems using Ruby. Most of the time, harder interview questions aren’t hard because they involve really complicated code; instead, they just require more thought and some insight. So, by figuring out how to do the easy stuff in Ruby, you should be set to tackle the hard problems, too.

A Note About Style

This article isn’t about how to write the most clever Ruby possible. The idea is to write clear code that is easy to understand, which is often more important (especially in an interview setting) than using every possible trick available in the Ruby grammar. So, the code presented is made to be as simple and straightforward as possible.

Linked Lists

Linked lists are probably the most common structures tested in interviews (with heavy competition for first place from hash tables.) As such, being intimately familiar with linked lists is a good idea. Although there are many other sources [1] to describe the concept behind a linked list, the basic idea is that a linked list consists of a bunch of nodes (i.e. pieces of data) and each node contains a link to the next node. Sometimes, we have to use doubly linked lists in which each node contains a link to the next node as well as the previous one.

Let’s figure out how to implement the linked list data structure before we work on the first problem. It’s pretty simple:

class Node
  attr_accessor :value, :next_node 

  def initialize(value, next_node)
    @value = value
    @next_node = next_node
  end
end

All we are doing is maintaining the value of each node and a reference to the next node. Let’s tackle the simplest thing we can first:

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

This is pretty easy. We start the current node at the node given to us, print out the value (or, add it to a string) and then move our current node to the @next_node attribute of that node. Here that is in Ruby:

  class Node
    ...
    def to_s 
      curr_node = self
      res = "["
      while curr_node.next_node != nil
        res = res + curr_node.value.to_s + ", " 
        curr_node = curr_node.next_node
      end
      res = res + curr_node.value.to_s + "]"
    ...
  end

Not the most beautiful code, but it works. We can test it:

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

Which gives us [8,7]. OK, let’s do something a tiny bit more complicated:

Reverse a linked list given its head.

This is a problem that’s so popular that pretty much no one uses it anymore. The solution is not immediately obvious, but becomes so once you’ve heard it a million times. Basically, we solve this problem recursively. Given a node, we first check whether or not the node is the last of the list. If it is, then we just return immediately (i.e. the reverse of [6] is just [6]). If not, pass the next node into our reverse function. This will reverse the list and place the node that we passed in at the end of the reversed list. Then, stick our current node on the “next” of this list. It’s a bit confusing because of the trick that the next of the current node actually ends up at the end of the reversed list so the next of the next of the current node is where we want to put the current node. Check it out in code:

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_head
end

The code is very straightforward. The “trick” comes in next_node.next_node = curr. Since we know that the next node of curr will be at the end of the reversed list, we just tack on curr onto the end of the next node of curr. Let’s take a look at another problem.

Implement a stack using a linked list.

First of all, let’s clarify what we mean by a stack. Basically, it’s like a stack of books sitting on your desk. You can put stuff at the top (this is called push) and you can take off the last book you put on there (this is called pop). There are a number of ways to implement a stack with a linked list and we’ll pick one of them.

We’ll keep track of the top of the stack as the head of a linked list. Then, we want to push stuff onto the top of stack, we will simply change the head of the list and point the next node of the new head to the old head. If we want to pop stuff off, we just move the head (we’ll let the garbage collector handle deallocation of the old head). Let’s take a look:

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
  end
end

As you can see, all we are doing is creating a head on push and moving the head to the next node on pop. We can test it:

stack = Stack.new
stack.push 3
stack.push 5
stack.push 7
stack.pop
stack.push 8
print stack.head

There’s some crucial stuff that we have omitted here though. What happens if you call pop on an empty stack? You should discuss edge cases like this with your interviewer and come up with a way to handle them (e.g. throw an exception).

Hash Tables

Hash tables are another data structure that you need to have down pat in order to ace those interviews. In Ruby, hash tables are instances of Hash. Although you can probably get away with a weak grasp of the internals of hash tables (e.g. universal hashing, chaining, etc.), understanding that stuff might come in handy at some point. Pretty much any algorithms textbook will give you this information.

Unlike linked lists, we don’t need our own implementation of hash tables since they are a part of the Ruby library and also only a few people care if you can implement a hash table from scratch. Let’s look at an easy problem:

Remove duplicates in an array of numbers.

Here’s what we do. We put each number in the hash table as a key and then return the keys at the very end. If we encounter a number we’ve already seen, that’s no biggie because that means we’ve already placed it into the hash table.

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

So, what’s the point of using the hash table here? The table allows us to check in constant time whether or not we have already seen an element before. That allows this code to run in linear time. OK, onto something a tiny bit more involved:

Two strings are considered anagrams if they are made up of the same letters (with the same frequencies of each letter) although they may be in a different order. Write a function to determine if a string is an anagram of another.

Another way to frame this question is that we are trying to determine if the frequencies of each letter in two strings is the same. We can compute frequencies with a hash table pretty easily. We just iterate over the string and add onto the value for each letter. Then, we compare and see if the two frequencies are the same. Here it is in Ruby:

def get_freq(str)
  freq = Hash.new(0)
  str.each_char do |chr|
    freq[chr] += 1
  end
  freq
end

def check_anagram(str1, str2)
  return get_freq(str1) == get_freq(str2)
end

The only unusual point here is Hash.new(0). This creates a hash where the “default” value for any key is 0. This might seem a bit trivial and unimportant but this is hugely useful for pretty much any hash table-related interview problem since you will often use hash tables for counting frequencies.

Wrapping It Up

That’s it for this short piece on interviewing with Ruby. Although the stuff we’ve discussed so far is pretty simple, it’s pretty surprising how easy it is to screw up the most basic stuff when you have an interviewer breathing down your neck. In the next installment, we will cover binary trees and the implementation of an LRU cache.