I remember this type of lexical analysis problem being in my compilers class. That said I have never used a stack in real coding but I can see various places where O(1) read/write to latest element can be useful. This problem from codility basically asks you to check if a String is properly nested.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

// you can also use imports, for example:
// import java.util.*;
import java.util.Stack;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
       Stack<Character> charStack = new Stack<Character>();
       
       for (int i=0; i < S.length(); i++)  {
           char c = S.charAt(i);
           if(c=='{')
                    charStack.push('{');
           else if(c=='[')
                    charStack.push('[');
           else if(c=='(')
                    charStack.push('(');
           else if(c=='}'){
               if(charStack.peek()=='{')
                    charStack.pop();
               else    
                    return 0;        
           }
           else if(c==']') {
               if(charStack.peek()=='[')
                    charStack.pop();
               else    
                    return 0; 
           }
           else if(c==')'){
                if(charStack.peek()=='(')
                    charStack.pop();
                else    
                    return 0; 
           }
           else {
            System.err.println("ERROR");
            return 0;
           }
       }
       
      return 1; 
    }
}

This problem can also be called find the missing number in the sequence. What is key to remember is the trick which is for any given sequence 1 to N, its value is given by (N(N+1))/2 . By that you can do all sorts of tricks because you know what the numbers should add up to. In this case if the numbers in the array do not match that formula then you know it is not a permutation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        int expectedTotal = N*(N+1)/2;
        int actualTotal = 0;
        for (int i : A) {
            actualTotal+=i;
        }
        
        if(actualTotal==expectedTotal)
            return 1;
        else
            return 0;
    }
}

I was not sure how to approach this one either until I took a look at the solutions discussion at leetcode and saw that people were calculating the depth. I actually had never seen recursion used in this way but it made sense since we can leverage what we already had by counting the depth of subtrees to determine if the trees were balanced. This solution seems fairly inefficient since for every node we have to calculate the depth of the subtree, there might be better ones out there on the forum.

1) If root is empty, tree is defintely balanced.

2) Calculate depth of current node left subtree and right subtree using

1
2
3

(Math.abs(depth(root.left) - depth(root.right)) > 1)

once you get this part it is downhill. If the tree is imbalanced return false. Otherwise recursively continue down the nodes left and right subtree with this

1
2
3

(isBalanced(root.left) && isBalanced(root.right))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        
        if(Math.abs(depth(root.left) - depth(root.right)) > 1)
            return false;
        else
            return (isBalanced(root.left) && isBalanced(root.right));
    }
    
    
    public int depth(TreeNode root) {
        if(root==null)
            return 0;
            
        if(root.left != null || root.right != null)
            return Math.max(depth(root.left),depth(root.right))+1;
        else
            return 1;
    }
}

One particular problem from leetcode asks you to find the maximum depth of a binary tree https://leetcode.com/problems/maximum-depth-of-binary-tree/ . Like linked list, I usually trace edge cases first when going through Binary Search Tree problems. Here are the edge cases I considered:

1) Case where BST is empty

This is simple just return 0 since there is no depth

2) Case where BST has one node or node is last element

If both node.left and node.right are empty that means this is the last node so the depth is (however many nodes it took to get here)+1.

3) Case where node has one or more children

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null) 
            return 0;
        
        if(root.left != null || root.right != null)
            return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
        else
            return 1;
    }
}

I struggled with Linked List problems before. I suppose the difficult for me with Linked List is that it is hard to conceptualize the edge cases. They really force you to slow down and check your assumptions about how your program is going to run. One thing I have done with Linked List is actually draw out the Linked List and follow program execution. Here is a problem from leetcode.com which asks you to write a function to remove all nodes with given value from a linked list given the head. The solution seems straight forward but there are edge cases to consider.

Edge case 1 you have a linked list that is null.
[]
In this case you can simply return the head you were given since there are no elements of the list to remove.

1
2
3
4
5

if (head==null) {
           return head;
       }

Edge case 2 you have one element and it is the value

In this case you can point head to the next element to delete the element, even if the next element is null. What if you had multiple elements that were the value we are searching for?

If this occurs then one solution is to turn the check into a loop until you get to a element that is either null or is not the value you are looking for.

becomes

and if the element was null we we get an empty list/null head. We can use the code below to take care of this.

1
2
3
4
5

while(head != null && head.val == val) {
            head=head.next;
        }

With those two edge cases taken care of we can now safely assume that the head value is not the value we are looking for and is not null. If it is the last element of the list then we can simply return the head. From here we can apply the standard pre/curr pointer idea to remove the matching values from the list. Psuedocode is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

pre = head;
curr = head.next;

while curr != null:
	if curr is value we are looking for
		point pre.next to curr.next to skip curr
		point curr to curr.next to check the next value
	else curr not value we are looking for
		advance pre to pre.next and curr to curr.next
done

return head;

We are basically looking one node ahead of our pre node because we need to know whether to route the previous node in the sequence say n to n+2 (the node containing the value being n+1 for example) thus skipping the value node. This was a problem covered in my undergrad lower divsion data structures class and I have also seen this in an interview. I think just getting familiarity with how to manipulate linked lists will help with this problem…personally I think this problem would be difficult if not prepared for in an interview since I would be willing to wager the vast majority of software devs probably do not deal with LinkedLists regularly. Here is the full code below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val) {
            head=head.next;
        }
        if (head==null) {
            return head;
        }
        
        ListNode preNode = head;
        ListNode currNode = head.next;
        while(currNode != null) {
            if(currNode.val==val) {
                preNode.next = currNode.next;
                currNode = currNode.next;
            }
            else {
                currNode = currNode.next;
                preNode = preNode.next;
            }
        }
        
        return head;
    }
}

Another fairly common problem. Main challenge that I see would be generating the random integer. I chose to do this in place, its possible to do it out of place too but in my opinion the in place solution is more natural to this sort of problem not to mention it has O(1) space complexity. My algorithm was:

for each element in array:
1) Generate the random index for the element that you will swap with the current element.
2) Save the current element index in a temp variable because we are going to ovewrite it with the element from the random index.
3) Copy the random element into the current element thus overwriting the value of the current element, however the value is saved in step 2.
4) Copy saved value of current element into the random element thus completing the swap of the current element and the random element.

return original array which was swapped in place.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import java.util.Random;


public class ArrayShuffleCalc {

	public int[] shuffleArray(int[] testArray) {
		Random randomInt = new Random();
		for(int i = 0; i < testArray.length; i++) {
			int tempIndex = randomInt.nextInt(testArray.length-1);
		    int tempInt = testArray[i];
		    testArray[i] = testArray[tempIndex];
		    testArray[tempIndex] = tempInt;
		}
		return testArray;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13

public class ArrayShuffleDriver {

	public static void main(String[] args) {
		int[] testIntArray = {1,2,3,4,5,6,7,8,9,10};
		
		ArrayShuffleCalc basicShuffle = new ArrayShuffleCalc();
		
		System.out.println(Arrays.toString(basicShuffle.shuffleArray((testIntArray))));
	}

}

This problem was originally supposed to be reverse the string in-place. However since I am using Java and Java strings are immutable this was not possible. If you were given a character array instead of a string in java you could reverse that character array in place. The approach I took below was to copy the String into the character array and then reverse it by using the standard reverse string algorithm of swapping array elements 0 and max, 1 and max-1…until floor(max/2). Not a hard problem but a common one asked in many interviews.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class ReverseStringCalc {
	public String reverseString(String testString) {
		char[] s = testString.toCharArray();
		for(int i = 0; i < Math.floor(s.length/2);i++) {
			if(((s.length-1)-i)==i){
				break;
			}
			char tempChar = s[i];
			s[i]=s[(s.length-1)-i];
			s[(s.length-1)-i] = tempChar;		
		}
		
		return new String(s);
	}
}

This problem basically asks you to check if a user has failed 10 times in a row to log into a system. If he has failed 10 times return true, if not return false. I thought this was a good problem because you had to read carefully to understand the edge cases. I kept getting the final 2 tests wrong before actually tracing the code and realizing that I was off by 1 when checking how many times a user has logged it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

boolean incorrectPasscodeAttempts(String passcode, String[] attempts) {
    if(attempts.length == 0) {
        return false;
    }
        
    int numAttempts = 0;
    boolean overTenFailures=false;
    for (String entry : attempts) {
        if (passcode.equals(entry)) {
           numAttempts = 0;
        }
        else if (numAttempts >= 9){
            overTenFailures=true;
            numAttempts++;
        }
        else{
            numAttempts++;
        }
    }
    
    return overTenFailures;
}