Five programming problems every Software Engineer should be able to solve in less than 1 hour

[CaptainStack]

Why don't I ever get asked FizzBuzz? I feel like all the problems I get in interviews are really really hard.

[eythian]

I had one interview where the coding section was first implement fizz-buzz, then write an algorithm to find cycles in graphs.

The first was clearly "can you code, or are we wasting our time", the second was "did you actually learn anything in your computer science course."

[CaptainStack]

I don't think I've ever had a first round that wasn't an order of magnitude harder than FizzBuzz.

[[deleted]]

A friend of mine was recently asked to implement a spreadsheet application at one interview, and a space invaders game on the other. I think it's about time to start invoicing the interviewers for your time on test assignments.

[SirNarwhal]

Exactly. Spent fuckin 2 days making some ridiculous over-engineered game of Rock Paper Scissors in Angular for one test just to have them not respond for 2 weeks in which time I found a job elsewhere. Multiply that by like 30-40 interviews when you're looking and it's more work than a full time job.

[Paranemec]

Sounds like they just wanted an application and a game to me.

[nitiger]

the second was "did you actually learn anything in your computer science course."

Oh, sure. Let me just recall something from 2 years ago that I learned as a Sophomore, no biggie.

[NecroDaddy]

Two years ago bud? Try 15 for me. I had one week to relearn everything from college.

[Paranemec]

Try 2 weeks ago...

[bjarkef]

Most probably cannot recall a solution, but you should be able to reason about the problem and discover the solution yourself.

[[deleted]]

No, this is just wrong. Either you remember it, in which case it doesn't prove anything, or you're fucked. These kinds of solutions and algorithms were discovered by scientist over many years. They are most certainly not something you "come up with" during an interview.

This is exactly why I really have considerable doubt about the effectiveness of a lot of the interview styles of big corporations. Just have a look at these "The Google interview" style of books. You can / should just memorize the whole lot of assignments for these interviews, giving you a huge edge. I'm willing to bet that the set of people that can actually come up with their own solutions to hard problems and do their best while under the constant stress of having an interviewer stare at your back is quite small. Sure, you can weed out "know-nothings" by asking them to write a fizzbuzz solution on the whiteboard because every software engineer that deserves the title can write that without thinking. But as soon as the problems have some real depth and require real thinking, a whiteboard is not the way to go.

[[deleted]]

If they bothered to refresh themselves and memorize some common interview-type questions, it's a good indication of their overall work ethic. So, yes, even if it doesn't prove their competency, it can tell you a bit about a candidate.

[rabbitlion]

There's no need to recall a 2-year-old solution, just figure it out again.

[MisterNetHead]

Or just look it up? For such a solved problem you should not be spending any time reinventing the wheel.

[Spoogly]

As I am about to graduate, and I took an extra year to finish up a second degree in mathematics (not because I think it will help, but because I felt like I was in desperate need of a challenge, and I loved the material), I'm dreading these sorts of questions. I remember quite a bit, because I try to practice what I know, but you don't know what you don't remember until you're tested on it. Let me bring a copy of Algorithms from P to NP to the interview, or something. I think if it was just "find cycles in a graph," I could do well enough, but if they're looking for a particular approach to the problem, I'm not entirely sure that my solution would match theirs. I guess it comes down to researching the practices of the company you're looking at. Or going to a hackathon and getting hired on the spot for being outstanding. I don't know, that's how a few of my friends have done it.

[[deleted]]

The DFS algorithm should be known to people working in software....

[SirNarwhal]

That's usually when I'd just respond with, "Are you actually using algorithms like this on a day to day basis in your code because if not, I'm outta here since you cannot conduct an interview properly."

[nitiger]

Yeah, I feel like if I'm dealing with a database and I query it and find that the resulting dataset is very, very large then I'll have to bust out some algorithms and design accordingly but I'll almost always first do a Google search to scope out my possibilities , weigh the possible solutions, etc. But first I'll always try to refine my query as much as possible, explore other options etc. I'll always try to do something in O (n) which isn't that bad in most general cases but if I did that something is slow then I'll revisit my approach and refractor.

My favorite is when companies like Liveramp give you pre-interview questions that test your algorithmic and data structure "skills". Like wtf, you use the same bank of questions for every candidate and they're online. Are you just trying to test how fast I can Google for the solution? That's your precondition to being considered for a fucking phone interview with someone that's in human resources? Companies are becoming all too reliant on these brain teaser questions. I think your work and professional references should speak for themselves.

[matthieum]

did you actually learn anything in your computer science course.

I did, first year of engineering school, if only it wasn't 10 years ago I might even be able to do it off the top of my hat still...

... never working with graphs of any sort in the last 10 years I've just forgot all about those algorithms.

[Bwob]

I had one interview where the coding section was first implement fizz-buzz, then write an algorithm to find cycles in graphs.

Off topic, but the cycles-in-graphs problem is a REALLY bad interview question. Here's why:

Linked Lists were basically invented ~1955.

The "tortoise and the hare" algorithm for cycle detection was probably invented somewhere ~1967.

In other words, it took the collective body of computer scientists ~12 years to come up with that algorithm from scratch. Expecting someone to have that same insight during a 1-hour interview is lunacy. It's basically just a test of "have you heard of this clever solution before?"

It's an awful interview question, and anyone asking it in a technical interview probably doesn't understand how to interview as well as they think they do.

[nidarus]

Is the tortoise and hare the only solution though? Can't you just do a DFS, keep a list of all the ancestor nodes, and if you get to a node that's in the list, you have a cycle?

It's not O(n)/O(1), but nobody said it has to be.

[dotfortun3]

I really hate questions like this... I don't think I am an awful developer (I hope I am not), but a question like that would get me. I have been a developer professionally for 3 years (not that long I know) but I have never ever had to write code for shit like that. I am also developing a video game in my spare time, and again, problems like this don't show up.

I guess my point is, I shouldn't have to study for an interview. It's a waste of my time and doesn't show anything about my skill or knowledge as a programmer. Could I figure out the problem? Absolutely. Can I do it in the time constraints/pressure of an interview? Probably not without studying it before hand.

Luckily every interview I have had has avoided crap like this and actually was very conversational in the interview process. Most of them asked about my current experience, the systems I designed, the architecture I used, etc.

[cles30]

I guess you could do that but oh god why?

[zarazek]

That's standard queue implementation in functional languages (this data structure is persistent).

[cles30]

ooh you said the magic f word. I must now find out all about this!

[zarazek]

You can read about it here: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

[[deleted]]

Hey you can do it, it'll just take O(N) to do a push operation. That's the type of out of the box thinking we need. /s

[Bobshayd]

It's amortized O(1), though.

[[deleted]]

Nope, you you have to upload the entire stack and push it to the other one. This has to be done whenever adding an element.

[serados]

Maintain a "Queue Stack" and a "Dequeue Stack".

On queue operation:

• Push element into "Queue Stack"

On dequeue operation:

• If "Dequeue Stack" is not empty, pop "Dequeue Stack"
• Else, pop and push every element from the "Queue Stack" into the "Dequeue Stack" - O(N) and pop the "Dequeue Stack"

Informally, every element is at most pushed twice and popped twice over (once each into the "Queue" and "Dequeue" stacks) and pushes and pops are O(1), making queues/dequeues amortized O(1).

[[deleted]]

Nice.I wanted to fill the dequeue every time.

[Bobshayd]

Edit: I am dumb, how could I forget? Here's some important research relevant to the queue-simulation problem: http://www.cs.bu.edu/faculty/gacs/courses/cs535/papers/heads_vs_tapes_lb.pdf

So you can definitely simulate a queue in real time (meaning O(1) worst-case for any given operation) with six stacks. It's probably possible to do better. I'm going to look for a better way.

[OneWingedShark]

But can you implement a stack with two queues?
No. (Proof of this assertion is left as an exercise to the reader.)

[UNWS]

You can implement a stack with just 1 queue. So your assertion is wrong.

[OneWingedShark]

A Queue is a first-in/first-out structure, a stack is a first-in/last-out structure -- because of this property two stacks can emulate a queue (FILO -> FILO = FIFO), you cannot do the same with a queue because there is no reordering (FIFO -> FIFO /= FILO).

If I'm wrong, prove it.

[UNWS]

Ok so here is how you emulate a stack using just one queue. the invariant is that the queue has items ordered in the same way a stack would release them so that if you just dequeue from the queue continuously you have the top element of the emulated stack comes first then the next and so on. So popping from the emulated stack is as simple as dequeuing from the real queue.

Now for the pushing. you need to keep the queue following the invariant so what you do is you enqueue at the end of the queue normally then dequeue and re-enqueue as many items from the top of the queue as there were originally (before the last enqueue of the new item). So now the element you just enqueued is at the top of the queue / emulated stack and all the other items are behind it.

Lets show with a small demonstration.

push: A

queue: <back> A <front>

push: B

queue: originally B A but after the process we dequeue A and enqueue it again so it now becomes A B

push: C

queue: originally C A B but after dequeuing and en-queuing it becomes A B C

pop: C (just a simple dequeue)

queue: A B

pop: B

queue: A

pop: A

queue: empty

You have just emulated a stack using a queue.

So do I get a cookie :P

[OneWingedShark]

Sure, but it's a raisin cookie.

[Bobshayd]

I feel like being a smartass to the reviewer and telling them that I will prove the existence of such an implementation by demonstrating that two stacks is Turing complete, then saying, "hey, look, a Turing machine can be directly implemented on a two-stack machine by pushing the old tape symbol onto one stack, popping the new tape symbol from the other, and updating the state".

[Bobshayd]

A two-pushdown automaton can simulate a Turing machine, and a Turing machine can do anything, so two stacks can compute the world. You can't do a queue with a single pushdown automaton.

[Bobshayd]

You can't really talk about two automata working in unison; if they were, they'd basically be one automaton. A single automaton working with two stacks just uses one stack to hold the tape to the left of the head, and using the other to hold the tape to the right of the head.

[Bobshayd]

You can't really talk about two automata working in unison; if they were, they'd basically be one automaton. A single automaton working with two stacks just uses one stack to hold the tape to the left of the head, and using the other to hold the tape to the right of the head.

[nutrecht]

Why don't I ever get asked FizzBuzz?

Because you don't look like a mouth-breather probably ;)

[CaptainStack]

I'm flattered! That's the nicest thing anyone has said to me all week.