All posts by Rawrosaur

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

Full width fluid Twenty Fourteen (2016)

So in case you are wondering how I modified the default Twenty Fourteen (as of 2016) theme all I did was add in the following custom CSS in the “Edit CSS” section under appearance.

.site, .site-header, .page-content, article header, .entry-header, .entry-content, .entry-summary, .entry-meta, .comments-area, nav.navigation.post-navigation {
max-width: inherit !important;
}

Updating Flash in Chrome

Sometimes no matter how much you try you just can’t get chrome to get rid of those annoying warning messages about your flash player version. I had a strange problem which I was able to debug by going to this url: chrome://flash/.

You’ll notice something like this in the begining:

Google Chrome 45.0.2454.85 (m)
OS Windows 7 or Server 2008 R2 SP1 64 bit
Flash plugin 18.0.0.232 C:\Windows\SysWOW64\Macromed\Flash\pepflashplayer32_18_0_0_232.dll
Flash plugin 18.0.0.232 C:\Program Files (x86)\Google\Chrome\Application\45.0.2454.85\PepperFlash\pepflashplayer.dll (not used)

If you see two Flash plugin lines then you’re in the same boat as me. I happen to have installed two versions of flash (and forgot about it). I have the regular version installed as well as the debug version. The regular version was up to date but the debug version was not. So that is why chrome was complaining all-along.

Solution

1. Update the debug version of Flash from here: http://www.adobe.com/support/flashplayer/debug_downloads.html
2. Disable the debug version of flash in chrome. Go to: chrome://plugins/ Click on details on the top right. Find the debug flash player and disable it.
3. Uninstall the debug version of Flash. Follow instructions here: https://helpx.adobe.com/flex/kb/uninstalling-flash-player-debugger.html

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