Question

Uber | OA Coding Questions and Solutions | Set - 6 | 2022

Answer 1

Q-2

 

private int luckyTickets(int n) {
  int[][] dp = new int[n/2 + 1][Math.pow(9, n / 2) + 1];

  dp[0][0] = 1;
  for (int i =  1; i <= n / 2; i++) {
    int sum = 0;
    for (int s = 0; s <= Math.pow(9, i / 2); s++) {
      for (int digit = 0; digit <= 9; digit++) {
        if (digit <= s) {
          dp[i][s] += dp[i - 1][s - digit];
        }
      }
      sum += dp[i][s];
    }
  }
  return sum;
}

Answer 2

Q-4 o(n*(n + e)) solution

 

class Solution
{
	public static int getMinCalCount(int n, int[] t, int[][] edges) {
    if(n <= 0) {
      throw new IllegalArgumentException();
    }
    Map<Integer, List<Integer>> adjList = getAdjList(n, edges);
    double minCal = (double) Integer.MAX_VALUE;
    int ans  = 0;
    for (int node = 0; node < n; node++) {
      double cal = dfs(adjList, node, t, null);
      if(cal < minCal) {
        minCal = cal;
        ans = node;
      }
    }
    return ans;
}


private static Map<Integer, List<Integer>> getAdjList(int n, int[][] edges) {
  Map<Integer, List<Integer>> adjList = new HashMap<>();
  for (int i = 0; i < n; i++) {
    adjList.put(i, new ArrayList<>());
  }
  for (int[] edge : edges) {
    adjList.get(edge[0]).add(edge[1]);
    adjList.get(edge[1]).add(edge[0]);
  }
  return adjList;
}



public static double dfs(Map<Integer, List<Integer>> adjList,
               int root, 
               int[] calorie, Integer prev) {
    double calCount = (double)calorie[root];
    double sum = 0;
    int neighbors = 0;
    for (int neighbor : adjList.get(root)) {
      if (prev == null || neighbor != prev) {
        sum += dfs(adjList, neighbor, calorie, root);
        neighbors++;
      }
    }
    if(neighbors == 0) {
    	return calCount;
    }
    return calCount + sum / (double)neighbors;
}
	public static void main (String[] args) throws java.lang.Exception
	{
		int[][] edges = {{0, 1}, {1, 2}, {2, 3}, {3,4}};
		int[] t = {2, 2, 1, 2, 2};
		System.out.println(getMinCalCount(5, t, edges));
	}
}

Answer 3

I applied without referral and got link for coding round. In this round I got 4 questions and 60 minutes for them. This test was on 13-06-2021.

 

Q-1
You are given an array of integers 'a' and an integer k. Your task is to calculate the number of ways to pick two different indices i<j that a[i] + a[j] is divisible by k.

 

Example

 

•  

  For a = [1, 2, 3, 4, 5] and k = 3,
  the output should be
  sumsDivisibleByK(a, k) = 4.
  There are 4 pairs of numbers that sum to a multiple of k = 3

   

  • a[0] + a[1] = 1 + 23
  • a[0] + a[4] = 1 + 5 = 6
  • a[1] + a[3] = 2 + 4 = 6
  • a[3] + a[4] = 4+ 5 = 9

•  

  Input/Output

   

  • [execution time limit] 0.5 seconds (cpp)
  • [input] array.integer a
    An array of integers from which two numbers should be picked. The elements are not necessarily all unique.
    Guaranteed constraints:
    1 <= a.length <= 10^5.
    1 <= a[i] <= 10⁹

•  

  [input] integer k
  An integer, which should be a divisor of the sum.
  Guaranteed constraints:
  1 <= k <= 10^9

   

•  

  [output] integer64
  The number of ways to pick two different numbers from 'a' such that their sum is divisible by K.

   

 

Q-2
A ticket number is usually represented by the even number of digits (leading zeros are allowed). It is considered to be lucky if the sum of the first half of the digits is equal to the sum of the second half.

 

Given an integer n find the number of lucky tickets with n -digit number.
Example

 

•  

  For n = 2, the output should be countLuckyNumbers(n) = 10
  They are: "00", "11", "22", "33", "44", "55", "66", "77", "88", "99"

   

•  

  Input/Output

   

  • [execution time limit] 0.5 seconds (cpp)
  • [input] integer n
    A positive even integer.
    Guaranteed constraints:
    2 <= n <= 10

•  

  [output] integer

   

 

Q-3
Lewis wants to go for a walk and the area around him is an unweighted directed graph of n nodes and m edges. He wants to have a perfect walk, which is a path S, a1, a2, ..., S (a, are distinct and not equal to S). Can you tell him if it possible to have a perfect walk from every node?

 

•  

  Example
  For n = 4, m = 4, edges = [[1, 2], [2, 3], [3, 1], [3, 4]], the output should be perfectWalk(n, m, edges) = [1, 1, 1, 0]. As 4 doesn't have a perfect walk and the rest of them has one. For 1, it is 1, 2, 3, 1. For 2, it is, 2, 3, 1, 2 For 3, it is 3, 2, 1, 3.

   

•  

  Constraints
  • 1 <= N <= 105
  • 1 <= M <= 2 x 105
  [execution time limit] 1 seconds (cpp)

   

  •  

    [input] integer n
    number of nodes

     

  •  

    [input] integer m
    Number of edges

     

   

  ■ [input] array.array.integer graph
  m x 2 matrix, each row consists of 2 nos,u and v depicting directed path between u and v. (1 <= u. V <= n).
  There will be no self-loops (u != v)

   

  • [output] array.integer
    n spaced integers either 0 or 1 depicting whether possible to have perfect path from node i

 

Q-4
For the purposes of this problem, suppose that there are n dishes, and dish i has t calories. Some dishes are related to each other. If we connect related dishes by edges, we get an undirected graph such that there exists exactly one path from any dish to another. In other words, the graph of related dishes is a tree.

 

Every time Steve orders a dish by UberEats, he will see a list of dishes that are directly related to it and will navigate at random to one that he hasn't tasted yet (all related dishes have an equal chance of being viewed). Steve will stop tasting once there are no untasted related dishes left.

 

Given the number of related dishes n an array that contains the estimated calorie for each dish t and an array containing the pairs of related dishes edges, which dish should we show to Steve first so that we minimize his total expected calorie intake? It is guaranteed that there is one unique dish that is optimal
Here's how the total expected calorie for tasting a dish 'i' with 'q' related dishes is calculated:

 

* Take the calorie t, that will be added to Steve's intake on tasting this dish;
* Recursively calculate the expected_calorie(j), for each related dish j without considering the ith dish;
* Add to t(i), the sum of expected_calorie(j), for each j, divided by aie the answer will be equal to t + sum(expected_calorie(j)) q.

• Example
  For n= 5t [2, 2, 1, 2, 2], and edges = [[0, 1]. [1, 2], [2, 3], [3,4]], the output should be calorieCount(n. t, edges) = 2.
  For this example, the tree can be visualized as:
  0->1->2->3->4
  Let's calculate the answers for each of the 5 vertices:
  • If Steve starts tasting from dish e, then the expected_calorie count equals t[0] + expected_calorie1 / 1 = t[0] + (t₁ expected_calorie2 / 1) / 1 = ... = t[0] + (t[1] + (t₂ + (t[3] + (t[4] + 0 / 1) / 1)/ 1)/ 1) / 1 = t[0] + t[1] + t[2] + t[3] + t[4] = 2 + 2 + 1 + 2 + 2 = 9.
  • If Steve starts tasting from dish 1, then the expected_calorie count equals t₁ + (expected_calories[0] + expected_calorie[2]) / 2 = t₁ + ((t[0] + 0 / 1) + (t₂ + expected_calories3 / 1))/2 = t₁ + (t[0] + t₂ + (t[3] + (t[4] + 0 / 1) / 1) / 1) / 2 = t₁ + (t[0] + t₂ + t[3] + t[4])/2 = 2+ (2 + 1 + 2 + 2)/2 = 5.5.
  • If Steve starts tasting from dish 2, then the expected calorie count equals t₂ + (expected calorie, + expected caloriez) / 2 t₂ + ((t₁ + expected_calorie / 1) (tz + expected calorie, 1))/2 = t₂ + ((t₁+to) + (tz + tu)) / 2 = t₂ + (t+to+to+ tu) / 2 = ²+ (2 + 2 + 2 + 2)/2 = 5
  • The expected calorie count for vertex 3 IS equal to the expected calorie count for vertex 1 because they are symmetric in the tree. The same works for vertices 4 and 0.

 

So, as we can see, the optimal vertex to start with is vertex 2, since that gives us the smallest expected calorie intake.

 

• Input/Output
  • [execution time nit] 1 seconds (cpp)
  • [input] integer n
    • The number of dishes.
    • Guaranteed constraints:
      1 <= n <= 1000.
  • [input] array.integer t
    • An array of positive integers. t₁ is the calorie count that Steve will consume on tasting the dishi for each valid i.
    • Guaranteed constraints.
      1 <= t.length = n <= 1000.
      1 <= t[i] ≤ 5000.
  • [input] array.array.integer edges
    • An array containing n - 1 pairs of related dishes. It is guaranteed that the dishes form a tree.
    • Guaranteed constraints:
      edges.length - n - 1.
      0 <= edges[i][j] <= n - 1
  • [output] integer
    • The e-based index of the best dish to show Steve first in order to minimize his calorie intake.

 

And I was able to solve 1st question fully and coded the last question but it wasnt compiling successfully.