Hacker News Reader

Comment by codesuela | Hacker News Reader

Does someone else have a few programming tests on hand aside from FizzBuzz? Also InterviewStreet ( https://www.interviewstreet.com/ ) has a nice collection of problems of varying degrees of difficulty. Quite handy if you want to "prepare" for an interview.

View on HN

We deal with maps a lot, and I usually ask this one: assume a matrix. Fill the matrix with numbers, so that the outer 'ring' of numbers has the value 1, one 'ring' more to the center has the value 2, and so on. To visualize this, imagine that this matrix represents a height map, where each number represents a cell in a surface, and the value of the number is the elevation of the area of that cell. The result should be a height map of a pyramid. To make things easier, assume that the number of rows and columns in the matrix is equal, and that that number is uneven.

Followup-questions may go into the direction of what if some of the assumptions are loosened, or what are the performance implications of several possible solutions, or how to do it when iterating in whatever is the most optimal manner performance-wise considering the storage implementation of the matrix (avoiding cache misses or disk seeking etc.).

I've only had a single person ever pass this test, out of 10 or so interviewees.

Another one was where a colleague of mine drew a car on a piece of paper and asked the candidate to explain how he would design a class hierarchy if one were to model a car in OOP. His answer was to have a class 'rectangle' and two classes 'circle' (referring to the box and the two wheels my colleague drew on the paper). Seeing the incredulous looks on our faces, he then proceeded to an unintelligible story of 'has-a' vs 'is-a' as it related to the point in the middle of the circles, and how a 'point' somehow 'was-a' circle except that it had room in the middle. True story.

>We deal with maps a lot, and I usually ask this one: assume a matrix. Fill the matrix with numbers, so that the outer 'ring' of numbers has the value 1, one 'ring' more to the center has the value 2, and so on. To visualize this, imagine that this matrix represents a height map, where each number represents a cell in a surface, and the value of the number is the elevation of the area of that cell. The result should be a height map of a pyramid. To make things easier, assume that the number of rows and columns in the matrix is equal, and that that number is uneven.

This sounded fun, so I thought about it for a couple minutes and came up with the following in JavaScript:

    var pyramatrix = function(a) {
        a += 1 - (a & 1); // increment a by one if even
        var b = [], // pyramid y-axis
          c = a-(a>>1), // get the "center" of the pyramid (eg. 7 -> 1234321 -> 4 is the center)
          d = function(x) { return Math.abs((x+1)-c) }, // calculate offset from center
          e, f, // values for storing current index offset
          g = ''; // initialize string for pretty output
    
        for(var i = 0; i < a; i++) {
          b[i] = []; // pyramid "x-axis" (current row)
          for (var j = 0; j < a; j++) {
            e = d(i); // get y offset
            f = d(j); // get x offset
            b[i][j] = c - (e > f ? e : f); // set current index to center minus larger offset
            g += '['+b[i][j]+']'; // add value to pretty output
          }
          g += '\n'; // add a line break after each row
        }
        console.log(g); // print pretty output
    }

Example usage and output:

    pyramatrix(7)
    [1][1][1][1][1][1][1]
    [1][2][2][2][2][2][1]
    [1][2][3][3][3][2][1]
    [1][2][3][4][3][2][1]
    [1][2][3][3][3][2][1]
    [1][2][2][2][2][2][1]
    [1][1][1][1][1][1][1]

I was pretty satisfied when it worked exactly as intended on the first try!

EDIT: Now that I look at it, you could obviously move e = d(i); outside the second for loop, but for the sake of posterity I'm not going to change the solution from what I first came up with.

That looks like a nice solution to me, some of the Javascript idioms I'm not familiar with, but after looking at it for a while it seems you're using what I'd consider the 'best' method of generating it - looping over each cell and calculating the height based on the distance to the 'top' (or 'center', depending on how you look at it).

Personally I consider the 'naive' version (as in: the first, easy to manually verify version one would bang out as a prototype) to be one where a matrix is pre-allocated and each ring is filled in from the outside inwards (so first assign all 1's, then all 2's, and so on), but funnily enough nobody ever went that route, not even my colleagues who did it.

>Personally I consider the 'naive' version (as in: the first, easy to manually verify version one would bang out as a prototype) to be one where a matrix is pre-allocated and each ring is filled in from the outside inwards (so first assign all 1's, then all 2's, and so on)

I'd consider the 'naive' version (and the first solution that popped to my mind pretty much instantly) to be where you first fill the grid with 1's, then then loop over the next level and add 1 and repeat until you're on the top. So like this for example:

  function(a) {
    a = a | 1; // add 1 to even numbers
    var b = new Array(a),
        i, y, x,
        s = 0;
  
    // initialize the array
    for(y = 0; y < a; y++) {
      b[y] = new Array(a);
      for(x = 0; x < a; x++) {
        b[y][x] = 0;
      }
    }
    // turn it into a pyramid heightmap
    for(i = a; i > 0; i--) {
      for(y = s; y < i; y++) {
        for(x = s; x < i; x++) {
          b[y][x]++;
        }
      }
      s++;
    }
    return b;
  }

Though in JavaScript it's a bit more complex than it might otherwise be since you can't just declare a multi-dimensional int array in a single line. Anyway, I discarded this solution about as fast as I came up with it because I knew there'd be more clever ways to go about it, and came up with the offset calculation method a couple minutes after that. And amusingly enough I had to actually test and iterate this 'naive' version a bit before I got it running right, whereas my 'complex' solution worked on the first try. Funny how that goes.

Thanks for the pyramid example, that's a good one. As a calibration point, it took me from 16 minutes past the hour when I read your post to 26 past the hour to complete. And the ten minutes included two interruptions where I had to go to another office. And 3 more minutes to write this post.

I did google "2d array python" when the array initialization I used at first didn't work. (I'm new to python and had not done a 2d array in it yet.)

Works fine, dumps the result in formatted output, and accepts any positive number as an argument to pyramid size, odd or even.

Thank you, that's interesting. That's in the magnitude of time I myself estimated when I started asking this question, but I started wondering over time if my expectation was realistic.

> I've only had a single person ever pass this test, out of 10 or so interviewees.

Did that person get the job? Lots of companies seem to administer those brain-bending tests and then does not use it as the deciding factor when hiring someone.

I've personally been exposed to several quizzies like checking if a number is a prime, walking a directory tree and printing .txt files, implementing a variant of the soundex algorithm, a web server to interact with the twitter api... The worst (or best) was one in which the interviewer asked me to solve a Roman Square problem as a homework. Except instead of a 3x3 square it was a hexagon containing 64 numbers. Aced all the tests, even the Roman Square and the interviewer even told me I was the only one they had interviewed that solved the problem. It was freakishly hard and involved creating a pretty complicated constraint solver.

I still didn't get the job. In fact, the common theme in my professional life, after dozens of interviews, is that if there is a programming test involved then I will not be offered the job, no matter how well I score.

My conclusion is that companies do not use tests to determine whether to hire applicants or not. Interviewers make up their decisions regardless of test results and then use them purely to make their decision seem more objective they in reality are: "Bill scored low on or test, he is not a good candidate..." or "Bill did score well, BUT $blablabla" where $blablabla is some irrational stuff.

This particular one did, yes, but not just because she could solve this problem. I refuse to let my hire/no hire recommendations be boxed into binary thinking or autistically rigid 'if a then b' type of testing. I will try my best to interview in a way that will eliminate or suppress any biases I may have, but will still use judgement when interpreting the results of any tests/questions. Rigid algorithms are too easy to game.

Pre-Screen for us is simply provide working code that 'Finds the the four highest integers in a list of integers'. We accept any language.

The controversial bit, is we ask for Big O of their solution. There are a lot of candidates who didn't get the CS degree and struggle with this, surprisingly no one has ever said "I don't know Big O".

Generally, working code is enough to at least get you in the door for a face-to-face. Yet this alone filters out more than 50% of the resumes.

Fun! Here's Ruby:

  def top_four_ints_from(input_list)                                                    
    working_set = []

    input_list.each do |n|                                                    
      working_set.push(n)
      working_set.sort!.shift while working_set.count > 4
    end                                                 
                                                                                 
    working_set                                                               
  end

I'm pretty sure that's O(n). Constant time to insert any one value to the working set, Roughly n sorts performed but since each individual sort covers at most five elements we're still at (5 lg 5) * n -> O(n).

I did a phone interview once for Facebook and my interviewer used binary search of an array of integers. I think it is a good thing to use for a first filter because even if you don't know it from memory it is pretty obvious from first principles, and it involves both looping (or recursion) and branching and it is only 10 lines of code. Also there are a few twists you can apply afterwards:

1. Turn it into bisect: return the index at which the searched value should be inserted to maintain the sorted list.

2. Allow any type of array member and require a comparison function provided that returns the standard -1,0,1.

3. Point out that binary search can be used for membership testing with O(log(n)) comparisons where n is array length. Then ask for a data-structure that can perform membership testing in constant time (answer: hash table.)

EDIT: the actual programming was in a shared buffer (something like etherpad). I was mock-interviewing a friend and I had him do it on paper and that worked alright too.

EDIT2: The hardest part about discussing FizzBuzz is avoiding derailing the discussion into FizzBuzz code golf.

  #!/usr/bin/env python
  for i in range(1,101):
    print [i,"Fizz","Buzz","FizzBuzz"][(0==i%3)+2*(0==i%5)]

1 line longer, but extensible.

  #!/usr/bin/env python
  rules = {3:'fizz, 5:'buzz'}
  for n in xrange(1, 101):
    print ''.join(n%x is 0 and rules[x] or '' for x in rules) or n

>The hardest part about discussing FizzBuzz is avoiding derailing the discussion into FizzBuzz code golf.

Well, since we're going there... have some JavaScript again!

  for(var i=0;i++<100;console.log(((i%3?'':'Fizz')+(i%5?'':'Buzz'))||i));

In the spirit of http://140byt.es I also condensed my pyramatrix function (though without the visualization) to 135 characters:

  function(a){a=a|1;var b=[],c=a>>1,d=Math.abs,e=0,f;for(;e<a;e++)for(b[e]=[],f=0;f<a;f++)b[e][f]=1+c-d(d(c-e)>d(c-f)?c-e:c-f);;return b}

And to get the same visualization as in the original version, you can use this helper function:

  function(a){var b=a.length,c='',d=0,e;for(;d<b;d++){for(e=0;e<b;)c+='['+a[d][e++]+']';c+='\n'}console.log(c)}

Assign those to say, pyramatrix and visualize and you can call visualize(pyramatrix(n)) and get the same pretty output!

#include <stdio.h>

void main(){for(int i=1;i<=100;i++)printf(i%3&&i%5?"%d\n":"%szz\n",i%3?(i%5?i:"Bu"):i%5?"Fi":"FizzBu");}

;)

That's the beauty of FizzBuzz, you don't really need other tests. It weeds out the dead wood very quickly and when you have 10 resumes to walk through in a week, that's a handy thing. Best to know this early on to avoid wasting your time and the candidate's as well.

Other examples of FizzBuzz-level tests? They aren't exactly tough to come up with. I used to ask for a function that takes a string and returns a boolean indicating whether or not it contains all uppercase letter.

Find all duplicate entries in a list, with Big O.

Reply on news.ycombinator.com