codebuster_10's blog

Uber Hiring Test Problems (India 2022)
By codebuster_10, history, 3 years ago, In English

Time limit for this test was 1 hour

150 points
200 points
250 points
My solution for 250 points (sorry for bad formatting)
Comments

Feel free to share your ideas/code on how to solve them.

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think the second problem(200 points) can be solved by compressing the graph into a bridge tree and then using binary lifting to obtain the bitwise or of all nodes on the path from the component of u to the component of v.

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

How to solve the first problem?

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

    Notice how for every position i in our process we end up either at i , either at i+1 ( this is because the values are <= 2 ).

    let dp[i][true/false][true/false] be the number of subsets such that in the process we end up at position i in the first string ( if true ) and at position i+1 ( if false ), similarly for the third state in the second string.

    How to transition ?

    just take some cases , if we reach position i in the first string and s[i] = 2 then this will go to dp[i+1][false][k].

    This way , we have an O(N) solution.

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

Problem A has been asked in Media.net previously.
Couldn't find a solution earlier too.
Problem A
Round 2 (same Problem)

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

Second question can be solved with help of DSU. As we can visit any vertex multiple times, so if the OR of whole component will be < w then the answer will be NO. Also problem statement was not correct, it should be greater than or equal to w to pass all the testcases.

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

    The statement is very vague in its definition of what exactly path is, I assumed path to be one where we cannot visit edges twice, Which makes it a way tougher question for a coding test (The solution above using bridge tree seems to be correct).

    → Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    We can even convert the graph into a weighted one where the cost to go from node a to node b is a bitwise OR b similar for the reverse direction and simply run tweaked Dijkstra to find the maximum distance from every query, but it would get TLE, cuz of O(q*(v+e)*logE). But we can simply take OR of all vertices from 1 to n and address each query in O(1) by checking if it's greater than w or not. There is no use for DSU right, it's greedy.

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

codebuster_10 , how did you get these 21's in your matrix, for the 250 points question. I am getting the same matrix without the 21's along the diagonal.

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

Was this an on campus test or off campus one?

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

what was your dp state for 250 points problem? codebuster_10

UPD: got it dp[i][j] -> # of ways to get j vowels odd number of times with i as the string length

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

I think overall every task seems copied or classic. I have seen each one of them before.

task 1 copied from cc , task 3 copied from techgig final round 2019 or 2020 maybe , but doesn't matter due to being so classic , task 2 i have seen before but not sure where. its parade of copied task lol.

task 1] https://www.codechef.com/problems-old/CHEFTWOS

task 2] seems classic

task 3] can be solved with exponential generating functions easily,

it would be coeffiecient of x^N in the below polynomial

$$$ {(\frac{e^{x} - e^{-x}} { 2}})^5 * e^{21x}$$$

multiplied by N!

even though N! would be large but it also would be divided by some K! K would be very large too.

→ Reply