Find all leaf node pairs which do not share common path in a N-ary tree


  • 0

    Re: Given an N-ary tree pair the leaf nodes such that leaf we are pairing do not have edge used in previous pairing. @codersx
    This is the round 1 question 2 in this post.
    Below is my solution. The basic idea is:

    1. Build a hash map contains all edges to store the used state.
    2. Build a list contains all edges along the root-leaf path for each leaf.
    3. Enumerate all leaf nodes, find out every set of valid leaf pairs, please see my comments for explanations.
    class NTreeNode
    {
    public:
    	NTreeNode(string defaultVal) : val{ defaultVal } {}
    	string val;
    	vector<NTreeNode *> children;
    };
    
    namespace std
    {
    	template <>
    	struct hash<pair<NTreeNode *, NTreeNode *>> : public unary_function<pair<NTreeNode *, NTreeNode *>, size_t>
    	{
    		size_t operator()(const pair<NTreeNode *, NTreeNode *> &value) const
    		{
    			size_t node1 = (size_t)value.first, node2 = (size_t)value.second;
    			return (size_t)(node1 ^ node2);
    		}
    	};
    
    
    	template <>
    	struct equal_to<pair<NTreeNode *, NTreeNode *>> : public unary_function<pair<NTreeNode *, NTreeNode *>, bool>
    	{
    		bool operator()(const pair<NTreeNode *, NTreeNode *> &x, const pair<NTreeNode *, NTreeNode *> &y) const
    		{
    			return x.first == y.first && x.second == y.second;
    		}
    	};
    }
    
    class G4G_MS_Set56_R1Q2 {
    public:
    	vector<unordered_set<pair<NTreeNode*, NTreeNode*>>> findDisjontLeafPairs(NTreeNode *root) {
    		// build edge hash map
    		unordered_map<pair<NTreeNode *, NTreeNode *>, int> edgeUsageMap;
    		buildEdgeUsageMap(root, edgeUsageMap);
    
    		// build edge list for each leaf node
    		vector<pair<NTreeNode *, NTreeNode *>> edgeList;
    		unordered_map<NTreeNode *, vector<pair<NTreeNode *, NTreeNode *>>> edgeListMap;
    		vector<NTreeNode *> leaves;
    		buildRootToLeafEdgeListMap(root, edgeList, edgeListMap, leaves);
    
    		// Recursively enumerate all leaf pairs find valid sets
    		vector<unordered_set<pair<NTreeNode*, NTreeNode*>>> validLeafPairSet;
    		vector<pair<NTreeNode*, NTreeNode*>> currentLeafPairs;
    		findAllValidLeafPairs(leaves, edgeListMap, edgeUsageMap, currentLeafPairs, validLeafPairSet);
    		return validLeafPairSet;
    	}
    private:
    	const int USED = 1;
    	const int FREE = 0;
    
    	void buildEdgeUsageMap(NTreeNode *root, unordered_map<pair<NTreeNode *, NTreeNode *>, int> &map) {
    		queue<NTreeNode *> q;
    		q.push(root);
    		while (!q.empty()) {
    			NTreeNode *node = q.front();
    			q.pop();
    			for (auto child : node->children) {
    				map.emplace(make_pair(node, child), 0);
    				q.push(child);
    			}
    		}
    	}
    
    	void buildRootToLeafEdgeListMap(
    		NTreeNode *node,
    		vector<pair<NTreeNode *, NTreeNode *>> &edgeList,
    		unordered_map<NTreeNode *, vector<pair<NTreeNode *, NTreeNode *>>> &map,
    		vector<NTreeNode *> &leaves) {
    		if (node->children.empty()) {
    			map[node] = edgeList;
    			leaves.emplace_back(node);
    		}
    		else {
    			for (auto child : node->children) {
    				edgeList.emplace_back(make_pair(node, child));
    				buildRootToLeafEdgeListMap(child, edgeList, map, leaves);
    				edgeList.pop_back();
    			}
    		}
    	}
    
    	void findAllValidLeafPairs(
    		vector<NTreeNode *> leaves,
    		unordered_map<NTreeNode *, vector<pair<NTreeNode *, NTreeNode *>>> &edgeListMap,
    		unordered_map<pair<NTreeNode *, NTreeNode *>, int> &edgeUsageMap,
    		vector<pair<NTreeNode*, NTreeNode*>> &currentLeafPairs,
    		vector<unordered_set<pair<NTreeNode*, NTreeNode*>>> &validLeafPairSet) {
    		if (leaves.empty() || leaves.size() == 1) {
    			// Give some node not picked, the rest nodes may form a set which is a subset of when that node was picked, this is not a valid solution.
    			// E.g. given leaves {A, B, C, D}, after considered combination (A, B), (A, C), (A, D), we may want try pairs in {B, C, D} without A picked, 
    			// however, if we pick (B, C), D may or may not be able to pair with A, if D can pair with A, then (B, C) is just a subset of {(B, C), {A, D)},
    			// if A & D cannot pair given B, C selected, then {(B, C)} is a valid solution.
    			if (!IsSubsetOfExistingLeafPairSet(currentLeafPairs, validLeafPairSet)) {
    				validLeafPairSet.emplace_back(unordered_set<pair<NTreeNode*, NTreeNode*>>(currentLeafPairs.begin(), currentLeafPairs.end()));
    			}
    		}
    		else {
    			NTreeNode *node = leaves[0];
    			leaves.erase(leaves.begin());
    			for (int i = 0; i < leaves.size(); i++) {
    				NTreeNode *node2 = leaves[i];
    				if (checkEdgeUsage(node, node2, edgeListMap, edgeUsageMap)) {
    					setEdgeUsage(node, node2, edgeListMap, edgeUsageMap, USED);
    					currentLeafPairs.emplace_back(make_pair(node, node2));
    					leaves.erase(leaves.begin() + i);
    					findAllValidLeafPairs(leaves, edgeListMap, edgeUsageMap, currentLeafPairs, validLeafPairSet);
    					leaves.insert(leaves.begin() + i, node2);
    					currentLeafPairs.pop_back();
    					setEdgeUsage(node, node2, edgeListMap, edgeUsageMap, FREE);
    				}
    			}
    
    			//  We should also try the combinations without the first node picked 
    			findAllValidLeafPairs(leaves, edgeListMap, edgeUsageMap, currentLeafPairs, validLeafPairSet);
    		}
    	}
    
    	bool checkEdgeUsage(
    		NTreeNode * node1,
    		NTreeNode * node2,
    		unordered_map<NTreeNode *, vector<pair<NTreeNode *, NTreeNode *>>> &edgeListMap,
    		unordered_map<pair<NTreeNode *, NTreeNode *>, int> &edgeUsageMap) {
    		auto edge_it1 = edgeListMap[node1].begin();
    		auto edge_it2 = edgeListMap[node2].begin();
    		// If the 2 path shares some edges in the beginning, we bypass these edges, since they are above the LCA of the 2 nodes.
    		// E.g. A->B->C->E ->F and  A->B->C->D are paths from root to leaves F and D, we can ignore the common path A->B->C, 
    		// since from F to D, we only need go via the the LCA node C, and only edges C->E, E->F and C->D will be used.
    		while ((*edge_it1).first == (*edge_it2).first && (*edge_it1).second == (*edge_it2).second) {
    			edge_it1++;
    			edge_it2++;
    		}
    
    		bool isUsed = false;
    		for (; edge_it1 != edgeListMap[node1].end(); edge_it1++) {
    			if (edgeUsageMap[*edge_it1] == USED) {
    				isUsed = true;
    				break;
    			}
    		}
    
    		if (!isUsed)
    		{
    			for (; edge_it2 != edgeListMap[node2].end(); edge_it2++) {
    				if (edgeUsageMap[*edge_it2] == USED) {
    					isUsed = true;
    					break;
    				}
    			}
    		}
    		return !isUsed;
    	}
    
    	void setEdgeUsage(
    		NTreeNode * node1,
    		NTreeNode * node2,
    		unordered_map<NTreeNode *, vector<pair<NTreeNode *, NTreeNode *>>> &edgeListMap,
    		unordered_map<pair<NTreeNode *, NTreeNode *>, int> &edgeUsageMap,
    		int state) {
    		auto edge_it1 = edgeListMap[node1].begin();
    		auto edge_it2 = edgeListMap[node2].begin();
    		// Same idea with checkEdgeUsage.
    		while ((*edge_it1).first == (*edge_it2).first && (*edge_it1).second == (*edge_it2).second) {
    			edge_it1++;
    			edge_it2++;
    		}
    		for (; edge_it1 != edgeListMap[node1].end(); edge_it1++) {
    			edgeUsageMap[*edge_it1] = state;
    		}
    		for (; edge_it2 != edgeListMap[node2].end(); edge_it2++) {
    			edgeUsageMap[*edge_it2] = state;
    		}
    	}
    
    	bool IsSubsetOfExistingLeafPairSet(vector<pair<NTreeNode*, NTreeNode*>> &currentLeafPairs, vector<unordered_set<pair<NTreeNode*, NTreeNode*>>> &validLeafPairSet) {
    		bool isSubset = false;
    		for (auto leafSet : validLeafPairSet) {
    			isSubset = true;
    			for (auto leafPair : currentLeafPairs) {
    				if (leafSet.find(leafPair) == leafSet.end()) {
    					isSubset = false;
    					break;
    				}
    			}
    			if (isSubset) {
    				break;
    			}
    		}
    		return isSubset;
    	}
    };
    
    
    void Print(vector<unordered_set<pair<NTreeNode*, NTreeNode*>>> &validLeafPairSet) {
    	for (auto pairSet : validLeafPairSet) {
    		for (auto pair : pairSet) {
    			cout << '(' << pair.first->val << ',' << pair.second->val << "), ";
    		}
    		cout << endl;
    	}
    	cout << "Total:" << validLeafPairSet.size()<<endl;
    }
    
    int main()
    {
    	NTreeNode *root = new NTreeNode("A");
    	root->children = { new NTreeNode("B"), new NTreeNode("C"), new NTreeNode("D") };
    	root->children[0]->children = { new NTreeNode("E") };
    	root->children[1]->children = { new NTreeNode("F"),new NTreeNode("G"),new NTreeNode("H") };
    	G4G_MS_Set56_R1Q2 worker;
    	Print(worker.findDisjontLeafPairs(root));
    
    	root = new NTreeNode("A");
    	root->children = { new NTreeNode("B"), new NTreeNode("C"), new NTreeNode("D") };
    	Print(worker.findDisjontLeafPairs(root));
    
    	root = new NTreeNode("A");
    	root->children = { new NTreeNode("B"), new NTreeNode("C"), new NTreeNode("D"), new NTreeNode("E") };
    	Print(worker.findDisjontLeafPairs(root));
    	
    	root = new NTreeNode("A");
    	root->children = { new NTreeNode("B") };
    	root->children[0]->children = { new NTreeNode("C"), new NTreeNode("D") };
    	root->children[0]->children[0]->children = { new NTreeNode("E"), new NTreeNode("F") };
    	root->children[0]->children[0]->children[0]->children = { new NTreeNode("G"), new NTreeNode("H") };
    	Print(worker.findDisjontLeafPairs(root));
    	return 0;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.