Heaps

I noted in my last post that I had a technical phone interview. When it was scheduled, the HR person told me that it would include "data structures, algorithms, and architecture". I decided that it wouldn't be a bad idea to review a bit and so I got a copy of Steven Skiena's "The Algorithm Design Manual" and started rummaging through it.

One of the data structures that I came across was a heap (as in heapsort if you've forgotten). A heap is a binary tree data structure that has the property that the parent is smaller for a min-heap or larger for a max-heap than its children. They can be used for priority queues as the minimum or maximum is always at the top of the heap or for sorting assuming that you a) take the top element and then b) recalculate the tree.

The code here follows Skiena's pretty closely excepting he starts his array at 1 and I use the more natural (for me anyway) 0 start. This code also implements only a min-heap, but you should take a bit of time to see if you can figure out how to make it either a min-heap or a max-heap as an initialization parameter. A couple of other things aren't that pretty (extract_min! in particular bugs me), but mostly it's not bad and is straight forward.

So ... here's the code

class Heap
    def initialize(a)
        @q = []
        a.each { |v| insert(v) } if a
    end

    def parent(n)
        n == 0 ? -1 : (n-1) / 2
    end

    def young_child(n)
        (2 * n) + 1
    end

    def insert(v)
        @q << v
        bubble_up(@q.size-1)
    end

    def bubble_up(n)
        return if parent(n) == -1 # Root of heap, no parent 
        if @q[parent(n)] > @q[n]
            swap(n, parent(n))
            bubble_up(parent(n))
        end
    end

    def swap(n, pn)
        @q[n], @q[pn] = @q[pn], @q[n]
    end

    def min
        @q.first
    end

    def extract_min!
        m, @q[0] = @q.first, @q.last
        @q.pop
        bubble_down(0)
        m
    end
 
    def bubble_down(n)
        c = young_child(n)
        min_index = n

        0.upto(1) { |i| min_index = c+i if ((c+i) <= @q.size-1) &&(@q[min_index] > @q[c+i]) }

        if (min_index != n)
            swap(n, min_index)
            bubble_down(min_index)
        end
    end

    def sort!
        a = []
        while v = extract_min! do a << v end
        a
    end
end

h = Heap.new([12, 14, 6, 10, 8, 27, 1, 4, 9])
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "min = #{h.min}"
puts "min = #{h.min}"
puts "sort! = #{h.sort!}"

Let me know if you have any questions or comments and if you make improvements, post those too.

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.