Sort by

recency

|

720 Discussions

|

1 day ago+ 0 comments

This Problem Is A Prime Example Of Why Hackerrank Is Such A Bad Platform

In HR, the input to the function isn't always similar to the input to the program/submission. Alright. But in this case the function they want us to implement takes the input as a 2D array and outputs the same data structure as a 1D array. This adds an unnecessary layer of complexity on top of the actual problem in the question.

The platform should stay consistant with the input and output representation. Why the hell would a tree look like A in the input but look like B in the output? It's a poor design choice that just makes file io easier for the person who made the question. Not to mention that in an interview we have to understand everything and nail both the problem and structuring the output in 30 minutes to get a job.

6 days ago+ 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);
    }

}

1 month ago+ 0 comments

Java Solution, using level order traversal using 2 queues Start with putting 1 in the primary queue, 1. poll from primary queue, check if you need to swap the child i.e level % k == 0. 2. add the child indexes in secondary queuue. repeat step 1 and 2 until primary queue is empty. once empty means level is done, go to next level. poll all the indexes from secondary and add into primary. do the inOrderTraversal of the tree and add the list to a list

public static List> swapNodes(List> indexes, List queries) { // Write your code here Queue primary = new LinkedList<>(); Queue secondary = new LinkedList<>();

    List<List<Integer>> res = new ArrayList<>();
    for (int k : queries) {
        primary.add(1);
        int level = 1;
        while (!primary.isEmpty()) {
            while (!primary.isEmpty()) {
                int p = primary.poll();
                List<Integer> child = indexes.get(p - 1);
                if (level % k == 0) { // swap left and right child
                    child.add(child.get(0));
                    child.remove(0);
                }
                child.stream().filter(ch -> ch != -1).forEach(secondary::add); //add the non null child to secondary queue representing next level
            }
            while (!secondary.isEmpty())
                primary.add(secondary.poll());
            level++;
        }
        List<Integer> traversal = new ArrayList<>();
        inOrderTraversal(1, indexes, traversal);
        res.add(traversal);
    }

    return res;
}

private static void inOrderTraversal(int root, List<List<Integer>> indexes, List<Integer> res) {
    int left = indexes.get(root - 1).get(0);
    if (left != -1)
        inOrderTraversal(left, indexes, res);
    res.add(root);
    int right = indexes.get(root - 1).get(1);
    if (right != -1)
        inOrderTraversal(right, indexes, res);
}

4 months ago+ 0 comments

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import deque

#
# 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
#



# very compact when to depict a tree
# use a list (or dic) of the nodes to represent the tree
# the ith node on the tree has the data of i+1
# so as long as you can find a node that is not -1 then you can find it child and kkep on 

sys.setrecursionlimit(2000)
# get the inorder from the i in tree
def inOrder(i, tree):
    # nothing to further check
    if i == -1:
        return []
    # get two sons for this non null node
    # note, its sons are in the i-1 position
    left, right = tree[i-1]

    return inOrder(left, tree) + [i] + inOrder(right, tree)


# make a list of list to track the depth (use the deque)
# 0: [1], 1:[2,3], can cause a blank list 
def getNodeDeepth(tree):
    depth_list = [[1]]
    # the initial queue
    depth_queue = deque([1])
    
    # those are in the same depth
    while depth_queue:
        # we are dealing a new depth of node
        depth_list.append([])
        for _ in range(len(depth_queue)):
            i = depth_queue.popleft()
            l,r = tree[i-1]
            if l != -1:
                depth_queue.append(l)
                depth_list[-1].append(l)
            if r != -1:
                depth_queue.append(r)
                depth_list[-1].append(r)
        if not depth_list[-1]:
            depth_list.pop()
    return depth_list     
            
        



def swapNodes(indexes, queries):
    #print(inOrder(1,indexes))
    depth_list = getNodeDeepth(indexes)
    
    ret = []
    for k in queries:
        i = 1
        while i * k <= len(depth_list):
            parents = depth_list[i * k -1]
            for p in parents:
                l,r = indexes[p -1]
                indexes[p -1] = r,l
            i += 1
        ret.append(inOrder(1,indexes))
    
    return ret
    # Write your code here

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    indexes = []

    for _ in range(n):
        indexes.append(list(map(int, input().rstrip().split())))

    queries_count = int(input().strip())

    queries = []

    for _ in range(queries_count):
        queries_item = int(input().strip())
        queries.append(queries_item)

    result = swapNodes(indexes, queries)

    fptr.write('\n'.join([' '.join(map(str, x)) for x in result]))
    fptr.write('\n')

    fptr.close()

5 months ago+ 0 comments

include

using namespace std; vector leftNode, rightNode; int swapLevel;

void traverse(int node=1){ if (node == -1) return; traverse(leftNode[node]); cout << node << " "; traverse(rightNode[node]); if (node == 1) cout << endl; }

void swap(int level=1, int node=1) { if (node == -1) return; if (level % swapLevel == 0) { int tmp = leftNode[node]; leftNode[node] = rightNode[node]; rightNode[node] = tmp; } swap(level+1, leftNode[node]); swap(level+1, rightNode[node]); }

int main() { int count;
cin>>count; leftNode.push_back(0); rightNode.push_back(0); while(count--){ int L, R; cin>>L>>R; leftNode.push_back(L); rightNode.push_back(R); } cin>>count; while(count--){ cin >> swapLevel; swap(); traverse(); } return 0; }

Sort by

|

720 Discussions

|

This Problem Is A Prime Example Of Why Hackerrank Is Such A Bad Platform

include

include

include

include

include

Cookie support is required to access HackerRank