So after I posted to the new interviewing category yesterday, Slashdot posted an article that fits right in. While the article was a quick read and got my wheels turning, I have some comments on the article and how accurate it is.
First, the links to Slashdot and the linked articles:
http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/
And the original Dice post – http://insights.dice.com/2015/11/06/the-trick-to-coding-interview-questions/
I’ve been asked these kinds of questions, and recently did a phone screen where the interviewer asked me to either do a programming exercise from projecteuler.net or from the ICPC 2013 competition (I chose problem F – https://github.com/joadavis/jobin). I definitely need more practice doing problems while people are watching and judging me (ooh the nerves). So this article looked like a good idea to build some skills.
The first problem with the Dice post is it is kinda short. While the point of looking for patterns is a good one, he really only mentions one pattern in the 3 problems he discusses. What about the buzzword of the decade map/reduce? Or how to intelligently pick estimates that many of the Microsoft-style interview questions seem to hinge on?
My next problem was that I don’t think one of his example solutions is optimal. In solution 3 to problem 1: mode, he loops through the data and populates a dictionary with the counts (so far so good), but then rather than doing the comparison for largest count as he went, he looped through the result set at the end looking for the largest. While that might not be so bad in a data set where there are only a few different values, in the worst case where each value in the data set is unique you are adding another O(n) loop.
Here is my proposed solution (which in some ways is similar to what he did in solution 2):
def get_mode_hashing(nums):
# keys: numbers in our input array
# values: the number of times that key number appears
# e.g.: if 5 appears 3 times, then counts[5] == 3counts = {}
# quick check
if nums.count < 1:
return Nonemax_count = 1
mode = nums[0]
# step 1: get the counts
for num in nums:
if num in counts:
num_count = counts[num] + 1
counts[num] = num_count
if num_count > max_count:
mode = num
max_count = num_countelse:
# we initialized on the first number, so there is always at least one entry already >= this one
counts[num] = 1# step 2: there is no step 2, just return
return mode
One thing I noticed in his implementation is that if there are multiple values with the same count then whichever one shows up first in the data set will be called the mode. In my case, whichever one reaches the maximum count first ‘wins’. I’d have to go read up on “mode” to decide if it matters. (Update[2022]: all answers with the most number are the “mode” so they all should be returned. Might depend on who is asking the question if they just want one or the whole set.)
At any rate, I need to go read through the “Top 10 Algorithms” article and see if there is anything else worth writing about.