• Solution 1

Logic: BFS level by level, the previous level is diffrent from other level by the length, DP for state transformation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Java:
public int[] numsSameConsecDiff(int N, int K) {
        List<Integer> cur = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
        for (int i = 2; i <= N; ++i) {
            List<Integer> cur2 = new ArrayList<>();
            for (int x : cur) {
                int y = x % 10;
                if (x > 0 && y + K < 10)
                    cur2.add(x * 10 + y + K);
                if (x > 0 && K > 0 && y - K >= 0)
                    cur2.add(x * 10 + y - K);
            }
            cur = cur2;
        }
        return cur.stream().mapToInt(j->j).toArray();
    }

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

vector<int> numsSameConsecDiff(int N, int K) {
        vector<int> cur = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
        for (int i = 2; i <= N; ++i) {
            vector<int> cur2;
            for (int x : cur) {
                int y = x % 10;
                if (x > 0 && y + K < 10)
                    cur2.push_back(x * 10 + y + K);
                if (x > 0 && K > 0 && y - K >= 0)
                    cur2.push_back(x * 10 + y - K);
            }
            cur = cur2;
        }
        return cur;
    }

• Solution 2: dfs find the path to construct a number and until all the number is added.

Below are two different coding style for DFS. The point is that which one is more efficiency.
In C++ solution, it start from 1 to 9, and the dfs path is directly find the num+K or num-K, as goes further.
the Java solution start from the 0 case, and dfs by 0 to 9 check every possible case.

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

vector<int> numsSameConsecDiff(int N, int K){
	//base case from 1
	if(N==1) return {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	vector<int> res;
	//from 1 ... dfs, because 0 can not be in the front
	for(auto num = 1; num <= 9; ++num){
		dfs(num, N-1, K, res);
	}
	return res;
}

//dfs method
void dfs(int num, int N, int K, vector<int> &res){
	//terinal cases
	if(N==0) res.push_back(num);
	else{
		//two path to find the final possible number
		if(num%10 + K<=9) dfs(num*10 + num%10 + K, N-1, K, res);
		if(nums10 -K >= 0) dfs(nums*10 + num%10 -K, N-1, K, res);
	}
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public int[] numsSameConsecDiff(int N, int K) {
        List<Integer> list = new ArrayList<>();
        if(N==0)
            return new int[0];
        if(N==1)
			list.add(0);      // edge case
        dfs(N, K, list, 0);
        return list.stream().mapToInt(i->i).toArray();   //list.toArray(new int[list.size()]); doesn't work for primitives
    }
    public void dfs(int N, int K, List<Integer> list, int number){
        if(N == 0){   // base case, if you have added enough number of integers then append it to list; Here N is used as the total digits in temporary number 
            list.add(number);
            return ;
        }
        for(int i=0; i<10; ++i){
            if(i==0 && number ==0)    // Do not add 0 at begining of a number
                continue;
            else if(number == 0 && i!=0){     // base case, we add all the digits when we do not have any previous digit to check if difference = K
                dfs(N-1, K, list, i);
            }
            else{
                if(Math.abs((number%10) - i )==K){
                    dfs(N-1, K, list, number*10+i);    // General dfs to add the digit at the units place and reducing the number of digits by 1.
                }
            }
        }
    }

• for tree inorder traversal, we have many different coding solution: recursion and iterative with stack mainly.

Iterative stack for basic inorder traversal

leetcode 94. Binary Tree Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public List<Integer> inorderTraversal(TreeNode root){
	List<Integer> res = new ArrayList<>();
	if(root == null) return res;
	Stack<TreeNode> stack = new Stack<>();
	while(root != null || !stack.empty()){
		while(root != null){
			stack.push(root);
			root = root.left;
		}
		root = stack.pop();
		res.add(root.val);
		root = root.right;
	}
	return res;
}

• Use this basic structure to find the kth smallest node

  Leetcode 230. Kth Smallest Element in a BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int KthSmallest(TreeNode root, int k){
	Stack<TreeNode> stack = new Stack<>();
	while(root != null || !stack.isEmpty()){
		//go all the way down to the left bottom if root is valid
		while(root != null){
			stack.push(root);
			root = root.left;
		}
		//pop the top and get the value and then go the left
		root = stack.pop();
		if(--k == 0) break;
		root = root.right;
	}
	return root.val;
}

Leetcode 98. Validate Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public boolean isValidBST(TreeNode root){
	if(root == null) return true;
	Stack<TreeNode> stack = new Stack<>();
	TreeNode pre = null;
	while(root != null || !stack.empty()){
		while(root != null){
			stack.push(root);
			root = root.left;
		}
		root = stack.pop();
		if(pre != null && root.val <= pre.val) return false;
		pre = root;
		root =root.right;
	}
	return true;
}

• Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.

Similar to Leetcode.98

Test Case

1
2
3
4
5
6
7
8
9
10
11

Input: [10,5,15,1,8,null,7]

   10 
   / \ 
  5  15 
 / \   \ 
1   8   7

Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one.
             The return value is the subtree's size, which is 3.

Follow up:
Can you figure out ways to solve it with O(n) time complexity?

logic

• 1. dfs, get the information from bottom(top down), should return the max value in the left node and the min value in the right node.
• 2. a inner class is useful for the data

• inner class:

  1 2 3 4 5 6 7 8 9 10

  class Res{ int size; int lower; int upper; Res(int size, int lower, int upper){ this.size = size; this.lower = lower; this.upper = upper; } }

• main method:

  1 2 3 4 5

  public int largestBSTSubtree(TreeNode root) { if(root==null) return 0; dfs(root); return max; }

• dfs treversal

  1 2 3 4 5 6 7 8 9 10 11 12

  private Res dfs(TreeNode root){ //fullfill the tree rule but the size = 0 if(root==null) {return new Res(0, Integer.MAX_VALUE, Integer.MIN_VALUE);} Res left = dfs(root.left); Res right = dfs(root.right); //not fullfill the tree rule and size = -1 and the lower and upper is 0; if(left.size==-1 || right.size == -1 || root.val <= left.upper || root.val >= right.lower) return new Res(-1, 0, 0); int size = left.size + 1 + right.size; max = Math.max(size, max); return new Res(size, Math.min(left.lower, root.val), Math.max(right.upper, root.val)); }

the other way is to use parent as para in the dfs instead of use max and min value.

Leetcode.98 Validate the BST tree

DFS search

1
2
3
4
5
6
7
8
9
10

public class Solution{
    public boolean isValidBST(root, long minVal, long maxVal){
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean isValidBST(TreeNode root, long minVal, long maxVal){
        if(root==null) return true;
        if(root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}

For example design a payment system for New York’s MTA. Tell how you would handle thousands of requests per second. Also how will you handle the different notifications systems such as text alert. How would you handle faults? Was asked this on an onsite round.

https://leetcode.com/discuss/interview-question/system-design/305388/design-a-transportation-payment-system

One solution

Basically you need to build two services, one to handle payment and one to handle notifications (can be email, whatsapp, text, etc.).

Payment system’s responsibility to only deduct the payment using any of the payment gateways and call notification service to notify client. Payment needs to be done real-time and you have to handle client request through some HTTP API, so that you can show gateway page, amount, confirmation etc. After user consent is given you process the payment and queue a message to notification system to send alert. For payments, you can use any noSQL database, since we don’t have any relation as such and you get fast read/write.

Notification service’s responsibility to notify users through channels. Notifications can be near realtime, so you can make use of queue/worker, so that you can autoscale your workers whenever there are more messages in queue. Workers are responsible for sending alerts. More workers you have, faster you process notifications to users. You can even distinguish different workers for different communication channel and scale them separately. As database you can use any noSQL, cause I don’t see any relation as such.

You should ask more specific questions to interviewer during system design rounds to understand the scenario better.

• Replies
  using SQL or noSQL

• For payments it needs to be SQL . you want to maintain consistency in such highly atomic operations.

• Need backup servers and replica in case some application servers or database severs fail.

1. Most common one, Use parent and child div as well as text-align: center

first, enclose the div you want to center with a parent element(wrapper or containner) second, set the text-align: center to the parent element.

• third, set the target div to display: inline-block.

By default, the div dispaly property is block, which will span the div to the whole
width of the page. By setting the display to inline-block, it ensure the div to the width which we set.

1
2
3
4
5
6
7
8
9
10

.blue-square-container {
  text-align: center;
}

.blue-square {
  background-color: #0074D9;
  width: 100px;
  height: 100px;
  display: inline-block;
}

Margin Auto Method

• do not need a parent element.

  simply apply “margin: 0 auto” to our yellow box, as long as we have a defined width.

• “margin: 0 auto” is shorthand for setting the top and bottom margins to zero, and the left and right margins to auto.

The width is important, since without the width defined, the browser will not
able to render the left and right margins to center the element. By setting the width the vbrowser will automatically distribute the right amount of margin on either side of the element.

The “0” portion can be set to any number of pixels you want for the top and bottom margins.

1
2
3
4
5
6

.yellow-square {
  background-color: #FFDC00;
  width: 100px;
  height: 100px;
  margin: 0 auto;
}

Another cool trick is just setting either margin-left to auto or margin-right to auto, which allows us to push our div to either the right or left side of the page, respectively (give this a try!).

Absolute Positioning Method

Absolute positioning an element allows us to essentially place the element wherever we want it on the page…with one drawback.

Absolute positioning removes the element from the flow of the page.

there are three steps we need to remember:

• 1.Set the element’s position property to absolute
• 2.Apply “left: 50%” to the element
• 3.Set a margin-left of half of the element’s width(negative adjust)

1
2
3
4
5
6
7
8

.green-square {
  background-color: #3D9970;
  width: 100px;
  height: 100px;
  position: absolute;
  left: 50%;
  margin-left: -50px;
}

Transform/Translate Method

*Up until now we’ve only dealt with centering things horizontally, but what if we want to put something right in the middle of the page? both horizontally and vertically.

• transform property set as translate can shift the x and y axios.

so the code like this, set both the left and top edge to 50%; and shift negative -50% for both sides.

1
2
3
4
5
6
7
8
9

.red-square {
  background-color: #FF4136;
  width: 300px;
  height: 300px;
  position: absolute;
  left: 50%;
  top: 50%;
  transform: translate(-50%, -50%);
}

By setting the top property to 50% as well, I’m telling the browser to line up the top edge of our red square with the middle of the page vertically. But like in the previous example, we don’t want the edges to be lined up with the center, we want the center of our square to fit right on top of the center of our page.

There are many cool things you can do with transform, such as translating, rotating, and scaling animations, but for this example, we’ll be using translate.

We give the transform property “transform: translate(-50%, -50%)” and voila!

Our red square is centered both horizontally and vertically!

I love this method, because regardless of what the width or the height of our element is, it will always be in the center of the page.

This method is used frequently in responsive design and doesn’t require margins to be defined, like in the absolute positioning method.

Flexbox Method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

html,
body {
  height: 100%;
}

.purple-square-container {
  height: 100%;
  display: flex;
  align-items: center;
  justify-content: center;
}

.purple-square {
  background-color: #B10DC9;
  width: 300px;
  height: 300px;
}

The four steps to centering horizontally and vertically with Flexbox are the following:

• HTML, body, and parent container need to have a height of 100%
• Set display to flex on parent container
• Set align-items to center on parent container
• Set justify-content to center on parent container

Setting display to flex on the parent defines it as a flex container.

By setting align-items to center, we’re saying that the children or flex items are to be centered vertically within the parent.

Justify-content works in the same way, but in the horizontal direction for our example.

This method goes well because again, it’s both responsive and doesn’t require any margin calculations.

A tutorial about flexbox

source link

Why?

• Use redux-starter-kit to general boilerplate code for redux to faster the development for react app.

  setup store is anoying

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

  import { applyMiddleware, compose, createStore } from 'redux'; import { composeWithDevTools } from 'redux-devtools-extension'; import thunkMiddleware from 'redux-thunk' import monitorReducersEnhancer from './enhancers/monitorReducers'; import loggerMiddleware from './middleware/logger'; import rootReducer from './reducers' export default function configureStore(preloadedState) { const middlewares = [loggerMiddleware, thunkMiddleware]; const middlewareEnhancer = applyMiddleware(...middlewares); const enhancers = [middlewareEnhancer, monitorReducersEnhancer]; const composedEnhancers = composeWithDevTools(...enhancers); const store = createStore(rootReducer, preloadedState, composedEnhancers); if (process.env.NODE_ENV !== 'production' && module.hot) { module.hot.accept('./reducers', () => store.replaceReducer(rootReducer)); } return store; }

1. typically you will first create the const action type and action creaters in two different file2.
   For example: you have a container component that has a button that when clicked, dispatches an action thru a bound action creator. To see how Redux handles this action (e.g. state changes via reducer and side effect via middleware), you would typically do the following steps:

Go to the file where the action creator was defined and see what action type constant is being used.
Go to the reducer file where the action type constant you found in the previous step is being used and see how the action is being handled via the switch statement in your reducer.
If you have a middleware like redux-saga, you would go to the saga file and also look for the the action-type constant and see how the action is being handled. Also in this file, you would normally see both the action type constant and action creator being imported.

two seperate files for action type and creaters

the first steps const and creaters is anoying, right?

What if you could skip step one and just use your action creator to handle an action in your reducers and middleware? What if you could reduce the amount of files that are being imported/used and just have one file that represents an action?

Problem Touching 4 files to implement a simple state

Have you added a state in your component using redux and you end up touching constants.js, actions.js, reducer.js and container-component.js? What more if you have a middleware for side-effect like saga?

This process can be tedious for implementing things that are so simple. Also, having too many files just make your code fragmented that it ends up difficult to reason about.

What if you could increase cohesion by bundling these pieces together into an isolated, self-contained module?

What?

Addressing Problems above with Redux Starter Kit
Redux Starter Kit is a library created by the same team who maintains Redux, and it offers a set of tools to make using Redux easier. Now, let’s see how this library can solve the 3 problems we mentioned above.

How?

• configureStore
  Redux Starter Kit has a configureStore function that abstract a lot of boilerplate code (like we had on Problem #1) and adds some defaults to make setting up a Redux store a breeze

Setup store will be like:

1
2
3
4
5
6

import { configureStore } from 'redux-starter-kit';
import rootReducer from './reducers';

const store = configureStore({ reducer: rootReducer }); 

export default store;

configureStore also allows you to pass some options so you could customize your store:

1
2
3
4
5
6
7
8
9
10
11

import { configureStore, getDefaultMiddleware } from 'redux-starter-kit';
import monitorReducersEnhancer from './enhancers/monitorReducers'; 
import loggerMiddleware from './middleware/logger';
import rootReducer from './reducers';

const store = configureStore({ 
   reducer: rootReducer, 
   middleware: [loggerMiddleware, …getDefaultMiddleware()],
   preloadedState, 
   enhancers: [monitorReducersEnhancer],
});

• createAction

This library has a createAction function that combines action type and action creator declarations into one, so you don’t have to create 2 separate files (constant.js and some-action.js).

This function returns an action creator that exposes a .type property so you can use it in your reducer and middleware to handle dispatched action. Here is an example of have you would create an action creator using createAction and how you can use the .type property in a reducer and saga:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// todo-actions.js
import { createAction } from 'redux-starter-kit';

// Create an action creator
export const addTodo = createAction('TODO/ADD_TODO');


// todo-reducers.js
import { addTodo } from './todo-actions';

export function todosReducer(state = [], action) {
  switch(action.type) {
    // Use the action creator's type property to handle action
    case addTodo.type: 
      return state.concat(action.payload);   
    default: 
      return state;
    }
}


// todo-sagas.js
import { addTodo } from './todo-actions';

function* addTodoSaga({ payload }) {
  // Some side effects
}

// Use the action creator's type property to handle action
export default takeLatest(addTodo.type, addTodoSaga);
By getting rid of the constant file for your action type, we reduce the amount of mappings we have to make between your React component and your Redux files when debugging. Plus, less files to import!

* Solution to Problem #3 — createSlice

Redux Starter Kit has a createSlice that allows you to put together pieces in Redux that are logically related to each other into a module.

Think of it as putting together pieces that works on a slice of state in the Redux state tree.

Example:

import { createSlice } from ‘redux-starter-kit’;

const todoSlice = createSlice({
slice: ‘todos’,
initialState: [],
reducers: {
addTodo(state, action) => [ …state, action.payload],
removeTodo(state, action) => state.filter(todo => todo !== action.payload),
},
});

// Extract the action creators object and the reducer
export const { actions, reducer } = todoSlice;

// Export the reducer, either as a default or named export
export default reducer;
`

Isn’t that better than creating 4 files for just a single state?

To know more about the concept behind createSlice, take a look at the “Redux Ducks” pattern.
https://github.com/erikras/ducks-modular-redux

Max Consecutive One serials

Find the longest consective subarray
Time: O(n) Space: O(1) max and cur_max

*Leetcode.485 findMaxConsecutiveOnes

1
2
3
4
5
6
7

public int findMaxConsecutiveOnes(int[] nums){
	int max, cur_max;
	for(int i = 0; i < nums.length; i++){
		max = Math.max(max, cur_max= nums[i]==0?0:cur_max+1);
	}
	return max;
}

Leetcode.487 findMaxConsecutiveOnesII

• condition: if you can flip at most one 0.
• Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can’t store all numbers coming from the stream as it’s too large to hold in memory. Could you solve it efficiently?

1
2
3
4
5
6
7
8
9
10
11
12
13

public int findMaxConsecutiveOnesII(){
	int max = 0, zero = 0;
	for(int l = 0, h = 0; h < nums.length; h++){
		if(nums[h] == 0) zero++;
		while(zero > 1){
			if(nums[l++]==0){
				zero--;
			}
		}
		max = Math.max(max, h-l+1);
	}
	return max;
}

Leetcode.1004 findMaxConsecutiveOnesIII

• condition: if you can flip at most k times.

  1 2 3 4 5 6 7 8 9 10 11 12

  public int findMaxConsecutiveOnes(int[] nums) { int max = 0, zero = 0, k = 1; // flip at most k zero for (int l = 0, h = 0; h < nums.length; h++) { if (nums[h] == 0) zero++; while (zero > k) if (nums[l++] == 0) zero--; max = Math.max(max, h - l + 1); } return max; }

dfs && stack + merge sort mothodology for the optimal solution

• Analysis
  Implement two stack, one store the value less than target in increase order by inorder dfs.

like the root = [4, 2, 5, 1, 3], target = 3.3 => stack1: 1, 2, 3(top); stack2: 4, 5(top)

so the inorder basically has two version:

• right part, which get larger value. skip small value

1
2
3
4
5
6
7
8
9

private void inorder1(TreeNode root, double target, Stack<Integer> stack){
	if(root==null) return;
	//dfs traversal the right path
	inorder1(root.right, target, stack);
	// if the root value less then target, no need to go deeper since it is bst
	if(root.val <= target) return;
	stack.push(root.val);
	inorder1(root.left, target, stack);
}

• left part, get the small part, skip the bigger one.

  1 2 3 4 5 6 7 8 9

  private void inorder2(TreeNode root, double target, Stack<Integer> stack){ if(root==null) return; //dfs traversal the right path inorder1(root.left, target, stack); // if the root value less then target, no need to go deeper since it is bst if(root.val > target) return; stack.push(root.val); inorder1(root.right, target, stack); }

• Combine those two parts together since just the differ just focus on traversal order

1
2
3
4
5
6
7

private void inorder(TreeNode root, double target, boolean reverse, Stack<Integer> stack){
        if(root == null) return;
        inorder(reverse ? root.right:root.left, target, reverse, stack);
        if((reverse && root.val<=target) || (!reverse && root.val > target)) return;
        stack.push(root.val);
        inorder(reverse ? root.left : root.right, target, reverse, stack);
    }

• Final solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<>();
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        
        inorder1(root, target, s1);
        inorder2(root,target, s2);
        // inorder(root, target, false, s1);
        // inorder(root, target, true, s2);
        
        while(k-- > 0){
            if(s1.isEmpty()) res.add(s2.pop());
            else if(s2.isEmpty()) res.add(s1.pop());
            else if(Math.abs(s1.peek() - target) < Math.abs(s2.peek() - target)) res.add(s1.pop());
            else res.add(s2.pop());
        }
        return res;
    }
    
    private void inorder(TreeNode root, double target, boolean reverse, Stack<Integer> stack){
        if(root == null) return;
        inorder(reverse ? root.right:root.left, target, reverse, stack);
        if((reverse && root.val<=target) || (!reverse && root.val > target)) return;
        stack.push(root.val);
        inorder(reverse ? root.left : root.right, target, reverse, stack);
    }
    
    private void inorder1(TreeNode root, double target, Stack<Integer> stack){
        if(root==null) return;
        inorder1(root.right, target, stack);
        if(root.val<=target) return;
        stack.push(root.val);
        inorder1(root.left, target, stack);
    }
    private void inorder2(TreeNode root, double target, Stack<Integer> stack){
        if(root==null) return;
        inorder2(root.left, target, stack);
        if(root.val>target) return;
        stack.push(root.val);
        inorder2(root.right, target, stack);
    }
}

1. 应用1：异步处理才能应用解耦
   用户注册后发送邮件/短信
   传统:50+50+50
   MQ异步处理：50+5