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

Question

For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in

https://interview.desiqna.in

 

 

Answer 1

You are given a tree of N nodes rooted at node 1. The tree will be given as an array p of size (N-1), where p[i] (0<=i<N-1) represents the parent of the (i+1)th node.
Each node also has a value associated with it, given as an array val of size N.
For each node V, you have to calculate the number of nodes in the subtree of V whose value is co-prime with the value of V.
You need to return the sum of this value for all nodes in the tree as an answer.

Constraints
1 <= n <= 100000
1 <= val[i] <= 1000
array p represents a valid tree, rooted at node 1.

Sample Input:
n: 5
par: [1, 1, 3, 3]
val: [1,2,3,4,5]

Sample Output:
6

Sample Explanation:
par array is [1,1,3,3]. This means parent of node 2 and node 3 is 1, and parent of node 4 and node 5 is 3.
val array is [1,2,3,4,5]. This means values of nodes 1,2,3,4 and 5 are 1,2,3,4 and 5 respectively.
The tree looks like this:

Sample Tree

For node 1, the nodes in its subtree whose values are co-prime with value of 1, i.e. 1 are: 2,3,4 and 5. Count: 4
For nodes 2,4 and 5 there are no such nodes as they have no subtree.
For node 3, the nodes in its subtree whose values are co-prime with value of 3 i.e. 3 are: 4 and 5. Count: 2.

So final answer = 4 + 2 = 6.

Input Generation
You are not directly given the arrays p and val. Instead you are given four integers N, seed, l, r and s for randomly generating the arrays p and val. Use the following stub to begin with:

int p[100001], val[100001]; // global arrays which will be randomly generated by below function

void generateTree(int N, int seed, int L, int R, int S) {
srand(seed);

for(int i=1;i<=N-1;i++) {
    p[i] = max(1, i-S+1) + (rand() % (i+2 - max(1, i-S+1))); // random node in [i-S+1, i+1]
}

for(int i=1;i<=N;i++) {
    val[i] = L + rand() % (R-L+1); // random integer between L and R
}

}

long long solution(int n, int seed, int l, int r, int s) {
generateTree(n, seed, l, r, s); // Call the random generator to generate p and val arrays first

// Write your code from here
}
[execution time limit] 3 seconds (cpp)

[input] integer n

The number of nodes in the tree. 1 <= n <= 100000

[input] integer seed

parameter for random generation

[input] integer l

parameter for random generation

[input] integer r

parameter for random generation

[input] integer s

parameter for random generation

[output] integer64

The sum of the number of co-prime values in the subtree, for each node.

Answer 2

https://leetcode.com/problems/tree-of-coprimes/description/
Only that the time complexity will be O(10^8) .
To check for coprime, we would have to build a 1000*1000 size table in O(10^6 * logon) time, so that we could check for coprime in O(1) time.

Answer 3

This is most trickiest out of the three.
Do what is said in the problem in the reverse way.
Instead of finding that how many nodes are co-prime to a node in its subtree
For a node find how many ancestors of it are co prime to it.

 

Lets maintain global ans = 0;
For finding this value. do a Euler tour / dfs maintain a list of 1000 values that represents
how many visited nodes in the current branch which are ancestor to current node are having value x where x >= 1 and x <= 1000.
Let's name this vector V.

 

On reaching every node XAND HAVING V.
Find out among all those 1000 values how many values can be co-prime to node x and add that count simply to our answer ans.

 

Time Complexity (Max node Value * Number of nodes)
Space Complexity (Max node value)

 

I can't think better solution to 3rd one but I guess with some pre-computation it may pass given the low constant factor of how you implement the idea.
Thanks let me know your opinions and better solutions in comments.