Showing posts with label Airbnb. Show all posts
Showing posts with label Airbnb. Show all posts

Sunday, July 16, 2017

212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example,
Given words = ["oath","pea","eat","rain"] and board = 
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
Return ["eat","oath"].
Note:
You may assume that all inputs are consist of lowercase letters a-z.
You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?
If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.



Solution:

We use a Trie to store all valid words.

Then use DFS to try if any word is valid in the board.



Code:


public class Solution {
    
    class TrieNode {
        TrieNode[] link;
        String word;
        public TrieNode() {
            this.link = new TrieNode[26];
            this.word = null;
        }
    }
    
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return result;
        }
        if (words == null || words.length == 0) {
            return result;
        }
        TrieNode root = buildTrie(words);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, root, i, j, result);
            }
        }
        return result;
    }
    
    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                if (curr.link[c - 'a'] == null) {
                    curr.link[c - 'a'] = new TrieNode();
                }
                curr = curr.link[c - 'a'];
            }
            curr.word = word;
        }
        return root;
    }
    
    public void dfs(char[][] board, TrieNode curr, int i, int j, List<String> result) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return;
        }
        char c = board[i][j];
        if (c == '#' || curr.link[c - 'a'] == null) {
            return;
        }
        curr = curr.link[c - 'a'];
        if (curr.word != null) {
            result.add(curr.word);
            curr.word = null;
        }
        board[i][j] = '#';
        dfs(board, curr, i - 1, j, result);
        dfs(board, curr, i + 1, j, result);
        dfs(board, curr, i, j - 1, result);
        dfs(board, curr, i, j + 1, result);
        board[i][j] = c;
    }
}

Saturday, June 17, 2017

415. Add Strings

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
Note:
  1. The length of both num1 and num2 is < 5100.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.



Solution:

This problem is similar to Add Binary.

We start from the end of the strings and go backward.



Code:


public class Solution {
    public String addStrings(String num1, String num2) {
        int len1 = num1.length() - 1;
        int len2 = num2.length() - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        while (carry == 1 || len1 >= 0 || len2 >= 0) {
            int v1 = len1 >= 0 ? num1.charAt(len1--) - '0' : 0;
            int v2 = len2 >= 0 ? num2.charAt(len2--) - '0' : 0;
            int sum = v1 + v2 + carry;
            sb.append(sum % 10);
            carry = sum / 10;
        }
        return sb.reverse().toString();
    }
}

Tuesday, June 6, 2017

68. Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
Note: Each word is guaranteed not to exceed L in length.
Corner Cases:
  • A line other than the last line might contain only one word. What should you do in this case?
    In this case, that line should be left-justified.



Solution:

We keep a last variable to store the first index we can use in a line.

We use count to store the total length of words (no space).

If count plus one more word and spaces exceed maxWidth, we know we have to use this count.

To evenly distributed spaces, we use (maxWidth - count) / (number of words in this line) as space between two words. The extra space is (maxWidth - count) % (number of words in this line).

We also need to consider when a word is the last in this line, we do not have spaces after it.

A corner case is to deal with the last line, where we fill spaces after the last word.

A annotated and clear version of code can be found HERE.



Code:


public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        if (words == null || words.length == 0) {
            return result;
        }
        int last = 0;
        int count = 0;
        for (int i = 0; i < words.length; i++) {
            // words[i] cannot fit this line.
            // We can only put from words[last] to words[i - 1].
            if (count + words[i].length() + (i - last) > maxWidth) {
                int space = 0;
                int extra = 0;
                // We have i - last words in this line.
                // So we have i - last - 1 intervals.
                if (i - last - 1 > 0) {
                    space = (maxWidth - count) / (i - last - 1);
                    extra = (maxWidth - count) % (i - last - 1);
                }
                StringBuilder sb = new StringBuilder();
                for (int j = last; j < i; j++) {
                    sb.append(words[j]);
                    // There is no space after the last word in this line.
                    if (j == i - 1) {
                        break;
                    }
                    for (int k = 0; k < space; k++) {
                        sb.append(" ");
                    }
                    if (extra > 0) {
                        sb.append(" ");
                        extra--;
                    }
                }
                // If this line has not filled, fill trailing spaces.
                while (sb.length() < maxWidth) {
                    sb.append(" ");
                }
                result.add(sb.toString());
                count = 0;
                last = i;
            }
            count += words[i].length();
        }
        // To deal with the last line
        StringBuilder sb = new StringBuilder();
        for (int i = last; i < words.length; i++) {
            sb.append(words[i]);
            if (sb.length() < maxWidth) {
                sb.append(" ");
            }
        }
        while (sb.length() < maxWidth) {
            sb.append(" ");
        }
        result.add(sb.toString());
        return result;
    }
}

Monday, June 5, 2017

10. Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true



Solution:

Method 1: DP

We use dynamic programming to determine whether s and p are match.

boolean match[i][j]: whether the first i characters in s match the first j characters in p.

There are two cases to consider:

1. s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j) == '.'.

match[i - 1][j - 1]

2. p.charAt(j) == '*'
 
a). match[i][j - 2], 0 occurrence of p.charAt(j - 1)
      or
b). match[i - 1][j], if s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.'.

The time complexity is O(mn) and the space complexity is O(mn) as well.



Code:


public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
        match[0][0] = true;
        
        // deal with a*, a*b*, a*b*c*...
        for (int i = 1; i < match[0].length; i++) {
            if (p.charAt(i - 1) == '*') {
                match[0][i] = match[0][i - 2];
            }
        }
        for (int i = 1; i < match.length; i++) {
            for (int j = 1; j < match[0].length; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    match[i][j] = match[i - 1][j - 1];
                }
                else if (p.charAt(j - 1) == '*') {
                    
                    // s: x   p xa*, we check a* is empty, which is match[i][j - 2];
                    match[i][j] = match[i][j - 2];
                    
                    // s: xa  p: xa* -> a is part of a*, so we check s: x  p: xa*, which is match[i - 1][j]
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        match[i][j] = match[i][j] || match[i - 1][j];
                    }
                }
                else {
                    match[i][j] = false;
                }
            }
        }
        return match[s.length()][p.length()];
    }
}



Method 2: Optimization (Rolling Array)

We need to update match[i % 2][0] in the j loop.



Code:


public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] match = new boolean[2][n + 1];
        match[0][0] = true;
        
        // p: a*, a*b*, a*b*c*...
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                match[0][j] = match[0][j - 2];
            }
        }
        
        for (int i = 1; i <= m; i++) {
            match[i % 2][0] = false;
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    match[i % 2][j] = match[(i - 1) % 2][j - 1];
                }
                else if (p.charAt(j - 1) == '*') {
                    // s: x  p: xa*
                    match[i % 2][j] = match[i % 2][j - 2];
                    
                    // s: xa  p: xa*  p: x.*
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        match[i % 2][j] = match[i % 2][j] || match[(i - 1) % 2][j];
                    }
                }
                else {
                    match[i % 2][j] = false;
                }
                
            }
        }
        
        return match[m % 2][n];
    }
}

Thursday, June 1, 2017

198. House Robber

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.



Solution:

Method 1: Dynamic Programming

This is a classic dynamic programming problem.

Suppose at any house, we already knows the optimal solution maxProfit[] for the previous houses.

For this particular house i, we have two choices: rob, or not rob.

If we rob this house, the profit is nums[i] +  maxProfit[i - 2].

If we do not rob this house, the profit is maxProfit[i - 1].

Therefore, the max profit at this house i is maxProfit[i] = Math.max(maxProfit[i - 2] + nums[i], maxProfit[i - 1]).

The time complexity is O(n) and the space complexity is O(n).



Code:


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



Method 2: Optimize using rolling arrays.

The time complexity is O(n) and the space complexity is O(1).



Code:


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

Monday, May 29, 2017

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.



Solution:

Method 1: Heap

Use a min-heap to store the head of all lists.

While the heap is not empty, we poll the smallest node and add it to the merged list.

If this node has next, we add its next to the heap.

The time complexity is O(nlogk) and the space complexity is O(k).



Code:


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            public int compare(ListNode x, ListNode y) {
                return x.val - y.val;
            }
        });
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                heap.offer(lists[i]);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            if (node.next != null) {
                heap.offer(node.next);
            }
            tail.next = node;
            tail = node;
        }
        return dummy.next;
    }
}



Method 2:

Method 3:

Sunday, May 28, 2017

221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.



Solution:

Method 1: Dynamic Programming

dp[i][j]: max size to form a square from this point as lower right point.

dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1



Code:


public class Solution {
    public int maximalSquare(char[][] matrix) {
        int max = 0;
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j] - '0';
                }
                else if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                }
                else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max * max;
    }
}



Method 2: Optimized with rolling array



Code:


public class Solution {
    public int maximalSquare(char[][] matrix) {
        int max = 0;
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[2][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i % 2][j] = matrix[i][j] - '0';
                }
                else if (matrix[i][j] == '0') {
                    dp[i % 2][j] = 0;
                }
                else {
                    dp[i % 2][j] = Math.min(Math.min(dp[(i - 1) % 2][j], dp[i % 2][j - 1]), dp[(i - 1) % 2][j - 1]) + 1;
                }
                max = Math.max(max, dp[i % 2][j]);
            }
        }
        return max * max;
    }
}

269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1:
Given the following words in dictionary,
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
The correct order is: "wertf".
Example 2:
Given the following words in dictionary,
[
  "z",
  "x"
]
The correct order is: "zx".
Example 3:
Given the following words in dictionary,
[
  "z",
  "x",
  "z"
]
The order is invalid, so return "".
Note:
  1. You may assume all letters are in lowercase.
  2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
  3. If the order is invalid, return an empty string.
  4. There may be multiple valid order of letters, return any one of them is fine.



Solution:

The idea is to use topological sort to get the order of characters.

To build the graph, we compare every two adjacent words.

If we found the character in the same index different, we know the order of these two characters, and thus add an edge and update the indegree.

After building the graph, we simply apply topological sort.



Code:


public class Solution {
    public String alienOrder(String[] words) {
        ArrayList<Character>[] adj = new ArrayList[26];
        int[] indegree = new int[26];
        Arrays.fill(indegree, -1);
        
        for (int i = 0; i < 26; i++) {
            adj[i] = new ArrayList<Character>();
        }
        
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                if (indegree[c - 'a'] < 0) {
                    indegree[c - 'a'] = 0;
                }
            }
            if (i == 0) {
                continue;
            }
            String w1 = words[i - 1];
            String w2 = words[i];
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 == c2) {
                    if (j == w2.length() - 1 && w1.length() > w2.length()) {
                        return "";
                    }
                    continue;
                }
                if (!adj[c1 - 'a'].contains(c2)) {
                    adj[c1 - 'a'].add(c2);
                    indegree[c2 - 'a']++;
                }
                break;
            }
        }
        
        Queue<Character> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (indegree[i] == 0) {
                queue.offer((char)('a' + i));
            }
        }
        while (!queue.isEmpty()) {
            char c = queue.poll();
            sb.append(c);
            for (char nei : adj[c - 'a']) {
                indegree[nei - 'a']--;
                if (indegree[nei - 'a'] == 0) {
                    queue.offer(nei);
                }
            }
        }
        for (int d : indegree) {
            if (d > 0) {
                return "";
            }
        }
        return sb.toString();
    }
}



Use HashMap


public class Solution {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }
        StringBuilder order = new StringBuilder();
        HashMap<Character, HashSet<Character>> adj = new HashMap<>();
        for (char c = 'a'; c <= 'z'; c++) {
            adj.put(c, new HashSet<Character>());
        }
        int[] degree = new int[26];
        Arrays.fill(degree, -1);
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                if (degree[c - 'a'] == -1) {
                    degree[c - 'a'] = 0;
                }
            }
            if (i == 0) {
                continue;
            }
            String w1 = words[i - 1];
            String w2 = words[i];
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 != c2) {
                    if (!adj.get(c1).contains(c2)) {
                        adj.get(c1).add(c2);
                        degree[c2 - 'a']++;  
                    }
                    break;
                }
                if (j == w2.length() - 1 && w1.length() > w2.length()) {
                    return "";
                }
            }
        }
        Queue<Character> queue = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if (degree[i] == 0) {
                queue.offer((char)(i + 'a'));
            }
        }
        while (!queue.isEmpty()) {
            char c = queue.poll();
            order.append(c);
            for (char nei : adj.get(c)) {
                if (--degree[nei - 'a'] == 0) {
                    queue.offer(nei);
                }
            }
        }
        for (int i = 0; i < 26; i++) {
            if (degree[i] > 0) {
                return "";
            }
        }
        return order.toString();
    }
}

Thursday, May 11, 2017

227. Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.



Solution:

Go through the sting:

1. Get the number

2. If we find a operator, it means we need to process the previous result, and update the sign.

After going through the string, we take all numbers from the stack and add them up to the result.



Code:


public class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int len = s.length();
        int num = 0;
        char sign = '+';
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            }
            if (c == '+' || c == '-' || c == '*' || c == '/' || i == len - 1) {
                if (sign == '+') {
                    stack.push(num);
                }
                if (sign == '-') {
                    stack.push(-num);
                }
                if (sign == '*') {
                    stack.push(stack.pop() * num);
                }
                if (sign == '/') {
                    stack.push(stack.pop() / num);
                }
                sign = c;
                num = 0;
            }
        }
        int res = 0;
        for (int i : stack) {
            res += i;
        }
        return res;
    }
}