7 ms·

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

by BadCRC 13y 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 13y ago
Am I reading the problem incorrectly or is that just ridiculously easy?
- chacham15 13y 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 13y 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 13y 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 13y 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 13y 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 13y ago
  I would assume that you have an arbitrary number of windows already displayed that you cannot move.
  - jiggy2011 13y 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 13y 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 13y 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.

by BadCRC 13y ago

gamegoblin 13y ago

Am I reading the problem incorrectly or is that just ridiculously easy?

chacham15 13y 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 13y 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 13y 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 13y 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 13y 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 13y ago
I would assume that you have an arbitrary number of windows already displayed that you cannot move.
- jiggy2011 13y 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 13y 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 13y 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.