Wednesday, July 24, 2019

Problem Statement

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
Example:
Input: 38
Output: 2
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2.
Since 2 has only one digit, return it.

Could you do it without any loop/recursion in O(1) runtime?

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Just do a simple brute force simulation. Unless you know what a digital root is, beforehand solving it in O(1) cannot collect any useful signals from the candidate.

The triple bar equal is quite interesting. It means congruence. E.g., if you have two exactly same figures but one is rotated or clock points to 13 and 1, they are considered congruence (just like 13 and 1 mod by 12 are equal). In our example,  it's about the mod result, e.g.,

Side note:
I am sharing with everyone on this problem just to express how useless this problem is... Honestly if someone ask you to solve this problem in O(1) time in a real interview, rethink joining that company. If you are an interviewer, please do yourself a favor not asking your candidate to solve it in O(1). It's an okay question to ask as a warm up just to calm your candidate down for the brute force solution.

Solutions

Brute force

Keep summing the each digit until the final number is < 10

Time Complexity: O(N), N is the length of the digit
Space Complexity: O(1), No extra space is needed

Use the digital root formula

return (num - 1) % 9 + 1
Time Complexity: O(1)
Space Complexity: O(1)

Sunday, July 14, 2019

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.

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

Saturday, July 6, 2019

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.

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