Any good places to view/practice sample interview programming questions?

KevySaysBeNice

[H]ard|Gawd
Joined
Dec 7, 2001
Messages
1,452
Hi all!

So, I'm packing up my stuff and moving with my wife and dog to Berkeley, CA (wife has a new job). I'm hoping to get a job in my field (CS), and in preparation for interviews I was/am hoping to "practice" working through some sample programming problems I might be asked to solve.

My HOPE would be to work through a few problems every few days. I realize then when I'm under pressure, things are a bit different, but I'm going to try to time myself and record myself working through/talking through these problems so I can see what I do well, and what I don't.

Part of the reason I'm doing this is because when I was last looking for a job (about 1.2 years ago), I had an interview that I feel I did well at EXCEPT for the programming bit. I was asked to write a bit of code and I was super nervous, my head felt like it was going to explode, and I wrote bad code that while probably solving the problem, didn't demonstrate any sort of confidence or ability to think quickly/efficiently.

Anyway, my HOPE is that if I work through enough of these problems on a regular basis I'll have a little more confidence going into the interview.

I've also started reading a few CS/programming interview books to help me.

Anyway, if you have any sample questions you would recommend, or if you know of any sites that have good examples, I'd really appreciate it! I might even post a few videos here for you to review/critique.

Thanks again everybody!
 
Joined
Oct 26, 2005
Messages
2,340
The TopCoder practice rooms are a pretty good source of relatively easy problems. Most are probably a bit harder (or at least, longer) than what you'd get in an interview, but still good practice. Might also be a good idea to code on paper just to get comfortable with the idea.

Codility might have some more appropriate questions, but it'll cost you ~$60.
 

BillLeeLee

[H]F Junkie
Joined
Jul 2, 2003
Messages
13,486
http://stackoverflow.com/questions/58354/algorithm-data-structure-design-interview-questions has some general stuff.

Use the resources/puzzles out there to refresh your memory (or just learn new information) about algorithms and data structures. I never know what to expect when I get to the 'write code' part of an interview, and it seems like interviewers will either give you stuff you just rock at, or they will lambast you with stuff that's completely uncharted territory for you.

Some of my favorites...

As-of-yet Current job: I was asked to design a smart pointer class in C++, and also the Observer pattern (in C++ code).

Future job: I was asked to write a function to crawl through a website, grab email addresses from it, and follow links on the page to other pages and repeat the process.

I was also asked a question of how to identify differences between two lists A and B - like stuff that was in A and B, stuff in A and not B, and stuff in B and not A. I was also asked to do the same thing but for massive data sets that would not fit in memory.


One of the interviewers at my current company likes to ask candidates to write code to solve Boggle (4x4 version).
 

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
How would you Move Mount Fuji? talks about using puzzles to interview candidates. Hopefully, you read this book an realize why it's a silly way to interview; and how to defend yourself against companies that insist on this outmoded method.

Puzzled Programmers is a classic. It might be out of print.

Programming Challenges is a good book to work through to sharpen your chops. Some interviewers use it as a source of harder puzzles. The questions are taken from previous ACM programming constests. I'd especially recommend this book to you because you say your goal is to work through some problems to build up your skills and confidence.

Programming Interviews Exposed is the newest edition of the programming interview book. This book was pretty popular, but it's really more about giving people answers they can crib than teaching anything about taking or giving good interviews. (At least, the first edition was.)

Cracking the Coding Interview is another book about programming interviews, this time with more than trivial content about giving or taking a good interview.

Puzzles for Programmers and Pros is another book for puzzles. A couple of my friends say it's interesting, but I haven't looked at it. There's a language-specific version of the book, but I haven't read that one.
 
Last edited by a moderator:

Wiseguy2001

2[H]4U
Joined
Nov 28, 2001
Messages
3,470

Correction: I never did fizzbuzz at school in the UK, however it is a VERY popular drinking game amonst students over here :D

I know that there are some people out there who shouldn't be in the software industry, but large numbers not being able to write for loops, let alone fizzbuzz? Damn, I thought fizzbuzz was too easy (guess it's all those drinking games have helped).
 

eon

2[H]4U
Joined
Oct 11, 2003
Messages
2,218
Im glad my current job didnt try to grill me on some tech questions, I happen to be great with algorithms and programming problems but I can see myself freezing up in an interview situation. Of course I can do a fizzbuzz level question in an interview but it seems many places now like to give gotcha questions or some question that relies on tech trivia instead of real skill where they are easy to solve if you happened to see a similar question before but likely stomped if you havent.
 

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
We kick off interview loops with simple questions like FizzBizz, or things like diddling linked lists or writing simple well-known functions. It gives the candidate a chance to warm up, get a base hit first thing, and go on to harder problems later. And it gives us a chance to separate the NO HIREs quickly.

People in this forum will claim that school choice is important, or that GPA matters, or that certs are useful. They really aren't; there's no correlation between those things and the people who don't make it to lunch on the loop schedule because they just cant write software.
 

Blazestorm

Supreme [H]ardness
Joined
Jan 17, 2007
Messages
6,940
We kick off interview loops with simple questions like FizzBizz, or things like diddling linked lists or writing simple well-known functions. It gives the candidate a chance to warm up, get a base hit first thing, and go on to harder problems later. And it gives us a chance to separate the NO HIREs quickly.

People in this forum will claim that school choice is important, or that GPA matters, or that certs are useful. They really aren't; there's no correlation between those things and the people who don't make it to lunch on the loop schedule because they just cant write software.

Wooo I know modulo operators and linked lists...

Just implemented an in-place merge-sort with a doubly linked list that sorted 1.6 million items in ~2.5 seconds ... I'm sure the STL is faster but that was a fun 10 hours to learn merge-sorting for that assignment... well not all the time was spent on the merge-sort, there was ~an hour implementing the linked list functions, and a selection sort. (also in-place). The sorting was easy, getting the swapping of two nodes in a doubly linked list to work for all cases required a bit more thinking .

What are some of the harder questions you might ask? Just curious to see what level I would be at after a little over 1 year at school / since I started programming.
 

ameoba

Supreme [H]ardness
Joined
Jan 9, 2001
Messages
6,413
Let me think of some of the problems I've been asked on interviews...

Ranking poker hands. This was a 1 hour timed, live programming exercise done while remoting into a machine & Skyping. The observer interrupted me about halfway through and prompted me to start writing tests.

I was given a page of buggy, ugly, PHP code and asked to point out bugs & correct them. I was then asked how I would write it well.

I've been given 5MB of imaginary log files & was asked to parse, analyze, visualize and describe the 'user' behavior that was described by them. This was for my current data-mining gig.

I've been given other tests for jobs I didn't get but, for some reason, they're not as memorable.
 

Crash250f

Gawd
Joined
Nov 9, 2007
Messages
640
People in this forum will claim that school choice is important, or that GPA matters, or that certs are useful. They really aren't; there's no correlation between those things and the people who don't make it to lunch on the loop schedule because they just cant write software.

Unfortunately (particularly for me since I'm not the best student) I'm guessing that there's quite a few recruiters/interviewers that don't have that same perspective. I would think that good students are better at accomplishing a specific task independently than a poor student, but I don't see that having a huge impact when both are in a working environment the whole day.

My main CS prof told us that one of this top students, with the 4.0GPA double CS/Math major and all that, went to a job fair and had Microsoft ask him how to reverse a linked list. I'm not sure if he wasn't thinking clearly or just couldn't come up with solutions on the spot, but I guess his solution involved using a stack, instead of just reversing the pointers, and he didn't get called back.

Anyways, I'm confident that I'll be able to answer most of those tricky little interview questions if I practice but I am worried about what eon said about tech trivia questions, as I would consider that my weak point, even though I find it interesting. Saving links to those resources though, thanks mike.
 

D1G1T4L

[H]ard|Gawd
Joined
Feb 1, 2001
Messages
1,212
Let's say you have 2 light bulbs and a 100 story building. If you throw a light bulb from a floor number less than X, it will not break. And it will always break if the floor number is equal or greater than X. Assuming that you can reuse the light bulb which didn't break, find the X in the minimal number of throws.
 

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
What are some of the harder questions you might ask? Just curious to see what level I would be at after a little over 1 year at school / since I started programming.

I have 500 trillion integers. Write code to find the median of that set.

I have a list of integers that isn't sorted. It should contain one each of the numbers 0 through 250,000,000,000. But I think some numbers are missing. Write code to read my list, then tell me how many numbers are missing, and what they are.

WRite a function that takes a pointer to the root of a tree, and some node within the tree. Return to me an integer describing the depth of the node within that tree.

Write a function which takes an integer and reverse the bits, so that the least significant bit is the most significant bit, and so on. Return that new integer from the function.

Write a function that takes nWord, nBit, and bFlag. If bFlag is false, clear bit number nBit in nWord, and return it. If bFlag is true, set bit number nBit in nWord, and return it. Leave the rest of the bits unchanged.

Write malloc().

Write strrev().

Write bsearch().

Write a function that takes a pointer to the head of a singly linked list and tells me if there are any loops in that list.

Write a function to reverse the words in a sentence. If it gets "Good day to you", it returns the string "you to day Good".

I have a list of cities; I made a circularly linked list of it, so that the last city points at the first city again. At each node, you might find some gas -- or not. You know the distance to the next city. Write a function that takes a pointer to a city and a starting quantity of gas. Tell me if you can drive the whole loop at that starting point. If you can, return the pointer to that city back to me. If you can't, return a pointer to a city where you could start and be successful. Or, return a pointer to NULL if you simply can't do it.

I have an array of booleans: true or false. Walk the array and find the largest rectangular region of true cells that you can find.

Take this structure:

Code:
struct foo
{
   int n;
   char *pstrA;
   char *pstrB;
   char *pstrC;
};

and write this function:

Code:
struct foo * AllocateFoo( int n, char *pstrA, char *pstrB, char *pstrC );

which creates a new foo and initializes the pointers in it by copying the values passed in. Correctly handling errors is important.

What do you think of the Standard Template Library? Do you use it? Should we? Why or why not?

What do you think of MySQL (or SQL Server, or Visual Basic, or Porsches, or The White Sox)? Do you like it? Would you use it on a project (drive one, bet on them to win)? Why or why not?

A composing word is a word that has other words in it. "FIREMAN" is a composing word that has "IRE", "MAN", "FIRE", and "AN" in it. Write a program that takes as its input a list of words in my dictionary, and prints out the composing word with the most words inside it.

This mutex implemention has a bug in it. What is that bug?

How big is the database that runs United Airlines (Chubb Insurance, Bank of America, eBay, the NYSE)? What kind of hardware do you think they use? What kind of servers? Let's design both the hardware and some of the tables.

That's all I can think of now. For questions which write code, asking about performance characteristics, error handling, and testing is a given.
 

BDV

[H]ard|Gawd
Joined
Dec 12, 2006
Messages
1,957
I would so fail your interview! But I bet you would fail mine too :p
 

Blazestorm

Supreme [H]ardness
Joined
Jan 17, 2007
Messages
6,940
Is that not what you had wanted, Blazestorm?

Haha, no that was a good list... although some of them I have no idea how to do some of them or what exactly you mean. But I guess that just means there's a lot more to learn.

Things like write malloc() ... would require underlying knowledge of how the operating system handles memory / how to grab it. I've never dealt with anything like that. I've written memory managers/object allocators on top of new and malloc which handled pages of memory / freeing that memory / validating it etc. but never dealt with the operating system directly.

Or the 500 trillion integers... which I see a few problems with, first being that you wouldn't have enough memory on a system to hold all that data for sorting/looking through. So you'd have to split it up into parts, but not sure how would move from there.

If I had time I'd try to go through some of them, but honestly with school I have no spare time. Physics, Calculus II, Data Structures, 3D Graphics... where we get a basic OpenGL library that has 1 function we can use, which is SetPixel(x,y,r,g,b); and we have to write all the code to rasterize lines, and triangles. All the matrix/vector libraries and then all the matrices to move from model to world, to camera, to projection to NDC to viewport. So right now we just have a matrix stack and basic camera. On top of all that, gotta work on a team with 3 other guys and write a 2D game engine from scratch, have about 2 weeks to finish the engine and have a prototype for our game, while taking midterms for all those classes. Wooo!
 
Last edited:

MrWizard6600

Supreme [H]ardness
Joined
Jan 15, 2006
Messages
5,779
Things like write malloc() ... would require underlying knowledge of how the operating system handles memory / how to grab it. I've never dealt with anything like that. I've written memory managers/object allocators on top of new and malloc which handled pages of memory / freeing that memory / validating it etc. but never dealt with the operating system directly.!

yeah I was gonna say, short of the sys calls thats practically taken straight from more than a few midterms I've written.

But I mean, hey, there is LFS, so as a term project: write malloc() using LFS... could be done. Mind you LFS is more about shells than it is about changing UNIX. If your really wanted to modify the damn kernal, fork $1500 over to red-hat and get started.
 

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
Sounds like you're no-hire, then. malloc() is not a kernel call; it's a C-language runtime function. The point of the question is to start that conversation; it weeds out people who don't know where memory comes from when they make calls like malloc() or use operator new(). There are lots of reasons to need a different memory manager than the one supplied by the runtimes, and someone who hasn't run into such circumstances probably isn't very experienced; or, at least, doesn't really understand how their code is interacting with the system.

(There are kernel-level implementations of malloc() on some systems; POSIX, I think. But if that comes up in conversation, even better.)

If they do understand these things, then they'll want to know what tradeoffs they're making. Should their implementation of malloc() be concerned with multiple threads accessing it? Tracing leaks? Helping with buffer over- and under-runs? Rapidly allocating or re-allocating objects? Handling large or small blocks?

How would it interface with the system's memory allocation code? What system are we targeting, anyway?

And so on. This question is more about talking over a design than actually coding the implementation. it should get into eventually writing some of the code, though.
 

Blazestorm

Supreme [H]ardness
Joined
Jan 17, 2007
Messages
6,940
I know malloc() isn't a kernel call, but I guess I misunderstood what you actually were asking.

"write malloc()" is kind of vague. If you said "write a memory manager to replace the use of malloc in a program" then I'd have a better idea what you meant and can say I've written those before and understand pro's / con's of them.

What I don't know anything about is the kernel level stuff, how exactly malloc works underneath.
 

BDV

[H]ard|Gawd
Joined
Dec 12, 2006
Messages
1,957
Are you looking for a job as a C/C++ programmer? If not, a lot of those questions are not relevant.
 

Blazestorm

Supreme [H]ardness
Joined
Jan 17, 2007
Messages
6,940
I am working towards game development which is mostly C / C++ ... mikeblas works at Valve so I think asking him for questions they ask would be a good idea. I still have ~2.5 more years until I'm looking for a job though.
 

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
mikeblas works at Valve so I think asking him for questions they ask would be a good idea.
We ask questions like these, but I don't think any of the questions we actually use are on the list.

"write malloc()" is kind of vague. If you said "write a memory manager to replace the use of malloc in a program" then I'd have a better idea what you meant and can say I've written those before and understand pro's / con's of them.
Yes, it's very vague. But another thing that's vague is success. If a path to success was clear, we'd all be there, right? You're not going to go to work every day with clear instructions about what to do. I mean, maybe if you're a programmer, you will; if you're an engineer, then no. Deciding what to write, talking about writing it, and using good judgment to arrive at a sensible conclusion are all things a good engineer needs to demonstrate.
 

Blazestorm

Supreme [H]ardness
Joined
Jan 17, 2007
Messages
6,940
We ask questions like these, but I don't think any of the questions we actually use are on the list

Right, but you expect someone you're hiring to know those things, or at least be able to work through most of them.

That's all I was looking for, I've only been programming for a year... so still have a lot to learn :D
 

Wiseguy2001

2[H]4U
Joined
Nov 28, 2001
Messages
3,470

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
Let's say you have 2 light bulbs and a 100 story building. If you throw a light bulb from a floor number less than X, it will not break. And it will always break if the floor number is equal or greater than X. Assuming that you can reuse the light bulb which didn't break, find the X in the minimal number of throws.

How is this possible, since you only have two light bulbs?
 

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
Oh! I totally snoozed on reusing bulbs that didn't break.
 

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
Now that I un-confused myself, it's not that hard. I'm not positive I have a general case for the optimal solution, but I can grind one out.

Where are you stuck?
 

rflcptr

Supreme [H]ardness
Joined
Mar 27, 2008
Messages
6,249
Think I have it. Since a linear search is guaranteed to exhaust only one bulb and have a worst case of O(n), I thought about a binary search and went from there. So you have a building of [0 ... n] stories. Drop a bulb at n / 2. If it breaks, start a linear search from 0 to n / 2 until X is found (the second bulb breaks). If the first bulb didn't break, repeat the strategy on the upper half of the building, and so on.

For my solution, the worst case should be about O( n / 2 ). How's that compare to you?
 
Last edited:

Khanmots

Gawd
Joined
May 12, 2007
Messages
905
My 5-second solution would be to start at the bottom testing every other floor. If it breaks, try the next floor down.

Spending another minute thinking about it isn't having me see anything better than that.
 

rflcptr

Supreme [H]ardness
Joined
Mar 27, 2008
Messages
6,249
Oh!

If I take a 100 story building every time, I could drop the first bulb every 10 stories, until it breaks at say, b. Then linear search at [b - 9] to [b - 1], which would be a worst case of about 20, or O(n / 5). Looks like I'm already doing better, since the worst case has been improved by a factor of more than 1 / 2 from the binary approach. Then, there's the optimal "step size." Setting each step to 5 degrades the worst case to O(n / 4). Setting it to 20 also gets me O(n / 4).

edit: I didn't see Khanmots's post before mine.
My 5-second solution would be to start at the bottom testing every other floor. If it breaks, try the next floor down.

Spending another minute thinking about it isn't having me see anything better than that.
The worst case here though is still about O(n / 2).

I'm now thinking about a generic building of any amount of stories, X. Would the optimal step size for X be the closest non-remainder divisor of X to the square root of X?
 
Last edited:

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
Oh!

If I take a 100 story building every time, I could drop the first bulb every 10 stories, until it breaks at say, b. Then linear search at [b - 9] to [b - 1], which would be a worst case of about 20, or O(n / 5). Looks like I'm already doing better, since the worst case has been improved by a factor of more than 1 / 2 from the binary approach. Then, there's the optimal "step size." Setting each step to 5 degrades the worst case to O(n / 4). Setting it to 20 also gets me O(n / 4)

That's the right approach. Picking that "optimal step size", particularly for an arbitrary building height, starts to get tricky.
 

Khanmots

Gawd
Joined
May 12, 2007
Messages
905
Hm, good thoughts y'all. That said, I'm pretty sure the optimal step size is going to wind up being sqrt(n); althought I haven't done any math to back that up.
 

Tawnos

2[H]4U
Joined
Sep 9, 2001
Messages
3,808
That's the right approach. Picking that "optimal step size", particularly for an arbitrary building height, starts to get tricky.

Is it? The optimal size is always going to be such that the linear search is equal to or less than the stepped search. For a building of size n, this means that if you were to break it into m separate parts, the maximum linear search would also be m for an optimal result.
Thus,
n/m = m
n = m^2
sqrt(n) = m

*edit* gah, should have refreshed before posting, seems Khanmots already said the answer is sqrt(n) :)
 

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
In our 100-story example, sqrt(n) is 10.

If you're dropping from every tenth floor, your worst case scenario is 19 drops. For example, you drop on the 10th, 20th, 30th, and ... 100th floors. The egg doesn't break on the 90th floor drop, but does break from the 100th floor. You've done 10 drops and broken one egg. Given that breakage, you've got to start at the 91st floor and start dropping with an incremental search. You'll do 9 more drops to find that the egg breaks on the 99th floor. (We can't deduce that the egg doesn't break after dropping off the 98th floor because we might have a truly unbreakable batch of eggs -- that is, the building might not be tall enough.)

A step size of sqrt(n) gives an upper bound of 19 drops. It's possible to beat that upper bound by picking a better step size. The upper bound we've deduced with sqrt(n) is actually indirectly helpful in deducing the algorithm that picks our step size.
 

Tawnos

2[H]4U
Joined
Sep 9, 2001
Messages
3,808
In our 100-story example, sqrt(n) is 10.

If you're dropping from every tenth floor, your worst case scenario is 19 drops. For example, you drop on the 10th, 20th, 30th, and ... 100th floors. The egg doesn't break on the 90th floor drop, but does break from the 100th floor. You've done 10 drops and broken one egg. Given that breakage, you've got to start at the 91st floor and start dropping with an incremental search. You'll do 9 more drops to find that the egg breaks on the 99th floor. (We can't deduce that the egg doesn't break after dropping off the 98th floor because we might have a truly unbreakable batch of eggs -- that is, the building might not be tall enough.)

A step size of sqrt(n) gives an upper bound of 19 drops. It's possible to beat that upper bound by picking a better step size. The upper bound we've deduced with sqrt(n) is actually indirectly helpful in deducing the algorithm that picks our step size.
I may have missed an edge case or have a bug (since this is just typed in browser and hasn't had any testing done), but I think this is the solution for the problem when there are two eggs:
Code:
// There is no 0th floor, ground floor will be counted as 1. 
// That means in a 100 story building, the top floor is 100, not 99, and it will be returned as such.
// n = number of floors
// returns floor that egg will break on
int drop(int n)
{
int breakFloor = -1;
int step = (int)floor(sqrt(n));
for (int i = step; i <= n; i += step)
{
  if (eggBreaks(i))
  {
    for (int j = i - step + 1; j < i; ++j)
    {
      if (eggBreaks(j))
      {
        breakFloor = j;
      }
    }
    if (-1 == breakFloor )
    {
      breakFloor = i;
    }
    break; // an egg ;)
  }
  return breakFloor;
}

*edit* there are a couple improvements I could make - eliminate the <= and then add an if (-1 == floor) below that loop. Alternatively, I could store i outside of the loop, and do two sequential loops

*edit 2* like this:
Code:
// There is no 0th floor, ground floor will be counted as 1. 
// That means in a 100 story building, the top floor is 100, not 99, and it will be returned as such.
// n = number of floors
// returns floor that egg will break on
int drop(int n)
{
  int breakFloor = -1;
  int step = (int)floor(sqrt(n));
  int i = step;
  for (; i < n && !eggBreaks(i); i += step);
  for (int j = i - step + 1; j < i; ++j)
  {
    if (eggBreaks(j))
    {
      breakFloor = j;
      break;
    }
  }

  if (-1 == breakFloor )
  {
    breakFloor = i;
  }
  
  return breakFloor;
}
 
Last edited:
Top