43 ms·

I hope this doesn't sound facetious, but what I hear over and over again is that places like Facebook have difficult technical interviews that are algorithm foc

I hope this doesn't sound facetious, but what I hear over and over again is that places like Facebook have difficult technical interviews that are algorithm focused to create more false negatives than false positives because they work on hard problems. What are some concrete examples of hard problems tech companies face that require novel solutions and why are algorithms problems the best way to find the people qualified to solve them? I know these seem like a naive questions, but these two things seem to be taken for granted in every interview discussion (or even if someone argues against them it's mostly a "this is how I find good people" argument). I think it's pretty clear this isn't the only way to find good people, I'd just love to hear more about the thinking behind this interview style and what it really means to these companies when they say "we deal with hard problems." The only concrete example I've ever been given is someone at another big Valley company speaking about difficulty of master-master writes between data centers at a large scale. Which certainly qualifies but I'd love to hear what other "hard problems" are out there.

BadCRC 14y ago
one I was given in an interview: You're working on the front-end development for a chatting website. Each conversation gets it's own 100x200px div and they are placed on the screen such that two conversation windows are never intersecting. We want to display a new conversation window, write an algorithm to determine where a conversation can be placed such that it does not overlap with any current conversations. Assume that the website is being displayed at 1024x1280px.
- gamegoblin 14y ago
  Am I reading the problem incorrectly or is that just ridiculously easy?
  - chacham15 14y ago
    As stated this seems really easy. I think it is supposed to be more like Meebo where the users can resize/move every window (i.e. they dont have to be aligned to any boundary) and they recieve a new message. The Meebo software wants to place a new 100x200 window not on top of any existing window. Write the algorithm to determine where to place it. Then generalize the algorithm to WxH. Hard enough? (If not, find an algorithm that does this in linear time)
    - anonymoushn 14y ago
      Is there a linear time solution? The normal solution is O(N^3) in the number of windows (and does not depend on W,H at all).
      - rlanday 14y ago
        Facebook Hacker Cup had a similar problem: https://www.facebook.com/hackercup/problems.php?pid=532506256782917&round=189890111155691 https://www.facebook.com/hackercup/problems.php?pid=53250625... I almost solved it; after screwing around for a while trying to record only one value for each square, I realized you need to store two values for each square. If we’re looking for the upper-left corner we can put a window, each dead pixel/pixel “poisons” all the pixels less than the width of the window to the left of it and the height of the window above it. Then you just do a linear scan over the remaining pixels. I think my problem was that I used too much RAM because I was trying to store the whole 2D grid; you only need to keep one dimension in memory. You can see people’s submissions here: https://www.facebook.com/hackercup/scoreboard?round=189890111155691 https://www.facebook.com/hackercup/scoreboard?round=18989011...
        anonymoushn 14y ago
        This problem is interesting. It doesn't make any sense to use an N^3 solution like the Meebo problem if N can be so large. I haven't looked at any solutions, but it seems like an N*lg N + WH solution would pass.
- jiggy2011 14y ago
  You can fit at most 60 chat windows on the screen. So surely you can just start at the top left and wrap around every 10 windows? When you get to 60 you can't display any more. Or is the problem different? For example you already have some arbitrary number of windows already displayed at arbitrary locations that you cannot move?
  - btilly 14y ago
    I would assume that you have an arbitrary number of windows already displayed that you cannot move.
    - jiggy2011 14y ago
      In that case, it's probably most space efficient to place each new window next to an already visible window or at an edge of the screen. So keep a list of possible candidate positions. Each of these positions represents either an edge of the screen or a position directly above/below/to the left/to the right of an existing window. You will need to calculate different offsets for each of these circumstances to generate candidate positions. You easily eliminate ones that fall outside of the screen. Each time you attempt to add a window you iterate the list of candidate positions. If a candidate position can fit a window (just use brute force 2D AABB collision detection against all windows, or a quadtree/spatial hash to optimise) then place the window there. If it cannot fit remove the position from the candidate list. Once you have added the window, calculate all the candidate positions (for each side) and add these to the list of possible positions for later windows. Well it's late and that's the best I can manage.. I know somebody will point out a flaw here :)
      - chacham15 14y ago
        You know, for people who have taken graphics classes, this seems like a much easier question because they know about AABB trees. That is the problem at the heart of the question. Also, your idea about candidate positions is wasteful. Just invert the tree so that it contains empty space instead of full space. Then, on insert, remove from the tree.
- victorhn 14y ago
  Naive solution: There are 924x1080 px as possible candidates for the upper-left corner of the new rectangle. Test each of these candidates to see if a rectangle placed there is a valid position. The complexity would be O(W * H * n) where W,H = dimensions in pixels of the screen, n = number of already placed windows. For practical purposes i think this would be a good solution, assuming the need for a new window is not very frequent. I suspect the complexity can be improved though, maybe with some sweep line algorithm.
jiggy2011 14y ago
I guess they also hire a lot of young people who might not have a lot of practical software engineering experience. They probably have studied a lot of algorithms at college though so that is probably the best way to test how good they are at applying things they have learnt. I also guess that when you run the largest online community out there you might run into problems that you can't find the answer to on stack overflow. Even if these are not the majority of problems you face day to day there's an advantage to having staff on-site who have a hope of solving them.
somethingnew 14y ago
For my Facebook interview for an internship, I was given a simple string manipulation problem which I solved quickly. Then I was given the N-Queens problem (a more generalized version of this one http://en.wikipedia.org/wiki/Eight_queens_puzzle http://en.wikipedia.org/wiki/Eight_queens_puzzle). Needless to say I didn't solve that with my remaining time, since the interviews are only 45 minutes. I didn't feel it was a fair assessment of my skills.
- gburt 14y ago
  Where there other constraints on your N-queens? (no bruteforce? no backtracking? must run in X time?)
  - somethingnew 14y ago
    Really it was just write code to verify whether it can be done or not (return boolean) based on the N input (integer). Without having to write code it would return true for N >= 4, but I didn't know that. I was just trying to get an initial solution down with recursion, not thinking about backtracking yet or worst case time (which was probably 2^N).
- mattacular 14y ago
  Do they really expect people to solve 8 queens in under 45 minutes? Even if you already know how to approach the problem, writing out the code to do it would take most of that time it seems like. Maybe they were trying to ascertain something else about their candidates. Like how they approach problem-solving in general?
gukjoon 14y ago
This is a great question. I can't speak to Facebook, but I ask hard algorithm questions and this is why I do it. The point of these hard questions is not to assess if you know some obscure algorithm. The algorithms in these questions are obscure precisely because you're not supposed to know them. If the candidate clearly knows the algorithm I switch to a new question. The point of these questions is to assess your ability to perform under pressure in an unfamiliar situation, which is a fundamental skill that all productive engineers require. I expect that any engineer I greenlight to encounter novel situations. These are not necessarily Hard Problems dun dun dun, but these situations will challenge your problem solving skills and you won't be able to look up the right answer on StackOverflow. I expect candidates to have the ability to deliver a solution that works and makes the right tradeoff between time, quality, and scope. I have also had interviewers ask hard problems for the wrong reasons. Frowntown to that.
btilly 14y ago
What are some concrete examples of hard problems tech companies face that require novel solutions and why are algorithms problems the best way to find the people qualified to solve them? This is best answered by awesome example. See http://research.google.com/people/jeff/ http://research.google.com/people/jeff/ for a list of some the problems that one Google programmer met, and solved. Many of said problems were novel at the time, though many have now learned the answers that Jeff came up with. These kinds of problems and answers are simply not understandable to people who don't understand algorithms. And you can tell people without a deep understanding of algorithms how to solve those problems, and they will consistently get it wrong.
- kamaal 14y ago
  >>These kinds of problems and answers are simply not understandable to people who don't understand algorithms. Are you saying that jeff or whoever algo genius can come up with a solution to all those problems given say a couple of hours? C'mon- Problem solving especially of difficult problems or big problems or long term projects is pretty much an iterative process. In which discovery and application of knowledge, and staying productive is more important than number of facts in the head.
  - btilly 14y ago
    Are you saying that jeff or whoever algo genius can come up with a solution to all those problems given say a couple of hours? Of course not. Those problems and solutions were the result of years of work, by one of the best programmers on the planet. (Inside of Google, Jeff is a legend.) The question was what real problems faced by real companies require an algorithm person to solve, and that is an answer. But any toy algorithm problem that you could be given in an interview, he could solve instantly. I guarantee it. Heck, I'm nothing on his scale. Yet most algorithm questions that I see people complain about having been given in an interview I can figure out a decent solution to in under 2 minutes. When I hear people talking about prepping for that sort of question, it seems to me like they are missing the point.
- vjeux 14y ago
  /What are some concrete examples of hard problems tech companies face that require novel solutions/ I'm a User Interface Engineer at Facebook in the Photos team. One common thing we do is to display photos in a grid. This is one subject that's really important, yet I haven't see any good documentation about it. I've first looked at all the websites that did some interesting image layouts algorithms, reproduced them and documented them. Google Plus: http://blog.vjeux.com/2012/image/image-layout-algorithm-google-plus.html http://blog.vjeux.com/2012/image/image-layout-algorithm-goog... Lightbox: http://blog.vjeux.com/2012/image/image-layout-algorithm-lightbox.html http://blog.vjeux.com/2012/image/image-layout-algorithm-ligh... Lightbox Android: http://blog.vjeux.com/2012/image/image-layout-algorithm-lightbox-android.html http://blog.vjeux.com/2012/image/image-layout-algorithm-ligh... 500px: http://blog.vjeux.com/2012/image/image-layout-algorithm-500px.html http://blog.vjeux.com/2012/image/image-layout-algorithm-500p... Unfortunately, none of them really suited our needs. We wanted to let users have the ability to make any (or all) images bigger. So I started playing around and writing a new image layout. The hardest part was to have an algorithm that was designed such that you could move images around in real time in ways that feel natural to the user, even though we have constraints that are impossible to solve. Basic algorithm: http://blog.vjeux.com/2012/image/image-layout-algorithm-facebook.html http://blog.vjeux.com/2012/image/image-layout-algorithm-face... Reordering algorithm: http://blog.vjeux.com/2012/image/image-layout-algorithm-facebook-reordering.html http://blog.vjeux.com/2012/image/image-layout-algorithm-face...
svachalek 14y ago
In my experience, I've seen 3 kinds of jobs that demand engineers who can solve "hard" problems: 1. Obviously hard, and needs no explanation e.g. self-driving cars. 2. Basic problems done at ridiculous scale. Quickly matching keywords to web pages is not a hard problem; quickly matching keywords to every web page on the internet is a hard problem. 3. The problem is that (forgivably or not, depending on circumstances) we have no idea what we're trying to do.
- jiggy2011 14y ago
  You can also add, doing all of the above things in a situation where it is extremely profitable for others to game your system.
freshfunk 14y ago
At the larger tech companies, many of their problems typically are an issue of scale. They are dealing with large datasets, massive numbers of users, terabytes of data, etc. When dealing with scale, its important to have efficient solutions. They may need to be time efficient or space efficient due to constraints. Even though space is cheap and hardware is fast, inefficient algos may never work or be very high cost. Maybe you won't be the one implementing this infrastructure but you may be implementing code on top of this infrastructure and it matters that you understand (at least the basics) the consequences of designing things a certain way.

BadCRC 14y ago

one I was given in an interview: You're working on the front-end development for a chatting website. Each conversation gets it's own 100x200px div and they are placed on the screen such that two conversation windows are never intersecting. We want to display a new conversation window, write an algorithm to determine where a conversation can be placed such that it does not overlap with any current conversations. Assume that the website is being displayed at 1024x1280px.

gamegoblin 14y ago
Am I reading the problem incorrectly or is that just ridiculously easy?
- chacham15 14y ago
  As stated this seems really easy. I think it is supposed to be more like Meebo where the users can resize/move every window (i.e. they dont have to be aligned to any boundary) and they recieve a new message. The Meebo software wants to place a new 100x200 window not on top of any existing window. Write the algorithm to determine where to place it. Then generalize the algorithm to WxH. Hard enough? (If not, find an algorithm that does this in linear time)
  - anonymoushn 14y ago
    Is there a linear time solution? The normal solution is O(N^3) in the number of windows (and does not depend on W,H at all).
    - rlanday 14y ago
      Facebook Hacker Cup had a similar problem: https://www.facebook.com/hackercup/problems.php?pid=532506256782917&round=189890111155691 https://www.facebook.com/hackercup/problems.php?pid=53250625... I almost solved it; after screwing around for a while trying to record only one value for each square, I realized you need to store two values for each square. If we’re looking for the upper-left corner we can put a window, each dead pixel/pixel “poisons” all the pixels less than the width of the window to the left of it and the height of the window above it. Then you just do a linear scan over the remaining pixels. I think my problem was that I used too much RAM because I was trying to store the whole 2D grid; you only need to keep one dimension in memory. You can see people’s submissions here: https://www.facebook.com/hackercup/scoreboard?round=189890111155691 https://www.facebook.com/hackercup/scoreboard?round=18989011...
      - anonymoushn 14y ago
        This problem is interesting. It doesn't make any sense to use an N^3 solution like the Meebo problem if N can be so large. I haven't looked at any solutions, but it seems like an N*lg N + WH solution would pass.
jiggy2011 14y ago
You can fit at most 60 chat windows on the screen. So surely you can just start at the top left and wrap around every 10 windows? When you get to 60 you can't display any more. Or is the problem different? For example you already have some arbitrary number of windows already displayed at arbitrary locations that you cannot move?
- btilly 14y ago
  I would assume that you have an arbitrary number of windows already displayed that you cannot move.
  - jiggy2011 14y ago
    In that case, it's probably most space efficient to place each new window next to an already visible window or at an edge of the screen. So keep a list of possible candidate positions. Each of these positions represents either an edge of the screen or a position directly above/below/to the left/to the right of an existing window. You will need to calculate different offsets for each of these circumstances to generate candidate positions. You easily eliminate ones that fall outside of the screen. Each time you attempt to add a window you iterate the list of candidate positions. If a candidate position can fit a window (just use brute force 2D AABB collision detection against all windows, or a quadtree/spatial hash to optimise) then place the window there. If it cannot fit remove the position from the candidate list. Once you have added the window, calculate all the candidate positions (for each side) and add these to the list of possible positions for later windows. Well it's late and that's the best I can manage.. I know somebody will point out a flaw here :)
    - chacham15 14y ago
      You know, for people who have taken graphics classes, this seems like a much easier question because they know about AABB trees. That is the problem at the heart of the question. Also, your idea about candidate positions is wasteful. Just invert the tree so that it contains empty space instead of full space. Then, on insert, remove from the tree.
victorhn 14y ago
Naive solution: There are 924x1080 px as possible candidates for the upper-left corner of the new rectangle. Test each of these candidates to see if a rectangle placed there is a valid position. The complexity would be O(W * H * n) where W,H = dimensions in pixels of the screen, n = number of already placed windows. For practical purposes i think this would be a good solution, assuming the need for a new window is not very frequent. I suspect the complexity can be improved though, maybe with some sweep line algorithm.

jiggy2011 14y ago

I guess they also hire a lot of young people who might not have a lot of practical software engineering experience. They probably have studied a lot of algorithms at college though so that is probably the best way to test how good they are at applying things they have learnt. I also guess that when you run the largest online community out there you might run into problems that you can't find the answer to on stack overflow. Even if these are not the majority of problems you face day to day there's an advantage to having staff on-site who have a hope of solving them.

somethingnew 14y ago

For my Facebook interview for an internship, I was given a simple string manipulation problem which I solved quickly. Then I was given the N-Queens problem (a more generalized version of this one http://en.wikipedia.org/wiki/Eight_queens_puzzle http://en.wikipedia.org/wiki/Eight_queens_puzzle). Needless to say I didn't solve that with my remaining time, since the interviews are only 45 minutes. I didn't feel it was a fair assessment of my skills.

gburt 14y ago
Where there other constraints on your N-queens? (no bruteforce? no backtracking? must run in X time?)
- somethingnew 14y ago
  Really it was just write code to verify whether it can be done or not (return boolean) based on the N input (integer). Without having to write code it would return true for N >= 4, but I didn't know that. I was just trying to get an initial solution down with recursion, not thinking about backtracking yet or worst case time (which was probably 2^N).
mattacular 14y ago
Do they really expect people to solve 8 queens in under 45 minutes? Even if you already know how to approach the problem, writing out the code to do it would take most of that time it seems like. Maybe they were trying to ascertain something else about their candidates. Like how they approach problem-solving in general?

gukjoon 14y ago

This is a great question. I can't speak to Facebook, but I ask hard algorithm questions and this is why I do it. The point of these hard questions is not to assess if you know some obscure algorithm. The algorithms in these questions are obscure precisely because you're not supposed to know them. If the candidate clearly knows the algorithm I switch to a new question. The point of these questions is to assess your ability to perform under pressure in an unfamiliar situation, which is a fundamental skill that all productive engineers require. I expect that any engineer I greenlight to encounter novel situations. These are not necessarily Hard Problems dun dun dun, but these situations will challenge your problem solving skills and you won't be able to look up the right answer on StackOverflow. I expect candidates to have the ability to deliver a solution that works and makes the right tradeoff between time, quality, and scope. I have also had interviewers ask hard problems for the wrong reasons. Frowntown to that.

btilly 14y ago

What are some concrete examples of hard problems tech companies face that require novel solutions and why are algorithms problems the best way to find the people qualified to solve them? This is best answered by awesome example. See http://research.google.com/people/jeff/ http://research.google.com/people/jeff/ for a list of some the problems that one Google programmer met, and solved. Many of said problems were novel at the time, though many have now learned the answers that Jeff came up with. These kinds of problems and answers are simply not understandable to people who don't understand algorithms. And you can tell people without a deep understanding of algorithms how to solve those problems, and they will consistently get it wrong.

kamaal 14y ago
>>These kinds of problems and answers are simply not understandable to people who don't understand algorithms. Are you saying that jeff or whoever algo genius can come up with a solution to all those problems given say a couple of hours? C'mon- Problem solving especially of difficult problems or big problems or long term projects is pretty much an iterative process. In which discovery and application of knowledge, and staying productive is more important than number of facts in the head.
- btilly 14y ago
  Are you saying that jeff or whoever algo genius can come up with a solution to all those problems given say a couple of hours? Of course not. Those problems and solutions were the result of years of work, by one of the best programmers on the planet. (Inside of Google, Jeff is a legend.) The question was what real problems faced by real companies require an algorithm person to solve, and that is an answer. But any toy algorithm problem that you could be given in an interview, he could solve instantly. I guarantee it. Heck, I'm nothing on his scale. Yet most algorithm questions that I see people complain about having been given in an interview I can figure out a decent solution to in under 2 minutes. When I hear people talking about prepping for that sort of question, it seems to me like they are missing the point.
vjeux 14y ago
/What are some concrete examples of hard problems tech companies face that require novel solutions/ I'm a User Interface Engineer at Facebook in the Photos team. One common thing we do is to display photos in a grid. This is one subject that's really important, yet I haven't see any good documentation about it. I've first looked at all the websites that did some interesting image layouts algorithms, reproduced them and documented them. Google Plus: http://blog.vjeux.com/2012/image/image-layout-algorithm-google-plus.html http://blog.vjeux.com/2012/image/image-layout-algorithm-goog... Lightbox: http://blog.vjeux.com/2012/image/image-layout-algorithm-lightbox.html http://blog.vjeux.com/2012/image/image-layout-algorithm-ligh... Lightbox Android: http://blog.vjeux.com/2012/image/image-layout-algorithm-lightbox-android.html http://blog.vjeux.com/2012/image/image-layout-algorithm-ligh... 500px: http://blog.vjeux.com/2012/image/image-layout-algorithm-500px.html http://blog.vjeux.com/2012/image/image-layout-algorithm-500p... Unfortunately, none of them really suited our needs. We wanted to let users have the ability to make any (or all) images bigger. So I started playing around and writing a new image layout. The hardest part was to have an algorithm that was designed such that you could move images around in real time in ways that feel natural to the user, even though we have constraints that are impossible to solve. Basic algorithm: http://blog.vjeux.com/2012/image/image-layout-algorithm-facebook.html http://blog.vjeux.com/2012/image/image-layout-algorithm-face... Reordering algorithm: http://blog.vjeux.com/2012/image/image-layout-algorithm-facebook-reordering.html http://blog.vjeux.com/2012/image/image-layout-algorithm-face...

svachalek 14y ago

In my experience, I've seen 3 kinds of jobs that demand engineers who can solve "hard" problems: 1. Obviously hard, and needs no explanation e.g. self-driving cars. 2. Basic problems done at ridiculous scale. Quickly matching keywords to web pages is not a hard problem; quickly matching keywords to every web page on the internet is a hard problem. 3. The problem is that (forgivably or not, depending on circumstances) we have no idea what we're trying to do.

jiggy2011 14y ago
You can also add, doing all of the above things in a situation where it is extremely profitable for others to game your system.

freshfunk 14y ago

At the larger tech companies, many of their problems typically are an issue of scale. They are dealing with large datasets, massive numbers of users, terabytes of data, etc. When dealing with scale, its important to have efficient solutions. They may need to be time efficient or space efficient due to constraints. Even though space is cheap and hardware is fast, inefficient algos may never work or be very high cost. Maybe you won't be the one implementing this infrastructure but you may be implementing code on top of this infrastructure and it matters that you understand (at least the basics) the consequences of designing things a certain way.