神刀安全网

Ruby Interview Questions: Linked Lists and Hash Tables

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.

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Ruby Interview Questions: Linked Lists and Hash Tables

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮