Wednesday, May 29, 2019

Leetcode solution 1036: Escape a Large Maze

Problem Statement 

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.
We start at the source square and want to reach the target square.  Each move, we can walk to a 4-directionally adjacent square in the grid that isn't in the given list of blocked squares.
Return true if and only if it is possible to reach the target square through a sequence of moves.

Example 1:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
Explanation: 
The target square is inaccessible starting from the source square, because we can't walk outside the grid.
Example 2:
Input: blocked = [], source = [0,0], target = [999999,999999]
Output: true
Explanation: 
Because there are no blocked cells, it's possible to reach the target square.

Note:
  1. 0 <= blocked.length <= 200
  2. blocked[i].length == 2
  3. 0 <= blocked[i][j] < 10^6
  4. source.length == target.length == 2
  5. 0 <= source[i][j], target[i][j] < 10^6
  6. source != target
Hints
  • If we become stuck, there's either a loop around the source or around the target.
  • If there is a loop around say, the source, what is the maximum number of squares it can have?
Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

At first, I am puzzled why this problem would be a hard one. It seems simply applying a BFS would get the answer. So here we go.
 

Brute force, simple BFS

Of course it will hit memory limit because I am allocating a 2-dimensional visited array. Assume boolean is 8 bit -> 1B, 1 Million * 1 Million = 1TB, OMG, immediately using a set instead.

P.S. fun fact, you can use this method to test how much memory leetcode allocate to this problem, you can use binary search and memory is around 300MB

However, this would start hitting Time Limit Exception. Now I begin to notice a few constrains, e.g., the block size is only 200 while the grid is 1M*1M. Simply going from source to target worst case would cause a timeout.

Next thought would be does it help if we sort the block array? While we are doing the BFS, if the block is already larger/smaller than the max/min of the block, we can early stop. However, this won't help if we simply place a block near the target. Also, this would be a nightmare to implement.

Check block loops on source and target

Following the two hints, it would be natural to come up with this idea. Given such huge contrast between the block size (0,200) and the grid size (1M, 1M), all we need to do is to check if there is any loops built by block on source and target b/c if there is a loop, we cannot explore outside of the loop. However, notice if target and source are in the same loop, then we are fine.

There are two ways to early stop this loop checking. One way is to count the BFS steps, the other way is to follow the hints, given 200 blocks, what's the max area it can cover. Given the length 200, Fig 2 in the below graph can result in the largest area. Therefore, we can early terminate the BFS search once we covered more than 19900 blocks. (We can relax this a bit to 20000, doesn't matter)
  • Fig 1 area = 100 * 100 = 10000
  • Fig 2 area = 1 + 2 + 3 + ... + 199 = (1+199)*199/2 = 19900
  • Fig 3 area = 1 * 200 = 200
  • Fig 4 area = 790 (2*Pi*R = 100, thus R = 15.92, Pi * R^2 = 790 )



Solutions

Brute force, simple BFS

Time Complexity: O(N), N = 1M * 1M, essentially need to cover the entire huge grid
Space Complexity: O(N), N = 1M*1M, essentially all the nodes need to be put to visited set

Check block loops on source and target

Time Complexity: O(N), N in terms of block size
Space Complexity: O(N), N in terms of block size

 

References

Friday, May 24, 2019

Alibaba Tech Festival - Silicon Valley & Game of Thrones Season 8 Finale

Alibaba Tech Festival - Silicon Valley

Alibaba, Jack Ma's empire has always been very active in Silicon Valley, trying to recruit the top talents. Traditionally it was mainly focused on somewhat cutting edge technologies. e.g, big data in the old days (while everyone is talking about it), cloud, and nowadays machine learning / AI of course. However, this time, the Taobao Team (淘系技术) was in town and shared some of the interesting projects they are working on.  This is mainly due to the early vision shifts from Jack Ma that technology should drive business instead of the old vision, business is key, technology plays only a secondary supporting role.

What is Taobao(淘宝), TMall(天猫) & Xianyu (闲鱼)?  

Taobao is the largest e-commerce platform in China, with over 600M monthly active users. Think about the size 1.4B Chinese, 1B has internet access, almost half of entire China is using Taobao. It is mostly C2C where TMall is B2C.They also have Xianyu(闲鱼), which is a second hand marketplace. 

Just to give another prospective, Alibaba single-handedly created a new holiday in China called Singles' Day (光棍节,双十一), where single day it creates $30B worth of spending.


Alibaba Tech Festival at Silicon Valley

A Swag, everyday struggle, but work makes me happy 😂



New Retails (新零售)

Alibaba is one of the pioneers of e-commerce innovation and they have proposed this new concept called "New Retails". So what exactly is the new retails idea? We lived through shopping from offline to online, then online back to offline due to certain limitations. E.g., you might want to try on lots of clothes or makeups before you buy them, and online shopping cannot really satisfy that. Moreover, some people might want to hear other's opinions whether the clothes looks good or not before they buy it, they have to be in store and talk to others. Therefore, the new retails idea is digitizing every thing in store and you can shop offline, but you can view all the items info online, place the order online and expect the items to be shipped home in a few hours.

Below is a very good article on the store Alibaba built in Hangzhou.
https://www.alizila.com/future-of-retail-happening-in-china/

A few interesting things I learned from the talk
  • Taobao is also all in in AI, so that everybody's shopping / recommendation experience is highly customized.
  • Wechat is No.1 chatting app in China, and Taobao's chat is actually No. 2. Taobao also has a large video live features for sellers to better engage the buyers, it's literally like a TikTok on its own 
  • Alibaba has built extensive tools for sellers to manage all their inventory, brand, marketing etc. 
  • They have tried many ideas in the Fashion AI field. I used to think having 3D AR technology could perfectly solve the clothes fitting requirement, apparently based on Alibaba that's not the case. That's why they use image recognition to split the body into three parts and try different clothes/dress match up.






  • Alibaba is a giant company, if you look at their org chart, it's crazy 


Game of Thrones Season 8 Finale

完全的题外话,这个剧我追了8年,md最后给了我们这个一个沙雕的结局,当大家是弱智呀?!这才是官方实锤的版本, 我也是这么认为的,当年2017年这个版本所谓被黑客泄露之后,我读了觉得完全靠谱,大家可以看看,欢迎讨论
https://www.youtube.com/watch?v=U435sekPlxg

References 

 

 

Thursday, May 16, 2019

Leetcode solution 272: Closest Binary Search Tree Value II

Problem Statement 

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note:
  • Given target value is a floating point.
  • You may assume k is always valid, that is: k ≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example:
Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
Hints
  • Consider implement these two helper functions:
    1. getPredecessor(N), which returns the next smaller node to N.
    2. getSuccessor(N), which returns the next larger node to N.
  • Try to assume that each node has a parent pointer, it makes the problem much easier.
  • Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
  • You would need two stacks to track the path in finding predecessor and successor node separately.  
Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

At first glance, it might look very similar to the Closest Binary Search Tree Value. They need look similar except finding K in less than O(N) time is way harder, hehehehe
 


Okay, more seriously.
 

 

Brute force, convert BST into sorted array

A quick thought would be if we traverse the BST in order, and put them into an array, now the problem becomes given an sorted array, find K elements that are closest to the target. That search should be done binary search find the target, and expand left and right compare the values with diff, take the smaller one and continue. Overall, this brute force idea time complexity would be O(N), and space complexity is O(N), N is the total number of tree nodes.


Use a max heap

Another way or anytime when you need to find K things, always think about heap. Here if we traverse the tree (in any order) and use a K sized max heap, we can solve the problem in O(NlgK) time complexity, O(K) space complexity


Use two stacks 

This is a smart idea that I read from leetcode discussion. This is also following leetcode's hint. Keeping two separate stacks, one stack is all the nodes less or equal to the target (i.e., predecessor), the other is all the nodes larger than the target (i.e., successor). After that, merge those two stacks and keep the K closest element to target.

Note, the time complexity is still O(N + K). Think about the worst case all elements larger or smaller than targets. However, if the problem assumes the BST is balanced, then it would be come O(K + lgN) since ideally we only traverse half of the tree.


Use threaded tree

You might also think about the double threaded tree given the hint, starting from the root, keep asking the predecessor and successor since double threaded tree allows you to have that. However, I didn't code this one up since it requires you to modify the tree structure which normally not allowed in interviews and also it's a bit too complicated for a coding interview

Solutions

Brute force, convert BST into sorted array

Code it on your own :)
Time Complexity: assuming tree size is N, O(N)
Space Complexity: O(N)

 

Use a max heap


Time Complexity: assuming tree size is N, O(NlgK) because insertion into PQ is O(lgK)
Space Complexity: O(K)

 

Use two stacks


Time Complexity: assuming tree size is N, O(N+K) worst case. Think about the worst case all elements larger or smaller than targets. However, if the problem assumes the BST is balanced, then it would be come O(K + lgN) since ideally we only traverse half of the tree.
Space Complexity: O(N) worst case. Even if BST is balanced, we still need O(N/2), still O(N)

 

References

Saturday, April 27, 2019

Leetcode solution 270: Closest Binary Search Tree Value

Problem Statement 

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
  • Given target value is a floating point.
  • You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:
Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

This is a very easy problem as long as you are familiar with Binary Search Tree.  In order to find the value that is closest to the given target, we can traverse the tree and keep a record of the minimum delta. Of course we can traverse the entire tree but we can definite do it better by always branch out either left or right given the target and root node value.

For example, if  current node is 10, and target is 9, the next possible smaller value must exist only on the left part of or with the current node

     10
   /   \
  7     11

Solutions

Recursion solution 


 

Time Complexity: assuming tree size is N,O(lgN) since we are doing binary search
Space Complexity:O(1) if not considering recursion function stacks.

Iterative solution 

public int closestValue(TreeNode root, double target) {
    int ret = root.val;   
    while(root != null){
        if(Math.abs(target - root.val) < Math.abs(target - ret)){
            ret = root.val;
        }      
        root = root.val > target? root.left: root.right;
    }     
    return ret;
}

From:
https://leetcode.com/problems/closest-binary-search-tree-value/discuss/70331/Clean-and-concise-java-solution

Time Complexity: assuming tree size is N,O(lgN) since we are doing binary search
Space Complexity:O(1)

 

References

Sunday, April 21, 2019

Leetcode solution 10: Regular Expression Matching

Problem Statement 

Given an input string (s) and a pattern (p), 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).
Note:
  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

The thought process is very similar to Leetcode Solution 44: Wildcard Matching, you can find the blog here and the video tutorial here.

Step 0 really is to understand what the "*" really means.
'*' Matches zero or more of the preceding element.
A few examples,
  • "" and "a*": True, since * could match zero occurrence of the preceding char 'a', not here zero means deleting the original 'a'
  •  "a" and "a*": True, since * could match "one" occurrence in total
  • "aa" and "a*": True since * could match an extra one occurrence of the preceding char 'a', you can also think of it as "two" occurrences of 'a' in total
  • "" and "*": A very tricky case, my code below returns True but leetcode expects False. My code still passes OJ so this is really not a valid case. I argue this should be True since it is one occurrence of empty "" in total

The first attempt (if you haven't seen this question before) is trying to solve it using recursion. The idea is simple. While comparing the s and p char by char, as soon as you see a "*", you will start recurse
  • remove the preceding char and the "*", recurse and compare 
  • for every char equals to the preceding char in the pattern, as long as they are equal to the current char in s, recurse and compare
The time complexity in a ballpark looks like exponential to the P length, but a more detailed analysis from leetcode's original solution can be found here.

If you recall what problems can be solved using DP, DP (Dynamic Programming) is normally a great way when trying to answer below two types of questions, and string related questions are a majority use case of DP
  • Only Yes/No, True/False question without returning detailed step by step results 
  • Extreme values, e.g., Max, Min, Best optimal value
 I have posted several videos on how to solve DP problems using a template, essentially
  1. Initialize your lookup array, could be 2 dimensional or 1 dimensional using rolling arrays
  2. Initialize the init values in your array
  3. Get the math formula for a[i] = a[i-1] * m - n or whatever condition you need
  4. Code it up
This problem can be solved using DP by having formulas like below when a "*" is seen


Once you have the formula, coding up DP problem should be a piece of cake. You can find the video tutorial on this problem here

Solutions

DP solution

Time Complexity: assuming S length is M, P length is N, this is O(M*N) because all we need to do is build up that lookup matrix
Space Complexity: assuming S length is M, P length is N, this is O(M*N), again, that lookup matrix

References

Sunday, April 14, 2019

Leetcode solution 44: Wildcard Matching

Problem Statement 

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input:
s = "acdcb"
p = "a*c?b"
Output: false
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

It seems an easy problem first using recursion and brute forcefully solving the problem, but the OJ will quickly throw a TLE (Time Limit Exceeded) error since it is exponential time. Well, if you were like me, tried really hard to optimize my brute force solution, either using some heuristics or pruning on the recursion, however, still no luck :(

DP (Dynamic Programming) is normally a great way when trying to answer below two types of questions, and string related questions are a majority use case of DP
  • Only Yes/No, True/False question without returning detailed step by step results 
  • Extreme values, e.g., Max, Min, Best optimal value
 I have posted several videos on how to solve DP problems using a template, essentially
  1. Initialize your lookup array, could be 2 dimensional or 1 dimensional using rolling arrays
  2. Initialize the init values in your array
  3. Get the math formula for a[i] = a[i-1] * m - n or whatever condition you need
  4. Code it up 
You can find the video tutorial on this problem here

Solutions

Brute force recursion, TLE

Time Complexity: assuming S length is M, P length is N, this is O(M*2^N), exponential basically
Space Complexity: No extra space needed other than the additional recursion function stack

 


DP solution

Time Complexity: assuming S length is M, P length is N, this is O(M*N) because all we need to do is build up that lookup matrix
Space Complexity: assuming S length is M, P length is N, this is O(M*N), again, that lookup matrix

References

Monday, April 1, 2019

Leetcode solution 208: Implement Trie (Prefix Tree)

Problem Statement 

Implement a trie with insertsearch, and startsWith methods.
Example:
Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true
Note:
  • You may assume that all inputs are consist of lowercase letters a-z.
  • All inputs are guaranteed to be non-empty strings.
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

Trie (prefix tree) is a very common data structure that appears very often in interviews. I used to get asked Trie at Fitbit, Snap and Google back in the days. I highly recommend you brush up on this basic data structure.

Please refer to this Baozi Training Blog for a modified version explained:
https://blog.baozitraining.org/2019/03/leetcode-solution-211-add-and-search.html

Leetcode actually did a great job explaining this problem. Feel free to download the explanation here (all credit and copyright goes to leetcode, obviously) 

Solutions

 


Time Complexity: assuming N is the word length, insert O(N), search O(N), startWith O(N)
Space Complexity: assuming N is the word length, insert O(N), search O(1), startWith O(1)

References