Category Archives: Algorithms

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

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 162 – Beggar My Neighbour

This was a pain to debug but I finally got it right. There’s a little bit of trickery with outputting the result as well so watch out for that!

import java.io.PrintWriter;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    while (sc.hasNextLine()) {
      String line = sc.nextLine().trim();
      while (line.equals(""))
        line = sc.nextLine();
      if (line.equals("#"))
        break;

      gameOver = false;
      Player[] players = new Player[2];
      for (int i = 0; i < players.length; i++) {
        players[i] = new Player();
      }
      Card[] deck = new Card[52];
      StringTokenizer st = new StringTokenizer(line);
      for (int i = 0; i < 13; i++) {
        deck[i] = new Card(st.nextToken());
      }
      for (int i = 13; i < 52; i++) {
        deck[i] = new Card(sc.next());
      }

      for (int j = 0; j < players.length; j++) {
        for (int i = 0; i < 26; i++) {
          players[j].deck.add(deck[i * 2 + j]);
        }
        Collections.reverse(players[j].deck);
      }

      // players[0] = non-dealer
      // players[1] = dealer

      int idx = 0;
      LinkedList<Card> stack = new LinkedList<>();
      while ((players[0].deck.size() > 0 || players[1].deck.size() > 0) && !gameOver) {
        Card played = players[idx].deck.poll();
        if (played == null)
          break;
        stack.add(played);
        if (played.isFaceCard()) {
          idx = doThing(stack, players, idx);
        }
        idx = 1 - idx;
      }
      if (players[0].deck.isEmpty()) {
        out.println("1 " + String.format("%2d", players[1].deck.size()));
      } else {
        out.println("2 " + String.format("%2d", players[0].deck.size()));
      }

    }
    out.close();
    sc.close();
  }

  private static boolean gameOver = false;

  private static int doThing(LinkedList<Card> stack, Player[] players, int idx) {
    boolean good = true;
    idx = 1 - idx;
    int val = getGameCardVal(stack.peekLast());
    for (int i = 0; i < val; i++) {
      Card played = players[idx].deck.poll();
      if (played == null) {
        gameOver = true;
        good = false;
        break;
      } else {
        stack.add(played);
        if (played.isFaceCard()) {
          return doThing(stack, players, idx);
        }
      }
    }
    if (good)
      while (!stack.isEmpty()) {
        players[1 - idx].deck.add(stack.poll());
      }
    return idx;
  }

  private static int getGameCardVal(Card c) {
    switch (c.card.charAt(1)) {
      case 'A':
        return 4;
      case 'K':
        return 3;
      case 'Q':
        return 2;
      case 'J':
        return 1;
    }
    return 0;
  }

  private static class Card {
    String card;

    public Card(String card) {
      int test1 = getSuitIdx(card.charAt(0));
      if (test1 == -1)
        return;
      int test2 = getNumIdx(card.charAt(1));
      if (test2 == -1)
        return;
      this.card = card;
    }

    public boolean isFaceCard() {
      int val = getCardValue();
      return (val == 1 || val == 11 || val == 12 || val == 13);
    }

    public int getCardValue() {
      return getNumIdx(card.charAt(1));
    }

    private int getSuitIdx(char suit) {
      switch (suit) {
        case 'H':
          return 0;
        case 'S':
          return 1;
        case 'D':
          return 2;
        case 'C':
          return 3;
      }
      return -1;
    }

    private int getNumIdx(char num) {
      switch (num) {
        case 'A':
          return 1;
        case 'T':
          return 10;
        case 'J':
          return 11;
        case 'Q':
          return 12;
        case 'K':
          return 13;
        default:
          try {
            int val = Integer.parseInt(num + "");
            if (val > 1 && val < 10)
              return val;
            return -1;
          } catch (Exception e) {
            return -1;
          }
      }
    }

    @Override
    public String toString() {
      return this.card;
    }

  }

  private static class Player {
    private LinkedList<Card> deck;

    public Player() {
      deck = new LinkedList<>();
    }

    @Override
    public String toString() {
      return this.deck.toString();
    }
  }

}

UVA 12478 – Hardest Problem Ever (Easy)

So this was an interesting problem. You could have technically solved it manually but that would have taken too much time. If you didn’t mind at most 7 WA’s you could have just tried all 8 solutions one at a time and gotten it correct. I did it the long way; making my program solve it for me.

I used this string normalization technique I was ‘taught’ in college. It’s a neat little trick that I seem to use every chance I get. Pretty easy solution once you know you can map all permutations of a string to just one string!

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    String[] grid = new String[] { "OBIDAIBKR", "RKAULHISP", "SADIYANNO", "HEISAWHIA", "IRAKIBULS", "MFBINTRNO", "UTOYZIFAH", "LEBSYNUNE", "EMOTIONNAL" };

    String[] originalNames = new String[] { "RAKIBUL", "ANINDYA", "MOSHIUR", "SHIPLU", "KABIR", "SUNNY", "OBAIDA", "WASI" };

    String[] names = new String[originalNames.length];
    int[] count = new int[names.length];

    for (int i = 0; i &lt; names.length; i++) {
      names[i] = normalize(originalNames[i]);
    }

    // Check Horizontally
    for (int zz = 0; zz &lt; 9; zz++) {
      for (int i = 0; i &lt; 9; i++) {
        for (int j = i + 4; j &lt;= 9; j++) { //Shortest name is 4 characters so we are checking for sub-strings of at least that length. We could also have capped the sub-string to at most 7 characters based on the names provided.
          String substring = normalize(grid[zz].substring(i, j));
          for (int k = 0; k &lt; names.length; k++) {
            if (substring.equals(names[k])) {
              count[k]++;
            }
          }
        }
      }
    }

    // Check Vertically
    String[] grid2 = new String[grid.length];
    for (int j = 0; j &lt; 9; j++) {
      char[] tmp = new char[9];
      for (int i = 0; i &lt; 9; i++) {
        tmp[i] = grid[i].charAt(j);
      }
      grid2[j] = new String(tmp);
    }

    for (int zz = 0; zz &lt; 9; zz++) {
      for (int i = 0; i &lt; 9; i++) {
        for (int j = i + 4; j &lt;= 9; j++) {
          String substring = normalize(grid2[zz].substring(i, j));
          for (int k = 0; k &lt; names.length; k++) {
            if (substring.equals(names[k])) {
              count[k]++;
            }
          }
        }
      }
    }

    for (int i = 0; i &lt; count.length; i++) {
      if (count[i] == 2) {
        out.println(originalNames[i]);
      }
    }

    out.close();
    sc.close();
  }

  // Normalizes all strings
  private static String normalize(String word) {
    char[] list = word.toCharArray();
    Arrays.sort(list);
    return new String(list);
  }
}

Edit: Further explanation. I’ve also updated the code to avoid the IndexOutOfBounds exception I was strangely using a try-catch for.

Firstly let us cover the normalize function. As you can tell by the code, it takes a word, splits it into a character array, sorts the character array and then converts it back into a string. Let us take some examples so that this is clear.

Take a word, let’s say: apple once you run it through the normalize function it will become aelpp. The same will happen for all permutations of apple (I won’t list them all) for example aplpe, ppael, leapp, etc. This allows us to quickly check if a particular permutation of a word is in the grid.

If this part is clear then we can just move on to the checking part.

We will go through the grid one row at a time (the code with the comment stating horizontal). Find all substrings within that line, normalize them and then compare them with the names array. If they are in the array then we increment a counter (named count). We do the same thing for the grid vertically.

Factors

A naive way of figuring out the number of factors of a particular number is to try every number from 1 up to the number itself.

public ArrayList getFactors(int N) {
  ArrayList factors = new ArrayList();
  for (int i=0; i if (N%i==0) {
      factors.add(i);
  }
  return factors;
}

We can do much better than this by noticing that for every number i that is a factor of N; the number N/i is also a factor of N! This means that we can change out O(N) algorithm to O(sqrt(N)) which is much much faster.

F(x) vs F(sqrt(X))
O(N) algorithm vs O(sqrt(N)) algorithm
public ArrayList getFactors(int N) {
  ArrayList factors = new ArrayList();
  int sqrt = (int) Math.sqrt(N);
  for (int i=0; i if (N%i==0) {
    factors.add(i);
  }
  if (sqrt * sqrt == N) {
    factors.add(sqrt);
  }
  return factors;
}

Save this code somewhere, I guarantee it’ll come in handy!