Phone Interview - 1

I had a phone interview with a great company yesterday and thought I'd share some of the questions, my answers, what I think might have been better answers, and some additional potential questions that might have been asked. First, this was for a manager position and the fact that they're asking technical questions as part of the interview process and as the first interview really impressed me. It shows that they value technical abilities and respect their engineers and developers enough to hire managers that are technically capable as a top priority. We started out, as is usually the case with a bit of small talk about myself, the interviewer, and the company. Nothing too interesting there. I don't recall the actual order of the questions, but I think I got them all.

1. What are horizontal and vertical scaling? Here I knew what horizontal scaling was, but I don't believe I've heard the term vertical scaling. Horizontal scaling means adding more servers to give more processing power while vertical scaling (as I learned when I looked it up) is beefing up the capabilities of an existing server by adding say memory, CPUs, or CPU power. A reasonable follow up to this would have been to discuss the advantages and disadvantages to each.

2. What is object oriented programming? Here I discussed encapsulation and inheritance. I probably should have mentioned polymorphism and message passing. The Wikipedia article is pretty decent and wouldn't be a bad place to do a high level review for this sort of question. I was a little surprised that I didn't get a question on a specific problem. I always would as someone to list out objects and methods for a card game or for a file system (stolen I believe from Steve Yegge if I remember correctly).

3. Given an unsorted list, how would you find a duplicate element. This one was interesting because it had recently appeared on Programming Praxis. I solved it there and used a hash table. The idea is to run through each element of the list and put it on the hash table. If when you go to put it on the hash table, there's something already there, then you've found the duplicate and should return it.

4. In the above question, what's the complexity using Big O notation. Here, since we're running through the list just once, it should be O(n) where n is the size of the list.

5. How does a hash table work or how is it implemented "under the hood"? There are actually a couple of ways of implementing hash tables. I gave the answer of an array of linked lists. You have an array of size n and then use the element that you're going to put on the table to generate a hash value using a hash function. Then use this mod n and add it to the linked list that's at that element.

6. How would you count the number of 1's in an integer? This is pretty classic. Probably the easiest is to use a shift/and technique. You would "and" the value with "1" and if it's non-zero (actually it'll be 1) then add one to the bit count. Shift right and repeat until the value is 0.

7. The final question was about Design Patterns and whether I knew about them and why they're useful. My response was that they're useful in that they give us a way to discuss our designs with a common language. People were using design patterns before the GoF book, but they codified the patterns and gave them names. This makes it much easier to talk about these things.

I think that was all of the questions. We then talked a bit about the position and the company in general. As I said, I was very impressed with them and their "corporate culture".

So ... what sorts of things do you ask or have you been asked in technical phone interviews? Anything interesting or unique? Let us know in the comments.

Tetrahedral Numbers

Here's another one from Programming Praxis this one on tetrahedral numbers. I'll leave you to read the description and just jump straight into the ruby solution. The interesting thing here is to use a lambda to create a method that we can pass around. Here's the entire program ...

def linear(target, f)
    n = 1
    while ( f.call(n) != target)
        n = n + 1
    end
    n
end

def binary(target, f)
    low, high = 1, 2
    while (f.call(high) < target) do high = high*2 end
    mid = (high + low) / 2
    while (fmid = f.call(mid)) != target do
        fmid < target ?  (low, mid = mid, (mid + high) / 2) : (high, mid = mid, (low + mid) / 2)
    end
    mid
end


tetrahedral = lambda { |n| n * (n + 1) * (n + 2) / 6 }

1.upto(10) { |i| puts tetrahedral.call(i) }

puts linear(169179692512835000, tetrahedral)
puts binary(169179692512835000, tetrahedral)

We start out with two methods linear and binary which are pretty straightforward with the exception that both take a function (in this case f) as a parameter. For linear, we start at 1 and continue calling f until the value of f(n) is the same as target. binary is similar, but here we keep doubling the high value until we're above the target and then we calculate the fmid and use it as a high or low value until we converge.

The tetrahedral function itself is created with a lambda so that we can pass it to the other two methods. The next lines are simply tests. Note how much longer the linear method takes than the binary.

As always, let me know if you have questions or comments.

Two String Exercise via Programming Praxis

Here's another one (or two rather) from Programming Praxis. Let's take a look at the second one first as it's trivial in ruby. If we're given a string, how do we replace multiple spaces with single spaces. F/or example the string "a b c" would become "a b c". For both of these, we're going to monkey patch the string class. Here's the code ...

class String

    def remove_consecutive_spaces

        self.gsub(/ +/, " ")

    end

end

All we do is do a global substitution of one or more spaces with a single space. This would be quite a bit trickier in C say which is why it ends up in interview questions.

The second (or first) problem is to remove duplicate characters from a string. For example, "aaaabbbb" becomes "ab" and "abcbd" becomes "abcd". This one is a bit trickier but shows another good example of how useful inject() can be. Here's the code ...

class String

    def remove_duplicate_characters

        self.split(//).inject([]) { |a, c| a << c if !a.include?(c); a }.join

    end

end

Going through it from left to right, we have first the split(//) which will turn the array into a string of characters. With that string of characters we do an inject([]) which a) initializes a new empty array (sometimes called the "memo") and then runs through the character array adding a character "c" to the array "a" if it's not already there include?. The ; a returns the current array back to the inject. Finally, we recreate the string by doing a join on the character string array.

Let me know if you have questions or comments.

Hett's Problem

Sorry for not writing for a while, I've been busy looking for a new job. If you've got one, you can contact me here or at slabounty at large search company that starts with "g".

Anyway ... over at Programming Praxis there's a problem via PrologSite concerning lists. Here's the problem statement ...

1.28 (**) Sorting a list of lists according to length of sublists
a) We suppose that a list (InList) contains elements that are lists themselves. The objective is to sort the elements of InList according to their length. E.g. short lists first, longer lists later, or vice versa.

Example:
?- lsort([[a,b,c],[d,e],[f,g,h],[d,e],[i,j,k,l],[m,n],[o]],L).
L = [[o], [d, e], [d, e], [m, n], [a, b, c], [f, g, h], [i, j, k, l]]

b) Again, we suppose that a list (InList) contains elements that are lists themselves. But this time the objective is to sort the elements of InList according to their length frequency; i.e. in the default, where sorting is done ascendingly, lists with rare lengths are placed first, others with a more frequent length come later.

Example:
?- lfsort([[a,b,c],[d,e],[f,g,h],[d,e],[i,j,k,l],[m,n],[o]],L).
L = [[i, j, k, l], [o], [a, b, c], [f, g, h], [d, e], [d, e], [m, n]]

Note that in the above example, the first two lists in the result L have length 4 and 1, both lengths appear just once. The third and forth list have length 3; there are two list of this length. And finally, the last three lists have length 2. This is the most frequent length.

So how can we solve these two problems in Ruby? The first one is pretty much trivial. Here's the code ...

list = [%w[a, b, c], %w[d], %w[e, f], %w[g, h, i, j, k], %w[l], %w[m, n, o]]

list_sort_length = list.sort {|a, b| a.length <=> b.length}

p list_sort_length

All we're going to do is use the option to sort that takes a block. The block will get two values and instead of the default, we're going to use the values length. Run this and you should see ...

[["l"], ["d"], ["e,", "f"], ["a,", "b,", "c"], ["m,", "n,", "o"], ["g,", "h,", "i,", "j,", "k"]]

.

The next piece is a bit trickier. Here, we can't do just a one-liner (that I could see anyway). Here's the code ...

hist = Hash.new{|h, k| h[k] = []}

list.each { |l| hist[l.length] << l }

list_sort_hist = []

hist.sort {|a,b| a.length <=> b.length}.each { |key, value| value.each {|e| list_sort_hist << e } }

p list_sort_hist

We start out creating the histogram hash and passing a block so that each element is initialized with an empty array. Then, we work through the list and add each element to an array at the appropriate histogram hash location. Next, create the empty sorted histogram array. Finally, we're going to sort the histogram the same way that we did in the earlier problem (we can do this because they both are Enumerable. We take the result of that and do and each for every item in the histogram. For each of the values (which remember are arrays), we add them to the list_sort_hist array. Finally, we print that out. If it makes it easier to see, split that long line in two. First create a sorted histogram array and then for each value loop through the value and add it to the list_sort_hist array.

Let me know if you have any comments, questions, or jobs.

Array.zip() and Upside Up Numbers

I've known about the zip method for arrays but have never really found much of a use for it. I was working a problem on Programming Praxis the other day and saw some Python solutions that used it, so I decided to give it a try in my solution. Let's start out with how it works.

In the simplest case, we have an array and we zip it with an array of the same size. Here's what it looks like ...

a = [1, 2, 3]
b = [4, 5, 6]
a.zip(b) => [[1,4], [2,5], [3,6]]

We can see that we end up with an array that's the same size as the original arrays made up of elements of each of the arrays. We can also zip multiple arrays ...

a = [1, 2, 3]
b = [4, 5, 6]
c = [7, 8, 9]
d = %w[a, b, c]
a.zip(b, c, d) => [[1, 4, 7, "a,"], [2, 5, 8, "b,"], [3, 6, 9, "c"]] 

With that here's the documented code for the upside_up program including, at the beginning, the original requirements from Programming Praxis ...

# An “upside up” number is a number that reads the same when it is rotated
# 180°. For instance, 689 and 1961 are upside up numbers.

# Your task is to find the next upside up number greater than 1961, and to
# count the number of upside up numbers less than ten thousand. When you are
# finished, you are welcome to read or run a suggested solution, or to post
# your own solution or discuss the exercise in the comments below.
#
# Create an array of pairs that can match. We should end up with
# UPSIDE_DICT = [[0, 0], [1, 1], [6, 9], [8, 8], [9, 6]] 
UPSIDE_DICT = %w[0 1 6 8 9].zip(%w[0 1 9 8 6])

# Open the Integer class and add the upside_up? method that returns true/false
# based on whether the integer is an upside number or not.
# Let's take this a piece at a time:
# 1) self.to_s.split(//) will give us an array of characters for the given number
#    such as [1, 9, 6, 1]
# 2) zip this array with
# 3) self.to_s.split(//).reverse will give us the array above reversed ...
#    [1, 6, 9, 1]
# 4) and zipping the two together should give us something like ...
#    [[1, 1], [9, 6], [6, 9], [1, 1]]
# 5) Now, we'll loop through the above zipped array using inject and make sure that every pair
#    in it is also in the UPSIDE_DICT array. If all of them are, then we'll return
#    true otherwise the inject() will return false.
class Integer
    def upside_up?
        self.to_s.split(//).zip(self.to_s.split(//).reverse).inject(true) { |r,v| r && UPSIDE_DICT.include?(v) }
    end
end

# Find all the upside values up to 10000 and print them.
(1..10000).each do |v|
    puts "#{v} is an upside number" if v.upside_up?
end

Be sure to let me know if you have questions or comments.

Interviewing

I had a young person come in for an internship interview a couple of days ago and it made me realize that I've never posted anything outside the programming world. I'm going to try to do a few different posts on the subject of interviews and resumes to hopefully help give some perspective to the hiring process from someone who actually hires rather than someone who tries to get you hired (head hunter). Is my perspective better than theirs? No probably not, but it may be a bit different.

With any interview there are going to be both soft questions and hard questions. By this I don't mean easy and hard but personality questions and technical questions. Let's start by looking at some of the soft questions you might get and why they're asked in the first place. The first thing to remember here is that you're going to be part of a group (as an aside, I hate the term "team" unless you're all dressed the same). Because of this, the hiring manager is going to want to know how you're going to fit in with the rest of the group and the soft questions will be used to try to ascertain that.

One question that seems to get asked is "Tell me about yourself". This is where you should discuss your interests related to the job. Since the interviewer is most likely going to ask about job related items later, now is a good time to bring up any outside projects that might relate. Open source projects that you've done or contributed to or a blog that you write (programming/technical related) are things that will get the interviewer's attention. Just about anything technically related is a good thing to bring up.

You're also almost certain to get a question on a group project that you worked on. Here, it won't matter if you're a developer with 20 years experience or a new grad, you'll probably have to talk about working with other people. The question may be as straight forward as "Tell me about a project that you worked on with other people." or it may be more subtle "Tell me about your last project" with the expectation that this involved other people. As you talk about this project, you may get follow on questions such as "Were there any personal issues between people in the group?" or "Was there anyone in the group who didn't pull their weight?". Then these will be followed up with "How did these issues get resolved?". All of these questions are geared towards finding out how well you will fit in in a group situation. And, as a subtext, the interviewer will be looking for your "leadership" capabilities. All of these questions are a chance for you to show that you will work well in a group and not just work well but make the whole group work better. In the example of someone not pulling their weight, stating that you noticed that Fred wasn't doing what was expected, you could tell how you talked with Fred and let him know that you'd noticed his work wasn't as good as it had been and then worked with him to get him back up to speed. In the case of personality issues, discuss how in a meeting where things were getting tense, you played the peacemaker by making sure that both sides got heard and then working through the issues.

There's probably more, but these are the types of questions that I'll usually pursue, these (or similar ones) and then follow ons based on the responses I receive. The thing to remember though is that all of these soft questions are designed for better or worse to figure out if you will fit in the group structure. Try to approach them in this way and you should do fine.

As always, let me know if you have questions or comments.

All True

I was working a problem on Programming Praxis yesterday and ended up writing a little piece of code that returned true if every element in a hash was true. It used inject and I thought it would be worth posting a generalized version here.

module Enumerable
    def all_true
        self.inject(true) { |r, v| r && (yield v) }
    end
end

We start by monkey patching the Enumerable module which will make it available for Arrays, Hashes, etc., basically anything that includes Enumerable. Next, we define the method all_true. The only line in the method is an inject which we initialize with true and then give it a block with two parameters, the r(esult) and the v(alue). We then and/&& the r(esult) with whatever the yield of the v(alue) returns.

You can test it with the following code ...

puts "#{[2, 4, 6, 8].all_true { |n| n%2 == 0 }}"
puts "#{[2, 4, 7, 8].all_true { |n| n%2 == 0 }}"

puts "#{{ 2=>2, 4=>4, 6=>6, 8=>8}.all_true { |n| n[0]%2 == 0 && n[1]%2 == 0 }}"
puts "#{{ 2=>2, 4=>4, 7=>7, 8=>8}.all_true { |n| n[0]%2 == 0 && n[1]%2 == 0 }}"

The first two of each set will return true, the second false.

As I've been doing the Programming Praxis problems, I've found myself using inject and its close relative map/collect more and more. I think this is partly because of the types of problems posted there and the influence of the solutions that are generated which tend to be functional programming based. At any rate, having a good understanding of both inject and map/collect will serve you well and simplify many of your day to day programming tasks.

Let me know if you have questions or comments.