Question

Google | OA Coding Questions and Solutions | Set - 23 | 2022 |

Answer 1

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 → 3 → 1 → 2 ( node values = 3 → 1 → 2 → 3)
5 → 3 → 1 → 2 → 6 ( node values = 3 → 1 → 2 → 3 → 3)
2 → 3 (node values = 3 → 3)
1 → 3 → 4 (node values = 2 → 1 → 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 ⇒ "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 ⇒ 5

 

2nd string ⇒ "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 ⇒ 5

 

output : [ 5, 5 ]

Answer 2

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

Answer 3

Q1 : Union Find Python3

 

https://leetcode.com/discuss/interview-question/2260088/Special-Paths-or-Google-OA-or-July-2022-or-Graph
Credit : @leetcode_dafu

 

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:
        adjList[u].append(v)
        adjList[v].append(u)

    # 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)
        for adj in adjList[curr]:
            adjAP = findAP(adj)
            if currAP==adjAP or value[adj] > value[curr] :  #  ignore adj with val>value[curr] because they will be added later.
                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
            if subtree[currAP][0] == subtree[adjAP][0] : 
                res += subtree[currAP][1]*subtree[adjAP][1]     # total combinations is the no of paths
                subtree[currAP][1] += subtree[adjAP][1]         # get count of max val in both subtree
            subtree[adjAP] = subtree[currAP][:]                # both curr ap and adj ap subtree are same i.e maxVal and maxValCount are same
            parent[adjAP] = currAP    # union currAP to adjAP subtrees      
    return res

print(countSpecialPaths(5, [[1,2], [1,3], [3,4], [3,5]], [2,3,1,2,3]))
print(countSpecialPaths(5, [[1,2], [1,3], [3,4], [3,5]], [2,2,1,2,3]))
print(countSpecialPaths(5, [[1,2], [1,3], [3,4], [3,5]], [2,2,1,2,2]))
print(countSpecialPaths(6, [ [1, 2], [1, 3], [3, 5], [3, 4], [2, 6] ],  [ 2, 3, 1, 2, 3, 3 ]))