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