0 like 0 dislike
1,392 views
| 1,392 views

0 like 0 dislike
GOGGLE
Online Assessment
Time: 60 min (1 hour)
Questions: 2 questions

Question 1
note: question summarized version
Given an integer N which is the number of nodes. And a 2-D matrix( N x 2) is also given in which each row represents bidirectional edges (1-indexed) which form a tree (no cycle) and integer Array A which have node values.
Count the number of nice paths in the tree.
paths are considered nice if:
i) path start node value is same as path end node value. But the path end node cannot be the same as the start node.
ii) any node in the path cannot be greater than start node value.
iii) count only distinct paths. But nodes can be part of different unique paths.

Input:
N = 6
edges = [ [1, 2], [1, 3], [3, 5], [3, 4], [2, 6] ]
node values = [ 2, 3, 1, 2, 3, 3 ]

expected output:
4

nice paths:
5 &rarr; 3 &rarr; 1 &rarr; 2 ( node values = 3 &rarr; 1 &rarr; 2 &rarr; 3)
5 &rarr; 3 &rarr; 1 &rarr; 2 &rarr; 6 ( node values = 3 &rarr; 1 &rarr; 2 &rarr; 3 &rarr; 3)
2 &rarr; 3 (node values = 3 &rarr; 3)
1 &rarr; 3 &rarr; 4 (node values = 2 &rarr; 1 &rarr; 2)

Question 2:
Given array of strings. Count the score of each string and return it.
The score of string is that for all possible prefixes of particular string count the total number of strings that in the given string array that have the common prefix

Example: [ "aab", "aac" ]

1st string &rArr; "aab"
so prefixes are:
"a" , two string have common prefixes in string array, i.e [ "aab", "aac" ] so score==2
"aa" two string have common prefixes i.e [ "aab", "aac" ] so score == 2
"aab" only one string (i.e. current string itself) has common prefix, i.e [ "aab"] so score == 1

thus, total score of 1st string == 2 + 2 + 1 &rArr; 5

2nd string &rArr; "aac"
so prefixes are:
"a" , two string have common prefixes in string array, i.e [ "aab", "aac" ] so score==2
"aa" two string have common prefixes i.e [ "aab", "aac" ] so score == 2
"aac" only one string (i.e. current string itself) has common prefix, i.e [ "aac"] so score == 1

thus, total score of 1st string == 2 + 2 + 1 &rArr; 5

output : [ 5, 5 ]
by Expert (107,750 points)
0 like 0 dislike

Q2 - Trie (C++)

Preprocess the strings into a Trie first, then we do another pass to count.
I came from Java, and I noticed that Trie in C++ with `struct` is really slow compared to Java for whatever reason.
We can use `vector<array<int, 26>>` to represent Trie too and it is faster and use less memory, but with slightly more bookkeeping.

``````vector<int> solve(vector<string> A){
int last = 2;
vector<array<int, 26>> trie(last);
vector<int> cnt(last);
for (string s : A){
int cur = 1;
for (char ch : s){
if (!trie[cur][ch-'a']){
trie[cur][ch-'a']=last++;
trie.emplace_back();
cnt.emplace_back();
}
cur = trie[cur][ch-'a'];
cnt[cur]++;
}
}
vector<int> ans;
for (string s : A){
int cur = 1, res = 0;
for (char ch : s){
cur = trie[cur][ch-'a'];
res += cnt[cur];
}
ans.push_back(res);
}
return ans;
}
``````

Sample TestCase

``````    for (int x : solve({"aab", "aac"})){
cout << x << ' ';
}

C:\WINDOWS\system32\cmd.exe /c (a)
5 5
Hit any key to close this window...

``````
by Expert (107,750 points)
0 like 0 dislike

## Q1 : Union Find Python3

``````def countSpecialPaths(n:int, edges:List[List[int]], value:int)->int:
# n and value are 0 indexed but given nodes are 1 indexed
n, value = n+1, [0]+value       # make n and value 1 indexed

# Make graph
adjList = defaultdict(list)      # record the neighbors for every node
for u,v in edges:

# union find
parent = list(range(n))
# find the Absolute parent
def findAP(curr):
if parent[curr] == curr:
return curr
parent[curr] = findAP(parent[curr])
return parent[curr]

subtree = [[val,1] for val in value]  # [maxVal,maxValCount]

res = 0
for curr in sorted(range(n),key=lambda i: value[i]): # add nodes from low to high to adj sub-trees
currAP = findAP(curr)
continue
# if curr Sub tree max value is equal to adj Sub tree max value we find one of its path
# check how many nodes in the subtree have the same val of the curr