Ruby Interview Questions: Linked Lists and Hash Tables

Share this article

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.

Frequently Asked Questions (FAQs) about Ruby, Linked Lists, and Hash Tables

What is the significance of Linked Lists in Ruby?

Linked Lists are a fundamental data structure in computer science and are widely used in various types of applications. In Ruby, Linked Lists are not used as frequently as in other languages due to the powerful Array and Hash data structures provided by the language. However, understanding Linked Lists is crucial for Ruby developers as they provide a basis for understanding more complex data structures and algorithms. They are also often a topic in coding interviews, so having a solid understanding of them can be beneficial for job seekers.

How do you implement a Linked List in Ruby?

Implementing a Linked List in Ruby involves creating a Node class and a LinkedList class. The Node class represents the individual elements of the list, each containing a value and a reference to the next node. The LinkedList class is used to manage the nodes, providing methods to add, remove, and search nodes in the list. Here’s a basic implementation:

class Node
attr_accessor :value, :next_node

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

class LinkedList
def initialize
@head = nil
end

def append(value)
if @head
find_tail.next_node = Node.new(value)
else
@head = Node.new(value)
end
end

def find_tail
node = @head
return node if !node.next_node
return node if !node.next_node while (node = node.next_node)
end
end

What are Hash Tables and how are they used in Ruby?

Hash Tables, also known as Hash Maps, are a type of data structure that provides fast access to values based on their keys. In Ruby, Hash Tables are implemented through the Hash class. Hashes are incredibly versatile and are used in a wide variety of applications in Ruby, from storing configuration settings to acting as a cache for expensive computations.

How do you create and manipulate Hash Tables in Ruby?

Creating a Hash Table in Ruby is straightforward. You can create a new Hash object and add key-value pairs to it. Here’s an example:

hash = Hash.new
hash["key"] = "value"

You can also create a Hash with initial values:

hash = {"key" => "value", "another_key" => "another_value"}

What are the differences between Linked Lists and Hash Tables in Ruby?

Linked Lists and Hash Tables are both data structures, but they serve different purposes and have different strengths and weaknesses. Linked Lists are a linear data structure, meaning they store elements in a sequential manner. This makes them excellent for tasks where order matters, such as implementing queues or stacks. On the other hand, Hash Tables are a type of associative array, meaning they store elements as key-value pairs. This makes them excellent for tasks where you need to quickly look up values based on a key, such as caching or storing configuration settings.

How does Ruby handle collisions in Hash Tables?

Ruby handles collisions in Hash Tables using a technique called “open addressing”. When a collision occurs, Ruby will probe the Hash Table for the next available slot and place the key-value pair there. This ensures that every key has a unique position in the Hash Table, even if multiple keys have the same hash value.

How can I traverse a Linked List in Ruby?

Traversing a Linked List in Ruby involves starting at the head of the list and following the references to the next node until you reach the end of the list. Here’s an example:

def traverse
node = @head
while node != nil
puts node.value
node = node.next_node
end
end

How can I search for a specific value in a Linked List?

Searching for a specific value in a Linked List involves traversing the list and checking each node’s value. If the value matches the value you’re looking for, you return that node. If you reach the end of the list without finding the value, you return nil. Here’s an example:

def find(value)
node = @head
while node != nil
return node if node.value == value
node = node.next_node
end
nil
end

How can I delete a node from a Linked List in Ruby?

Deleting a node from a Linked List in Ruby involves finding the node and then updating the next_node reference of the previous node to point to the next node. If the node to be deleted is the head of the list, you update the head to be the next node. Here’s an example:

def delete(value)
if @head.value == value
@head = @head.next_node
else
node = find_before(value)
node.next_node = node.next_node.next_node if node != nil
end
end

def find_before(value)
node = @head
return nil if node == nil
while node.next_node != nil
return node if node.next_node.value == value
node = node.next_node
end
end

How can I sort a Linked List in Ruby?

Sorting a Linked List in Ruby can be done using various algorithms, such as bubble sort, insertion sort, or merge sort. The choice of algorithm depends on the specific requirements of your application, such as whether you need a stable sort (i.e., a sort that maintains the relative order of equal elements) or whether you need to optimize for time or space complexity.

Dhaivat PandyaDhaivat Pandya
View Author

I'm a developer, math enthusiast and student.

algorithmsGlennGjob interview
Share this article
Read Next
Get the freshest news and resources for developers, designers and digital creators in your inbox each week
Loading form