Kubernetes version 1.13.2

Helm 3 removes the Tiller server, see this post

This blog primarily talks about Tiller server, especially creating service account and cluster role binding for it. 还有一种解决办法是Tillerless, 将Tiller server 运行在本地的container中，见我的 <<Helm Quick Start>>

Zen uses Helm to install in ICP4D cluster. Helm is a tool for managing Kubernetes charts. Charts are packages of pre-configured Kubernetes resources. Think of Helm like apt(deb), yum(rpm), homebrew for Kubernetes.

Resource

Helm Git Repos

Download Helm Installer

Download the Latest release from Helm Release. For example in Linux, we use:

1

Linux amd64 (checksum / 9f50e69cf5cfa7268b28686728ad0227507a169e52bf59c99ada872ddd9679f0)

Helm needs to be put in the control node that already configured with kubectl.

Untar the file and you can move helm binary to one of the exectuable path, such as /usr/local/bin:

1
2

# which helm
/usr/local/bin/helm

Deploy Tiller Server

Helm client needs to talk to Tiller server, which will be deploied in the K8s cluster.

Most cloud providers enable a feature called Role-Based Access Control - RBAC for short. If your cloud provider enables this feature, you will need to create a service account for Tiller with the right roles and permissions to access resources.

From here, you need to create a cluster role binding which specifies a role and a service account name that have been set up in advance rbac-config.yaml:

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

apiVersion: v1
kind: ServiceAccount
metadata:
  name: tiller
  namespace: kube-system
---
apiVersion: rbac.authorization.k8s.io/v1
kind: ClusterRoleBinding
metadata:
  name: tiller
roleRef:
  apiGroup: rbac.authorization.k8s.io
  kind: ClusterRole
  name: cluster-admin
subjects:
  - kind: ServiceAccount
    name: tiller
    namespace: kube-system

Then install Helm:

1
2

kubectl create -f rbac-config.yaml
helm init --service-account tiller --history-max 200

If you forget to create service account and cluster role binding before you initiate Helm, no worries, create rbac-config.yaml objects and patch it by:

1

kubectl patch deploy --namespace kube-system tiller-deploy -p '{"spec":{"template":{"spec":{"serviceAccount":"tiller"}}}}'

Then check Tiller pod is running:

1
2
3
4

kubectl get pods -n kube-system -l app=helm

NAME                             READY   STATUS    RESTARTS   AGE
tiller-deploy-845fb7cfc6-rn4nq   1/1     Running   0          20h

Now, we are in good shape, actually I can config SSL/TLS between Helm and Tiller, not covered in this blog.

Uninstall Tiller Server

There are 2 ways to uninstall:

1
2

helm reset
helm delete deploy tiller-deploy -n kube-system

OpenShift version: 3.10

There are by default 7 SCCs in OpenShift, but that may not satisfy the demands and it’s better to create a new dedicated one to use for non-root deployment.

To get basic understand about SCC, see my blog <<OpenShift Security Context Constraint>>.

7 default existing SCCs are:

1
2
3
4
5
6
7
8
9
10

oc get scc

NAME               PRIV      CAPS      SELINUX     RUNASUSER          FSGROUP     SUPGROUP    PRIORITY   READONLYROOTFS   VOLUMES
anyuid             false     []        MustRunAs   RunAsAny           RunAsAny    RunAsAny    10         false            [configMap downwardAPI emptyDir persistentVolumeClaim projected secret]
hostaccess         false     []        MustRunAs   MustRunAsRange     MustRunAs   RunAsAny    <none>     false            [configMap downwardAPI emptyDir hostPath persistentVolumeClaim projected secret]
hostmount-anyuid   false     []        MustRunAs   RunAsAny           RunAsAny    RunAsAny    <none>     false            [configMap downwardAPI emptyDir hostPath nfs persistentVolumeClaim projected secret]
hostnetwork        false     []        MustRunAs   MustRunAsRange     MustRunAs   MustRunAs   <none>     false            [configMap downwardAPI emptyDir persistentVolumeClaim projected secret]
nonroot            false     []        MustRunAs   MustRunAsNonRoot   RunAsAny    RunAsAny    <none>     false            [configMap downwardAPI emptyDir persistentVolumeClaim projected secret]
privileged         true      [*]       RunAsAny    RunAsAny           RunAsAny    RunAsAny    <none>     false            [*]
restricted         false     []        MustRunAs   MustRunAsRange     MustRunAs   RunAsAny    <none>     false            [configMap downwardAPI emptyDir persistentVolumeClaim projected secret]

Don’t forget to examine SCC, such as oc describe scc privileged.

SCC Yaml Demo

How to write SCC yaml and what does each field mean? OpenShift SCC official

Create a file named as scc-customized.yaml, carefully fill the value to satisfy the demands

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

kind: SecurityContextConstraints
apiVersion: v1
metadata:
  name: scc-customized
## permission
allowPrivilegedContainer: false
allowHostIPC: true
allowHostNetwork: true
allowHostPID: true
allowHostPorts: true
#allowedFlexVolumes: null
## linux capabilities, some pods require these
allowedCapabilities:
- SYS_NICE
- IPC_OWNER
- SYS_RESOURCE
requiredDropCapabilities: []
defaultAddCapabilities: []
## strategies
runAsUser:
  type: MustRunAsNonRoot
seLinuxContext:
  type: RunAsAny
fsGroup:
  type: RunAsAny
supplementalGroups:
  type: RunAsAny
## who can access this SCC
users: []
groups:
- system:authenticated
## may narrow down insteaf of `*`
volumes:
- '*'

1

oc create -f scc-customized.yaml

Then, for example, you can bind default service account to this SCC:

1

oc adm policy add-scc-to-user scc-customized system:serviceaccount:<project>:default

A default service account is used by all other pods unless they specify a different service account.

Let’s see how to grant a regular user sudo privilege, this is summaried from process to use regular user instead of root. Use of sudo does not require access to the superuser’s password. If Authenticating, using sudo requires the user’s own password.

Say, there is a regular user named guest, the simplest way is to edit sudoers file solely, run as root user:

1

visudo

Append this line after root user field

1
2
3

# root    ALL=(ALL)       ALL
# 如果需要仅仅开放某些命令，这里可以进行调整
guest ALL=(ALL)       ALL

Then user guest can run sudo free.

Another way is adding guest user to wheel group then give this special group password-less sudo privilege.

why uses wheel? Because sometimes I also need grant su password-less to the user, wheel group is easy for both. See my blog <<Linux PAM Module Configuration>>

Run as root user, add guest to wheel group:

1

usermod -a -G wheel guest

Then edit sudoers file

1

visudo

Comment and uncomment like this:

1
2
3
4
5

## Allows people in group wheel to run all commands
#%wheel ALL=(ALL)       ALL

## Same thing without a password
%wheel  ALL=(ALL)       NOPASSWD: ALL

I was previously working on a separate branch branch-tmp, now I want to merge some files in that branch into my main personal branch chengdol_master, and finally create a pull request to merge int master.

Resource

Git tip: How to “merge” specific files from another branch Interactive merge

Solution

Notice that in my case, the target files in branch-tmp are completely applicable for chengdol_master, so I just want to overwrite corresponding files in chengdol_master. If we need to pick some changes and leave others in the file, do an interactive merge, run this from chengdol_master:

1

git checkout --patch brach-tmp <relative path to target file>

First check if you have origin/branch-tmp locally

1

git branch -r | grep branch-tmp

If not, you need to fetch it alone or fetch all origin branches:

1
2

git fetch origin branch-tmp
git fetch origin

Then go to your target branch chengdol_master, use git checkout command to do the job:

1

git checkout origin/branch-tmp <relative path to target file>

then the merged files from branch-tmp are in staging phase, you can directly commit or unstage them in the chengdol_master branch, then push and handle the pull request.

TO-DO

0. hiring season, internal reference
1. position: backend developer, DevOps, Infra
2. system design from x code in my laptop? baidu cloud?
3. company series, buy x code or leetcode?
4. resume project chat
5. blog review

Data Structure

java Integer notation, see this post:

1
2
3
4

// 10^9
int a = (int)1e9;
int a = (int)Math.pow(10, 9);
int b = 2_000_000_000;

Class features

basic structure and syntax nested class, inner class static class private public protected

LRU

LRU除了可以使用自定义的double linked list去实现，也可以用Java API LinkedHashMap，在constructor中指定参数:

1
2
3
4
5
6
7
8
9
10

// 设置capacity
int CAPACITY = 10;
// true表示自动实现LRU功能
LinkedHashMap<String, Integer> lru = new LinkedHashMap<>(CAPACITY, 0.75f, true){
  // override
  protected boolean removeEldestEntry​(Map.Entry<String, Integer> eldest)
  {
    return size() > CAPACITY;
  }
}

如此一来，可以直接使用put(), get()即可，其他不用操心，当达新增的量超过capacity时会自动删除least recently used item.

此外，如果不使用这个special constructor new LinkedHashMap<>(CAPACITY, 0.75f, true)，则linked list中的顺序是insertion order，即最先insert的在前面，最近的在后面，如果用keySet() iterator是按照linked list的顺序出来的，即最先insert的先出来。

经过试验发现，LRU声称的access order，都是insertion order的顺序，只不过LRU实现每次会自动把最新活动的元素重新放到linked list最后， 然后超出capacity时，把least recently used one删除了.

Pair class

https://docs.oracle.com/javase/8/javafx/api/javafx/util/Pair.html https://www.baeldung.com/java-pairs

1

import javafx.util.Pair;

https://www.geeksforgeeks.org/pair-class-in-java/

input method

Deque

如果把Deque既当stack又当queue, 不要使用他们的native method，用能明确指出操作位置的method:

1
2
3
4
5
6
7

addLast(x)
removeLast()
peekLast()

addFirst()
removeFirst()
peekFirst()

如果只充当stack or queue之一，则可以用native method:

1
2

stack: push, pop
queue: add, poll

Segment Tree

https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

1
2
3
4
5
6
7
8
9
10

// get min value >= x
// 返回的都是整数，但是是double type
Math.ceil(double x)
// get max value <= x
// 返回的都是整数，但是是double type
Math.floor(double x)
// log e of x
Math.log(double x)
// calculate log2
Math.log(x) / Math.log(2)

Complete binary tree number of nodes: 2^height - 1 (height start from 1) For segment tree, number of nodes:

1
2
3
4

// n is the length of array
int h = (int)Math.ceil(Math.log(n) / Math.log(2));
int maxSTSize = 2 * (int)Math.pow(2, h) - 1;
int[] st 

Or you can define class Node to build segment tree.

List

• LinkedList is doubly-linked!
• change array to list

1

List<Integer> list = Arrays.<Integer>asList(1, 2, 3, ...);

but this is fixed size list backed by array, you can create a new one:

1

List<Integer> list = new ArrayList<Integer>(Arrays.<Integer>asList(1,2,3, ...));

use slow-fast pointer to find middle of linkedlist or find cycle

1
2
3
4
5
6

ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// when loop break, slow is in middle

reverse the linked list: https://leetcode.com/problems/reorder-list/submissions/

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

// 1->2->3->4
// 1<-2<-3<-4
ListNode pre = null;
ListNode cur = <node 1>;
while (cur != null)
{
    ListNode next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
}
// 注意这里不要弄错了
ListNode newHead = pre;

PriorityQueue

Priority queue has contains(object) and remove(object) method, but that will take O(n) time.

如果要构造比较整数大小的priority queue

1
2

// if use (a, b) -> a - b, this may overflow when encounter MAX MIN
Queue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(a, b));

注意priorityQueue iterator返回的是random order!

String

String: immutable StringBuilder: mutable, not thread safe StringBuffer: mutable, thread safe

注意"\t", "\n"在string中只相当于一个长度！！！

“abcdefg” substring 是连续的: “cdef” subsequence可以不连续，但顺序要一致: “abdf”

1
2
3
4
5
6
7
8
9

String str = new String("123");
String str = "123";
// convert number 123456 to string "123"
String str = String.valueOf(123456);
str.length();
// use + to concatenate
str1 + str2
// string compare
str1.compareTo(str2);

when do replace

1
2
3
4

String str = "a.b.c.d";
str.replace(".", ""); // get "abcd"
// don't use str.replace('.',''), cannot be empty char
// there is no regex, just CharSequence type

if just want to create a string using other type:

1

"" + other type

caution:

1
2
3
4
5
6

String a = "1.2.3.";
// a.split("\\.") will get length of 3, it will ignore last '.'
String a = ".1.2.3";
// a.split("\\.") will get length of 4, it will not ignore first '.'
String b = "1..2.3";
// b.split("\\.") will get length of 4, it will not ignore consecutive '.'

Notice the parameters format

1
2
3
4
5
6

indexOf(int ch, int startIndex)
split(String reg)

// returns the index within this string of
// the last occurrence of the specified character.
int lastIndexOf​(int ch)

StringBuilder

1
2
3
4
5
6
7
8
9

StringBuilder sb = new StringBuilder(String);
sb.append(x);
// insert in head
sb.insert(0, x);
sb.toString();
// return stringbuilder
sb.reverse();
// stringbuilder does not implement equals method!!
sb.equals(another stringbuilder object); // wrong!!

more methods:

1
2
3
4
5
6
7

// return String
// 这里只有一个参数的时候是start index!
substring(int startidx)
// [start end)
substring(int startidx, int endidx) 
append(lot of types)
setLength(int len)

Character

1
2
3
4
5
6
7
8

// return Character
Character.valueOf(char)
//return char
c.charValue()

// actually the convert is auto like int and Integer!
char c1 = new Character('a');
Character c1 = 'b';

char compare in if use == if use ± with char, such as ch - 'a', don’t forget (char)(ch)

check letter:

1
2
3

Character.isDigit(ch);
Character.toLowerCase(ch);
Character.isLetterOrDigit(ch);

Non-ASCII character (> 256):

1

Character.toString((char)342)

3 items if expression

1
2
3

// I forget the precedence
// this will first 1 + 2 + 3 then compare with 3!
1 + 2 + 3 == 3? true: false

Enhenced for Loop

1
2
3
4
5

// enhanced for loop
for (Character ch : str.toCharArray())
{
  ...
}

Collection

convert list to array

1
2
3

// result is List<int[]> type
// think about it
result.toArray(new int[result.size()][]);

convert Integer list to int array (from Java8): https://stackoverflow.com/questions/718554/how-to-convert-an-arraylist-containing-integers-to-primitive-int-array

1

int[] arr = list.stream().mapToInt(i -> i).toArray();

also from int array to Integer list https://stackoverflow.com/questions/1073919/how-to-convert-int-into-listinteger-in-java

1

List<Integer> list = Arrays.stream(ints).boxed().collect(Collectors.toList());

这个是Java stream的知识点

Array

1
2
3
4
5
6
7

// one dimension
int[] arr = new int[]{1,2,3};
int[] arr = new int[4]; // default value is 0
// two dimensions
int[][] arr = new int[3][4]; // 3 rows 4 columns
int[][] arr = new int[3][]; // still ok, you can init one dimension array later
int[][] arr = new int[][]{{1,2,3}, {4,5}, {6,7,8,9}}; // each one dimension array can have different length!

Let’s see char array

1

char[] arr = str.toCharArray();

Use sort static method, if you want to use comparator, see my lambda section

1
2
3

Arrays.sort(E[] e);
// also for collections
Collections.sort(List<xx> l);

Arrays.sort(int[]) primitive type是不能自己写comparator的！

数组内容字符串化用:

1
2
3
4
5

int[] a = new int[]{1,2,3,4,5};
// correct!
Arrays.toString(a);
// wrong! 这个返回id string
a.toString()

Shuffle arrays: Every permutation of array element should equally likely: https://www.geeksforgeeks.org/shuffle-a-given-array-using-fisher-yates-shuffle-algorithm/ https://introcs.cs.princeton.edu/java/stdlib/StdRandom.java.html

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

// nums[0] swap with element in range [0, n)
// nums[1] swap with element in range [1, n)
// nums[2] swap with element in range [2, n)
public static int[] shuffle(int[] nums)
{
  for (int i = 0; i < nums.length; i++)
  {
    int j = i + rand.nextInt(nums.length - i);
    // swap
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
  }
  return nums;
}

Set

TreeSet operation time complexity, from java TreeSet doc: This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

Map

1

import java.util.*;

HashMap<>() not thread safe HashTable<>(), thread safe but ConcurrentHash…

有时用char[26]（c - 'a'） 或者 int[256] (直接用c即可) 可以用来代替hashmap

1
2
3
4
5
6
7
8

map.containsKey()
// also has contains value method!
map.containsValue()
// return set
map.keySet()
map.entrySet()
// return collection
map.values()

1
2
3
4
5
6

// provide value for new key which is absent 
map.put(key, map.getOrDefault(key, 0) + 1);
// if value is a collection object can use:
map.computeIfAbsent(key, k -> new ArrayList<Stone>()).add(new Stone(x,y));
// remove current key if it's value is val
map.remove(key, val)

Treemap/TreeSet (sorted map) perform all operation based on it’s default/custom comparator! if two key are equal in comparator, should be treated as equal in equals() method! 但如果没有一致，还是按照comparator去做. treemap/treeset.remove(object) 用的是comparator去比较相等！！

range query API:

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

// treemap
tm.ceilingKey(K key)
tm.ceilingEntry(K key)
tm.floorEntry(K key)
tm.floorKey(K key)

tm.firstKey()
tm.firstEntry()
tm.lastKey()
tm.lastEntry()

tm.pollFirstEntry()
tm.pollLastEntry()
// treeset
ts.ceiling(K key)
ts.floor(K key)

ts.first()
ts.last()
// 可以用来模拟pq
ts.pollFirst()
ts.pollLast()

如果要返回map中的任意一个key，比如key是string类型

1

return (String)map.keySet().iterator().next();

this is java syntax, I see it in leetcode https://stackoverflow.com/questions/1958636/what-is-double-brace-initialization-in-java

Exception Handling

1

throw new Exception("xxx");

Random Number Generation

1
2
3
4
5
6

import java.util.Random;
Random rand = new Random();
int randomNum = rand.nextInt((max - min) + 1) + min;
// simply can use this:
// return double, need to force convert to int maybe
Math.random(): [0.00,1.00) 

Lambda Expression

for comparator and comparable, let’s see how to wirte it, this post

原来的方法，在constructor中定义comparator:

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

Queue<Integer> que = new PriorityQueue<>(new Comparator<Integer>(){
      @Override
			public int compare(Integer n1, Integer n2) {
				return Integer.compare(n1, n2);
			} 
});

int[] arr = new int[]{5, 3, 56, 78, 4, 2, 5};
// anonymous class to implement comparator
Arrays.sort(arr, new Comparator<Integer>(){
  public int compare(Integer n1, Integer n2)
  {
    return Integer.compare(n1, n2);
  }
});

1
2
3
4

int[][] arr = {{5,1}, {2,3}};
// sort by the first element of one dimenstional array
Arrays.sort(arr, (int[] a, int[]b) -> a[0] - b[0]);
System.out.println("result= " + Arrays.deepToString(arr));

用lambda构造comparator 时可以用到外部的数据结构？ https://leetcode.com/problems/top-k-frequent-elements/solution/ 比如这个的官方solution

1
2
3

// init heap 'the less frequent element first'
    PriorityQueue<Integer> heap =
            new PriorityQueue<Integer>((n1, n2) -> count.get(n1) - count.get(n2))

其实这里可以使用Map.Entry<> 放入pq中。 count是一个外部定义的hashmap. 这个到底是怎么回事？

Java Memory Management

java heap space, java stack memory Memory Allocation in Java Stack Memory and Heap Space in Java

Java Garbage Collection

you can watch the operting system course video implemented by DFS with marked bit in each object, scan from stack

Why use Deque instead of stack

check this post https://leetcode.com/problems/flatten-nested-list-iterator/discuss/80147/Simple-Java-solution-using-a-stack-with-explanation/165585

I just recently interviewed with 16 different companies in the silicon valley (including FAANG except Netflix) for senior software engineering positions. Here’s my opinion, based on my experience:

Some interviewers will expect you to know why Deque is better than Stack.

Showing mastery of at least one programming language (in this case, Java) can, at worst, score you extra points in the interview, and at best get you the job and even help you get higher compensation or leveling. Getting the optimal solution is the basic requirement to pass an interview. Additionally, you are being benchmarked against other candidates being asked exactly the same question. Lastly, for those targeting senior level positions, the interviewer will also evaluate your seniority. This is one case where I think most interviewers will expect to see that you’ve mastered the Java programming language (if you chose to use it in your interview).

Here are a few reasons why Deque is better than Stack:

Object oriented design - Inheritance, abstraction, classes and interfaces: Stack is a class, Deque is an interface. Only one class can be extended, whereas any number of interfaces can be implemented by a single class in Java (multiple inheritance of type). Using the Deque interface removes the dependency on the concrete Stack class and its ancestors and gives you more flexibility, e.g. the freedom to extend a different class or swap out different implementations of Deque (like LinkedList, ArrayDeque).

Inconsistency: Stack extends the Vector class, which allows you to access element by index. This is inconsistent with what a Stack should actually do, which is why the Deque interface is preferred (it does not allow such operations)–its allowed operations are consistent with what a FIFO or LIFO data structure should allow.

Performance: The Vector class that Stack extends is basically the “thread-safe” version of an ArrayList. The synchronizations can potentially cause a significant performance hit to your application. Also, extending other classes with unneeded functionality (as mentioned in #2) bloat your objects, potentially costing a lot of extra memory and performance overhead.

Tries

string symbol table: specialized to string key. Faster than hashing, flexible then BST recall the structure of tries, very simple! put value in last node (character). put and search method for tries can be recursion implementations. 一般都用的这个。

3-way tries: 这里注意，当前char的值和node char比较，less then go left, larger then go right, then compare, if not match, miss hit. Using recursion to do put and search operation. TST is as fast as hashing (for string key) and space efficient. support in-order traverse (obey BST rule)

Implementation: prefix matching, wildcard match, longest prefix.

Algorithms

Tushar Roy youtube channel princeton algorithms，在youtube or coursera上都有

Time complexity: https://en.wikipedia.org/wiki/Time_complexity usually:

1
2
3
4
5
6
7
8
9

constant O(1)
logarithmic O(logn)
linear O(n)
quasilinear O(nlogn)
quadratic O(n^2), n to the power of 2
cubic O(n^3), n to the power of 3
polynomial O(n^x + n^y + ..)
exponential O(2^n)
factorial O(n!)

Tilde notation: ignore lower order terms, negligible best case, lower bound worst case, upper bound, Big O does this average case, cost for random input, expected cost when upper bound equals lower bound, we get optimal algorithms

tilde notation vs big-O

Prime

LC 886 https://leetcode.com/problems/prime-palindrome/ isPrime是如何检查的，函数记住, 并不是检查每个递增+1的除数是否整除！ 检查特殊的值就可以了 https://en.wikipedia.org/wiki/Primality_test

Monotonic Stack

LC 496 Next Greater Element I LC 503 Next Greater Element II 还有LC 31 next permutation 也是属于monotonic problem, 见这题我的note

Monotonic stack practice: https://medium.com/@vishnuvardhan623/monotonic-stack-e9dcc4fa8c3e

increasing monotonic stack: from stack top to stack bottom is increasing decreasing monotonoc stack: reverse order

General

bit and boolean can use XOR ^ operator!

Sliding Window

相关window问题的template and summary, good sliding window demo

basic sliding window problem leetcode 904 find the longest sequence with at most 2 integers

Quick select

Average O(n), worst case O(n^2), need to shuffle. if quick select Kth element, then in the range [0, K] is guarantee the K smallest elemets in unsorted array.

Summary of top k problem: https://leetcode.com/problems/k-closest-points-to-origin/discuss/220235/

Binary search

how to decide the condition? lo < hi or lo <= hi? hi = mid - 1 or hi = mid? lo = mid + 1 or lo = mid?

when target exists, use

1

while (lo <= hi)

because it will finally concentrate. lo == hi will be the result: hi = mid - 1 or hi = mid? or lo = mid + 1 or lo = mid? does not matter. 对于可能不存在的也用lo <= hi，但要保证hi = mid - 1 和 lo = mid + 1

You use while (start <= end) if you are returning the match from inside the loop. You use while (start < end) if you want to exit out of the loop first, and then use the result of start or end to return the match.

Backtracking

Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, abandons those solutions that fail to satisfy the constraints of the problem at any point of time.

for example: SudoKo N Queens problem, smart at process diagonal row-col and row + col. think recursion as a tree, back and forth.

leetcode summary backtracking about Subsets, Permutations, and Combination Sum

Others

x^y how to describe: x to the power of y x^2: x squard x^3: x cubed

Find rectangle

p1[x,y], p2[x,y] if p1 and p2 are diagonal, check if other 2 points exist, can use hashmap or hashset

Toggle 1 and 0

use xor 1 to toggle 1 and 0

1
2
3

int a = 1
a ^= 1; // a is 0
a ^= 1; // a is 1

calculate power of 2:

1
2
3

Math.pow(2, n); // slow
// or can use shift
1 << n // fast

Union Find

for quick find, all sites in a component must have the same value in id[], directly check id[p] == id[q] for quick union, set the root of pool p to the root of q then improve quick union, compress the path when seach the root:

1
2
3
4
5
6
7
8
9

private int find(int[] uf, int i)
{
  while (uf[i] != i)
  {
    // path compression
    uf[i] = uf[uf[i]];
    i = uf[i];
  }
}

sort

in-place: bobble sort stable selection sort not stable insertion sort stable quick sort not stable heap sort not stable need space: merge sort stable

insertion sort对于partial sorted的数组排序很快。 merge sort O(nlogn) 很稳定，可以用merge sort的思路去divide and conquer解决其他问题 quick sort 最坏O(n^2)，比如排好序的数组，所以需要shuffle: Collections.shuffle(list)

radix sort不是通过comparison机制实现的, leetcode 164

sort one array based on another array

1
2
3
4
5
6
7
8
9
10
11

// sort a based on b
int[] a = new int[]{3,5,7,2,5,78,4,2};
int[] b = new int[]{7,45,2,4,7,78,2,4};

// pair[i][0] = a[i];
// pair[i][1] = b[i];
int[][] pair = new int[a.length][a.length];
Arrays.sort(pair, (a, b) -> a[1] - b[1]);

// or use map <b value: b index>
// the sort b, recreate a using the map mapping

0/1 knapsack

Binary Search Tree

need to know different traverse orders:

• pre-order: current -> display -> left -> right
• post-order: current -> left -> right -> display
• in-order: current -> left -> display -> right, this will get ascending order if traverse a BST.
• out-order: current -> right -> display -> left, this will get descending order if traverse a BST

pre order list can build BST uniquely. (post)pre order + in order can build BT uniquely

threaded binary search tree

LC 99: https://leetcode.com/problems/recover-binary-search-tree/submissions/ video: morris traversal inorder to binary tree: 不用递归的方式，实现constant space的一种traverse https://www.youtube.com/watch?v=wGXB9OWhPTg https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

Undirected graph

vertex and edge matters degree: num of edge connect to a vertex graph API design:

1
2
3
4

addEdge()
Iterable adjacent nodes
numEdge()
numVertex()

How to repesent vertex and it’s edge, here use adjacency list 如果发现graph的node是连续的，比如0 ~ n-1则用adjacency list比较好，否则用Map<Integer, List<Integer>>

1
2
3
4
5
6
7
8
9
10

// generic array
List<Integer>[] adj = (List<Integer>[]) new List[n];
// it seems we can do now:
List<Integer>[] adj =  new List[n];
TreeMap<Integer, Integer>[] tmap = new TreeMap[n];
// init
for (int i = 0; i < n; i++)
{
  adj[i] = new ArrayList<Integer>();
}

actually we can use list of list instead of this format, but array is faster. how to create an array of list

may contains: self-loop parallel edges

BFS

use queue to hold the vertices add all unmarked vertices to queue adjacent to v and mark them

1
2
3

boolean[] marked;
int[] edgeTo;
int[] distTo;

time complexity: O(E + V)

DFS

for example, find exit for maze graph mark vertex has visited recursive (or use stack )visit all unmarked vertices w adjancent to v

1
2

boolean[] marked;
int[] edgeTo;

time complexity: O(E + V)

Bridge

leetcode: 1192 这是一种找bridge的算法: Tarjan algorithm 可以看看这个频道的graph theory playlist: https://www.youtube.com/watch?v=aZXi1unBdJA https://www.youtube.com/watch?v=TyWtx7q2D7Y

Connected components

a connected component is a max pool of connected vertices answer the question: is v and w connected in contact time.

DFS? yes, run DFS for each unvisited vertex, verteice in same connected component has the same id (this can represent component number!), so, check vertex id will get result.

Directed graph

also called digraph outdegree, indegree directed cycle

DAG: directed acyclic graph

Unweighted

without weight on edge, the same for DFS and BFS we use adjacency list the same as undirected graph

1

List<Integer>[] adj;

topological sorting

for example, precedence scheduling at least one vertex has 0 indegree and should be directed acyclic graph (DAG)

BFS: 从indegree为0的node开始，压入队列中，每次下一个node的indegree减1，再把下一批indegree为0的node压入队列中，最后如果没有cycle，所有node都应该被explored.

DFS也可以，但要注意visited用2种记号表示, 0:没有访问，1:当前访问, 2:完全访问。如果在一次DFS中再次遇到了1，则说明有cycle.当完全访问后，再设置成2.

strongly connected component

Strongly connected: there is a path from v to w and w to v as well. skip this topic

Weighted

API design:

1
2
3
4

class DirectedEdge: weight, from, to
class EdgeWeightedDigraph: addEdge(new DirectedEdge(from, to, weight));
distTo(int w);
pathTo(int w);

we still use adjacency list representation:

1
2
3

List<DirectedEdge>[] adj = (List<DirectedEdge>[]) new List[n];
// new init array
List<DirectedEdge>[] adj = new List[n];

Dijkstra

non-negative weight SPT: shortest path tree exist in graph from the source vertex

remember: Use minium priority queue, to choose the next vertex cloest to the source vertex! Then update the path accordingly if it’s shorter than before (如何实现这个degrade呢?) implementation

有几点需要注意：

1. 它没有实现degrade操作，只是又加入了新的元素在pq中，这样旧的就沉到底部了
2. 有一个visited set去控制结束
3. 注意comparator interface是怎么实现的，override了compare method，其实也用不着，在pq初始化的时候可以用lambda去实现。

time complexity of the construct computation: O(ElogV)

Bellman-Ford

no negative cycle

A*

A graph traversal and path search algorithm leetcode 1263

regular expression

leetcode 819 去掉所有非字典字母，然后split每个word组成数组:

1

String[] words = p.replaceAll("\\W+" , " ").toLowerCase().split("\\s+");

OpenShift version: 3.10

I have worked on Kubernetes and OpenShift for several months, both are good container management and schedule tools, they have many overlaps and the kubectl commands are compitable in OpenShift, so what the exactly differences between them are?

我大概是从2018年下半年开始接触OpenShift的，当时要求将部署移植到OpenShift平台上。推荐一本书:<<开源容器云OpenShift 构建基于Kubernetes的企业应用云平台>>，这本书基本上介绍清楚了OpenShift的一些基本操作和概念，也提到了和K8s不同的地方。

A brief Digression: Today IBM officially close the acquisistion of Red Hat!

Resource

OpenShift-wikipedia

1. OpenShift is a family of containerization software developed by Red Hat. Its flagship product is the OpenShift Container Platform, an on-premises platform as a service built around Docker containers orchestrated and managed by Kubernetes on a foundation of Red Hat Enterprise Linux.

The Differences Between Kubernetes and Openshift

1. Kubernetes is the kernel
2. Openshift is the distribution

10 most important differences between OpenShift and Kubernetes

1. OKD can install on rhel and centos
2. Kubernetes is an integral part of OpenShift with more features built around it.
3. OpenShift has more strict security policies than default Kubernetes, most of container images available on Docker Hub or we have built before won’t run on OpenShift, because it forbids to run a container as root. we need to relax this strict to give the workspace higher privileges to run container as root, or update our image to

The Differences Between Kubernetes and Openshift

Using Git everyday and pull push everyday, let’s spend time to undestand the concept origin and upstream fully.

You can edit the upstream and origin in this file for your local repo only:

1
2

# see local config in your repo
vim .git/config

Resource

Difference Upstream and Origin

• upstream generally refers to the original repo that you forked from
• origin is your fork: your own repo on GitHub, clone of the original repo of GitHub

I haven’t noticed the path format when I created tarball, this time the format issue plays as a major blocker.

We use a module tar file to deploy Zen in ICP4D cluster, when I use my customized tar file, I get:

1
2
3
4
5
6
7
8
9

Loading images
/xxx/InstallPackage/modules/./xxx-iisee-zen:1.0.0//images
Loaded Images [==============================================================================] 7m29s (35/35) done
Pushed Images [==============================================================================] 15m17s (35/35) done
Deploying the chart as name xxx-iisee-zen100
Running command: /xxx/InstallPackage/components/dpctl --config /xxx/InstallPackage/components/install.yaml helm rewriteChart -i /xxx/InstallPackage/modules/./xxx-iisee-zen:1.0.0//charts/*.tgz -o /xxx/InstallPackage/modules/./xxx-iisee-zen:1.0.0//charts/updated_xxx-iisee-zen100.tgz
Running command: /xxx/InstallPackage/components/dpctl --config /xxx/InstallPackage/components/install.yaml helm installChart -f /xxx/InstallPackage/components/global.yaml   -r zen-xxx-iisee-zen100 -n zen -c /xxx/InstallPackage/modules/./xxx-iisee-zen:1.0.0//charts/updated_xxx-iisee-zen100.tgz
Starting the installation ...
There was a problem installing /xxx/InstallPackage/modules/xxx-iisee-zen:1.0.0/charts/updated_xxx-iisee-zen100.tgz chart. Reason: chart metadata (Chart.yaml) missing

Let’s highlight the command:

1

Running command: /xxx/InstallPackage/components/dpctl --config /xxx/InstallPackage/components/install.yaml helm rewriteChart -i /xxx/InstallPackage/modules/./xxx-iisee-zen:1.0.0//charts/*.tgz -o /xxx/InstallPackage/modules/./xxx-iisee-zen:1.0.0//charts/updated_xxx-iisee-zen100.tgz

Look carefully there is a ./ in path /xxx/InstallPackage/modules/./xxx-iisee-zen:1.0.0/...., this is because I create tarball use:

1

tar cf xxx-iisee-zen-1.0.0.tar ./xxx-iisee-zen:1.0.0

the ./ will be put in the extract path! which is the trouble maker.

Correct way:

1
2

cd <xxx-iisee-zen:1.0.0 parent folder>
tar cf xxx-iisee-zen-1.0.0.tar xxx-iisee-zen:1.0.0

If we list the tarball contents, no prefix in the file structure:

1
2
3
4
5
6
7
8

tar tvf xxx-iisee-zen-1.0.0.tar

drwxr-xr-x 1001/docker       0 1969-12-31 16:00 xxx-iisee-zen:1.0.0/
drwxr-xr-x 1001/docker       0 2019-07-02 15:13 xxx-iisee-zen:1.0.0/charts/
-rw-r--r-- root/root    245868 2019-07-02 15:12 xxx-iisee-zen:1.0.0/charts/xxx-iisee-zen-1.0.1.tgz
-rw------- 1001/docker    4758 1969-12-31 16:00 xxx-iisee-zen:1.0.0/manifest.yaml
drwxr-xr-x 1001/docker       0 1969-12-31 16:00 xxx-iisee-zen:1.0.0/LICENSES/
...

For more information about tar commands, I have a blob about it already <<Tar Command Daily Work Summary>>

Sometimes if the local working branch messes up but you want to sync up with your remote branch, for example origin master, first remove all untracked files:

1
2
3
4
5

# -d: remove untracked dirs
# -f: force
git clean -df
# -x: remove ignored files as well
git clean -dfx

you can have a dry-run first to see what files will be removed

1
2

# -n: dry run
git clean -dfn

Check the commit logs in current branch:

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

# verbose
# -n: commit number
git log -n 10

# oneline and color
# color: show color
git log --oneline --color -n 10

# -p: show diff for each commit
git log -p --oneline --color -n 10

# show branch relationship
# --graph: show ascii graph
git log --graph --oneline --color -n 10

Then properly select one good commit that also appears in remote master branch, run

1

git reset --hard <good commit hash>

All the commits later than the good commit hash will be removed, then you can just run the command below to sync up remote master branch.

1

git pull origin master

Note that it’s safe to do git reset here because only I use this branch and I want to clean

Sometimes I see people use:

1
2
3
4

# reset to current commit, discard all uncommitted changes
git reset --hard HEAD
# HEAD~1: move to the commit right before HEAD
git reset --hard HEAD~1

HEAD points to your current commit, check by:

1
2

# get HEAD short hash
git rev-parse --short HEAD

so all that git reset --hard HEAD will do is to throw away any uncommitted changes you have and point to your latest commit.