We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Trees
  4. Swap Nodes [Algo]
  5. Discussions

Swap Nodes [Algo]

  • rajivaiyer
     + 0 comments

    My Java 8 solution, which passes all test cases, for Max Score of 40:

    I iterate over the entire tree structure as outlined in List<List<Integer>> indexes, and then I make a Map<Integer, Integer> nodeDepthMap, which maps a node to its corresponding depth in the tree. I also make a Map<Integer, List<Integer>> depthNodesLstMap which maps a given depth as Key to a List of Nodes occurring at that Depth as Value. These then come in handy for the next step, when I iterate through all the Queries, and execute them sequentially, performing swaps, and doing Recursive Inorder Traversals, accumulating the intermediate results.

    (Ignore the verbose debug print statements, as those helped in validating my logic with the initial limited test cases, and I commented it out once I verified that the logic is sound).

    class Result {

    public static List<Integer> inorderTraversal(List<List<Integer>> indexes) {
        List<Integer> result = new ArrayList<>();
        performInorderTraversal(indexes, 1, result);
        return result;
    }

    private static void performInorderTraversal(List<List<Integer>> indexes,
                                                int nodeNum, List<Integer> result) {
        if (nodeNum == -1 || nodeNum > indexes.size()) {
            return;
        }

        performInorderTraversal(indexes,
            indexes.get(nodeNum - 1).get(0), result);       // Visit left subtree

        result.add(nodeNum);                                // Visit current node

        performInorderTraversal(indexes,
            indexes.get(nodeNum - 1).get(1), result);       // Visit left subtree
    }
    
    public static void performSwapOnNode(List<List<Integer>> indexes, int nodeNum) {
        int nodeIdx = (nodeNum - 1);
        int temp = indexes.get(nodeIdx).get(0);
        indexes.get(nodeIdx).set(0, indexes.get(nodeIdx).get(1));
        indexes.get(nodeIdx).set(1, temp);
    }
    
    public static List<List<Integer>> executeAllSwapQueries(
            List<List<Integer>> indexes, List<Integer> queries,
            LinkedHashMap<Integer, List<Integer>> depthNodesLstMap) {

        int numQueries = queries.size();
                             
        int maxDepth = depthNodesLstMap.keySet()
                           .parallelStream()
                           .mapToInt(Integer::intValue)
                           .max()
                           .orElseThrow(NoSuchElementException::new);
                     
        List<List<Integer>> postSwapInorderResult = new ArrayList<>();

        System.err.println(""); System.err.println("");

        for (int qIdx = 0 ; qIdx < numQueries ; qIdx++) {

            int baseDepth = queries.get(qIdx);

            // System.err.println("Processing Query qIdx = >" + qIdx + "< with " + 
            //                    "baseDepth = >" + baseDepth + "<");

            for (int curDepth = baseDepth, curFactor = 1 ; 
                 curDepth <= maxDepth ; 
                 curFactor++, curDepth = (curFactor * baseDepth)) {

                List<Integer> nodesToBeSwappedLst = depthNodesLstMap.get(curDepth);

                // System.err.println("curDepth = >" + curDepth + "< | " + 
                //                    "nodesToBeSwappedLst = >" + nodesToBeSwappedLst + "<");

                for (Integer nodeNum : nodesToBeSwappedLst) {

                    performSwapOnNode(indexes, nodeNum);

                }

            }
            
            List<Integer> curPostSwpInorderLst = inorderTraversal(indexes);
            postSwapInorderResult.add(qIdx, curPostSwpInorderLst);

            // System.err.println("Processed Query qIdx = >" + qIdx + "< with " + 
            //                    "baseDepth = >" + baseDepth + "< | " + 
            //                    "curPostSwpInorderLst = >" + curPostSwpInorderLst + "<");
        }

        // System.err.println("Processed All >" + numQueries + "< Queries. " +
        //                    "postSwapInorderResult = >" + postSwapInorderResult + "<");

        return postSwapInorderResult;
    }

    /*
     * Complete the 'swapNodes' function below.
     *
     * The function is expected to return a 2D_INTEGER_ARRAY.
     * The function accepts following parameters:
     *  1. 2D_INTEGER_ARRAY indexes
     *  2. INTEGER_ARRAY queries
     */

    public static List<List<Integer>> swapNodes(List<List<Integer>> indexes, 
                                                List<Integer> queries) {
        // Write your code here
        // System.err.println(""); System.err.println("");
        // System.err.println("ENTRY: indexes.size() = >" + indexes.size() + "<");
        // System.err.println("ENTRY: queries.size() = >" + queries.size() + "<");

        // System.err.println(""); System.err.println("");
        // System.err.println("ENTRY: indexes = >" + indexes + "<");
        // System.err.println("ENTRY: queries = >" + queries + "<");
        
        int numNodes = indexes.size();

        LinkedHashMap<Integer, List<Integer>> depthNodesLstMap = new LinkedHashMap<>();

        LinkedHashMap<Integer, Integer> nodeDepthMap = new LinkedHashMap<>();
        IntStream.range(1, numNodes)
                 .forEach(i -> nodeDepthMap.put(i, 0));

        // Initializing for the Root Node '1', at Depth / Level 1
        nodeDepthMap.put(1, 1);
        if (!depthNodesLstMap.containsKey(1)) {
            depthNodesLstMap.put(1, new ArrayList<Integer>());
        }
        depthNodesLstMap.get(1).add(1);
        
        for (int i = 0 ; i < indexes.size() ; i++) {
            int leftChild = indexes.get(i).get(0);
            int rightChild = indexes.get(i).get(1);
            int nodeNum = (i + 1);
            
            if (leftChild != -1) {

                int leftChildDepth = (nodeDepthMap.get(nodeNum) + 1);

                nodeDepthMap.put(leftChild, leftChildDepth);

                if (!depthNodesLstMap.containsKey(leftChildDepth)) {
                    depthNodesLstMap.put(leftChildDepth, new ArrayList<Integer>());
                }
                depthNodesLstMap.get(leftChildDepth).add(leftChild);

            }

            if (rightChild != -1) {

                int rightChildDepth = (nodeDepthMap.get(nodeNum) + 1);

                nodeDepthMap.put(rightChild, rightChildDepth);

                if (!depthNodesLstMap.containsKey(rightChildDepth)) {
                    depthNodesLstMap.put(rightChildDepth, new ArrayList<Integer>());
                } 
                depthNodesLstMap.get(rightChildDepth).add(rightChild);

            }
        }

        // System.err.println(""); System.err.println("");
        // System.err.println("INIT: nodeDepthMap = >" + nodeDepthMap + "<");
        // System.err.println("INIT: depthNodesLstMap = >" + depthNodesLstMap + "<");

        return executeAllSwapQueries(indexes, queries, depthNodesLstMap);
    }

}