Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
1,509 views
in Interview-Experiences by Expert (30,360 points) | 1,509 views

2 Answers

0 like 0 dislike
Best answer
Today I had my coderpad round with GS. We dived straight into the code. This was the First question: https://leetcode.com/discuss/interview-question/1837422/Goldman-Sachs-or-Coderpad-or-First-non-repeating-character

Second question:
https://leetcode.com/discuss/interview-question/1837465/Goldman-Sachs-or-Coderpad-or-Find-the-maximum-gold-that-can-be-collected

I had solved two questions within 30 minutes so the interviewer asked me this third question:

A forest is represented with a hashmap. This hashmap has this key -> value relationship: child -> parent.
Every node has a unique integer element. I needed to find out the largest tree's root node. If there is a tie, return the smallest root.

The tree with the highest number of nodes, is the largest one. The edges are directed from parent to child.

Input:
{{1 -> 2}, {3 -> 4}}

Output:
2

I first found out the roots present in the forest. Then created an adjacency list and applied BFS to count the nodes. Maintained the maximum count and root with the largest tree in two variables.

Hope it helps.
by Expert (30,360 points)
0 like 0 dislike

Solution to find longest tree in a forest of tree. It means there are multiple trees which implies multiple root nodes. My approach was, first found all root nodes and than the size of tree and also calculate size and root node with max size and min root node.

 

package main;

 

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
/*
** Instructions:
**
** Given a forest ( one or more disconnected trees ), find the root of largest tree
** and return its Id. If there are multiple such roots, return the smallest Id of them.
**
** Complete the largestTree function in the editor below.
** It has one parameter, immediateParent, which is a map containing key-value pair indicating
** child -> parent relationship. The key is child and value is the corresponding
** immediate parent.
** Constraints
** - Child cannot have more than one immediate parent.
** - Parent can have more than one immediate child.
** - The given key-value pair forms a well-formed forest ( a tree of n nodes will have n-1 edges )
**
** Example:
**
** Input:
** { { 1 -> 2 }, { 3 -> 4} }
**
** Expected output: 2
** Explanation: There are two trees one having root of Id 2 and another having root of Id 4.
** Both trees have size 2. The smaller number of 2 and 4 is 2. Hence the answer is 2.
*/
public class LongestTree {

 

/*
 ** Get the size of the tree with root index rootIndex
 */
public static Integer getTreeSize(final Map<Integer, List<Integer>> parentToChild, final Integer rootIndex) {
	Integer result = 0;
	final Stack<Integer> nodes = new Stack<>();
	nodes.push(rootIndex);
	while (!nodes.empty()) {
		final Integer index = nodes.pop();
		for (final Integer childIndex : parentToChild.getOrDefault(index, new ArrayList<>())) {
			nodes.push(childIndex);
			result++;
		}
	}
	System.out.println("Tree Size: "+result);
	return result;
}

/*
 ** Find the largest tree.
 */
public static Integer largestTree(final Map<Integer, Integer> immediateParent) {
	Integer maxTreeSize = 0;
	Integer minRootId = 0;
	final Map<Integer, List<Integer>> parentToChild = new HashMap<>();
	final List<Integer> rootIndexes = new ArrayList<>();
	for (final Map.Entry<Integer, Integer> childToParent : immediateParent.entrySet()) {
		final Integer childIndex = childToParent.getKey();
		final Integer parentIndex = childToParent.getValue();
		
		System.out.println("Child Index: "+childIndex+", parent Index: "+parentIndex);
		
		parentToChild.putIfAbsent(parentIndex, new ArrayList<>());
		parentToChild.get(parentIndex).add(childIndex);
		for(Map.Entry<Integer, List<Integer>> ptC:parentToChild.entrySet()) {
			System.out.print("key: "+ptC.getKey()+" ---> "+ptC.getValue().toString());
		}
		System.out.println("");
		if (!immediateParent.containsKey(parentIndex)) {
			rootIndexes.add(parentIndex);
			System.out.println("parent Index added in root indexes: "+parentIndex);
		}
		System.out.println("--------------------------------------------------------");
	}
	for (final Integer rootIndex : rootIndexes) {
		final Integer treeSize = getTreeSize(parentToChild, rootIndex);
		System.out.println("Root Indexes : "+rootIndex+" and size of tree : "+treeSize);
		if (treeSize > maxTreeSize) {
			maxTreeSize = treeSize;
			minRootId = rootIndex;
		} else if (treeSize == maxTreeSize) {
			minRootId = Math.min(minRootId, rootIndex);
		}
	}

	return minRootId;
}

/*
 ** Returns true if the tests pass. Otherwise, returns false;
 */
public static boolean doTestsPass() {
	// map of test cases to expected results
	final Map<Map<Integer, Integer>, Integer> testCases = new HashMap<>();

	// example
	final Map<Integer, Integer> testCaseOneKey = new HashMap<>() {
		{
			put(1, 2);
			put(3, 4);
		}
	};
	testCases.put(testCaseOneKey, 2);

	// More than two trees
	final Map<Integer, Integer> testCaseTwoKey = new HashMap<>() {
		{
			put(2, 3);
			put(7, 8);
			put(12, 15);
			put(3, 1);
			put(0, 20);
			put(13, 15);
			put(11, 15);
			put(9, 8);
			put(5, 12);
		}
	};
	testCases.put(testCaseTwoKey, 15);

	// really large index values
	final Map<Integer, Integer> testCaseThreeKey = new HashMap<>() {
		{
			put(200000000, 300000000);
			put(500000000, 200000000);
			put(700000000, 300000000);
			put(600000000, 700000000);
			put(900000000, 400000000);
			put(100000000, 400000000);
			put(800000000, 400000000);
			put(1000000000, 400000000);
		}
	};
	testCases.put(testCaseThreeKey, 300000000);

	// two trees of same size
	final Map<Integer, Integer> testCaseFourKey = new HashMap<>() {
		{
			put(9, 4);
			put(1, 4);
			put(5, 2);
			put(8, 4);
			put(7, 3);
			put(2, 3);
			put(6, 7);
			put(10, 4);
		}
	};
	testCases.put(testCaseFourKey, 3);

	// tree sizes differ by one
	final Map<Integer, Integer> testCaseFiveKey = new HashMap<>() {
		{
			put(35, 33);
			put(33, 28);
			put(31, 22);
			put(28, 25);
			put(34, 31);
			put(29, 27);
			put(21, 23);
			put(25, 21);
			put(22, 29);
		}
	};
	testCases.put(testCaseFiveKey, 23);

	boolean passed = true;
	for (Map.Entry<Map<Integer, Integer>, Integer> entry : testCases.entrySet()) {
		final Integer actual = largestTree(entry.getKey());
		if (!actual.equals(entry.getValue())) {
			passed = false;
			System.out.println("Failed for " + entry.getKey().toString() + "\n  expected " + entry.getValue()
					+ ", actual " + actual);
		}else {
			System.out.println("Actual : "+actual+", entry.getValue() : "+entry.getValue());
		}
		break;
	}

	return passed;
}

/*
 ** Execution entry point.
 */
public static void main(String[] args) {
	// Run the tests
	if (doTestsPass()) {
		System.out.println("All tests pass");
	} else {
		System.out.println("Tests fail.");
	}
}

 

}

by Expert (30,360 points)