Join Us
Loading Similar Posts
Entering edit mode
Avg CTC: 20lpa
Job roles: Software Engineer, Backend Developers, Program Analyst and more
Job List: Positions open for Uber, India
Question 1
Click here to Practice
Submit Problem to OJ
Given an array, Find number of elements equal to mean of neighbor elements.
Example
Sample Input
2 4 6 6 3
Sample Output
3
Example
2,4,3 satisfy that condition, hence output 3.
2 = (4+0)/2, 4 = (2+6)/2
Question 2
Click here to Practice
Submit Problem to OJ
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.
Question 3
Click here to Practice
Submit Problem to OJ
Given an array and operations
There are 3 operations:
1 x --- add x to end of an array
2 x --- add x to all the elements of the array
3 --- You should return min element in the array and remove it from the array
Output should be array with all values of operation 3 that is min at that time
Question 4
Tree of Co-Primes
Click here to Practice
Submit Problem to OJ
There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a value associated with it, and the root of the tree is node 0.
To represent this tree, you are given an integer array nums and a 2D array edges. Each nums[i] represents the ith node's value, and each edges[j] = [uj, vj] represents an edge between nodes uj and vj in the tree.
Two values x and y are coprime if gcd(x, y) == 1 where gcd(x, y) is the greatest common divisor of x and y.
An ancestor of a node i is any other node on the shortest path from node i to the root. A node is not considered an ancestor of itself.
Return an array ans of size n, where ans[i] is the closest ancestor to node i such that nums[i] and nums[ans[i]] are coprime, or -1 if there is no such ancestor.
Example 1:
Input:
nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
Output:
[-1,0,0,1]
Explanation:
In the above figure, each node's value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its closest valid ancestor.
Example 2:
Input:
nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output:
[-1,0,-1,0,0,0,-1]
Constraints:
- nums.length == n
- 1 <= nums[i] <= 50
- 1 <= n <= 105
- edges.length == n - 1
- edges[j].length == 2
- 0 <= uj, vj < n
- uj != vj
Entering edit mode
Q2)
Approach 1 : First of all let's come up with a solution that is most obvious for each node X count number of nodes that are in it's subtree and are co-prime with value[X] which will have time complexity of O(n^2) for counting for each node and then return the sum of all of them.
Approach 2 : Let's try to reduce it to some better complexity. Observe the values of nodes are < = 1000. Will it help??
If we define cnt[node][V] representing count of nodes in the subtree of node which have value=V then we could compute it by
cnt[node][V]=(sum of cnt[neighbour][v])+1 if (value of node=V)
cnt[node][V]=(sum of cnt[neighbour][V]) if (value of node is not equal to V)
In this way we could precompute for each node how many nodes in the subtree are there with value equal to any arbitrary value and then we could return
cnt[1][value[1]]+cnt[2][value[2]]+cnt[3][value[3]].... And we could do it in time complexity of O(n*maximum value of node) and in worst case it would have to do O(1000*100000) which is O(10^8) operations which is still slow.
Approach 3 : First of all do we have to calculate the result for each node or our target is to find the sum of results for each node. So instead of calculating number of nodes(X) whose value is co prime with subtree's nodes, we should find that in how many nodes that value could contribute to the sum of results. Representing ans[X] as count of nodes in the subtree of X which are coprime with value[X] and res[X] as count of ancestors of X which are co prime with value[X], we have to return sum(ans[X]) for all nodes.
sum(ans[X]) for all nodes X is equal to sum(res[X]) Why ??
Let's represent (i,j) number of valid pairs such that j is in subtree of i and value[i] is coprime with value[j]. Therefore count of pairs(i,j)=sum(ans[i]) for all nodes i.
and if we represent (j,i) number of valid pairs such that i is ancestor of j and value[i] is coprime with value[j]. Therefore count of pairs(j,i)=sum(res[j]) for all nodes j.
Hence if (i,j) is counted in sum(ans[i]) then the pair (j,i) have contributed in sum(res[j]) therefore {sum(ans[i]) for all node i = sum(res[i]) for all node i }
Therefore we will try to calculate sum(res[i])
Calculation of sum(res[i]) over all nodes i from 1 to n
If we are at some node X then we need to count number of ancestors which satisfy GCD( value[ancestor],value[X] ) = 1
We could again implement it in O(n*maximum value of node) but wait !!! We could optimize it..
Optimizing Approach 3: Let's suppose if there are 2 number A and B and GCD(A,B)=1 then it means that they do not share any prime number as there common factor which means that if prime factors of A are {A_1,A_2...A_k} and prime factors of B are {B _1,B_2...B_m} then there exist no(i,j) such that 1<=i <=n , 1<=j<=m, A_i=B_j.
Therefore by using above we could say that if there is some node X then we need to count number of ancestor nodes whose value do not share atleast one prime factor with prime factors of value[X] which can be also said as Total ancestors - (Ancestors whose value share a prime factor with atleast one prime factor of value[X]).
Let's analyze how to calculate how many numbers in an array are there which share at least one prime factors with prime factors of X ??
Suppose X has prime factors {p_1,p_2,...,p_k} .Representing mul[m] as count of numbers which are multiples of m. Then our answer is by Inclusion-Exclusion which is mul[p_1]+mul[p_2]+...+mul[p_k] - mul[p_1p_2] - mul[p_1p_3]..... (Taking one at a time - taking two at a time +taking three at a time and so on)
You can read it about here.Inclusion-Exclusion
For example if value[X] has prime factors as {2,5} then we need to chose those ancestor's nodes which do not have 2 or 5 as their prime factors or we could also say Total Ancestors - (Ancestors whose value are either multiple of 2 or 5) or which could be also written as Total Ancestors - (count of ancestors which are multiple of 2 + count of ancestors which are multiple of 5 - count of ancestors which are multiple of (2*5=10) ).
Implementation
First of all we will keep an array mul mul[m] representing count of numbers which are multiples of m currently(storing data of only from root to current node) and update it when we enter at some node or exit from some node. If we enter at some node and it's value has prime factors {p_1,p_2,..,p_k}, then by using inclusion exclusion as described above we need to just find res[node] = Total ancestors -(mul[p_1]+mul[p_2]+...+mul[p_k] - mul[p_1p_2] - mul[p_1p_3].....) .
For example if value = 10 then we need to find Total ancestors - (mul[2]+mul[5]-mul[10])
and if value =30 , then we need to find Total ancestors - (mul[2]+mul[3]+mul[5]-mul[6]-mul[10]-mul[15]+mul[30]).
Now the update part of mul[m]
Let's suppose if we are at some node and it has value = 36 or (2^2.3^2). Now we need to check to which m's will it update . Now as described in above evaluation of res[node] we need to update only on distinct multiple of primes
For example in case of value=36 we have to increment mul[2] by 1 , mul[3] by 1, mul[6 which is product of 2 and 3] by 1.
Therefore for updating we will iterate over all subset of prime factors and update mul[product of subset of prime factors] by +1 for all subset when we enter at some node and when we exit from some node update mul[product of subset of prime factors] by -1 for all subset.
Time Complexity Since in update part and evaluating res[i] part we iterate over all subsets of prime factors of value[i]. and number of prime factors of value[i] can be atmost 4 and we need to iterate over all subset which take at most 2^4 iterations. and we have to do it for every i.
Hence time complexity would be roughly O(2^4.n).
Implementation/Code will be added ...
Entering edit mode
Q4)
Quick Solution
Let's suppose if we are currently at some node X then we need to find the nearest ancestor of X whose value is coprime(or GCD=1) with value of X. Let's first try Bruteforce , we could just iterate over all the ancestors of X then we could find the nearest ancestor with it's value coprime with value of X which gives our complexity of O(n^2).
Optimization
The values at each nodes are at most 50???? Can it optimize the solution ???
For each value[X] we are having atmost 50 values to check for the valid one.
Now we need to think of how to find the nearest ancestor satisfying coprime with that node using the above constraint.
We could do it by storing(array of lists or map of lists) a list L for each values v where L[v] representing list of nodes which has value=v. Then for each node X we could check values V from 1 to 50 which which are coprime with value[X] then we need to check in the L[V] which is the nearest ancestor of X for all V(like if we get a node P1,P2,.... then we need to output the one which is nearest to X. But still it is O((n^2)*50).
Do we need to iterate over all the nodes and do ancestor check and then find the one with nearest to X ????
No, because there is a way we can just check out nearest ancestors for each value by storing only those nodes which are from root to node.
Let's run a DFS from root (0) and we include a node when we enter that node during DFS and remove it when we have completed DFS in it's subtree.
DFS(node s)
{
//entered on node s
ancestor_depth=0
ancestor=-1
for(v in 1...50)
{
if(gcd(v,value[s]) is 1)
{
if(L[v] is not empty)
{
//Since L[v] stores the nodes according to decreasing order of distances from current node then last node of the list would be the nearest.
last_node=L[v].last //last node
//For all the possible ancestors find the one with maximum depth
if(depth[last_node]>=ancestor_depth)
{
ancestor_depth=depth[last_node]
ancestor=last_node;
}
}
}
}
L[values[s]].push(s)
visited[s]=1
if(s is not visited)
{
iterate over neighbour nodes of s
{
if(neighbour is not visited)
DFS(neighbour)
}
}
//completed DFS on subtree of node s
L[value[s]].remove() //because s would be the last node
ans[s]=ancestor
}
Finally we could get a complexity of O(n*50).
Entering edit mode
Solution to Problem 1
Overview
Given an array of numbers, You need to find the number of elements which are equal to the mean of their neighbor elements. It is assumed that the left neighbor of the first element and the right neighbor of the last element is zero.
Analysis
We can solve this problem naively by iterating through the array and checking for each element if it is the mean of its neighbor elements. This will solve the problem in O(N).
PseudoCode
solve(arr):
ans = 0
for i from 1 to N:
left = 0, right = 0
if(i != 1):
left = arr[i-1]
if(i != N):
right = arr[i+1]
if(left + right == 2*arr[i]):
ans++
return ans;
Entering edit mode
Solution to Problem 3
Analysis
This problem can be solved using Venice Technique. Lets Define a sequence (A1,…,AN) so that if the i-th operation is Operation 2, then Ai=Xi, or otherwise 0. Then, the number written on each ball in the bag right before the (K+1)-th operation is Xi+Ai+1+⋯AK. Here, with the aid of the idea of cumulative sums, it can be expressed as Xi+(SK−Si)=(Xi−Si)+SK, where Si=A1+⋯Ai. Here, (Ai) and (Si) can be easily calculated by inspecting them in order.
Now, when we pick up the ball with the minimum number, SK is independent of balls, so it is sufficient to pick up the ball with the minimum value of Xi−Si. Therefore, for each Operation 1, we can assume that we put all ball with the value Xi−Si written on it, rather than Xi, so that we only have to consider Operation 1 and 3. (We will add SK before outputting the ans.)
This can be solved fast enough with a data structure like a priority queue or a multiset (BST that can handle duplicates), specifically in a total of O(QlogQ) time.
PseudoCode
solve(queries):
ans[] = new int[]
sum = 0
pq = new minHeap<int>
for query in queries:
if(query.type == 1):
pq.push(query.x - sum)
else if(query.type == 2):
sum += query.x
else:
ans.append(pq.min() + sum)
pq.pop()
return ans
