# How do the algorithms to solve problems encountered in interviews translate into real world solutions?

I have recently finished an undergraduate course in computer science and I am looking for a job. During the search I encountered several interesting (and tough) problems that needed clever algorithms to solve. I also use google code jam as a practice set.

I cannot understand how those solutions translate in solving real world problems. Many problems appear (to me) not only contrived and fantastical but also highly specific to be a general purpose solution (although it isn't impossible to extend them using ingenuity).

Are these problems there only to test the problem solving skills or are these some aspect of real world problem camouflaged?

-
You are assuming they are supposed to translate to solving real world problems. They are not. They are supposed to help the interviewer find out if you have good analytic and algorithmic capabilities. –  Oded May 25 '12 at 10:38
@josh88: if you give some examples for those problems, the community here may tell you if and how they are related to real-world problem. –  Doc Brown May 25 '12 at 11:21
Lifting a barbell over your head is itself something you will never, ever need to do in real life, but if you do it a lot, you'll be much better at moving heavy furniture. –  Steven Burnap May 25 '12 at 15:56
Not everything learnt would be used in real world and not everything used in real world is taught at college. Its just gives a set of tools and a way of thinking to expand our knowledge that could help in solving real-world problems. When Newton invented calculus(no copyright wars on who actually invented it), he would have never thought if being used to predict stock prices –  Ubermensch May 26 '12 at 4:21
@josh88, you might want to check out the following question - programmers.stackexchange.com/questions/137462/… –  user396089 May 26 '12 at 21:29

Usually, interview problems are simpler than the actual problems that arise on the job. The interview problems are designed to see if you are familiar with fundamental algorithms and data structures: hashing, tree traversal, graph search, dynamic programming, etc. Every CS graduate should know these, but many don't.

-

Generally these questions are only there to test your problem solving skills especially, as you've found, when you're asked for a solution to a contrived scenario.

However, you may find in some cases the company will use examples from their field, but that's usually because they can pull an example from their own code base, so they already have a good solution (or, at least, a working one) - and see if you can come up with something similar. But even in these cases, it's not as if they're looking for someone who can solve a particular problem for them.

Just concentrate on your general problem solving ability. It's like learning to drive... practice often and for long enough and it will become second nature. Good luck!

-

Sometimes they don't translate to the company's core business at all. That's a fact.

However, at least some of the time, they are associated with a core business problem that the team, or the company, you're interviewing with, faces.

At one company I interviewed with, mostly known for helping users find a cost-effective flight, I was asked a couple of problems with roots in combinatorial complexity and in routing. One of them was an n choose k problem, which certainly can come up when you have a large number of sets and you need to enumerate all subsets of say, 1, 2 or 3 elements; there's at least a plausible case that finding all nonstop, one-stop and 2-stop flights might benefit from knowing how to solve the abstract problem. Separately, I was asked a 2D convex hull problem, which is closely related to a bunch of problems used in say, collision detection in computer graphics, some classes of image recognition and graphics-to-text transformation problems, and, in fact, certain classes of routing problems; they might as well have asked me about the minimum spanning tree problem, which has previously been used by, say, telephone companies to figure out where to nearly-optimally place telephone poles and switches and the like, and comes up in transportation problems as well.

In this particular team, I wouldn't have had any involvement in solving routing problems; I would have been mostly focused on internationalization work. But perhaps because of the culture of the organization, and their core business problems, these types of problems now pervade their software developer interview process, regardless of what you might end up actually working on.

Although I didn't do particularly well solving these problems, given my very non-algorithmic, non-academic background in software, I somehow was offered a job; I'm guessing that in some organizations, they just want to see you sweat, and see how you approach problems out of your comfort zone under pressure. In some teams, it might have actually been important to also solve the problem well, rather than just demonstrate your thought process.

While I don't think this is the best possible strategy to identify good developers, Google, Amazon, Microsoft, and dozens of other well-known companies have adopted the algorithm-heavy ritualized hazing interview process, so it may be unavoidable depending on where you want to work. You can prepare for them by reading Skiena's Algorithm Design Manual, which will help you pattern match concrete problems to abstract ones, and lead you to propose appropriate solutions, even if you can't implement them in an hour long coding interview.

If I were interviewing a candidate for a role that involved deep algorithmic knowledge, I would be inclined to probe by proposing problems that require them to pull from their algorithm toolkit. However, in most of my work, I focus mostly on finding candidates that realize why doing three layers of nested loops to issue separate queries to an external source one ID at a time is a bad idea, and try to find proof that they know how to do better than that. I focus on seeking evidence that they've figured out some sensible strategies for writing maintainable code, that they have intellectual curiosity, and that they have basic social skills. I try to verify that they've worked deeply enough through some problem that they've learned enough to be the local expert on it.

If you end up interviewing at a company whose business is built around solving some tough problem with the help of smart algorithms, there's a good chance they'll try to find evidence that you, too, can solve problems with the help of smart algorithms. I also think that, even if you end up writing "boring" enterprisey software, having a firm grasp on the landscape of algorithms is worthwhile, because you'll recognize insanely bad approaches when you see them and you'll step back and try to come up with better solutions. I've now seen a ton of crappy production code that basic computer science applied to the problem would have prevented.

Because of that, even though I don't find the algorithm-heavy interview as useful as some companies appear to, I am convinced that, if you can't see the connection between abstract algorithms and real business problems, the problem is, at least in part, you. You can get practice on pattern matching with the help of Skiena's book and by thinking about real world problems that you'd like to solve and implementing defensible solutions, so do that.

-

Sometimes it's just useful to test, how employees will react to unusual problems. I'm sure, if you're applying for a position of a web developer, you can set up a wordpress blog or write your own. But you can't fully evaluate someones skills by giving them routine problems.

To do that, you need to push the boundaries a bit further and throw the candidate off balance. Give him a tough problem and see, how he reacts. Will he be able to quickly solve it by himself? Or will he just say "Hey, I would just google it, I'm sure there's a ready to use solution for this". Both approaches have it's ups and downs, and both answers are acceptable. Most of the time it doesn't even matter, weather the candidate will be able to solve the problem, but it's important, how he addresses it.

-

It depends on the type of programming jobs you're interviewing for and who's doing the interviewing.

If the potential employer is hiring someone who's going to be working on an embedded system where there aren't any existing frameworks or libraries, they may need someone who can code clever algorithms. In this case, it's a valid thing to ask.

But, if they're looking for someone to maintain and enhance a 5 year old corporate CRUD or reporting app, then it's probably a waste of their time and yours to ask you to code an algorithm that's already in the framework they're using (example, asking someone to code a sorted list in C# from scratch). It's much more valuable to give them an example of something that needs to be fixed/enhanced and let them tell you how they would approach it.

It's my opinion that to a lot of interviewers use complex programming puzzles and other such stuff unrelated to the work they're doing to make themselves feel superior to applicants rather than to evaluate the applicants' skill level. Others use them because Google/Facebook/Microsoft/etc. use them so they think they should too in order to be 'cool'.

I'm not to saying that asking problem solving questions should be off limits but that good ones should fit the job or be reasonably simple and generic with no trickery or gotchas involved. FizzBuzz instead of Kobayashi Maru

So, in my experience, such questions rarely have anything to do with the job at hand and some are asked for the wrong reasons.

-

It all depends on the software you're working on. CRUD solutions typically aren't very clever unless you're attempting to replace various analytical\clerical professionals with software. If you get into data mining with statistical analysis, it might help to know various ways of structuring data. You're going to need to know your geometry operations if you're going to work with graphics. Understanding various numerical algorithms is extremely important if you go into engineering or financial areas where accuracy and speed are crucial. Algorithms are among the skills that will allow you to explore and work in an area that pushes the envelope in some domain as opposed to working on another reporting solution.

-