Archive for May, 2014

Nth Element of a BST


This question seems very straight forward on the surface but an efficient solution is tricky to implement in Java due to pass-by-value semantics. Read on to see why!


Given a BST of integer elements, return the nth element as quickly as possible. Counting starts at 1 (not 0).

Input (input.txt):


Output (stdout):



A very naive solution is to traverse through the entire tree in-order, adding each element to an ArrayList as you go, and returning the nth element of the resulting ArrayList. This solution is simple to implement but uses extra memory and has a wasteful run-time if n is small compared to the size of the tree (although the run-time can be improved via early termination).

A better idea is to perform the recursive in-order traversal on the tree nodes while keeping a global counter that we can modify across the recursion stack. (Note that we need to define a custom wrapper object for this counter to simulate pass-by-reference of primitive values.) As far as the search logic goes, we can terminate the search and return the result as soon as the counter is fully decremented from n to 0. One final trick: we need to use the Integer primitive wrapper so we can return a null value when the nth element is not found in a substree.

    public static void main (String [] args) throws IOException {
        Scanner in = new Scanner (new FileReader("src/input.txt"));
        int n = in.nextInt();
        BSTNode root = new BSTNode(in.nextInt());
        while(in.hasNext()) {
           root.insert(new BSTNode(in.nextInt()));
        System.out.println(findNthElement(root,new Counter(n)));

    static Integer findNthElement(BSTNode node, Counter counter) {
        //If we reached the end of subtree return null to indicate "not found in subtree"
        if(node==null )  {
            return null;
        //Traverse left subtree
        Integer result = findNthElement(node.left, counter);
        //Return result if found in left subtree
        if (result!=null) {
            return result;
        //In-order visit
        //Return node value if found
        if(counter.value == 0) { 
          return node.value;  
        //Traverse right subtree
        result = findNthElement(node.right, counter);
        return result;

    static class Counter {
        int value;
        public Counter(int value) {
            this.value = value;
    static class BSTNode {
        BSTNode left;
        BSTNode right;
        int value;

        public BSTNode(int value) {
            this.value = value;

        //Standard BST insertion algorithm
        public void insert(BSTNode node) {
            if(node.value<value) {
                if (left==null) {
                    left = node;
                } else {
            if(node.value>value) {
                if (right == null) {
                    right = node;
                } else {

A Simple Regex Matcher


This is a classic technical interview question which tests knowledge of string manipulation and recursion.


Given a regex expression and a string, return true if the regex matches the string. The rules:

  • Strings are composed of alphanumeric characters.
  • Regexes are composed of alphanumeric characters and 2 special characters ‘.’ and ‘*’.
  • A regex matches a string if every character in the regex matches every character in the string.
  • Two single characters match if they are equal.
  • The special character ‘.’ matches with any single character.
  • If the special character ‘*’ appears in the regex, then for our string we can match 0 or more contiguous occurrences of the character preceding the ‘*’. For example, “a*bc” matches “aaabc”.
  • For “.*”, we can match 0 or more contiguous occurrences of any character. For example, “.*bc” matches “xyzbc”.
  • A pair of quotes (“”) denotes an empty string.

Input (input.txt):

a a
abc abc
a.c axc
a*bc aaabc
a*bc bc
.*bc xyzbc
a*aa aaaa
aa aaa
aaa aa
a* “”

Output (stdout):



The basic idea is to attempt to match the start of the regex with the start of the string and recursively match the remaining regex against the remaining string.

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new FileReader("src/input.txt"));
        while (in.hasNextLine()) {
            String regex =;
            String string =;
            //Special handling of empty strings
            System.out.println(regexMatchesString(regex, string));

    static boolean regexMatchesString (String regex, String string) {
        if(regex.equals("") && string.equals("")) {
            //Base case when regex matches string.
            return true;
        } else if (regex.equals("")) {
            //Base case when string exceeds regex.
            return false;
        } else {
            //Attempt to match start of regex with start of string.
            if(regex.length()>1 && regex.charAt(1)=='*') {
                //Handle wild card:
                //a)Try ignoring wild card.
                boolean matched = regexMatchesString (regex.substring(2), string); 
                if (matched) {
                    return true;
                //b)Try consuming one or more matching characters.
                for (int i=0;i<string.length();i++) { 
                    if (matches(regex.charAt(0), string.charAt(i))) {
                        matched = regexMatchesString (regex.substring(2), string.substring(i+1));
                        if (matched) {
                            return true;
                    } else {
                        return false;
                //Remaining regex does not match remaining string.
                return false;
            } else if (string.equals("")) {
                //Base case when regex exceeds string.
                return false;
            } else if (matches(regex.charAt(0), string.charAt(0))) {
                //Try consuming a single character.
                return regexMatchesString (regex.substring(1), string.substring(1));
            } else {
                //Start of regex does not match start of string.
                return false;
    //Returns whether a single regex character matches a single string character.
    static boolean matches (char regexChar, char stringChar) {
        return regexChar == '.' || regexChar == stringChar;

The trickiest part of this solution is how the wildcard is handled – we must test all n+1 cases of consuming 0 to n matching characters with our wild card since it not necessarily the case that we want to consume all matching characters. (Ex. “a*ab” should match “aab” – the “a*” only consumes a single “a” in this case.)

Shortest Distance Between Two Nodes


What is the shortest distance from point A to point B?

If you’ve taken a CS 101 class in college, this problem should sound very familiar to you. Some of you may even remember that you can solve this problem using something called Dijkstra’s algorithm. You remember that the algorithm is not too hard, so you never bother giving it a second thought. Yet, when it comes time to implement the solution, particularly during a technical interview, you may find yourself at a complete loss as to where to even begin (much like trying to correctly spell “Dijkstra”).

This article presents a Java implementation of Dijkstra’s algorithm using breadth-first-search with a PriorityQueue. This is a very useful algorithm to keep in your arsenal. It is also a great starting place for interview prep since the solution touches upon some of the most fundamental CS concepts including:

  • Map (HashMap implementation)
  • PriorityQueue (Heap implementation)
  • Overriding equals and hashCode (when using a custom class in a Map)
  • Overriding compareTo (when using a custom class in a PriorityQueue)

Without further ado, here is the formal question statement:


Given a set of bi-directional, weighted edges of connected nodes in a graph, compute the shortest distance between a starting node and an ending node. The edge weights are non-negative.

Input (input.txt):

A B 2
B C 3
A D 5
B E 2
C F 1
D E 3
E F 6
D G 2
E H 1
F I 4
G H 8
H I 2

Output (stdout):



The solution presented below is an end-to-end solution and has three parts: processing the input, implementing Djkstra’s algorithm, and implementing supporting data structure.

1) Process input and construct graph.

The tricky part here is that the nodes can come in any order and must be correctly linked with previous nodes. Thus, a hashmap is needed in order to build the graph in O(n) time since we need to be able to perform look-up on exisiting nodes in O(1) time. Note that a Node data structure is all we need in order to represent our graph – the edges can be stored as a map of weights to adjacent Nodes within the Node data structure – this greatly simplifies our code.

    public static void main (String [] args) throws IOException{

        //Scanner is much more user-friendly than BufferedReader.
        Scanner in = new Scanner(new FileReader("src/input.txt"));

        //Obtain start and end nodes.
        String startLabel =;
        String endLabel =;

        //Construct bi-directional graph (potentially cyclic).
        Map<String,Node> graph = new HashMap<String,Node>();

            //Read edge.
            String labelA =;
            String labelB =;
            int weight = in.nextInt();
            Node nodeA;
            Node nodeB;

            //Retrieve or create nodeA.
            if (graph.keySet().contains(labelA)) {
            	nodeA = graph.get(labelA);
            } else {
            	nodeA = new Node(labelA);
            	graph.put(labelA, nodeA);

            //Retrieve or create nodeB.
            if (graph.keySet().contains(labelB)) {
            	nodeB = graph.get(labelB);
            } else {
            	nodeB = new Node(labelB);
            	graph.put(labelB, nodeB);

            //Add bi-drectional edges.
            //(A possible problem variant can use uni-directional edges.)

        //Invoke algorithm and print solution.


2) Implement Djkstra’s algorithm.

The crux of Djkstra’s algorithms lies in a simple loop invariant: Each time we “visit” a node, it is guranteed to possess the minimum distance from the starting node. We maintain this invariant by repeatedly minimizing our tentative distances to unvisited nodes AND always visiting the nodes closest to our starting node first. Under this strategy, it would be impossible to end up in a situation where a current node we visit does not possess the minimum distance from the starting node, since a hypothetical alternative path would necessarily include an intermediary node with a smaller minimum distance from the starting node, in which case we would have visited this intermediary node first and have shrinked our tentative distance to our current node to the minimum, a contradiction.

A common setup to this algorithm involves initializing the distance to the starting node to 0 and the distance to all other nodes to infinity. A priority queue is used to provide efficient access to the closest node at all times. (The Java PriorityQueue is a heap-based implementation that offers O(logn) insertion/removal time.)

    public static int solve(Map<String, Node> graph, String startLabel,
            String endLabel) {
        //toVisit queue contains nodes we can reach and visit.
        Queue<Node> toVisit = new PriorityQueue<Node>();

        //Determine start node.
        Node startNode = graph.get(startLabel);

        //Set distance to start node to 0.

        //Start our search at the start node.

        //While there are more nodes we can reach and visit...
        while (!toVisit.isEmpty()) {

            //Visit the closest node (Djkstras loop-invariant).
            Node currentNode = toVisit.poll();
            if(currentNode.isVisited()) {
                continue; //See Note A.

            //If we reached the end node, return its distance.
            //This must be the shortest distance to the end node.
            if (currentNode.getName().equals(endLabel)) {
                return currentNode.distance;

            //For each neighbor, compute the distance to reach the neighbor
            //through our currentNode, and update shortest distance as needed.
            for (Entry<Integer, Node> edge : currentNode.getEdges().entrySet()) {
                int weight = edge.getKey();
                Node neighbor = edge.getValue();

                //It is unnessary to check on neighbors we already visited
                if (!neighbor.isVisited()) {

                    //Compute new distance
                    int newDistance = currentNode.distance + weight;

                    //Update old distance if new distance is better
                    if (newDistance < neighbor.getDistance()) {
                        //Add neighbor to our toVisit priority queue with the new lower priority. See Note B.

        return -1; //No path to goal exists.

Note A: Since there can be multiple paths to the same node and we do not remove nodes from our PriorityQueue when we make the path update (for efficiency reasons), it is likely for our PriorityQueue to contain duplicate nodes. We should ignore the nodes we’ve already visited to avoid redundant traversals.

Note B: In light of the above, it is redundant to add a neighbor to our toVisit queue if it doesn’t have a better tentative distance since it will just be discarded when it’s dequeued (it will already have been visited by that time). Of course, since any distance is better than infinity, we will always add a “fresh” neighbor to our toVisit queue.


3) Implement supporting data structure.

The Node data structure contains the key fields that support the algorithm including name, distance, and a visited flag. The weighted edges to neighboring nodes are represented by a mapping of edge weights to nodes – this is simply a convenient construct - we are not actually using the map look-up capabilities.

    static class Node implements Comparable<Node> {
        //Always declare fields as private if possible
        private String name;
        private int distance; //distance from starting node.
        private Map<Integer, Node> edges;
        private boolean visited;

        //Each node has a unique name
        public Node(String name) {
   = name;
            //Our algorithm requires distance to be initialized to infinity
            distance = Integer.MAX_VALUE; 
            edges = new HashMap<Integer, Node>();
            visited = false;

        //Add an edge to a neighboring node with the specified weight.
        public void addEdge(Node node, int weight) {
            edges.put(weight, node);

        //equals and hashCode must be overridden for usage in HashMap.
        //We use "name" as our key for this problem.
        public boolean equals(Object obj) {
            if (obj == null)
                return false;
            if (obj == this)
                return true;
            if (!(obj instanceof Node))
                return false;

            Node other = (Node) obj;
            return this.getName() == other.getName();

        public int hashCode() {
            return name.hashCode();

        //compareTo must be overridden for usage in PriorityQueue.
        //We use "distance" as our comparison value for this problem.
        public int compareTo(Node other) {
            if (other == null) {
                return -1;
            if (this.getDistance() == other.getDistance()) {
                return 0;
            return this.getDistance() > other.getDistance() ? 1 : -1;

        //Boiler-plate getter/setters
        public String getName() {
            return name;

        public int getDistance() {
            return distance;

        public void setDistance(int distance) {
            this.distance = distance;

        public Map<Integer, Node> getEdges() {
            return edges;

        public void setVisited(boolean visited) {
            this.visited = visited;

        public boolean isVisited() {
            return visited;


Additional Notes:

  • The runtime of this algorithm is O(m * log(n)) time where n is the number of vertices (a.k.a. nodes) and m is the number of edges in the graph.
  • This algorithm does not support negative edge weights since negative edge weights will break the loop-invariant.
  • If all the edge weights are 1, then this algorithm reduces to a plain breadth-first-search. In this scenario, using a FIFO queue will give us an O(m) solution.

Pausing a Sprite Kit Game, Correctly


When I first added a pause button to my SKScene, I wrote just a single line of code to toggle the pause-state of my scene:

self.paused=!self.paused; //If you think you can get away with this, you are in for a treat, my friend.

While this method “works” to some extent (it correctly pauses/unpauses the physics simulation), it doesn’t address any of the nuances associated with pausing a Sprite Kit game, many of which will lead to spectacular crashes when improperly handled. In order to pause the game in a bullet-proof manner, you should follow these steps:


1) Create dedicated selectors for pausing and unpausing the SKScene.

Link these selectors to the in-game pause button as usual. Note that it is very important to declare a separate “isGamePaused” flag as opposed to relying on SKScene’s self.paused  - there are corner-cases where self.paused is not congruent with the game’s actual pause-state.

-(void)pauseGame {
    _isGamePaused = YES; //Set pause flag to true
    self.paused = YES; //Pause scene and physics simulation
    if (_bgMusicOn) { //Pause background music if bg music setting is ON
        [_bgMusicPlayer pause];
    //Display pause screen etc.
-(void)unpauseGame {
    _isGamePaused = NO; //Set pause flag to false
    self.paused = NO; //Resume scene and physics simulation
    if (_bgMusicOn) { //Resume background music if bg music setting is ON
        [_bgMusicPlayer play]; 
    //Hide pause screen etc.

Note: This tutorial uses the traditional game design style where pausing the game also pauses the background music.


2) Register the SKScene as an observer for important app transitions.

We will handle each event appropriately in the steps to follow.

-(void)registerAppTransitionObservers {

[[NSNotificationCenter defaultCenter] addObserver:self

[[NSNotificationCenter defaultCenter] addObserver:self

[[NSNotificationCenter defaultCenter] addObserver:self


Note: You have the option to handle these events from the AppDelegate, but I think it makes more sense to let the SKScene manage its own resources instead of going through a middleman.


3) Handle the applicationWillResignActive event.

This event occurs when the home button is pressed once (bringing up the device home screen) OR when the home button is double-tapped (bringing up the task-switch screen). In either case, the correct behavior should be to pause the game, if it’s not already paused by the user. Nothing fancy so far.

-(void)applicationWillResignActive {
    if (!_isGamePaused) { //Pause the game if necessary
        [self pauseGame];

Note: If the user immediately returns to the game from the task-switch screen, the game will never have gone into the background state. The user should be returned to a paused state AS IF they clicked on the in-game pause button. This is a good consistency to have.


3) Handle the applicationDidEnterBackground event.

This event occurs when the home button is pressed once (bringing up the device home screen) OR when the user switches tasks. Note that if this event occurs, it will ALWAYS come after the applicationWillResignActive event. In either case, we will need to handle three “gotchas” associated with putting the game into a background state:

-(void)applicationDidEnterBackground {
    [_bgMusicPlayer stop]; //A.
    [[AVAudioSession sharedInstance] setActive:NO error:nil]; //B.
    self.view.paused = YES; //C.

A. Quirky iOS behavior does not honor music player “pause” when putting the game into the background. It tries to be a “smart-ass”, fading out the music when the app resigns and fading in the music when the app resumes. The only way to prevent this from happening is to forcefully “stop” the music when the game goes into the background. Otherwise, your background music will resume playing automatically when you return to the game even though the game itself is still in the paused state!

B. AVAudioSession must be turned off when your app is in the background or an EXC_BAD_ACCESS exception will be thrown. There are forums that claim this operation may not always be successful, so they wrap it inside an unbounded while-loop with infinite retries. I have yet to encounter such a problem, but if you insist on adding retry logic, at least have the decency to bound the number of your attempts.

C. The SKView containing your scene must be paused when your game goes into the background or an EXC_BAD_ACCESS exception will be thrown. I believe this is a bug on Apple’s part. There are forums that claim this problem can be avoided if you make your game using storyboard, but I don’t buy that crap.


4) Handle the applicationWillEnterForeground event.

This event occurs when the game is first launched OR when the game is relaunched (either from the home screen or the task-switch screen). We should reverse the steps taken by applicationDidEnterBackground (but keep in mind that applicationDidEnterBackground may not have happened).

-(void)applicationWillEnterForeground {
    self.view.paused = NO; //Unpause SKView. This is safe to call even if the view is not paused.
    if (_isGamePaused) { //See note.
        self.paused = YES;
    [[AVAudioSession sharedInstance] setActive:YES error:nil]; //This is technically optional, but included to preserve symmetry.

Note: Due to a questionable design choice, unpausing the view automatically unpauses the scene (and the physics simulation). Therefore, we must manually pause the scene again, if the game is supposed to be in a paused state.


And there you have it! Feel free to test your game to your heart’s content to convince yourself that this is indeed a bullet-proof solution~

Go to Top