Category Archives: Cracking the Coding Interview

Algorithms, Cracking the Coding Interview, HackerRank, Java

Hackerrank: Cracking the Coding Interview – Stacks: Balanced Brackets

Leave a comment

This is again a classic problem of detecting matching parenthesis. In fact, the title even tells you the appropriate data structure to use in order to solve this problem. The solution relies on the fact that if a left bracket (by bracket in this post I mean ‘(‘, ‘[‘ or ‘{‘) is found we can push it on to the stack and eventually whenever the corresponding right bracket (‘)’, ‘]’ or ‘}’) is found then we would be popping it off the stack. If the stack is empty after we are done with the entire input then we know that the input string was balanced properly.

The code I have written should be easy to understand but is a bit lengthy. In retrospect I could have refactored the checking and comparing part into a function so it looks nicer.

FYI this is what all those characters are actually called:

( ) – Parenthesis
{ } – Braces
[ ] – Brackets

Problem: https://www.hackerrank.com/challenges/ctci-balanced-brackets

Solution:

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

public class Solution {
    
    public static boolean isBalanced(String expression) {
        LinkedList<Character> stack = new LinkedList<>();
        char[] input = expression.toCharArray();
        for (int i=0; i<input.length; i++) {
            if (stack.isEmpty()) {
                stack.push(input[i]);
            } else {
                if (stack.peek() == '{') {
                    if (input[i] == ']' || input[i] == ')') {
                        return false;
                    } else if (input[i] == '}') {
                        stack.pop();
                    } else {
                        stack.push(input[i]);
                    }
                } else if (stack.peek() == '[') {
                    if (input[i] == '}' || input[i] == ')') {
                        return false;
                    } else if (input[i] == ']') {
                        stack.pop();
                    } else {
                        stack.push(input[i]);
                    }
                } else if (stack.peek() == '(') {
                    if (input[i] == ']' || input[i] == '}') {
                        return false;
                    } else if (input[i] == ')') {
                        stack.pop();
                    } else {
                        stack.push(input[i]);
                    }
                }
            }
        }
        return stack.isEmpty();
    }
  
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int a0 = 0; a0 < t; a0++) {
            String expression = in.next();
            System.out.println( (isBalanced(expression)) ? "YES" : "NO" );
        }
    }
}
Algorithms, Cracking the Coding Interview, HackerRank, Java

Hackerrank: Cracking the Coding Interview – Linked Lists: Detect a Cycle

Leave a comment

For this problem we can apply a classic algorithm known as the tortoise and hare algorithm by Robert W. Floyd. We will use two pointers, one going faster than the other. If one of them reaches null then we know there are no cycles. Otherwise, eventually, the two pointers will point to the same node in the LinkedList and we will know that a cycle has been detected.

The wikipedia article I have linked also mentions some other algorithms for cycle detection that can be read for fun.

Problem: https://www.hackerrank.com/challenges/ctci-linked-list-cycle

Solution:

boolean hasCycle(Node head) {
    if (head == null || head.next == null) {
        return false;
    }
    Node tortoise = head;
    Node hare = head;
    while (tortoise != null && hare != null) {
        tortoise = tortoise.next;
        hare = hare.next;
        if (hare != null) {
            hare = hare.next;
            if (tortoise == hare) {
                return true;
            }
        }
    }
    return false;
}
Cracking the Coding Interview, HackerRank, Java

Hackerrank: Cracking the Coding Interview – Hash Tables: Ransom Note

Leave a comment

This solution just involves keeping track of how many words are available and how many are used. If at any point we are using more than are available then we know the answer is “No”. If all goes will after trying to print out the ransom note then we can safely print “Yes”.

Problem: https://www.hackerrank.com/challenges/ctci-ransom-note

Solution:

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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        String magazine[] = new String[m];
        for(int magazine_i=0; magazine_i < m; magazine_i++){
            magazine[magazine_i] = in.next();
        }
        HashMap<String,Integer> map = new HashMap<>();
        for (int i=0; i<magazine.length; i++) {
            if (map.containsKey(magazine[i])) {
                map.put(magazine[i], map.get(magazine[i]) + 1);
            } else {
                map.put(magazine[i], 1);
            }
        }
        String ransom[] = new String[n];
        boolean done = false;
        String ans = "Yes";
        for(int ransom_i=0; !done && ransom_i < n; ransom_i++){
            ransom[ransom_i] = in.next();
            if (map.containsKey(ransom[ransom_i])) {
                int x = map.get(ransom[ransom_i]);
                if (x > 1) {
                    map.put(ransom[ransom_i], x - 1);
                } else {
                    map.remove(ransom[ransom_i]);
                }
            } else {
                done = true;
                ans = "No";
            }
        }
        System.out.println(ans);
    }
}
Cracking the Coding Interview, HackerRank, Java

Hackerrank: Cracking the Coding Interview – Strings: Making Anagrams

Leave a comment

The solution to this problem involves figuring out that if we just take the differences in the counts of the number of distinct characters in each string then that is the optimal amount of deletions we need to make. It should also be noted that while doing the calculations we need to ignore negative values and make them positive instead.

Problem: https://www.hackerrank.com/challenges/ctci-making-anagrams

Solution:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
    public static int numberNeeded(String first, String second) {
        char[] a = first.toCharArray();
        char[] b = second.toCharArray();
        int[] ac = new int[26];
        int[] bc = new int[26];
        for (int i=0; i<a.length; i++) {
            ac[a[i]-'a']++;
        }
        for (int i=0; i<b.length; i++) {
            bc[b[i]-'a']++;
        }
        int ans = 0;
        for (int i=0; i<ac.length; i++) {
            ans += Math.abs(ac[i] - bc[i]);
        }
        return ans;
    }
  
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();
        System.out.println(numberNeeded(a, b));
    }
}
Cracking the Coding Interview, HackerRank, Java

Hackerrank: Cracking the Coding Interview – Arrays: Left Rotation

Leave a comment

The solution is easy if you know how the mod operator works. You take every original index and shift it to the left by d. This, however, can lead to negative values so we increment this value by the size of the array (n) and mod it by n so that all values fit within [0, n – 1]. You can also think of this as adding (n-k) to every index if that makes more sense.

Problem: https://www.hackerrank.com/challenges/ctci-array-left-rotation

Solution:

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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int a[] = new int[n];
        for(int i=0; i < n; i++){
            a[(i - k + n) % n] = in.nextInt();
        }
        for (int i=0; i<n; i++) {
            System.out.print(a[i]);
            System.out.print(" ");
        }
    }
}