rahul_107's blog

Google / Swiggy Past Online Assessment | Solution?
By rahul_107, 4 years ago, In English 
### Question:
There is a grid with a balloon at some cells. Players can shoot arrows from outside the grid horizontally and vertically. Every arrow shot will burst all balloons in that row if fired horizontally and in that column if fired vertically.
Given the positions of the balloons in the grid find the minimum no of arrows required to burst all the balloons.

### Constraints:
1 <= N(No of ballons) <= 50
0 <= x, y -> Positions of the balloons < 10^9-1

### Input Format:
Line1: Integer denoting N.
Next N lines, where each of the ith lines contains two integers representing (row, col) of ith balloon.

### Sample Input :
6
15 21
33 8
17 21
17 8
28 11
28 19

### Sample Output:
3

### Sample Input :
6
15 1
15 2
15 3
15 4
18 1
20 1

### Sample Output:
2
  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (24)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where did this assessment held?

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Is the assessment going on right now, if so then pls remove the question.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rahul_107 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rahul_107 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

EDIT-Seems like I have the wrong approach

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Future can affect the past here :)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Wait, no, I can't see how it fails

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Let say for some balloon at (x, y) you shoot an arrow in vertical direction, then it affect the already calculated value for (x, y-1), (x, y-2).... (x, -INF);

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Please never change the original comment, now all replies make no sense to upcomming readers.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rahul_107 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

Think in terms of graph, assume line to point graph, it will be bipartite, then the question is minimum vertex cover on bipartite graph, or MBM using konig theorem.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can yoou share the link of the problem?

→ Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

This is such a bad problem for online assessment for job interviews.

I guess recruiters just select some problems from Hackerrank library for job interviews without even checking what the solution requires :P

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    IMO final objective of companies to take online assessment is to just reduce the number of candidates, so if they are achieving their objective goal why would they even care.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think we can solve it the following way in order, although i am not sure.

  1. If there are no balloon in that row and column, then remove that and increment the answer by one.

  2. Then If there are no balloon in this column, (it is profitable to hit by row). Hence remove all the balloons in this row. Similarly do for columns.

  3. Now if there is a balloon in a cell, then we have at least one balloon in that row and in that column. Hence there can be no more than 25 distinct rows or columns. We will do brute force(i.e. check all subset of rows / columns and then if we do row/column shot on that subset, then how many column/row shots I need for the remaining) and then get the minimum.

The complexity should be no more than O(N * 2^(N/2))

→ Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

This is min vertex cover of a bipartite graph. Construct a graph where the left nodes are the rows and right nodes are the columns with an edge between a row and a col iff that position in the grid contains a balloon. The min cut of this graph is the minimum number of arrows required to pop all balloons.

Since the max flow across a graph is equal to the min cut, we can solve this in V*sqrt(E) time after coordinate compressing to only count rows or columns with at least one balloon, or in other words 102*sqrt(50) runtime, which should be plenty fast enough if we use Dinic's algorithm to calculate the max flow.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    smh people hiring software engineers based on this. Yeah, in the 2AM server crash, someone who knows vertex cover, and Dinic's algorithm will fix it in mere minutes.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      You dont have any idea how difficult it is to manage google's servers!

      Any company can face such issues, and it happens once in a blue moon. The fact that that google has been able to manage everything smoothly so far suggests that the people they hired are not bad.

      Of course one cannot be a master of everything. Once you enter an organization you have to learn stuff.

      So people who can think smart and learn fast do great in this IT field.

      → Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

https://tryalgo.org/en/matching/2016/08/05/konig/

This is a good article to understand the minimum vertex cover for a bipartite graph.

→ Reply