## Sunday, November 18, 2018

### Problem Statement

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

### Video Tutorial

You can find the detailed video tutorial here

### Thought Process

This looks like a string pattern matching problem, we might start go down the KMP or Rabin Karp route (calculate string hash value). However, the unique requirement is they need to be anagrams. We already know several way to compare if two words are anagrams. Sort, bucketize it. Assuming the longer string length is N, the shorter pattern string length is M, if we do it in brute force way, i.e., for each M length substring in N, we check if they are anagrams, it is O(N*M) assuming we have to repopulate all the maps. Obviously we can optimize this by keeping a sliding window only insert and delete one character at a time. That way, it is only O(N*256), still O(N). (note, 256 is the ASCII char length since every time we need to compare if two ASCII char maps are the same or not)

It is also a good problem to have a pattern on coding for two pointers (sliding) window problem.
• Initialize the two maps
• Keep a start and end pointer, move one at a time
• Don't forget to compare the last element

### Solutions

#### Sliding Window using Two Pointers

Time Complexity:O(N), len(s) is N, len(p) is M. We only loop through s once, each time we compare anagrams with a constant 256 loop, thus O(256*N) = O(N)
Space Complexity: O(N)

## Sunday, November 4, 2018

### Problem Statement

Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:
• All inputs will be in lowercase.
• The order of your output does not matter.

### Video Tutorial

You can find the detailed video tutorial here

### Thought Process

Every time we hear about anagrams, we automatically think would relate to how to find two words are anagrams, where we can solve in O(N), easy. That would result in a brute force solution.

Another quick thought would be sort each word and keep a map to track it, however, sorting is also not free.

Now we think harder, how can we avoid the O(MlgM) sorting (M is the word length) as the map's lookup key? Now the question becomes how we can generate a unique value (ideally string) for the same set of characters regardless of its order?  This is similar to the MD5 or SHA1 or hash value of certain object. So we can keep an array of chars, count the chars and translate that array into a string. Note simply count the sum of the array won't work, e.g., "ac" and "bb" will result in the same value.

### Solutions

#### Brute force, for every pair of string in the array, check if they are anagrams.

Time Complexity:O(M*N^2), M is the word length, and N is the string array length
Space Complexity: O(N)

#### Sort each string as key

As described above,we sort each string and use it as the lookup key so we can group the anagrams.
Time Complexity: O(N*M*LgM), M is the word length, and N is the string array length
Space Complexity: O(N)

#### "Hash" each string as key

Kind similar to hashing, we covert each string as key by generating a unique value using linear algorithm instead of sorting NlgN algorithm.

Time Complexity: O(N*M), M is the word length, and N is the string array length
Space Complexity: O(N)

## Monday, April 9, 2018

### Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

### Video Tutorial

You can find the detailed video tutorial here

### Thought Process

Since the Min Stack preserves most of the stack operations, it is natural to composite with a normal stack, the question is how do we keep the minimum value. Simply keeping the smallest value won't work since once that value is popped out from the stack, there is no way to track the next smallest value.

One solution is to define an extra struct where it carries the minimum value before itself is popped out of the stack, basically the current minimum value so far seen in this stack. When newer element comes in, if value is smaller than the previous one, we update. Else ignore the larger values and carry over the smaller value.

Another solution is to keep two stacks. Similarly, the other stack only keeps the smallest value. We can only keep the smallest value or we can always push a value with the current smallest value seen far (essentially similar to solution one).

### Solutions

#### Define own structure to carry over the minimum value so far

Time Complexity:O(1) Push, Pop, Top, GetMin
Space Complexity: O(N) , N is the total number of nodes, used extra class storage, negligible in practice.

#### Use two stacks.

As described above, we simply keep a minimum stack. Below implementation only pushes the smallest value, and when pop, need to peek the stack.
Time Complexity: O(1),Push, Pop, Top, GetMin
Space Complexity: O(N) , N is the total number of nodes

## Saturday, April 7, 2018

### Problem Statement

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:
Input: The root of a Binary Search Tree like this:
5
/   \
2     13

Output: The root of a Greater Tree like this:
18
/   \
20     13

### Video Tutorial

You can find the detailed video tutorial here

### Thought Process

When a tree problem is presented, normally we will think if any kind of traversal could be applied, e.g, preorder/inorder/postorder or level order traversal. In this problem, we want to update the tree node value with the sum of itself and all the node values larger itself. Yep, directly modifying the input param values (In real world, it is bad practice to directly manipulate the input value since it might surprise your downstream callers unless it is clearly documented), so tree structure is not modified.

You might first think of a brute force method, perform a normal left to right inorder traversal, then it is sorted ascendingly, then do a rolling sum from largest to smallest element. This is normal when we don't really know how to deal with tree structure so we serialize the tree into an array and later we can deserialize it back. In this problem, we don't need to deserialize since tree structure is not changed. This however requires extra O(N) space.

Now let's look at a better solution. In BST, all the nodes that have greater value than the node itself lives in the right subtree, so if we traverse the right subtree first, update the tree value, then traverse the left subtree (all the right subtree nodes have greater value than left subtree), then the problem becomes doing an inorder traversal, except this time we go to right first, update value, then go to left. To keep the running sum, it is most easy to keep a global variable to track it.

### Solutions

#### Naive inorder traversal with serialize tree into array

Time Complexity: O(N), N is the total number of tree nodes
Space Complexity: O(N) , N is the total number of tree nodes, since we are using extra list.

#### Reverse inorder traversal

As described above, we simply do a reverse inorder traversal, right to left and keep a running sum.

Time Complexity: O(N), N is the total number of tree nodes
Space Complexity: O(lgN) , N is the total number of tree nodes, since we are doing recursion.

## Sunday, February 4, 2018

### Problem Statement

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
Note:
1. The number of tasks is in the range [1, 10000].
2. The integer n is in the range [0, 100].

### Video Tutorial

You can find the detailed video tutorial here

### Thought Process

1. Array is not sorted, could it be sorted?
2. Task is a finite set, 26 maximum.
3. It is about extreme value (min value in this case), can Dynamic Programming (DP) be applied?
4. DP seems cannot be applied here, it is very hard to come up with a mathematical induction function, even though there is a solution by coming up with a math formula, but it is very hard to come up with this in a real interview session.
5. Can we do any binary search hear, nope
6. Hmm... it seems maybe we can be greedy here, doing it in a round robin way. Schedule the largest job first, then 2nd largest job, then 3rd largest job until the internal is met. Note, we have to always apply the largest job as soon as possible, for example, if we have a test case [A, A, A, A, A, B, C, D, E] and interval n is 2, if we are doing strict round robin, it would be A, B, C, D, E, A, idle, idle, A, idle, idle, A, idle, idle, A -> 15 cycle, where we should really apply A as soon as possible, so it becomes A, B, C, A, D, E, A, idle, idle, A, idle, idle, A -> 13 cycle.

### Solutions

#### Sort after every iteration

Given the greedy sort, we want to always apply the largest job first, so we should sort the jobs first (job name does not matter), after meeting the interval requirement, sort the array again and repeat by applying the largest job first, then 2nd largest etc.

#### Use priority queue (max heap)

Instead of sorting after every iteration, we can use a max heap to always pop out the largest element, and instead of sort O(NlgN) on every iteration, it will just be O(lgN) to heaptify, even though N is fixed 26 on size.

## Monday, January 15, 2018

### Problem Statement

A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

You can find the detailed video tutorial here:

### A few edge cases to think about

• Null array, one element array
• Strictly increasing array
• Strictly decreasing array
• Array with all same element (won't happen in this case)

Here is an example:

### Code Sample

• Use first and last element as negative infinite (Solution: just skip the first and last then)
• There could be same elements and they can be equal. (Solution: same thing, just need to change your comparison logic in this case)

### References

• https://www.tangjikai.com/algorithms/leetcode-162-find-peak-element
• https://leetcode.com/problems/find-peak-element/solution/

## Monday, October 27, 2014

### 包子IT面试培训 助你拿到理想的offer!

Consistent Hashing 是一个经常会被问到的数据结构，在实际工程中也非常有用，比如在cache 系统中，partition系统，积极distributed hash table中，都会用到。这里转载了Tom White一篇网上写的很赞的文章，非常清楚的讲解了consistent hashing里面这个环式如何工作的。wiki里面还有类似的一个算法，HRW (Highest Random Weight), 也比较简单。总结一下，consistent hashing就是要做到增加或者删除节点的时候，要尽可能少得影响其他node，正所谓牵一发，而不动全身。

I've bumped into consistent hashing a couple of times lately. The paper that introduced the idea (Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web by David Karger et al) appeared ten years ago, although recently it seems the idea has quietly been finding its way into more and more services, from Amazon's Dynamo to memcached (courtesy of Last.fm). So what is consistent hashing and why should you care?
The need for consistent hashing arose from limitations experienced while running collections of caching machines - web caches, for example. If you have a collection of n cache machines then a common way of load balancing across them is to put object o in cache machine number hash(o) mod n. This works well until you add or remove cache machines (for whatever reason), for then n changes and every object is hashed to a new location. This can be catastrophic since the originating content servers are swamped with requests from the cache machines. It's as if the cache suddenly disappeared. Which it has, in a sense. (This is why you should care - consistent hashing is needed to avoid swamping your servers!)
It would be nice if, when a cache machine was added, it took its fair share of objects from all the other cache machines. Equally, when a cache machine was removed, it would be nice if its objects were shared between the remaining machines. This is exactly what consistent hashing does - consistently maps objects to the same cache machine, as far as is possible, at least.
The basic idea behind the consistent hashing algorithm is to hash both objects and caches using the same hash function. The reason to do this is to map the cache to an interval, which will contain a number of object hashes. If the cache is removed then its interval is taken over by a cache with an adjacent interval. All the other caches remain unchanged.

### Demonstration

Let's look at this in more detail. The hash function actually maps objects and caches to a number range. This should be familiar to every Java programmer - the hashCode method on Object returns an int, which lies in the range -231 to 231-1. Imagine mapping this range into a circle so the values wrap around. Here's a picture of the circle with a number of objects (1, 2, 3, 4) and caches (A, B, C) marked at the points that they hash to (based on a diagram from Web Caching with Consistent Hashing by David Karger et al):
To find which cache an object goes in, we move clockwise round the circle until we find a cache point. So in the diagram above, we see object 1 and 4 belong in cache A, object 2 belongs in cache B and object 3 belongs in cache C. Consider what happens if cache C is removed: object 3 now belongs in cache A, and all the other object mappings are unchanged. If then another cache D is added in the position marked it will take objects 3 and 4, leaving only object 1 belonging to A.
This works well, except the size of the intervals assigned to each cache is pretty hit and miss. Since it is essentially random it is possible to have a very non-uniform distribution of objects between caches. The solution to this problem is to introduce the idea of "virtual nodes", which are replicas of cache points in the circle. So whenever we add a cache we create a number of points in the circle for it.
You can see the effect of this in the following plot which I produced by simulating storing 10,000 objects in 10 caches using the code described below. On the x-axis is the number of replicas of cache points (with a logarithmic scale). When it is small, we see that the distribution of objects across caches is unbalanced, since the standard deviation as a percentage of the mean number of objects per cache (on the y-axis, also logarithmic) is high. As the number of replicas increases the distribution of objects becomes more balanced. This experiment shows that a figure of one or two hundred replicas achieves an acceptable balance (a standard deviation that is roughly between 5% and 10% of the mean).

### Implementation

For completeness here is a simple implementation in Java. In order for consistent hashing to be effective it is important to have a hash function that mixes well. Most implementations of Object's hashCode do not mix well - for example, they typically produce a restricted number of small integer values - so we have a HashFunction interface to allow a custom hash function to be used. MD5 hashes are recommended here.
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash<T> {

private final HashFunction hashFunction;
private final int numberOfReplicas;
private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();

public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
Collection<T> nodes) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;

for (T node : nodes) {
}
}

for (int i = 0; i < numberOfReplicas; i++) {
circle.put(hashFunction.hash(node.toString() + i), node);
}
}

public void remove(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.remove(hashFunction.hash(node.toString() + i));
}
}

public T get(Object key) {
if (circle.isEmpty()) {
return null;
}
int hash = hashFunction.hash(key);
if (!circle.containsKey(hash)) {
SortedMap<Integer, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}

}
The circle is represented as a sorted map of integers, which represent the hash values, to caches (of type T here).
When a ConsistentHash object is created each node is added to the circle map a number of times (controlled by numberOfReplicas). The location of each replica is chosen by hashing the node's name along with a numerical suffix, and the node is stored at each of these points in the map.
To find a node for an object (the get method), the hash value of the object is used to look in the map. Most of the time there will not be a node stored at this hash value (since the hash value space is typically much larger than the number of nodes, even with replicas), so the next node is found by looking for the first key in the tail map. If the tail map is empty then we wrap around the circle by getting the first key in the circle.

### Usage

So how can you use consistent hashing? You are most likely to meet it in a library, rather than having to code it yourself. For example, as mentioned above, memcached, a distributed memory object caching system, now has clients that support consistent hashing. Last.fm's ketama by Richard Jones was the first, and there is now a Java implementation by Dustin Sallings (which inspired my simplified demonstration implementation above). It is interesting to note that it is only the client that needs to implement the consistent hashing algorithm - the memcached server is unchanged. Other systems that employ consistent hashing include Chord, which is a distributed hash table implementation, and Amazon's Dynamo, which is a key-value store (not available outside Amazon).

References