Graph Problem based on Traversal (DFS) | Hackerrank : Roads and Libraries

Hello Friends,

I am here with an problem based on Graphs. This I took from Hacker rank https://www.hackerrank.com/challenges/torque-and-development

The Problem summary is as follows.

Input and the problem Summary

1. There are n cites. 
2. Each city must either have a library or  be connected directly or indirectly via another city to a city having a library.
3. There are only m roads which can be build. These m paths are provided in the questions and represented by pair (city1,city2) : path connecting city1 and city2 directly.
4.  Cost of building the library is given as a part of input. (Big number between 1 and 10^5)
5. Cost of building road between any two cities is constant and is also given as a part of input.
   (Big number between 1 and 10^5)

Output

Minimum cost to make each city accessible to Library. 

Here is the code in Java for above problem:

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for(int a0 = 0; a0 < q; a0++){
            int n = in.nextInt();
            int m = in.nextInt();
            long x = in.nextLong(); // lib
            long y = in.nextLong(); // road
            Graph g = new Graph(n,m,x,y);
            g.addSingleNodes();
            for(int a1 = 0; a1 < m; a1++){
                int city_1 = in.nextInt();
                int city_2 = in.nextInt();
                g.addEdge(city_1,city_2);
            }
            System.out.println(g.computeCost());
        }
    }
    
        public static class Graph{
            long costRoad;
            long costLib;
            int n,m;
            Graph(int n, int m , long costLib, long costRoad){
                this.costRoad = costRoad;
                this.costLib = costLib;
                this.n = n;
                this.m = m;
            }
            private static class Node{
                Integer name;
                AdjListNode listHead;
                boolean isVisited;
                public Node(Integer name){
                    this.name = name;
                }
            }
            private static class AdjListNode{
                AdjListNode next;
                Node adj;
                AdjListNode(Node adj, AdjListNode next){
                    this.adj = adj;
                    this.next = next;
                }
            }
            Map<Integer,Node> nameNodeMap = new HashMap<>();
            void addEdge(Integer c1, Integer c2){
                Node n1 = nameNodeMap.get(c1);
                Node n2 = nameNodeMap.get(c2);
                n1.listHead = new AdjListNode(n2,n1.listHead);
                n2.listHead = new AdjListNode(n1,n2.listHead);
            }
            void addSingleNodes(){
                for(Integer i = 1; i <= n; i++){
                   nameNodeMap.put(i,new Node(i));
                }
            }
            long computeCost(){
               long answer = 0;
               if(costLib <= costRoad){
                   answer = n*costLib;
                   return answer;
               } 
               for(Node node : nameNodeMap.values()){
                   if(!node.isVisited){
                       answer += dfs(node)-costRoad + costLib;
                   }
               }
               return answer;
            }
            
            long dfs(Node node){
                AdjListNode temp = node.listHead;
                long cost = costRoad; 
                node.isVisited = true;
                while(temp != null){
                    if(!temp.adj.isVisited){
                       cost += dfs(temp.adj);
                    }
                    temp = temp.next;       
                }
                return cost;
            }
        }
}

 
 
 ** Make Sure we initialize all the vertices (nodes) of the graph. This should be independent of edge adding logic as the input edges may not contain all the vertices , there may be nodes which are not connected to any other vertices.

TRIE based java solution for Hacker rank : good set, bad set problem.

Hi Friends,

I am here with a problem, which is based on the No Prefix Set. It is about a set of input strings and we are supposed to find out if any string in the set is prefix of  any other one in the string. 

We are given N strings, we have to print "GOOD SET" if none of the strings in the set are prefix of any other string in the set. 
If any string is a prefix of any other string in the set then we are supposed to print "BAD SET" followed by the FIRST string for which such condition is detected in the set.

Link for the problem is : https://www.hackerrank.com/challenges/no-prefix-set

Please find below the TRIE based java solution for the same.

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        Node head = new Node();
        for(int i = 0; i < n ; i++){
            String line = sc.nextLine();
            if(!head.add(line)){
                System.out.println("BAD SET");
                System.out.println(line);
                sc.close();
                return;
            }
        }
        System.out.println("GOOD SET");
    }
    static class Node{
        Map<Character, Node> map = new HashMap<>();
        boolean isComplete;
        public boolean add(String word){
            return add(word,0);
        }
        private boolean add(String word, int index){
            if(isComplete){
                return false;
            }
            if(index == word.length()){
                isComplete = true;
                return true;
            }
            Node child = map.get(word.charAt(index));
            if(child == null){
                child = new Node();
                map.put(word.charAt(index),child);
            }else if(index + 1 == word.length()){
                return false;
            }
            return child.add(word,index+1);
        }
    }   
}

Contacts problem from Hacker rank. Count the number of contacts with given prefix | TRIE data structure | Java Based Solution

Hello Friends,

I am today with you with yet another good programming challenge. I have taken this problem from Hackerrank. The link for the problem is : https://www.hackerrank.com/challenges/contacts

It asks us to build an algorithm similar to the contacts application we have in our mobile phones.
The operations we need to support are

1. add (String contact) : The problem statement guarantees that always the contact will be unique
2. count (String partial) : Return all the number of contacts with prefix as partial. 

Friends for solving the problem optimally we will use TRIE data structure. Please find below my code for the same.

package hacker.rank.trie.contacts;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        Node head = new Node();
        for(int i = 0; i < n ; i++){
            String lines = sc.nextLine();
            String[] commands = lines.split(" ");
            if(commands[0].equals("add")){
                head.add(commands[1]);
            }else{
                int answer = head.getCount(commands[1]);
                System.out.println(answer);
            }
        }
    }
    static class Node{
        Map<Character, Node> map = new HashMap<>();
        boolean isComplete = true;
        int count = 0;
        public void add(String contact){
            add(contact,0);
        }
        private void add(String contact, int index){
            count++;
            if(index == contact.length()){
                isComplete = true;
                return;
            }
            Node child = map.get(contact.charAt(index));
            if(child == null){
                child = new Node();
                map.put(contact.charAt(index),child);
            }
            child.add(contact,index+1);
        }
        
        public int getCount(String partial){
            return getCount(partial,0);
        }
        
        private int getCount(String partial, int index){
            if(index == partial.length()){
                return count;
            }
            Node child = map.get(partial.charAt(index));
            if(child == null){
                return 0;
            }
            return child.getCount(partial, index+1);
        }
    }   
}

 

Vertical Level order traversal of Binary Tree. | Java solution

Dear Friends,

I am with you with a data structure and algorithmic problem based on Binary tree and Hashing.

Given a binary tree we need to print the nodes according to vertical level ordering.



For above Binary tree the vertical level ordering is as below
4
2
1 5 6
3 8
7
9

Lets try to analyze the above binary tree  

1. Lets record the horizontal (left, right) distance of each node from root
2. To record horizontal distance for a node from root , lets see as how many lefts and how many rights do we need to travel from root's horizontal position to reach the node's horizontal position.
3. Lets take 1 Left step as -1 and 1 Right step as +1.

Node	Horizontal distance of Node from Root
Node with value 1 (root)	0	Root => 0
Node with value 2	-1	0 + (-1) = -1
Node with value 4	-2	-1+(-1) = -2
Node with value 5	0	-1 + 1= 0
Node with value 3	+1	0 + 1 = +1
Node with value 6	0	+1 +(-1) = 0
Node with value 8	+1	0 +1 = +1
Node with value 7	+2	+1 +1 = +2
Node with value 9	+3	2+1 = +3

With above analysis lets see the code in java for the solution of this problem.

package krishnalearnings.binarytree;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class VerticalLevelOrderTraversal {
    public static class Node {
        private Node left;
        private Node right;
        private int data;

        public Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        // lets construct a tree
        Node root = new Node(1);
        Node node2 = new Node(2);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node3 = new Node(3);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node6.right = node8;
        node7.right = node9;
        // tree constructed
        printVerticalLevelOrder(root);
    }

    private static void printVerticalLevelOrder(Node root) {
        TreeMap<Integer, List<Node>> map = new TreeMap<>();
        initilizeMap(root, 0, map);
        Set<Integer> horizontalDistances = map.keySet();
        for (Integer distance : horizontalDistances) {
            for (Node node : map.get(distance)) {
                System.out.print(node.data + " ");
            }
            System.out.println();
        }
    }

    private static void initilizeMap(Node root, int horizontalDistance, Map<Integer, List<Node>> map) {
        if (root != null) {
            List<Node> list = map.get(horizontalDistance);
            if (list == null) {
                list = new ArrayList<>();
                map.put(horizontalDistance, list);
            }
            list.add(root);
            initilizeMap(root.left, horizontalDistance - 1, map);
            initilizeMap(root.right, horizontalDistance + 1, map);
        }
    }
}