[LeetCode] Minimum Path Sum

Problem:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Solution:
Generally, dynamic programming is applicable to problems exhibiting the properties of overlapping subproblems, and optimal substructure.
For this kind of maximum/minimum problem(also for yes/no, count all possible solutions problems) , when the array cannot be sort or swapped, the solution should be dynamic programming. 

Attention:
Tried to solve the problem by recursion, but failed. Then, tried to use the for-loop, but tried to initialize the two dimensional array form the end to the start, which made it a little bit wired and hard to think.

Code:

public class Solution {
    public int minPathSum(int[][] grid) {
        //state: s[i][j] is minimum path sum from (0,0) to (i,j)
        //function: s[i][j] = min(s[i - 1][j], s[i][j - 1]) + cost[i][j]
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int[][] s = new int[grid.length][grid[0].length];
        s[0][0] = grid[0][0];
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                if (i - 1 < 0) {
                    s[i][j] = s[i][j - 1] + grid[i][j];
                    continue;
                }
                if (j - 1 < 0) {
                    s[i][j] = s[i - 1][j] + grid[i][j];
                    continue;
                }
                s[i][j] = Math.min(s[i - 1][j], s[i][j - 1]) + grid[i][j];
            }
        }
        
        return s[grid.length - 1][grid[0].length - 1];
    }
}

面试时可以问面试官的问题

Source:

https://docs.google.com/document/d/13vY5KA0teLBxlId6l81T4SRxBZ56CvOebtG8QnbFvlQ/edit

闲来没事可以问的问题：

Question to HR:

• How would you describe the company culture?
• What type of employees tend to excel at this company?
• Can you tell me more about the interview process?
• How would you describe the work environment here—collaborative or independent?

Hiring Manager: Your Future Boss

• What is the ideal candidate?
• What are some challenges one might face in this position?
• What are the most important skillset for the job?
• What are the backgrounds of people in the team?
• What's a typical career path at the company for someone in this role?
• If I am luck enough to get the job, what preparation would you suggest me do?
• Learning/training opportunities

 The Executive or high level expert

• How do you think this industry will change in the next five years?
• What do you think is the competitive advantage of our company?
• What's the company's biggest challenge? How is it planning to meet that challenge?

The Coworker

• Could you please describe a typical day?
• How would you describe the work environment at the company?
• Share something about your background.

 

普适的问题：

• What do you particularly like about the company?
• What do you dislike about the company if there is any?
• Could you tell me something about the projects that you are working on? The size of the team. The language the team is adopting?

以上的问题比较普适，不过最好还是能够在面试前去linkedin上搜搜相关信息，如果能对他正在做的东西进行提问会更让对方感到你是对这个position是特别感兴趣且上心的。

千万别问的问题！！：

1. 除了HR之外，不要讨论薪水的问题。

2. 别问我面试面的怎么样，结果怎么样。

[LeetCode] LRU Cache

Problem:

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution:

Cache should achieve the O(1) time complexity of get and set operation.

(1) To achieve the O(1) time complexity of look up operation, HashMap should be used to store the mapping relation between key and value(Node, in this solution).

(2) To achieve the O(1) time complexity of the invalidation operation of the least recently used item, double linked listed should be used. Every time, when there is a get operation, the accessed item will be moved to the head of the linked list. And the tail of the least recently used element of the cache.

Therefore, HashMap and Linked List should be used in this solution.

Code:

public class LRUCache {
    
    private int capacity;
    
    private Node head;
    private Node tail;
    
    private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
    
    private class Node {
        public int key;
        public int value;
        public Node pre;
        public Node next;
        
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        
        head.next = tail;
        head.pre = null;
        tail.pre = head;
        tail.next = null;
    }
    
    public int get(int key) {
        if (!hs.containsKey(key)) {
            return -1;
        }
        
        Node n = hs.get(key);
        n.pre.next = n.next;
        n.next.pre = n.pre;
        
        n.next = head.next;
        head.next = n;
        n.pre = head;
        n.next.pre = n;
        
        return n.value;
        
    }
    
    public void set(int key, int value) {
// Attention, made a mistake here, did not consider if the key already exist in hs.
        if (hs.containsKey(key)) {
            Node n = hs.get(key);
            n.pre.next = n.next;
            n.next.pre = n.pre;
            hs.remove(key);
            capacity++;
        }
        
        if (capacity <= 0) {
            Node n = tail.pre;
            n.pre.next = n.next;
            n.next.pre = n.pre;
            hs.remove(n.key);
            
            capacity++;
        }
        
        Node temp = new Node(key, value);
        temp.next = head.next;
        head.next = temp;
        temp.pre = head;
        temp.next.pre = temp;
        
        hs.put(key, temp);
        
        capacity--;
        
        
    }
}

[LeetCode] Max Points on a line

Problem:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution:

Assume there are two lines, line AB and AC.
AB and AC start from the same point A, then, if the slope of the two lines are equal, point A, B and C are on a line.
So, for each point A, calculate the slope of lines starts from A and connected to all other points in the points array. Store the slopes into HashMap.

Attention:

1) Duplicate points
For each point A in the array, when calculating the slope, if the value of A is equal to another point B, then the slope will not be calculated, and a variable "dup" will be used to store the number of duplicated points.
2) When the line is parallel to x-axis
Slope k = (y2 - y1) / (x2 - x1), and when x2 - x1 == 0 ( the line is parallel to x-axis )
The slope of the line will be infinity, and in Java, if a double is divided by zero, there will be an ArithmeticException, the program will blow up.
To fix it, assume the slope of lines parallel to x-axis is Integer.MIN_VALUE\
3) Double has two zeros, -0.0 and 0.0
Therefore, when calculating the slope, it should be like that:
slope = 0.0 + (double) (points[i].y - points[j].y) / (points[i].x - points[j].x);

Code:

/**
 * Definition for a point. class Point { int x; int y; Point() { x = 0; y = 0; }
 * Point(int a, int b) { x = a; y = b; } }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        // Map<Integer,String> map = new HashMap<Integer,String>();
        if (points == null || points.length < 1)
            return 0;
        else if (points.length == 1)
            return 1;

        Map<Double, Integer> map = new HashMap<Double, Integer>();
        int length = points.length;

        int max = 1;

        for (int i = 0; i < length; i++) {
            int dup = 0;
            map.clear();

            // Input: [(0,0),(0,0)]
            // Output: 1
            // Expected: 2

            // maybe all points contained in the list are same points,and same
            // points' k is
            // represented by Integer.MIN_VALUE
            map.put((double) Integer.MIN_VALUE, 1);

            for (int j = i + 1; j < length; j++) {
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    dup++;
                    continue;
                }

                // Zero and minus zero issue
                // Input: [(2,3),(3,3),(-5,3)]
                // Output: 2
                // Expected: 3
                double slope = (double) Integer.MIN_VALUE;
                if (points[i].x != points[j].x) {
                    slope = 0.0 + (double) (points[i].y - points[j].y)
                            / (points[i].x - points[j].x);
                }

                if (map.containsKey(slope)) {
                    map.put(slope, map.get(slope) + 1);
                } else {
                    map.put(slope, 2);
                }

            }

            for (int temp : map.values()) {
                max = temp + dup > max ? temp + dup : max;
            }
        }

        return max;
    }

}

[LeetCode] Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
_____________________________________________________________________

1. About Reverse Polish Notation
Searched Wikipedia, and find it. Just remember the example below.
Polish Notation (Prefix Notation): + 3 4
Infix Notation: 3 + 4
Reverse Polish Notation (Postfix Notation): 3 4 +

2. Solutions
Traverse the String array token. if the string is a number, push it to stack. if it is an operator, pop 2 elements from the stack and take this two elements as operand, and push the result of the operation into stack. In the end, pop the result from stack and return.
2.1 My solution

Accepted

Time Complexity: O(n)
Space Complexity: O(n)
___________________code___________________
public class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens == null) {
            return 0;
        }
       
        Stack s = new Stack();
       
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].equals("+")) {
                int a = (int)s.pop();
                int b = (int)s.pop();
                s.push(b + a);
            } else if (tokens[i].equals("-")) {
                int a = (int)s.pop();
                int b = (int)s.pop();
                s.push(b - a);
            } else if (tokens[i].equals("*")) {
                int a = (int)s.pop();
                int b = (int)s.pop();
                s.push(b * a);
            } else if (tokens[i].equals("/")) {
                int a = (int)s.pop();
                int b = (int)s.pop();
                s.push(b / a);
            } else {
                s.push(Integer.parseInt(tokens[i]));
            }
        }
       
        int result = (int)s.pop();
        return result;
    }
}
___________________code___________________

2.2 Mistake Made
Used  token[i] == "/", which is grammatically correct but cannot really work.
Should use token[i].equals("/")  here.

2.3 Better solution
They used operations.contains(token), which I think is better.
http://answer.ninechapter.com/solutions/evaluate-reverse-polish-notation/

[Leetcode] Maximum Product Subarray

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

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution 1:(Brute-Force approach)
s[i][j] represents the product of A.subarray(i,j). Initialize s, and update the value of max product each time. Then, after proceeding the nested for loop, return the max product.
However, this solution is Time Limit Exceeded
Time Complexity: O(n * n)
Space Complexity: O(n * n)
------------------code------------------
public class Solution {
    public int maxProduct(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        } else if (A.length == 1) {
            return A[0];
        }
     
        int length = A.length;
        int [][] s = new int[length][length];
        int maxProduct = Integer.MIN_VALUE;
     
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (i >= j)
                    ;
                else if (i == j - 1)
                    s[i][j] = A[i] * A[j];
                else
                    s[i][j] = s[i][j - 1] * A[j];
                 
                if (maxProduct < s[i][j])
                    maxProduct = s[i][j];
            }
        }
     
        return maxProduct;
    }
}
------------------code------------------
Solution 2:
sMin[i] The min product subarray end with the index i.
sMax[i] The max product subarray end with the index i.
sMin[i] = The minimum of the three values: sMin[i - 1] * A[i], sMax[i - 1] * A[i], A[i]
sMin[i] = The maximum of the three values: sMin[i - 1] * A[i], sMax[i - 1] * A[i], A[i]

Accepted

Time Complexity: O(n)

Space Complexity: O(n)

------------------code------------------
public class Solution {
    public int maxProduct(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        } else if (A.length == 1) {
            return A[0];
        }
     
        int length = A.length;
        int [] sMax = new int[length];
        int [] sMin = new int[length];
        int maxProduct = A[0];
     
        sMax[0] = A[0];
        sMin[0] = A[0];
        for (int i = 1; i < length; i++) {
            sMax[i] = Math.max(Math.max(sMax[i - 1] * A[i], sMin[i - 1] * A[i]), A[i]);
            sMin[i] = Math.min(Math.min(sMax[i - 1] * A[i], sMin[i - 1] * A[i]), A[i]);
            maxProduct = Math.max(maxProduct, sMax[i]);
        }
     
        return maxProduct;
    }
}
------------------code------------------
There is also a O(n) solution that take O(1) space. See URL:
https://oj.leetcode.com/discuss/11923/sharing-my-solution-o-1-space-o-n-running-time