Tag Archives: java

Hackerrank: Cracking the Coding Interview – Stacks: Balanced Brackets

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" );
        }
    }
}

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

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;
}

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

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);
    }
}

Hackerrank: Cracking the Coding Interview – Strings: Making Anagrams

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));
    }
}

Hackerrank: Cracking the Coding Interview – Arrays: Left Rotation

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(" ");
        }
    }
}

UVA 10855 – Rotated square

This problem has an interesting algorithm used it in. How to rotate a square matrix. Basically if you want to rotate a square matrix by 90 degress you can notice that 4 elements in the 2D array get changed in a cyclical manner. You can just repeat this for (almost) one quarter of the square that you are rotating.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P10855 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);
    StringTokenizer st = null;

    while (true) {

      st = new StringTokenizer(br.readLine());
      int N = Integer.parseInt(st.nextToken());
      int n = Integer.parseInt(st.nextToken());
      if (N + n == 0)
        break;

      char[][] big = new char[N][N];
      for (int i = 0; i < N; i++) {
        char[] line = br.readLine().toCharArray();
        for (int j = 0; j < N; j++) {
          big[i][j] = line[j];
        }
      }

      char[][] small = new char[n][n];
      for (int i = 0; i < n; i++) {
        char[] line = br.readLine().toCharArray();
        for (int j = 0; j < n; j++) {
          small[i][j] = line[j];
        }
      }

      out.print(check(big, small) + " ");
      rotate(small);
      out.print(check(big, small) + " ");
      rotate(small);
      out.print(check(big, small) + " ");
      rotate(small);
      out.println(check(big, small));
    }
    
    out.close();
    br.close();
  }

  private static int check(char[][] big, char[][] small) {
    int ans = 0;
    for (int i = 0; i <= big.length - small.length; i++) {
      for (int j = 0; j <= big.length - small.length; j++) {
        if (big[i][j] == small[0][0]) {
          boolean found = true;
          for (int k = 0; k < small.length; k++) {
            for (int l = 0; l < small.length; l++) {
              if (big[i + k][j + l] != small[k][l]) {
                found = false;
                break;
              }
            }
          }
          if (found)
            ans++;
        }
      }
    }
    return ans;
  }

  private static void rotate(char[][] m) {
    int n = m.length;
    for (int i = 0; i < n / 2; i++)
      for (int j = 0; j < (n + 1) / 2; j++) {
        char temp = m[i][j];
        m[i][j] = m[n - 1 - j][i];
        m[n - 1 - j][i] = m[n - 1 - i][n - 1 - j];
        m[n - 1 - i][n - 1 - j] = m[j][n - 1 - i];
        m[j][n - 1 - i] = temp;
      }
  }
}

UVA 101 – The Blocks Problem

Basic simulation. Just need to follow the instructions in the question.

import java.awt.Point;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P101 {

  public static void main(String args[]) // entry point from OS
  {
    Scanner sc = new Scanner(System.in);
    int size = sc.nextInt();
    @SuppressWarnings("unchecked")
    ArrayList<Integer>[] blocks = new ArrayList[size];
    for (int i = 0; i < size; i++) {
      blocks[i] = new ArrayList<Integer>();
      blocks[i].add(i);
    }

    // System.out.println(Arrays.deepToString(blocks));

    while (sc.hasNext()) {
      String t = sc.next();
      if (t.equals("quit")) {
        break;
      } else {
        int a = sc.nextInt();
        String x = sc.next();
        int b = sc.nextInt();

        if (a == b)
          continue;

        Point posA = findBlock(a, blocks);
        Point posB = findBlock(b, blocks);

        if (posA.x == posB.x)
          continue;

        if (t.equals("move")) {
          moveBack(posA, blocks);
          if (x.equals("onto")) {
            moveBack(posB, blocks);
            blocks[posA.x].remove(posA.y);
            blocks[posB.x].add(a);
          } else {
            blocks[posA.x].remove(posA.y);
            blocks[posB.x].add(a);
          }
        } else if (t.equals("pile")) {
          if (x.equals("onto")) {
            moveBack(posB, blocks);
            int removed = 0;
            int tSize = blocks[posA.x].size();
            for (int i = posA.y; i < tSize; i++) {
              blocks[posB.x].add(blocks[posA.x].remove(i - removed));
              removed++;
            }
          } else {
            int removed = 0;
            int tSize = blocks[posA.x].size();
            for (int i = posA.y; i < tSize; i++) {
              blocks[posB.x].add(blocks[posA.x].remove(i - removed));
              removed++;
            }
          }
        }
      }
      // System.out.println(Arrays.deepToString(blocks));
    }

    // System.out.println(Arrays.deepToString(blocks));

    for (int i = 0; i < size; i++) {
      System.out.print(i + ":");
      int tSize = blocks[i].size();
      for (int j = 0; j < tSize; j++) {
        System.out.print(" " + blocks[i].remove(0));
      }
      System.out.println();
    }
    sc.close();
  }

  private static void moveBack(Point posA, ArrayList<Integer>[] blocks) {
    int removed = 0;
    int tSize = blocks[posA.x].size();
    for (int i = posA.y + 1; i < tSize; i++) {
      int x = (Integer) blocks[posA.x].remove(i - removed);
      removed++;
      blocks[x].add(x);
    }
  }

  private static Point findBlock(int a, ArrayList<Integer>[] blocks) {
    for (int i = 0; i < blocks.length; i++) {
      for (int j = 0; j < blocks[i].size(); j++) {
        if ((Integer) blocks[i].get(j) == a) {
          return new Point(i, j);
        }
      }
    }
    return null;
  }
}

UVA 12356 – Army Buddies

So this question is interesting. I was updating too much and was getting TLE. Once a buddy dies, there are obviously no more requests containing army members who are no more. We can therefore safely update only the end points of every given query.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P12356 {

  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);
    StringTokenizer st = null;

    String line = null;
    while ((line = br.readLine()) != null) {
      st = new StringTokenizer(line);
      int S = Integer.parseInt(st.nextToken());
      int B = Integer.parseInt(st.nextToken());
      if (S == 0 && B == 0)
        break;
      int[] leftBuddy = new int[S + 2];
      int[] rightBuddy = new int[S + 2];
      for (int i = 1; i <= S; i++) {
        leftBuddy[i] = i - 1;
        rightBuddy[i] = i + 1;
      }
      rightBuddy[S] = 0;
      for (int i = 0; i < B; i++) {
        st = new StringTokenizer(br.readLine());
        int l = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        if (leftBuddy[l] == 0)
          out.print("* ");
        else
          out.print(leftBuddy[l] + " ");
        if (rightBuddy[r] == 0)
          out.println("*");
        else
          out.println(rightBuddy[r]);
        leftBuddy[rightBuddy[r]] = leftBuddy[l];
        rightBuddy[leftBuddy[l]] = rightBuddy[r];
      }
      out.println("-");
    }
    out.close();
    br.close();
  }
}

UVA 10050 – Hartals

Simultaed all the holidays and then removed them from the list of total days.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P10050 {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);

    int numTestCases = Integer.parseInt(br.readLine().trim());
    for (int testCase = 1; testCase <= numTestCases; testCase++) {
      int N = Integer.parseInt(br.readLine().trim());
      int P = Integer.parseInt(br.readLine().trim());
      HashSet<Integer> ans = new HashSet<Integer>();
      for (int i = 0; i < P; i++) {
        int tmp = Integer.parseInt(br.readLine().trim());
        int max = N / tmp;
        for (int j = 1; j <= max; j++) {
          ans.add(tmp * j);
        }
      }
      int max = N / 7 + 1;
      for (int j = 1; j <= max; j++) {
        int tmp = 7 * j;
        if (ans.contains(tmp))
          ans.remove(tmp);
        if (ans.contains(tmp - 1))
          ans.remove(tmp - 1);
      }
      out.println(ans.size());
    }
    out.close();
  }
}

UVA 10038 – Jolly Jumpers

Easy problem. Take all differences, put them in a HashSet and then check if all the requred numbers are in the HashSet or not.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.StringTokenizer;

/**
 *
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 *
 */
public class P10038 {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);
    StringTokenizer st;

    String line = null;
    while ((line = br.readLine()) != null) {
      st = new StringTokenizer(line.trim());
      int N = Integer.parseInt(st.nextToken());
      if (N == 1) {
        out.println("Jolly");
      } else {
        HashSet<Integer> ans = new HashSet<Integer>();
        int last = 0;
        for (int i = 0; i < N; i++) {
          if (i == 0) {
            last = Integer.parseInt(st.nextToken());
          } else {
            int tmp = Integer.parseInt(st.nextToken());
            ans.add(Math.abs(tmp - last));
            last = tmp;
          }
        }

        if (ans.size() != N - 1) {
          out.println("Not jolly");
        } else {
          boolean found = true;
          for (int i = 1; i < N; i++) {
            if (!ans.contains(i)) {
              found = false;
              break;
            }
          }
          if (found) {
            out.println("Jolly");
          } else {
            out.println("Not jolly");
          }
        }
      }
    }
    out.close();
    br.close();
  }
}