Header Ad

HackerRank Swap Nodes [Algo] problem solution

In this HackerRank Swap Nodes [Algo] interview preparation kit problem You are given a tree of n nodes where nodes are indexed from [1..n] and it is rooted at 1. You have to perform t swap operations on it and after each swap operation print the in-order traversal of the current state of the tree.

HackerRank Swap Nodes [Algo] Interview preparation kit solution


Problem solution in Python programming.

from collections import deque

class Node:
    def __init__(self, index):
        self.left = None
        self.right = None
        self.index = index
        
    
def in_order_traverse(root):
    """Don't use recursion b/c of recursion limit."""
    stack = deque([root])
    visited = set()
    while stack:
        node = stack.pop()
        if node is None:
            continue
        if node.index in visited:
            print(node.index, end=' ')
            continue
        visited.add(node.index)
        stack.append(node.right)
        stack.append(node)
        stack.append(node.left)
    
    
def swap(root, k):
    """Don't use recursion b/c of recursion limit."""
    q = deque([(root, 1)])
    while q:
        node, level = q.popleft()
        if node is None:
            continue
        if level % k == 0:
            node.left, node.right = node.right, node.left
        q.append((node.left, level+1))
        q.append((node.right, level+1))

        
        
# get number of nodes    
N = int(input())

# create node list
nodes = [None]*(N+1)
for i in range(1, N+1):
    n = Node(i)
    n.left_index, n.right_index = [v if v > 0 else 0 for v in map(int, input().split())]
    nodes[i] = n

# fill out node objects
for n in nodes[1:]:
    left = nodes[n.left_index]
    right = nodes[n.right_index]
    n.left = left
    n.right = right

T = int(input())
root = nodes[1]
# do the swapping
for _ in range(T):
    k = int(input())
    swap(root, k)
    in_order_traverse(root)
    print('')



Problem solution in Java Programming.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

import java.util.*;

public class Solution{
    static Node root = new Node(1);

    public static void main(String ... arg)
    {
        Scanner sc = new Scanner(System.in);
        int n,t,k;
        n = sc.nextInt();
        int[][] tree = new int[n][2];
        for(int i=0;i<n;i++)
        {
            tree[i][0] = sc.nextInt();
            tree[i][1] = sc.nextInt();
        } 
        root = ConstuctTree(tree);
        t = sc.nextInt();
        while(t-->0)
        {
            k = sc.nextInt();
            levelWise(root,k);
            InOrderRec(root);
            System.out.println();
        }
    }

    public static void levelWise(Node root,int k)
    {
        Stack<Node> currentlevel = new Stack<>();
        Stack<Node> nextlevel = new Stack<>();
        int level=1;
        Node temp;
        currentlevel.push(root);
        while(!currentlevel.empty())
        {
            temp = currentlevel.peek();
            currentlevel.pop();
            if(temp.left!=null)
                nextlevel.push(temp.left);
            if(temp.right!=null)
                nextlevel.push(temp.right);
            if(level%k == 0)
            {
                Node n = temp.left;
                temp.left = temp.right;
                temp.right = n;
            }
            if(currentlevel.empty())
            {
                Stack<Node> t = currentlevel;
                currentlevel = nextlevel;
                nextlevel = t;
                level++;
            }
        }
    }

    public static void InOrderRec(Node root)
    {
        if(root == null)
            return;
        InOrderRec(root.left);
        sout(root.data);
        InOrderRec(root.right);
    }

    public static Node ConstuctTree(int[][] tree)
    {
        Node root = new Node(1);
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        for(int i=0;i<tree.length;i++)
        {
            Node left,right;
            if(tree[i][0]!=-1)
                left = new Node(tree[i][0]);
            else
                left = null;
            if(tree[i][1]!=-1)
                right= new Node(tree[i][1]);
            else
                right = null;

            Node temp = q.remove();
            temp.left = left;
            temp.right = right;

            if(left!=null)
                q.add(left);
            if(right!=null)
                q.add(right);
        }
        return root;
    }


    public static void sout(int info)
    {
        System.out.printf("%d ",info);
    }
}

class Node{
    int data;
    Node left,right;
    Node(int item)
    {
        data = item;
        left = null;
        right = null;
    }
}


Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> 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;
}


Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>


struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* create_node(int val){
    if(val == -1){
        return NULL;
    }
    struct node *temp=(struct node*)malloc(sizeof(struct node));
    temp->data=val;
    temp->left=NULL;
    temp->right=NULL;
    return temp; 
}

void inorder(struct node *root){
    if(!root){
        return;
    }    
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int max(int a, int b){
    if(a>b){
        return a;
    } else {
        return b;
    }
}

int height(struct node * root){
    if(!root){
        return 0;
    }
    return(1+max(height(root->left),height(root->right)));
}

void swap_nodes_at_level(struct node *root, int inc, int level, int height){
    struct node *tnode;
    if(!root){
        return;
    }
    if(level > height){
        return;
    }
    if(!(level%inc)){
        tnode=root->left;
        root->left=root->right;
        root->right=tnode;
    }
    swap_nodes_at_level(root->left, inc, level+1, height);
    swap_nodes_at_level(root->right, inc, level+1, height);
}

int tail=0;
int head=0;


void enqueue(struct node **queue, struct node *root){
    
    queue[tail]=root;
    tail++;   
}

struct node* dequeue(struct node **queue){
    
    struct node *temp = queue[head];
    head++;
    return temp;
}

int main() {
    
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int nodes_count, i, temp, h, tc_num, index, inc, temp1, temp2;
          
    scanf("%d", &nodes_count);
    
  //  printf("%d\n", nodes_count);
    
    // int arr[2*nodes_count+1];
    
    struct node *root_perm, *root_temp;
    
    //queue=create_queue(nodes_count);

    struct node *q[nodes_count];
    for(i=0;i<nodes_count;i++){
        q[i]=NULL;
    }    
    
    //building the array
    
    //arr[0]=1;
    
   // for(i=1;i<=2*nodes_count;i++){
     //   scanf("%d",&temp);
      //  arr[i]=temp;
   //   printf("%d ", arr[i]);
   // }
    
    i=0,index=1;
    root_temp=root_perm=create_node(1);
    enqueue(q, root_temp);
    
    while(index<=2*nodes_count) {
       
        //printf("\n In Loop : i : %d",i);
        root_temp=dequeue(q);
        //setting up the left child
        scanf("%d", &temp1);
        if(temp1 == -1){
       
        } else {
            root_temp->left=create_node(temp1);
            enqueue(q, root_temp->left);
        }
        //setting up the right child
        scanf("%d", &temp2);
        if(temp2==-1) {
            
        } else {
            root_temp->right=create_node(temp2);
            enqueue(q, root_temp->right);
        }
        index=index+2;
      //  i++;
        
    }
   
    h = height(root_perm);
    
    scanf("%d", &tc_num);
    
    //printf("%d",tc_num);
    //printf("\n");
    
    //inorder(root_perm);
    
    while(tc_num){
        scanf("%d",&inc);
        temp=inc;
        //while(temp < height){
        swap_nodes_at_level(root_perm, inc, 1, h);
        //temp=temp + inc;
        //}
        //temp=0;
        inorder(root_perm);
        printf("\n");
        tc_num--;
    }  
    
    //Tree is created at this point 
    
    return 0;
}


Problem solution in JavaScript programming.

function toNumber (arr) { return arr.map(function (i) { return Number(i); })}

function nodesAtDepth(root, depth, current) {
    current = current || 1;
    if (depth === current) {
        return [root];
    } else {
        return (
            [].concat(root.left ? nodesAtDepth(root.left, depth, current + 1) : [])
              .concat(root.right ? nodesAtDepth(root.right, depth, current + 1) : []));
    }
}

function inOrderTraversal(root) {
    var out = [];
    if (root.left) out = out.concat(inOrderTraversal(root.left));
    out.push(root.val);
    if (root.right) out = out.concat(inOrderTraversal(root.right));
    return out;
}

function TNode(v, l, r) {
    this.val = v;
    this.right = r || undefined;
    this.left = l || undefined;
} 
    
TNode.prototype.swap = function () {
    tmp = this.right;
    this.right = this.left;
    this.left = tmp;
}

function swap(root, k, max) {
    var d = k, i = 2;
    while (d <= max) {
        nodesAtDepth(root, d, 1).forEach(function (node) { node.swap(); });
        d = i * k;
        i++;
    }
    console.log(inOrderTraversal(root).join(' '));
}

function processData(input) {
    
    var lines = input.split('\n').reverse();
    
    var n = Number(lines.pop().split());
    var nodes = new Array(n+1);
    
    var _index, _lr, i, k;
    
    for (i = 0; i < n ; i++) {
        _index = i + 1;
        nodes[_index] = new TNode(_index);
    }
    
    for (i = 0; i < n ; i++) {
        _index = i + 1;
        _lr = toNumber(lines.pop().split(' '));
        if (_lr[0] > -1) nodes[_index].left = nodes[_lr[0]];
        if (_lr[1] > -1) nodes[_index].right = nodes[_lr[1]];
    }
    
    var ops = Number(lines.pop());
    for (var j = 0; j < ops; j++) {
        k = Number(lines.pop()) ;
        swap(nodes[1], k, n - 1);
    }
    
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});


Post a Comment

3 Comments

  1. This comment has been removed by the author.

    ReplyDelete
  2. void swap(int level=1, int node=1) ..why are we intialising level? shouldnt it come from "swapLevel" ..i dont understand this part, could someone help?

    ReplyDelete
    Replies
    1. no swapLevel is side variable that count the level of node. level is the indexing point while the swapLevel is the node level where we are performing the swapping.

      Delete