Reconstruct Itinerary

I didn't think of using DFS approach at first and use a map instead. So I stuck when it reaches the end of the itinerary but the map is yet empty. Then I searched online for a while and realize it is a DFS problem, all I need to add with my first approach is to use a Stack. Later I use recursion again, and the first one is actually neater.

Iteration:

public List<string> findItinerary(String[][] tickets) {
        List<string> rst = new ArrayList<>();
        if (tickets == null || tickets.length == 0)
            return rst;
        Map<string, priorityqueue<string>> map = new HashMap<>();
        for (String[] ticket : tickets) {
            String from = ticket[0];
            if (!map.containsKey(from)) {
                map.put(from, new PriorityQueue<>());
            }
            map.get(from).add(ticket[1]);
        }
        Stack<string> temp = new Stack();
        temp.add("JFK");
        while (!temp.isEmpty()) {
            String from = temp.peek();
            if (map.containsKey(from) && map.get(from).size() > 0)
                temp.push(map.get(from).poll());
            else
                rst.add(temp.pop());
            }
        Collections.reverse(rst);
        return rst;
    }

Recursion:

public List findItinerary(String[][] tickets) {
        List<string> itinerary = new ArrayList<>();
        if (tickets == null || tickets.length == 0)
            return itinerary;
        Map<string, priorityqueue<string>> destinations = new HashMap<>();
        for (String[] ticket : tickets) {
            if (!destinations.containsKey(ticket[0]))
                destinations.put(ticket[0], new PriorityQueue<>());
            destinations.get(ticket[0]).offer(ticket[1]);
        }
        findItinerary("JFK", destinations, itinerary);
        Collections.reverse(itinerary);
        return itinerary;
        
    }
    private void findItinerary(String from, Map<string, priorityqueue<string>> destinations, List<string> itinerary) {
        if (!destinations.containsKey(from) || destinations.get(from).size() == 0) {
            itinerary.add(from);
            return;
        }
        PriorityQueue<string> curr = destinations.get(from);
        while (!curr.isEmpty()) {
            String to = curr.poll();
            findItinerary(to, destinations, itinerary);
        }
        itinerary.add(from);
    }

Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

Initialize x1 and x2 to max value. Traverse the array, if num is less than x1, set x1 to num. Else if x1 < num < x2, set x2 to num. Else if num > x2, return true. The idea is to keep a sequence of triplet, and reduce the differences among the three numbers until find a solution.

public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3)
            return false;
        int x1 = Integer.MAX_VALUE, x2 = Integer.MAX_VALUE;
        for(int num : nums) {
            if (num < x1)
                x1 = num;
            else if (x1 < num && num < x2)
                x2 = num;
            else if (num > x2)
                return true;
        }
        return false;
    }

The second solution is also an accepted one, but it's too complicated and requires extra space.

public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3)
            return false;
        TreeMap<Integer, List<Integer>> map = new TreeMap<>();
        map.put(nums[0], new ArrayList<>());
        for (int i = 1; i < nums.length; i++){
            int num = nums[i];
            if (map.floorKey(num) != null) {
                for (Integer key : map.headMap(num).keySet()){
                    if (key == num)
                        continue;
                    List<Integer> values = map.get(key);
                    if (values.size() > 0 && num <= values.get(0))
                        values.clear();
                    values.add(num);
                    if (values.size() == 2)
                        return true;
                }

            }
            if (!map.containsKey(num))
                map.put(num, new ArrayList<>());
        }
        return false;
    }

Self Crossing

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south,x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Example 1:

Given x = [2, 1, 1, 2],
┌───┐
│   │
└───┼──>
    │

Return true (self crossing)

Example 2:

Given x = [1, 2, 3, 4],
┌──────┐
│      │
│
│
└────────────>

Return false (not self crossing)

Example 3:

Given x = [1, 1, 1, 1],
┌───┐
│   │
└───┼>

Return true (self crossing)

I think this problem is quite "hard" to me. There are only three situations when the path will not cross itself:

1. The number keeps increasing (which will form an growing spiral).
2. The number keeps decreasing (which will form an shrinking spiral).
3. The number increases first, then decreases, and never increases again.   

The harder part is to implement all three situations. Since our program should be one pass, we should check if the number keeps increasing (or decreasing), or if it changes its trend.

public boolean isSelfCrossing(int[] x) {
        if (x == null || x.length < 4)
            return false;
        int length = x.length;
        int t1 = 0, t2 = x[0], t3 = x[1], t4 = x[2], t5;
        boolean isIncrease = (t4 > t2);
        for (int i = 3; i < length; i++) {
            t5 = x[i];
            if (isIncrease && (t3 >= t5)) {
                //condition 1
                if ((t1 + t5) < t3 || ((i < length - 1) && x[i + 1] + t2 < t4))
                    isIncrease = false;
                //condition 2
                else if (i < length - 1)
                    return true;
            // condition 3
            } else if (!isIncrease && (t3 <= t5))
                return true;
            t1 = t2;
            t2 = t3;
            t3 = t4;
            t4 = t5;
        }
        return false;
    }

Palindrome Pairs

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]

Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

This one doesn't look like a hard one: the easiest way is to go through the whole array and find the solution. Yet it definitely will exceed time limit. A smarter way is first to use a map and store all the words and their positions. Then go through the list and find the following pattern:

1. If the word is palindrome, find if there is empty string exists.

2. Find if the reverse word exists in the list. 

3. For each word, traverse through the word and separate them to two parts: if one of the two parts is palindrome, find if there exists the reverse word of the other part. 

4. Make sure the position of the words are different. 

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> rst = new ArrayList<>();
        if (words == null || words.length == 0)
            return rst;
        Map<String, Integer> positions = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            positions.put(words[i], i);
        }
        for (int i = 0; i < words.length; i++) {
            String s = words[i];
            String rs = reverse(s);
            if (isPalindrome(s, "") && positions.containsKey("")) {
                int pos = positions.get("");
                if (pos != i) {
                    addToList(rst, i, pos);
                    addToList(rst, pos, i);
                }
                
            }
                
            if (positions.containsKey(rs) && positions.get(rs) != i) {
                int pos = positions.get(rs);
                addToList(rst, i, pos);
            }
                
            for (int j = 1; j < s.length(); j++) {
                String left = s.substring(0, j);
                String right = s.substring(j, s.length());
                String r_left = reverse(left);
                String r_right = reverse(right);
                if (isPalindrome(left, "") && positions.containsKey(r_right))
                    addToList(rst, positions.get(r_right),i);
                if (isPalindrome(right, "") && positions.containsKey(r_left))
                    addToList(rst, i, positions.get(r_left));
                    
            }
        }
        return rst;
    }
    
    private void addToList(List<List<Integer>> rst, int first, int second) {
        List<Integer> curr = new ArrayList<Integer>();
        curr.add(first);
        curr.add(second);
        rst.add(curr);
    }
    
    private boolean isPalindrome(String a, String b) {
        String ab = a + b;
        int start = 0;
        int end = ab.length() - 1;
        while (start < end) {
            if (ab.charAt(start) != ab.charAt(end))
                return false;
            start++;
            end--;
        }
        return true;
    }
    
    private String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

House Robber I, II and III

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

The first one is just a simple DP problem.

public int rob(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int len = nums.length;
        if (len == 1)
            return nums[0];
        int[] sum = new int[len];
        sum[0] = nums[0];
        sum[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < len; i++) {
            sum[i] = Math.max(sum[i - 1], sum[i - 2] + nums[i]);
        }
        return sum[len - 1];
    }

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

The second one, now the first house is connected with the last house, which means one of the house cannot be robbed. Then we can find the max money we can get if we rob nums[0] to nums[len - 2] and that we can get if nums[1] to nums[len - 1] are robbed.

public int rob(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int len = nums.length;
        if (len == 1)
            return nums[0];
        int[] sum = new int[len];
        sum[0] = nums[0];
        sum[1] = Math.max(nums[0], nums[1]);
        return Math.max(max(nums, 0, len - 2), max(nums, 1, len - 1));
     }
     private int max(int[] nums, int start, int end) {
         if (start == end)
            return nums[start];
         int len = end - start + 1;
         int[] sum = new int[len];
         sum[0] = nums[start];
         sum[1] = Math.max(nums[start], nums[start + 1]);
         for (int i = 2; i < len; i++) {
             sum[i] = Math.max(sum[i - 1], sum[i - 2] + nums[start + i]);
         }
         return sum[len - 1];
     }

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

     3
    / \
   2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

The third one is a tree like structure. Consider a tree of two level, either the two leaves are robbed, or the root is robbed. Then we can recursively find the max money of robbing two leaves or root + leaves children.

public int rob(TreeNode root) { 
        return robHelper(root)[0];
        
    }
    
    private int[] robHelper(TreeNode root) {
        int[]sum = {0, 0};
        if (root == null) {
            return sum;
        }
        int[]sum_left = robHelper(root.left);
        int[]sum_right = robHelper(root.right);
        sum[1] = sum_left[0] + sum_right[0];
        sum[0] = Math.max(sum[1], sum_left[1] + sum_right[1] + root.val);
        return sum;
    }

Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

• It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

This is a DP problem. The first two numbers, 0 and 1, have 0 and 1 bits. From then on, each time we hit a number that is a power of 2, we have one more carries, but all other digits are repeated again from the very beginning.

    0        1

    0        1

                     10     11

                       1       2

100    101   110   111

    1        2       2       3

public int[] countBits(int num) {
        int[] bits = new int[num + 1];
        if (num < 0)
            return bits;
        bits[0] = 0;
        if (num == 0)
            return bits;
        bits[1] = 1;
        int index = 0;
        for (int i = 2; i <= num; i++) {
            if (isPowerOfTwo(i))
                index = 0;
            bits[i] = 1 + bits[index++];
        }
        return bits;
    }
    
    private boolean isPowerOfTwo(int num) {
        return (num & (num - 1)) == 0;
    }

Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

if n <= 1, equally divid the number by 2.
else
   if n % 3 == 0, return the product of all 3s.
   else if n % 3 == 1, return product of (n / 3 - 1) of 3s and two 2s.
   else, return the product of all 3s and one 2.

public int integerBreak(int n) {
        if (n / 3 <= 1) 
            return (n / 2) * (n - n / 2);
        if (n % 3 == 0)
            return (int)Math.pow(3, n / 3);
        else if (n % 3 == 1) {
            int p = n / 3;
            int remd = n - (p - 1) * 3;
            return remd * (int)Math.pow(3, p - 1);
        } else 
            return (int)Math.pow(3, n / 3) * 2;
    }