Length of Last Word

Problem: Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = “Hello World”,
return 5.

Analysis:

There are two ways to solve the problem. First one is using the Java built in String method split. Quite a cheating way to do it.

public class Solution {
    public int lengthOfLastWord(String s) {
        String[] S = s.split(" ");
        if (S.length == 0) return 0;
        else return S[S.length-1].length();
    }
}

Second way is to use a counter like a ‘normal person’.

public class Solution {
    public int lengthOfLastWord(String s) {
        if (s == null || s.length() == 0 || (s.length() == 1 && s.charAt(0) == ' ')) return 0;
        
        int right = s.length() - 1;
        int len = 0;
        
        while (right >= 0 && s.charAt(right) == ' ') {
            right --;
        }
        
        while (right >= 0 && s.charAt(right) != ' ') {
            len++;
            right--;
        }
        
        return len;
    }
}

Container With Most Water

Problem:
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Analysis:

This question was confusing, be sure to make sure what kind of container, I thought only neighbor lines can be part of the container so I ‘solved’ it with just one line.

It is easily to come up with a O(n^2) solution, however there are a lot of cases we counted twice.

public class Solution {
    public int maxArea(int[] height) {
        int left = 0; 
        int right = height.length-1;
        
        int result = 0;
        
        while (left < right) {
            result = Math.max(((right-left)*Math.min(height[left], height[right])), result);
            if (height[left] < height[right]) left++;
            else right--;
        }
        
        return result;
    }
}

Unique Paths

Problem:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Thinking:

This problem is actually an example when we are having the Algorithm course, when introducing DP (Well of course the not the first example because the first example is always Fibonacci Numbers.)

 

 

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] table= new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            table[i][1] = 1;
        }
        
        for (int i = 1; i <= n; i++) {
            table[1][i] = 1;
        }
        
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                table[i][j] = table[i-1][j] + table[i][j-1];
            }
        }
        
        return table[m][n];
    }
}

Maximum Subarray *****

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Thinking: Using DP, there is a pattern that for subarray 0-i, the maximum subarray is the maximum in this subarray. Therefore we need to keep one max that keeps track on what is the first maximum subarray so far.

public class Solution {
    public int maxSubArray(int[] A) {
        if (A.length == 0) return 0;
        
        int max = A[0];
        int sum = 0;
        
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            max = Math.max(max, sum);
            sum = Math.max(0, sum);
        }
        
        return max;
    }
}

Linked List Cycle

Problem:
Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Thinking: Using fast & slow runner method. If one leap forward two steps per time, and one leap forward one step per time. If there is a cycle, then the fast runner will catch the slow one at some point.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        
        ListNode fast = head.next;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            if (fast == slow) return true;
            fast = fast.next.next;
            slow = slow.next;
        }
        
        return false;
    }
}

Merge Two Sorted Lists

Problem: Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        ListNode dummy = new ListNode(0);
        ListNode pointer = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                pointer.next = l1;
                l1 = l1.next;
                pointer = pointer.next;
            } else {
                pointer.next = l2;
                l2 = l2.next;
                pointer = pointer.next;
            }
        }
        
        if (l1 == null && l2 != null) {
            while (l2 != null) {
                pointer.next = l2;
                l2 = l2.next;
                pointer = pointer.next;
            }
        }
        
        if (l2 == null && l1 != null) {
            while (l1 != null) {
                pointer.next = l1;
                l1 = l1.next;
                pointer = pointer.next;
            }
        }
        
        return dummy.next;
    }
}

Plus One

Problem: Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

public class Solution {
    public int[] plusOne(int[] digits) {
        if (digits.length == 0) return digits;
        
        int toAdd = 1;
        
        for (int i = digits.length-1; i >= 0; i--) {
            if (digits[i] + toAdd > 9) {
                toAdd = 1;
                digits[i] = 0;
            }else{
                digits[i] += toAdd;
                toAdd = 0;
                break;
            }
        }
        
        if (digits[0] == 0) {
            int[] temp = new int[digits.length + 1];
            temp[0] = 1;
            for (int i = 0; i < digits.length; i++) {
                temp[i+1] = digits[i];
            }
            digits = temp;
        }
        
        return digits;
    }
}

Remove Element

Problem: Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Thinking: We are only moving elements to the left, everywhere in between left and right pointers does not matter anymore because we will ignore them anyway.

public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A.length == 0) return 0;
        int position = 0;
        for (int i = 0; i < A.length; i++) {
            A[position++] = A[i];
            if (A[i] == elem) position--;
        }
        return position;
    }
}

Valid Parentheses

Problem:  Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Thinking:

Assumption: {[()]}() is valid.

Since there are only brackets in the string, we can easily make assumption that if the length of the string is not an even number, there must be a lonely parenthesis that is not valid.

Look at the pattern, if we have one opening bracket, then if it is valid, there must be a closing bracket. And if it is valid, the closing bracket is gonna be checked after everything is checked in this corresponding bracket. Therefore it is a FIFO behavior, because we’re always checking the closest correspondence. Therefore using a stack to check which one is nearest is ideal. At the end, we just need to check if there is anything left in the stack.

 

 

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() ==0) return true;
        if (s.length() % 2 != 0) return false;
        
        Stack stack = new Stack();
        Map map = new HashMap();
        
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
        
        for (int i = 0; i < s.length(); i++) {
            char current = s.charAt(i);
            Character correspondence = map.get(current);
            if (!stack.empty() && current == stack.peek()) {
                stack.pop();
            } else if (correspondence != null) {
                stack.push(correspondence);
            } else {
                return false;
            }
        }
        
        return stack.empty();
        
        
    }
}

HashMap vs. HashTable

When come to a time you need to choose from HashMap and HashTable, here is the differences.

1. HashMap is faster in single thread environment because it is not thread safe. On the other hand HashTable is thread safe, but performs slower than HashMap in single thread environment. Therefore for technical questions sake, mostly it is wise to choose HashMap.

2. HashMap allows null values whereas HashTable does not. Therefore if want to use a HashMap to check if a key has a correspondence, it will simply return null if there is no such correspondence.

3. “The third significant difference between HashMap vs HashTable is that Iterator in the HashMap is a fail-fast iterator while the enumerator for the HashTable is not and throw ConcurrentModificationException if any other Thread modifies the map structurally by adding or removing any element except Iterator’s own remove() method. ” – quote from MANISH CHHABRA’s blog. Therefore if in the case wanting to predict iteration order, HashMap can be swapped by one of its subclass LinkedHashMap.

Basically, unless synchronization is a issue, normally HashMap is a wiser choice.