Daily Archives: October 18, 2015

Sqrt(x)

Posted on by
Reply

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

Challenge

O(log(x))

Solution: Binary search O(log(x)). Remember to use Long during computation

public int sqrt(int x) {
    // find the last number which square of it <= x
    long start = 1, end = x;
    while (start + 1 < end) {
        long mid = start + (end - start) / 2;
        if (mid * mid <= x) {
            start = mid;
        } else {
            end = mid;
        }
    }

    if (end * end <= x) {
        return (int) end;
    }
    return (int) start;
}
FacebookTwitterGoogle+Share

Shortest Word Distance I, II & III

Posted on by
Reply

Word Distance I – Only called once

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution: One pass. O(n), Every time find an occurrence of word1 or word2, compare the distance of p1 and p2.

public int shortestDistance(String[] words, String word1, String word2) {
        int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;
    
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) 
                p1 = i;
    
            if (words[i].equals(word2)) 
                p2 = i;
    
            if (p1 != -1 && p2 != -1)
                min = Math.min(min, Math.abs(p1 - p2));
        }
    
        return min;
    }

Shortest Word Distance II – API, will be called multiple times

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution: First preprocess the word to dict, which is a <word, list of index>map.

Then every time just get the word only check two list of indexes.

public class WordDistance {
    Map<String, List<Integer>> dict;
    public WordDistance(String[] words) {
        dict = new HashMap<>();
        for(int i=0;i<words.length;i++){
            if(dict.containsKey(words[i])){
                dict.get(words[i]).add(i);
            }else{
                List<Integer> indexes = new ArrayList<>();
                indexes.add(i);
                dict.put(words[i], indexes);
            }
        }
    }

    public int shortest(String word1, String word2) {
        if(dict==null||!dict.containsKey(word1)||!dict.containsKey(word2)){
            return 0;
        }
        int res = Integer.MAX_VALUE;
        List<Integer> indexes1 = dict.get(word1);
        List<Integer> indexes2 = dict.get(word2);
        int index1 = 0;
        int index2 = 0;
        while(index1<indexes1.size()&&index2<indexes2.size()){
            res = Math.min(res, Math.abs(indexes1.get(index1)-indexes2.get(index2)));
            if(indexes1.get(index1)<indexes2.get(index2)){
                index1++;
            }else{
                index2++;
            }
        }
        return res;
        
    }
}

Shortest Word Distance III – word1 could be the same as word2

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = "makes", word2 = "makes", return 3.

Note:
You may assume word1 and word2 are both in the list.

Solution: if word1==word2==words[], then p1=p2=i, and every time we update p1, we check the distance between p1 and p2.

public int shortestWordDistance(String[] words, String word1, String word2) {
    int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;

    for (int i = 0; i < words.length; i++) {
        if (words[i].equals(word1)) {
            p1 = i;
            if (word1.equals(word2) && p1 != -1 && p2 != -1) {
                min = Math.min(min, Math.abs(p1 - p2));
            }
        }

        if (words[i].equals(word2)) {
            p2 = i;
        }

        if (!word1.equals(word2) && p1 != -1 && p2 != -1) {
            min = Math.min(min, Math.abs(p1 - p2));
        }
    }

    return min;
}

Binary Tree Maximum Path Sum

Posted on by
Reply

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Example

Given the below binary tree:

  1
 / \
2   3

return 6.

Solution: Divide and Conquer. for each node, calculate two maxPath:

1. maxSinglePath: start from root to any nodes, could be empty. 从root往下走到任意点的最大路径，这条路径可以不包含任何点.

2. maxPath: 从树中任意到任意点的最大路径，这条路径至少包含一个点. Max path in the tree, can not be empty, doesn’t have to include root.

So the result is root.maxPath

O(n) time complexity. Each node is visited once.

Version 1. cleaner version, with global variable

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
     
    int maxPath = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        maxSinglePath(root);
        return maxPath;
    }
    
    public int maxSinglePath(TreeNode root){
        if(root==null){
            return 0;
        }
        //devide
        int left = Math.max(0, maxSinglePath(root.left));
        int right = Math.max(0, maxSinglePath(root.right));
        
        //conquer
        maxPath = Math.max(maxPath, left+right+root.val);
        
        return Math.max(left, right)+root.val;
    }
}

Version 2. jiuzhang, with result class

private class maxPathResult {
    int maxSinglePath;
    int maxPath;
    public maxPathResult(int maxSinglePath, int maxPath) {
        this.maxSinglePath = maxSinglePath;//start from root to any nodes, could be empty
        this.maxPath = maxPath;//max path in the tree, can not be empty, doesn't have to include root
    }
}
public int maxPathSum(TreeNode root) {
    // write your code here
    return helper(root).maxPath;
}

public maxPathResult helper(TreeNode root) {
    if (root == null) {
        return new maxPathResult(0, Integer.MIN_VALUE);
    }
    //devide
    maxPathResult left = helper(root.left);
    maxPathResult right = helper(root.right);

    //conquer
    int maxSinglePath = Math.max(left.maxSinglePath, right.maxSinglePath) + root.val;
    maxSinglePath = Math.max(maxSinglePath, 0);

    int maxDoublePath = left.maxSinglePath + right.maxSinglePath + root.val;

    int maxPath = Math.max(Math.max(left.maxPath, right.maxPath), maxDoublePath);
    return new maxPathResult(maxSinglePath, maxPath);
}

 

Binary Tree Zigzag Level Order Traversal

Posted on by
Reply

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Solution: Use two linked list to represent curr level and the next level. While iterating through the node on the current level, we put the child nodes to next level in order based on if the current level is odd or even.

If current is odd level, so next level should be right->left, so we always insert right node in front of left node.

If current is even level, so next level should be left->right, we always insert left node in front of right node.

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> curr = new LinkedList<>();
        LinkedList<TreeNode> next = new LinkedList<>();
        curr.add(root);
        while (!curr.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            while (!curr.isEmpty()) {
                TreeNode node = curr.remove();
                tmp.add(node.val);
                //current is odd level
                //so next level should be right->left
                if (res.size() % 2 == 0) {
                    if (node.left != null) {
                        next.add(0, node.left);
                    }
                    if (node.right != null) {
                        next.add(0, node.right);
                    }
                }
                //current is even level
                //so next level should be left->right
                else {
                    if (node.right != null) {
                        next.add(0, node.right);
                    }
                    if (node.left != null) {
                        next.add(0, node.left);
                    }
                }
            }
            curr = next;
            next = new LinkedList<>();
            res.add(tmp);
        }
        return res;
    }

First Missing Positive

Posted on by
Reply

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

Example

Given [1,2,0] return 3, and [3,4,-1,1] return 2.

Challenge

Your algorithm should run in O(n) time and uses constant space.

public int firstMissingPositive(int[] A) {
    if (A.length == 0) {
        return 1;
    }
    int i = 0;
    while (i < A.length) {
        if (A[i] != i + 1) {
            if (A[i] <= A.length && A[i] > 0 && A[A[i] - 1] != A[i]) {
                swap(A, i, A[i] - 1);
            } else {
                A[i] = 0;
                i++;
            }
        } else {
            i++;
        }
    }
    for (int j = 0; j < A.length; j++) {
        if (j + 1 != A[j]) {
            return j + 1;
        }
    }
    return A.length + 1;
}

public void swap(int[] nums, int a, int b) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
}