Can anyone offer suggestions on how to tackle this problem?
PS: This came in an online assessment of Uber (India)
# | User | Rating |
---|---|---|
1 | Benq | 3783 |
2 | jiangly | 3666 |
3 | tourist | 3611 |
4 | Um_nik | 3536 |
5 | inaFSTream | 3477 |
6 | fantasy | 3468 |
7 | maroonrk | 3464 |
8 | QAQAutoMaton | 3428 |
9 | ecnerwala | 3427 |
10 | Ormlis | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 184 |
2 | adamant | 178 |
3 | awoo | 177 |
4 | nor | 169 |
5 | maroonrk | 165 |
6 | -is-this-fft- | 163 |
7 | antontrygubO_o | 152 |
7 | ko_osaga | 152 |
9 | dario2994 | 150 |
10 | SecondThread | 149 |
Can anyone offer suggestions on how to tackle this problem?
PS: This came in an online assessment of Uber (India)
Name |
---|
Observe that any two nodes connected by an edge must belong to group with different parity (odd or even). So, if the graph has odd cycles, the answer doesn't exist.
Secondly, observe that if a node $$$i$$$ belongs to group $$$1$$$, all its neighbours must belong to group $$$2$$$. I can safely replace the group of node $$$i$$$ with group $$$3$$$. It won't make a difference. So, WLOG I can say that there is exactly $$$1$$$ node which belongs to group $$$1$$$.
Next, fix a node $$$j$$$ belonging to group $$$1$$$. Then, imagine assigning groups to nodes in increasing order. This seems similar as BFS! So, start a BFS with node $$$j$$$, and whenever you reach an unvisited node, just assign it the appropriate group number, more formally, if you reach unvisited node $$$u$$$ via node $$$v$$$, then assign the group of node $$$u$$$ as $$$g[v] + 1$$$, where $$$g[i]$$$ denotes group of node $$$i$$$, finally take the maximum group number among all the possible starting node $$$j$$$.
Complexity: $$$O(N*(N+M))$$$ where, $$$N$$$ is the no. of nodes and $$$M$$$ is the number of edges.
Its too blurry, the condition part. Please can you clear that
We are given N cities and M bridges, each bridge connects two cities where it is possible to travel from any one city to any other city using a sequence of bridges.
We want to divide these N cities into X disjoint groups G1, G2....Gx such that any one of the following conditions meet for any bridge that connects two cities A and B:
if A belongs to Gi then B belongs to Gi+1 (1 <= i <= x-1) if A belongs to Gi then B belongs to Gi-1 (2 <= i <= x) Find the maximum value of X, or print -1 if such division is impossible
Constraints 2 <= N <= 250
Input Format
First line contains N, an integer N line follows, one for each city, ith line contains N characters , where the jth character is 1 if there is a bridge between city i and j, else the character is 0
Sample Input 1
4 0111 1011 1101 1110
Sample Output 1
-1
Explanation It is not possible to divide the cities into different groups by following the given constraints
Sample Input 2
2 01 10
Sample Output 2
2
Explanation City 1 can be in 1st group and city 2 can be in 2nd group, hence, max value of x is 2
Sample Input 3
3 011 100 100
Sample output 3
3
Explanation City 2 can be in 1st group, city 1 can be in 2nd group and city 3 can be in 3nd group, hence, max value of x is 3
[execution time limit] 3 seconds (java)
[input] integer n
[input] array.array.char mat
N line follows, one for each city, ith line contains N characters , where the jth character is 1 if there is a bridge between city i and j, else the character is 0
[output] integer
Thanks bro
Can you share the other questions that were in that OA? Also, what was the difficulty level of the rest of the questions? Were they harder?