Question

Microsoft | OA Coding Questions and Solutions | Set - 92 | 2022

Answer 1

Longest Alternating Path

 

You are given a tree consisting of N nodes, numbered from 0 to N-1. Each Nodes contain one of the letter 'a' and 'b'.

 

The Tree is represented as an array A of length N. A[k] (k from 0 to N-1) denotes the parent of the kth Node. Node 0 is the root node and doesnot have a parent, so, the value corresponding to it in array A will always be -1. Letters in the node are represented as a string S. S[k] (k from 0 to N-1) denotes the letter in the kth node.

 

 

The task was to write an effecient algorithm for the following assumptions.

 

• N is an integer within the range [1... 40000]
• String s consists of only characters 'a' and/or 'b'
• string s and array A are both of length N
• array A defines a proper tree with a root in node 0

 

I was able to code an O(n^2) solution by making an undirected graph and using greedy BFS traversal from considering every node as the root and keeping track of the maximum alternating path starting from that root.

Answer 2

https://leetcode.com/contest/weekly-contest-289/problems/longest-path-with-different-adjacent-characters/

Answer 3

Easy C++ code:
Just same as Diameter of the tree....

 

class Solution {
public:
    int ans;
    int rec(vector<vector<pair<char,int>>> &adj,int node,string &s){
        int MaxLength=0;
        int LeftMaxLength=0;
        for(auto to:adj[node]){
            if(to.first!=s[node]){
                int temp = rec(adj,to.second,s);
                ans=max(ans,LeftMaxLength+1+temp);
                LeftMaxLength=max(LeftMaxLength,temp);
                MaxLength=max(MaxLength,temp);
            }
            else{
                int temp = rec(adj,to.second,s);
                ans=max(ans,temp);
            }
        }
        return MaxLength+1;
    }
    int longestPath(vector<int>& parent, string s) {
        int n=parent.size();
        vector<vector<pair<char,int>>> adj(n,vector<pair<char,int>>());
        ans=min(1,n);
        for(int i=0;i<n;i++){
            if(parent[i]==-1) continue;
            adj[parent[i]].push_back({s[i],i});
        }
        rec(adj,0,s);
        return ans;
    }
};

Answer 4

from collections import defaultdict

# this solution is inspired from Diameter of tree
def solution(S, A):
    tree = defaultdict(set)
    root = -1
    for node, parent in enumerate(A):
        if parent == -1:
            root = node
        tree[parent].add(node)

    # f[i] maximum alternating path starting from i node and in its subtree
    f = [0] * len(S)
    # g[i] maximum alternating path starting from  x node passing i node and terminating in y node and in i node subtree
    g = [0] * len(S)
    max_length = 0

    def dfs(current_node):
        nonlocal max_length
        # if node is a leaf
        if current_node not in tree:
            return
        child_list = []
        for child in tree[current_node]:
            dfs(child)
            if S[child] != S[current_node]:
                f[current_node] = max(f[current_node], f[child] + 1)
                child_list.append(f[child])
        max_length = max(max_length, f[current_node])
        child_list = sorted(child_list)
        if len(child_list) >= 2:
            g[current_node] = 2 + child_list[-1] + child_list[-2]
            max_length = max(max_length, g[current_node])

    dfs(root)
    return max_length

print(solution("abbab", [-1, 0, 0, 0, 2]))  # should return 2
print(solution("abbbaabaab", [-1, 0, 0, 0, 1, 2, 2, 3, 3, 4]))  # should return 5
print(solution("aaaaaaaaaa", [-1, 0, 0, 0, 1, 2, 2, 3, 3, 4]))  # should return 0
print(solution("abbbabaaaa", [-1, 0, 0, 0, 1, 2, 2, 3, 3, 4]))  # should return 4