The Zen of Python:

Beautiful is better than ugly.

Explicit is better than implicit.

Simple is better than complex.

Complex is better than complicated.

Flat is better than nested.

Sparse is better than dense.

Readability counts.

Special cases aren’t special enough to break the rules.

Although practicality beats purity.

Errors should never pass silently.

Unless explicitly silenced.

In the face of ambiguity, refuse the temptation to guess.

There should be one– and preferably only one –obvious way to do it.

Although that way may not be obvious at first unless you’re Dutch.

Now is better than never.

Although never is often better than right now.

If the implementation is hard to explain, it’s a bad idea.

If the implementation is easy to explain, it may be a good idea.

Namespaces are one honking great idea – let’s do more of those!

(Reference: https://www.python.org/dev/peps/pep-0020/)

Question:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:
If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary

1.[“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].

2.All airports are represented by three capital letters (IATA code).

3.You may assume all tickets form at least one valid itinerary.

Example 1:

tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]

Return

["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Return

["JFK","ATL","JFK","SFO","ATL","SFO"].

Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]. But it is larger in lexical order.

Thinking:

We need to use dfs to travse all the graph and record the graph. But we need to record it in order. So it should be stored in PriorityQueue and store the route while visiting. If it’s stuck we back up but also record the previous information, because we know there are other ways to get there. Until all the edges are visited once, it’s finished.

Solution:

List<String> res = new ArrayList<String>();
HashMap<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();

public List<String> findItinerary(String[][] tickets) {
    for (String[] ticket: tickets)
        map.computeIfAbsent(ticket[0], k -> new PriorityQueue<String>()).add(ticket[1]);
    visit("JFK");

    return res;
}

private void visit(String cur) {
    while (map.containsKey(cur) && !map.get(cur).isEmpty())
        visit(map.get(cur).poll());
    res.add(0, cur);
}

Reference: https://leetcode.com/discuss/84659/short-ruby-python-java-c

Question:

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.

Thinking:

This problem is similiar with the MaxSubArray. One thing we need to notice is that we should maintian another variable which is the minimum value of the negative value. When it multiple the negtive value in the array, it maybe the maximum.

Solution:

public int maxProduct(int[] nums) {
    int l = nums.length;
    int max = nums[0];
    int maxhere = nums[0];
    int minhere = nums[0];

    for (int i = 1; i < l; i++) {
        if (nums[i] >= 0) {
            maxhere = Math.max(maxhere*nums[i], nums[i]);
            minhere = Math.min(minhere*nums[i], nums[i]);
        } else {
            int temp = maxhere;
            maxhere = Math.max(minhere*nums[i], nums[i]);
            minhere = Math.min(temp*nums[i], nums[i]);
        }
        max = Math.max(maxhere, max);
    }

    return max;

Question:

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

Thinking:

We should use stack and scan the elements of this string array. Whenever we get the operator, we pop element from the stack and push new element to the stack.

Solutioin:

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<Integer>();

    for (String s: tokens) {
        if (s.equals("+")) {
            int num1 = stack.pop();
            int num2 = stack.pop();
            stack.push(num1+num2);
        }
        else if (s.equals("-")) {
            int num1 = stack.pop();
            int num2 = stack.pop();
            stack.push(num2-num1);
        }
        else if (s.equals("*")) {
            int num1 = stack.pop();
            int num2 = stack.pop();
            stack.push(num1*num2);
        }
        else if (s.equals("/")) {
            int num1 = stack.pop();
            int num2 = stack.pop();
            stack.push(num2/num1);
        }
        else
            stack.push(Integer.parseInt(s));
    }

    return stack.pop();
}

Question:

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.

Thinking:

We need to implement this algorithm in linear time and constant space. So we need to scan this array once and record the information needed in one time. We need to variable to record the information, the first one is the minimum of this array, and the second one is the number which is bigger than its previous elements. If one element is bigger than it, the result will be true. Otherwise, we should update the two variables’ values.

Solution:

public boolean increasingTriplet(int[] nums) {
    int l = nums.length;
    if (l < 3)    return false;
    int min = nums[0];
    int secmin = Integer.MAX_VALUE;

    for (int i = 1; i < l; i++) {
        if (nums[i] > secmin)    return true;
        else if (nums[i] <= min) min = nums[i];
        else if (nums[i] < secmin)    secmin = nums[i];
    }
    return false;
}