Блог пользователя codebuster_10

Uber Hiring Test Problems (India 2022)
Автор codebuster_10, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve the first problem?

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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).

    → Ответить
  • »
    »
    10 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Was this an on campus test or off campus one?

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
2 года назад, # |
← Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится

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.

→ Ответить