Sunday, July 14, 2019

Leetcode solution 291: Word Pattern II

Problem Statement 

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.
Example 1:
Input: pattern = "abab", str = "redblueredblue"
Output: true
Example 2:
Input: pattern = pattern = "aaaa", str = "asdasdasdasd"
Output: true
Example 3:
Input: pattern = "aabb", str = "xyzabcxzyabc"
Output: false
Notes:
You may assume both pattern and str contains only lowercase letters.
Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

It is quite similar to Word Pattern and Isomorphic String problem, where we would keep a mapping from char to a string while also ensure there would be a one to one mapping, i.e., bijection mapping. The tricky part is it seems there are way many combinations of the mapping, how can we efficiently solve them?

Maybe we could list all the combinations? Maybe we could use DP since it is string related and only ask for true/false result?

How to list all combinations? Think about this way, let's say you have pattern = "aba" and str = "redbluered", since one char in pattern can map to any string length >= 1 in str, it is equivalent to divide up str into 3 parts (length of pattern) and check all cases. For instance, the cut of the words is like below:
  1. r | e | d b l u e r e d
  2. r | e d | b l u e r e d
  3. r | e d b | l u e r e d
  4. r | e d b l | u e r e d
  5. r | e d b l u | e r e d
  6. r | e d b l u e | r e d
  7. r | e d b l u e r | e d
  8. r | e d b l u e r e | d
  9. r e | d | b l u e r e d 
  10. r e | d b | l u e r e d 
  11. r e | d b l | u e r e d  
  12. r e | d b l u | e r e d 
  13. r e | d b l u e | r e d  
  14. r e | d b l u e r | e d 
  15. r e | d b l u e r e | d  
  16. r e d | b | l u e r e d  
  17. ..... 
 In general, if the length of pattern is M, the str length is N, the time complexity of this brute force method is O(N^M), more accurately, it should be

cmn=m!n!(nm)!


DP solution does not work since we cannot easily get a deduction formula :(

Solutions

Brute force list all the combos

For each character in pattern, try to map any possible remaining strings in str from length 1 to the end. During this process, need to make sure the string mapping is bijection (no two chars in pattern map to the same string in str) and if a mapping has been seen before, continue use that mapping.



A DFS recursion would be the implementation. A few caveats in implementation
  • Remember to reset the map and set after recursion returned false
  • When there is a bijection mapping, should continue instead of directly break

Time Complexity: O(N^M), or C(N^M) to be exact. Pattern length is M, str length is N
Space Complexity: O(M), Pattern length is M, str length is N. We use a map and a set to store the lookup, but at one time, the map should not exceed the pattern size, so is the set

References

Saturday, July 6, 2019

Leetcode solution 205: Isomorphic Strings

Problem Statement 

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
Example 1:
Input: s = "egg", t = "add"
Output: true
Example 2:
Input: s = "foo", t = "bar"
Output: false
Example 3:
Input: s = "paper", t = "title"
Output: true
Note:
You may assume both and have the same length.
Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

A relatively straightforward problem, very similar to Word Pattern. All we have to do is check the one to one mapping from string a to string b, also it needs to maintain a bijection mapping (meaning no two different characters in a should map to the same character in b)
 

Use bijection mapping

Check character one by one from a and b. If char in a hasn't been seen before, create a one to one mapping between this char in a and the char in b so later if this char in a is seen again, it has to map to b, else we return false. Moreover, need to make sure the char in b is never mapped by a different character.
An explanation int the video


Solutions


Time Complexity: O(N), N is the length of string a or string b
Space Complexity: O(N), N is the length of string a or string b because the hashmap and set we use

References

Tuesday, June 25, 2019

Leetcode solution 290: Word Pattern

Problem Statement 

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Example 1:
Input: pattern = "abba", str = "dog cat cat dog"
Output: true
Example 2:
Input:pattern = "abba", str = "dog cat cat fish"
Output: false
Example 3:
Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false
Example 4:
Input: pattern = "abba", str = "dog dog dog dog"
Output: false
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

A very simple problem thus normally can solve it in multiple ways.
 

Encode string and patterns then compare

Since we are comparing "patterns" here, one straightforward way is encode the pattern into a string, then use the same encoding algorithm to encode the str array into a string, then compare the string.

What encoding should we choose? Well it's not really an encoding per se. What I did is just convert any word or character to a character staring with ('a' + an index). If we see this character before, we just directly return from the hash map lookup. For example, "duck dog dog" would be encoded as "abb" while "bcc" would also be encoded as "abb".

Use bijection mapping

Note in the problem description it mentions it is a bijection mapping (i.e., a one to one mapping).
As shown in the graph below, you see the differences between injection, surjection and bijection. That said, bijection does not allow duplicates. We can build a one to one mapping between the pattern and string, since it's bijection, if two characters in the pattern map to the same string, then it's not a valid bijection, therefore return false.
Ref: https://en.wikipedia.org/wiki/Injective_function


Solutions

Encode string and patterns then compare

Time Complexity: O(N), N is the length of pattern or string array, we loop it 3 times, but still O(N)
Space Complexity: O(N), N is the length of pattern or string array, we need the extra map and string to store the results

Use bijection mapping (Recommended)

There is also a clever implementation like below. The key point is use the index to compare, if there is duplicate index, meaning there are two keys already mapped to the same value. Also, remember java put() returns a valid, not a void :) 

Time Complexity: N is the length of pattern or string array
Space Complexity: O(N), N is the length of pattern or string array, we need a map regardless

 

References

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