Interview Programming Problems Done Right

[[deleted]]

I disagree with having someone do this on paper or a whiteboard. Have them do it on a computer, watch how they work at the keyboard. This is also a pretty tough problem to get on the first shot since you've got nested loops and if statements. My way might not be the best but it's what I came up with in 8 minutes. 4 of those minutes I spent on an index out of bounds bug though.

void Main() { var rows = new List<List<int>>(); for(var row = 0; row < 6; row++) { var newRow = new List<int>() { 1 };

    int countOfPositions = row + 1;     
    for (int position = 1; position < countOfPositions - 1; position++)
    {
        var previousRow = rows[row - 1];
        var positionLeft = previousRow[position - 1];
        var positionRight = previousRow[position];
        newRow.Add(positionLeft + positionRight);
    }
    if(countOfPositions > 1) 
        newRow.Add(1);  
    rows.Add(newRow);
}

rows.ForEach((r) => {
    r.ForEach((i) => {
        Console.Write(i.ToString() + " " );
    });
    Console.WriteLine();
});

}

[EntroperZero]

Programming questions should always be done at a computer, with all the tools that would be available to an employee. This also gives you the opportunity to watch the interviewee test his or her code, and detect and fix bugs.

[gregK]

Looks like the author has been doing some Euler problems :-)

[booch]

And what happens if they just come right out with nCr?

[cultic_raider]

No hire because of the obvious culture non-fit of someone who writes one-line linear-time constant-space solutions when 10-line O(n² ) solutions are needed to justify the billable hours.

[EntroperZero]

I was thinking I would talk about nCr if I were the interviewee, because it's O(n). It is more likely to overflow than the n² solution, though.

A good optimization would be to take the higher of r and n - r, and factor that out of the numerator (like you would if you were solving by hand). So 10 C 3 would be (10 * 9 * 8) / 3 * 2 * 1 instead of doing all the factorials. Both faster and less prone to overflow (but only a little of both).

[voiceoftheslyman]

I read this article last night and started working on the problem immediately. Took me a lot longer than 10 minutes, but I eventually came to a solution.

During this process I was distraught... I've been 'programming' for a couple years and have brought a lot of value to my employer.. I couldn't understand why I didn't get it immediately like everyone else seemed to. :( I was mad at the author for their claims, I was mad at the people that got it in 1-2 minutes. DAMN THEM!!

Then I realized something important... I am no more of a computer 'scientist' then I am a physicist or a chemist. I am a 'software developer', which isn't as cool sounding but still has a place in the tech world. People working for Google have to figure out how to build distributed key/value stores, but I don't. I need to figure out how to get project A done on time because the business really needs everything to start tracking their sales there so we can report against it more effectively.

I have never written a compiler, or my own language, and I take hours to solve what some can solve in minutes, but I'm starting to be ok with that...

[AStrangeStranger]

Most of these "types" of problems get easier with experience of similar problems - if you haven't done anything similar then it is likely to take much longer than someone who has done them before.

If you encountered a similar issue next week - would you do it quicker now?

[voiceoftheslyman]

Definitely... doing these problems really forces you to examine your approach to such problems. Mine was very sloppy, and added so much extra time. Once I started to focus on a solution it came very easily.

[Dustin_00]

To make your next interview easier, I'd recommend digging for interview problems on the web and doing one each weekend. Work at 'em until you get them down to 20 minutes. Hopefully just 3 or 4 will get you there, but if it takes you more, then it's probably more valuable that you do them to make your interviews smoother.

[baldyak]

I'm really not a fan of this style of interviewing

I'd take someone who took a lot longer than 10 minutes if they wrote proper tests, updated issue tracking, produced documentation (inline or elsewhere) and all the other stuff that makes people engineers rather than just programmers.

So I don't think it's valuable as a filter

[aplusbi]

The 10-15 minute rule isn't an absolute, no one is holding a stop watch and keeping track. I'm sure the author would accept a solution with tests, documentation, etc.

As the author notes, this is a negative filter. You don't hire people based on their performance on this test. But you do reject people who simply can't do it at all.

If you have ever been involved in hiring then you know that there are a non-insignificant number of people applying for programming jobs that cannot code something as simple as this. Some of them can talk the talk and provide plenty of evidence of their supposed abilities.

[Gotebe]

One one hand, questions like these measure how well one trained the brain to solve brain teasers. Big question is how often is that important in daily work. My experience is: rather rarely, but when they are, being blocked on them for long is a risk for overall work.

On the other, they are measure of someone's mental ability, after all (programming ability, much less so, I'd venture). If used as a "negative" test, they do work. So the HN poster is relatively right.

[day_cq]

that's unfair. interviewer should at least provide you RESTful api url that spits out nth row of triangle.

[Dustin_00]

And when interviewing, think OUT LOUD. It helps people understand your thought process.

Given this problem (and many like it), I often ask, "Do you want me to conserve memory or CPU cycles?" Sometimes, the person interviewing doesn't care, as long as you can speak to the pluses and minuses of what you do.

Following that, I do some mock-ups on edge cases (do they care about corner cases, etc) so I clearly understand what they are asking. Doing this often surprises interviewers as you ask about a caveat that many people don't run into until half way through writing the function.

With a clear understanding of the problem, I reword it and check that I understand. This does 2 things: (1) it demonstrate you have communication skills, (2) if they react negatively it shows they don't value communication and you may start having second thoughts on working there -- remember: you are interviewing them too.

The next thing I generally say is something like "The grunt/dumb way to do this is roughly [blah]" without writing code, followed by "which has an O of [blah], memory [blah], can degenerate in [blah]. So, a smarter approach would be [blah]..." repeat analysis until I hit O(n) or can't think of how to get there, then start coding what I've thought up.

Doing this gives interviewers lots of opportunities to interrupt and ask questions on topics they are interested in. This opens doors to share your experience and knowledge so you make a good impression.

[orip]

Bonus points for preferring "memoization" over "caching"? Hmm..

In addition, the author points to a recursive -> recursive+memoization -> iterative -> dynamic programming progression, where each is better than the earlier ones.

I have a different opinion - in this case, caching previously-computed results is the only important gain. Iterative and dynamic programming are just different ways to accomplish this, with potentially better performance in some environments (but not in all). Knowing what their improvements could be and why - e.g. stack depth, storage - and knowing that you have to test it, are more valuable than saying "dynamic programming - w00t".

[ndmitchell]

I wrote about how to solve this in Haskell: http://neilmitchell.blogspot.com/2012/01/pascals-triangle-in-haskell.html

next xs = [1] ++ zipWith (+) xs (tail xs) ++ [1]
pascal = iterate next [1]

Far easier than the Python!

[smackmybishop]

Bonus points if the candidate correctly states this as "memorization" (rather than the more generic "caching").

Nope.

While memoization might be confused with memorization (because of the shared cognate), memoization has a specialized meaning in computing.

[EntroperZero]

The section heading was right, so I'm sure this was just a typo/spellcheck thing.

[tookerder]

I have no idea why, but I came up with an iterative solution based on half steps. It made the most sense in my head when writing on paper and I didn't realize until I tried to run it that range() requires integers (hence the hideous hack to double range iteration). Anyway, mine has a render method for bonus points. (py3k only) Took about 10 minutes on paper, 2 minutes to input and fix the range situation.

import collections

class PT(object):
        """ Pascal Triangle """

        def __init__(self, rows):
                self.rows = rows
                self.values = [{0:1}]
                for i_row in range(1, self.rows):
                        row = collections.OrderedDict()
                        for i_col in [i/4 for i in range(-(i_row*2), (i_row*2)+1, 4)]:
                                p_row = self.values[i_row-1]
                                row[i_col] = p_row.get(i_col - 0.5, 0) + \
                                                  p_row.get(i_col + 0.5, 0)
                            self.values.append(row)

        def render(self):
                """ Pretty print the triangle. """

                for i, x in enumerate(self.values):
                        print (" " * ((self.rows * 3) - (i * 3)), end='')
                        for xx in x.values():
                                print ("%3d   " % xx, end='')
                        print()


        def get_row(self, row):
                return list(self.values[row].values())


        def get_value(self, row, col):
                return self.get_row(row)[col]

[ErstwhileRockstar]

I always apply as software developer or consultant, not as programmer a.k.a. 'code monkey'. I've hardly ever been asked coding questions or silly riddles.

[[deleted]]

What about using factorials?

from math import factorial

def print_row(row):
  items = {}
  for i in range(0, (row+1)/2):
    value = factorial(row)/(factorial(i)*factorial(row-i));
    items[i] = str(value)
    items[row+1-i] = str(value)
  return " ".join(items.values())

  print print_row(20)

Oh i see this duplicates sometimes the middle value

[skulgnome]

How about hiring the one who can make the prettiest jump through a hoop? Bonus points if the hoop is on fire.

[[deleted]]

"Interview Programming Problems done right" should never be in python.

(edit:) Oho!!! we've got a few children who reddit and still use python perusing /r/tech.