Question

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

Answer 1

Given an n-ary tree with N nodes numbered 0..N-1. Each node is marked as 'a' or 'b'.
Find longest path in a tree with alternating characters.

 

Input : parent array of size n, string tag

 

Example 1 :
parent : [-1, 0, 1] , tag ="abb"
       0 'a'
	   |
	   1 'b'
	   |
	   2 'b' 
	   
Path length = 2 (0->1)


Example 2:
parent : [-1, 0, 0] , tag ="abb"
        0 'a'
	 /     \
   1 'b'   2'b'
   
Path length = 2 (1->0->2)

Answer 2

dp on trees similar to maximum path sum.

Answer 3

public class LongPath
    {
        int res = 0;
        string tag;
        public int Solve(int[] parent,string tag)
        {
            this.tag = tag;
            var dict = new Dictionary<int, List<int>>();
            for(int i = 0; i < parent.Length; i++)
            {
                if (!dict.ContainsKey(parent[i]))
                    dict[parent[i]] = new List<int>();

                dict[parent[i]].Add(i);
            }

            Calculate(dict,0,tag[0]);
            return res;
        }
        private int Calculate(Dictionary<int,List<int>> dict,int parent,char prev)
        {
            if (!dict.ContainsKey(parent))
            {
                return 1;
            }

            int max1 = 0, max2 = 0;

            foreach(var child in dict[parent])
            {

                var childVal = Calculate(dict,child,tag[parent]);
                if (max1 < childVal)
                {
                    max2 = max1;
                    max1 = childVal;
                }
                else if (max2 < childVal)
                {
                    max2 = childVal;
                }
            }
            res = Math.Max(res, max2 + max1);
            if (tag[parent] != prev)
                return max1+1;
            return 0;

        }
    }

Answer 4

Similar to binary tree find longest path problem on leetcode, but since we are dealing with n-ary tree with alternating tags, some modifications are needed.

 

int ans;
List<Integer>[] adjList;
String values;
public int longestAlternatingPath(int[] parent, String tag) {
 int n = parent.length;
 adjList = new List[n];
 ans = 0;
 values = tag;
 for(int i=1; i<n; i++) {
  if(adjList[parent[i]]==null) adjList[parent[i]] = new ArrayList<>();
  adjList[parent[i]].add(i);
 }
 dfs(0);
 return ans;
}

private int[] dfs(int node) {
 PriorityQueue<Integer> top2a = new PriorityQueue<>(), top2b = new PriorityQueue<>();
 if(adjList[node]!=null) {
  for(int child : adjList[node]) {
   int[] counts = dfs(child);
   top2a.offer(counts[0]);
   if(top2a.size()>2) top2a.poll();
   top2b.offer(counts[1]);
   if(top2b.size()>2) top2b.poll();
  }
 }
 int a2 = top2a.isEmpty()? 0 : top2a.poll(), a1 = top2a.isEmpty()? 0 : top2a.poll();
 int b2 = top2b.isEmpty()? 0 : top2b.poll(), b1 = top2b.isEmpty()? 0 : top2b.poll();
 int count = values.charAt(node)=='a'? (b1+b2+1) : (a1+a2+1);
 ans = Math.max(ans, count);
 return values.charAt(node)=='a'? new int[]{b1+1, 0} : new int[]{0, a1+1};
}