Data Stream Median

Data Stream Median

24%

Accepted

Numbers keep coming, return the median of numbers at every time a new number added.

Have you met this question in a real interview? 

Yes

Example

For numbers coming list: [1, 2, 3, 4, 5], return[1, 1, 2, 2, 3].

For numbers coming list: [4, 5, 1, 3, 2, 6, 0], return[4, 4, 4, 3, 3, 3, 3].

For numbers coming list: [2, 20, 100], return [2, 2, 20].

Challenge

Total run time in O(nlogn).

Clarification

What's the definition of Median? - Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median isA[(n - 1) / 2]. For example, if A=[1,2,3], median is 2. If A=[1,19], median is 1.

public class Solution {

    /**

     * @param nums: A list of integers.

     * @return: the median of numbers

     */

    public int[] medianII(int[] nums) {

        // write your code here

        if(nums == null || nums.length == 0) return nums;

        int[] medians = new int[nums.length];

        int size = 10;

        Queue<Integer> minHeap = new PriorityQueue<Integer>(size, new Comparator<Integer>(){

            public int compare(Integer a, Integer b){

                return b - a;

            }

        });

        

        Queue<Integer> maxHeap = new PriorityQueue<Integer>(size, new Comparator<Integer>(){

            public int compare(Integer a, Integer b){

                return a - b;

            }

        });

        for(int i = 0; i < nums.length; i++){

            if(minHeap.size() > maxHeap.size()){

                if(nums[i] > minHeap.peek()){

                    maxHeap.offer(nums[i]);

                } else {

                    maxHeap.offer(minHeap.poll());

                    minHeap.offer(nums[i]);

                }

            } else {

                if(minHeap.isEmpty() || nums[i] <= maxHeap.peek()){

                    minHeap.offer(nums[i]);

                } else {

                    minHeap.offer(maxHeap.poll());

                    maxHeap.offer(nums[i]);

                }

            }

            medians[i] = minHeap.peek(); 

        }

        return medians;

    }

}

Post Office Problem

Post Office Problem

23%

Accepted

On one line there are n houses. Give you an array of integer means the the position of each house. Now you need to pick k position to build k post office, so that the sum distance of each house to the nearest post office is the smallest. Return the least possible sum of all distances between each village and its nearest post office.

Have you met this question in a real interview? 

Yes

Example

Given array a = [1,2,3,4,5], k = 2. return 3.

Challenge

Could you solve this problem in O(n^2) time ?

public class Solution {

    /**

     * @param A an integer array

     * @param k an integer

     * @return an integer

     */

    public int postOffice(int[] A, int k) {

        // Write your code here

        int n = A.length;

        Arrays.sort(A);

        int[][] dp = new int[n+1][n+1];

        int[][] dis = init(A);

        if(n == 0 || k >= A.length) return 0;

        for(int i = 0; i <= n; i++){

            dp[i][1] = dis[1][i];

        }

        

        for(int l = 2; l <= k; l++){

            for(int i=l; i <= n; i++){

                dp[i][l] = Integer.MAX_VALUE;

                for(int j = 0; j < i; j++){

                    if(dp[i][l] == Integer.MAX_VALUE || dp[i][l] > (dp[j][l-1] + dis[j+1][i])){

                        dp[i][l] = dp[j][l-1] + dis[j+1][i];

                    }

                }

            }

        }

        return dp[n][k];

    }

    

    private int[][] init(int[] A){

        int n = A.length;

        int[][] dis = new int[n+1][n+1];

        for(int i = 1; i <= n; i++){

            for(int j = i+1; j <= n; j++){

                int mid = (i+j)/2;

                for(int k = i; k <= j; k++){

                    dis[i][j] += Math.abs(A[k-1] - A[mid-1]);

                }

            }

        }

        return dis;

    }

}

Longest Increasing Continuous subsequence II

Longest Increasing Continuous subsequence II

20%

Accepted

Give you an integer matrix (with row size n, column size m)，find the longest increasing continuous subsequence in this matrix. (The definition of the longest increasing continuous subsequence here can start at any row or column and go up/down/right/left any direction).

Have you met this question in a real interview? 

Yes

Example

Given a matrix:

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

return 25

public class Solution {

    /**

     * @param A an integer matrix

     * @return  an integer

     */

    public int longestIncreasingContinuousSubsequenceII(int[][] A) {

        // Write your code here

        if(A == null || A.length == 0 || A[0].length == 0) return 0;

        int [][] store = new int[A.length][A[0].length];

        int res = 0;

        for(int i = 0; i < A.length; i++){

            for(int j = 0; j < A[0].length; j++){

                if(store[i][j] == 0){

                    res = Math.max(res, dfs(store, i, j, A));

                }

            }

        }

        return res;

    }

    

    private int dfs(int[][] store, int i, int j, int[][] A){

        if(store[i][j] != 0) return store[i][j];

        

        int left = 0, right = 0, up = 0, down = 0;

        if(j+1 < store[0].length && A[i][j+1] > A[i][j]){

            down = dfs(store, i, j+1, A);

        }

        if(j > 0  && A[i][j-1] > A[i][j]){

            up = dfs(store, i, j-1, A);

        }

        if(i+1 < store.length && A[i+1][j] > A[i][j]){

            right = dfs(store, i+1, j, A);

        }

         if(i > 0 && A[i-1][j] > A[i][j]){

            left = dfs(store, i-1, j, A);

        }

        store[i][j] = Math.max(Math.max(left, right), Math.max(up, down)) + 1;

        return store[i][j];

    }

}

Binary Representation

Binary Representation

17%

Accepted

Given a (decimal - e.g. 3.72) number that is passed in as a string, return the binary representation that is passed in as a string. If the fractional part of the number can not be represented accurately in binary with at most 32 characters, return ERROR.

Have you met this question in a real interview? 

Yes

Example

For n = "3.72", return "ERROR".

For n = "3.5", return "11.1".

public class Solution {

    /**

     *@param n: Given a decimal number that is passed in as a string

     *@return: A string

     */

    public String binaryRepresentation(String n) {

        // write your code here

        int intPart = Integer.parseInt(n.substring(0, n.indexOf(".")));

        double decPart = Double.parseDouble(n.substring(n.indexOf(".")));

        String intStr = "";

        String decStr = "";

        if(intPart == 0) intStr = "0";

        while(intPart != 0){

            int c = intPart % 2;

            intStr = c + intStr;

            intPart = intPart / 2;

        }

        

        while(decPart > 0.0){

           

            if(decStr.length() > 32) return "ERROR";

             double r = decPart * 2;

            if(r >= 1.0){

                decStr += '1';

                decPart = r - 1.0;

            } else{

                decPart = r;

                decStr += '0';

            }

        }

        return decStr.length() > 0 ? intStr + "." + decStr : intStr;

    }

}

Expression Tree Build

The structure of Expression Tree is a binary tree to evaluate certain expressions. All leaves of the Expression Tree have an number string value. All non-leaves of the Expression Tree have an operator string value.

Now, given an expression array, build the expression tree of this expression, return the root of this expression tree.

Have you met this question in a real interview? 

Yes

Example

For the expression (2*6-(23+7)/(1+2)) (which can be represented by ["2" "*" "6" "-" "(" "23" "+" "7" ")" "/" "(" "1" "+" "2" ")"]). The expression tree will be like

                 [ - ]
             /          \
        [ * ]              [ / ]
      /     \           /         \
    [ 2 ]  [ 6 ]      [ + ]        [ + ]
                     /    \       /      \
                   [ 23 ][ 7 ] [ 1 ]   [ 2 ] .

After building the tree, you just need to return root node [-].

Clarification

See wiki: Expression Tree

public class Solution {
    /**
     * @param expression: A string array
     * @return: The root of expression tree
     */
    public ExpressionTreeNode build(String[] expression) {
        // write your code here
        int base = 0;
        int val = 0;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        for(int i = 0; i <= expression.length; i++){
            if(i != expression.length){
                if(expression[i].equals("(")){
                    base += 10;
                    continue;
                }
                if(expression[i].equals(")")){
                    base -= 10;
                    continue;
                }
                val = getValue(base, expression[i]);
            }
            TreeNode right = i == expression.length ? new TreeNode(Integer.MIN_VALUE, "") : new TreeNode(val, expression[i]);
            while(!stack.isEmpty()){
                if(right.val <= stack.peek().val){
                    TreeNode cur = stack.pop();
                    if(stack.isEmpty()){
                        right.root.left = cur.root;
                    } else{
                        TreeNode left = stack.peek();
                        if(left.val < right.val){ // operator compare
                            right.root.left = cur.root;
                        } else{
                            left.root.right = cur.root;
                        }
                    }
                   
                } else break;
            }
            stack.push(right);
        }
        return stack.peek().root.left;
    }
   
    private int getValue(int base, String s){
        if(s.equals("+") || s.equals("-")){
            return 1+base;
        }
       
        if(s.equals("/") || s.equals("*")){
            return 2+base;
        }
        return Integer.MAX_VALUE;
    }
   
    class TreeNode{
        public int val;
        public String s;
        public ExpressionTreeNode root;
        public TreeNode left, right;
        public TreeNode(int val, String s){
            this.val = val;
            this.root = new ExpressionTreeNode(s);
        }
       
    }
}

Sliding Window Maximum

Sliding Window Maximum

23%

Accepted

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

Have you met this question in a real interview? 

Yes

Example

For array [1, 2, 7, 7, 8], moving window size k = 3. return[7, 7, 8]

At first the window is at the start of the array like this

[|1, 2, 7| ,7, 8] , return the maximum 7;

then the window move one step forward.

[1, |2, 7 ,7|, 8], return the maximum 7;

then the window move one step forward again.

[1, 2, |7, 7, 8|], return the maximum 8;

Challenge

o(n) time and O(k) memory

public class Solution {

    /**

     * @param nums: A list of integers.

     * @return: The maximum number inside the window at each moving.

     */

    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {

        // write your code here

        ArrayList<Integer> res = new ArrayList<Integer>();

        Deque<Integer> deque = new LinkedList<Integer>();

        if(nums == null || nums.length == 0 || k <= 0) return res;

        

        for(int i = 0; i < k; i++){

            

            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){

                deque.removeLast();

            }

            deque.addLast(i);

        }

        

        for(int i = k; i < nums.length; i++){

            res.add(nums[deque.peekFirst()]);

            while(!deque.isEmpty() && deque.peek() <= i - k){

                deque.removeFirst();

            }

            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){

                deque.removeLast();

            }

            deque.addLast(i);

        }

        res.add(nums[deque.peekFirst()]);

        return res;

    }

}