A list of coding interview questions that I was asked in 2018.

### Statement (leetcode: 791)

Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"


### Solution

String addBinary(String a, String b) {
int i = a.length() - 1, j = b.length() - 1;
int carry = 0;
StringBuilder sb = new StringBuilder();
while (i >= 0 || j >= 0) {
int sum = carry;
if (i >= 0) {
sum += a.charAt(i) - '0';
i--;
}
if (j >= 0) {
sum += b.charAt(j) - '0';
j--;
}
carry = sum / 2;
sb.insert(0, sum % 2);
}
if (carry != 0) sb.insert(0, carry);
return sb.toString();
}

Time O(n) /
Space O(n) StringBuilder

### Extention

What if the given strings can be numbers of any base ?

String addBinary(String a, String b) {
int i = a.length() - 1, j = b.length() - 1;
int carry = 0;
StringBuilder sb = new StringBuilder();
while (i >= 0 || j >= 0) {
int sum = carry;
if (i >= 0) {
sum += a.charAt(i) - '0';
i--;
}
if (j >= 0) {
sum += b.charAt(j) - '0';
j--;
}
carry = sum / 2;
sb.insert(0, sum % 2);
}
if (carry != 0) sb.insert(0, carry);
return sb.toString();
}


## Question 2: cd command

### Statement

Write a function to simluate linux command cd

Example 1:

Input: cur = "/etc", path = "/bin/"
Output: "/bin"

Example 2:

Input: a = "/etc", b = "hadoop"

Example 3:

Input: a = "/etc/hadoop/conf", b = "../../hive"
Output: "/etc/hive"

Example 4:

Input: a = "/etc/hadoop/conf", b = ".././conf"


### Solution

String cd(String cur, String path) {
if (path.startsWith("/")) return path;
Stack<String> stack = new Stack<>();

for (String dir : cur.split("/"))
if (!dir.isEmpty()) stack.push(dir);

for (String dir : path.split("/"))
if (dir.equals("..")) {
if (!stack.isEmpty()) stack.pop();
} else if (!dir.equals(".")) {
stack.push(dir);
}

String res = String.join("/", stack);
return res.startsWith("/") ? res : "/" + res;
}

Time O(n) /
Space O(n) Stack

## Question 3: Custom Sort String

### Statement (leetcode: 791)

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.
S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.
Return any permutation of T (as a string) that satisfies this property.

Example :

Input: S = "cba", T = "abcd"

Explanation:
"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a".
Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.


Note:

• S has length at most 26, and no character is repeated in S.
• T has length at most 200.
• S and T consist of lowercase letters only.

### Solution

public String customSortString(String S, String T) {
int[] dict = new int;
for (char c : T.toCharArray()) {
dict[c - 'a'] += 1;
}
StringBuilder sb = new StringBuilder();

for (char c : S.toCharArray()) {
for (int i = 0; i < dict[c - 'a']; i++)
sb.append(c);
dict[c - 'a'] = 0;
}

for (char c = 'a'; c <= 'z'; c++)
for (int i = 0; i < dict[c - 'a']; i++)
sb.append(c);

return sb.toString();
}

Time O(n) /
Space O(n) StringBuilder

## Question 4: Position of the leftmost one

### Statement

Given a binary matrix (containing only 0 and 1) of order n * n. All rows are sorted already. We need to find position of the left most 1.
Note: in case of tie, return the position of the smallest row number.

Example:

Input matrix
0 1 1 1
0 0 1 1
1 1 1 1  // this row has maximum 1s
0 0 0 0

Output: [2, 0]


### Solution

int[] findPosition(int[][] matrix) {
int r = matrix.length;
if (r == 0) return null;
int c = matrix.length;
if (c == 0) return null;

int[] res = new int[] {};
int j = c - 1;
for (int i = 0; i < r; i++) {
while (j >= 0 && matrix[i][j] == 1) {
j--;
res = new int[] {i, j + 1};
}
}
return res;
}

Time O(r + c) ends on the boundary
Space O(1) /

## Question 5: Validate Binary Search Tree

### Statement (leetcode: 98)

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.
Example 1:

Input:
2
/ \
1   3
Output: true

Example 2:

5
/ \
1   4
/ \
3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.


### Solution

boolean validate(TreeNode node, long min, long max) {
if (node == null) {
return true;
} else {
if (node.val > min && node.val < max) {
return validate(node.left, min, node.val) && validate(node.right, node.val, max);
} else {
return false;
}
}
}

boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

Time O(n) visit all the nodes
Space O(log n) recursice call stack

## Question 6: Search word in the dictionary

### Statement (leetcode: 211)

Design a data structure that supports the following two operations:

class WordDictionary {

/** Initialize data structure */
public WordDictionary()

/** Adds a word into the data structure. */

/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word)
}

bool search(word)


search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:
search("b..") -> true


### Solution

class WordDictionary {
class TrieNode {
TrieNode[] next = new TrieNode;
String word = null;
}

TrieNode root;

public WordDictionary() {
this.root = new TrieNode();
}

/** Adds a word into the data structure. */
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (node.next[c - 'a'] == null) node.next[c - 'a'] = new TrieNode();
node = node.next[c - 'a'];
}
node.word = word;
}

/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
return match(word, 0, root);
}

private boolean match(String word, int i, TrieNode node) {
if (i == word.length()) return node.word != null;

char c = word.charAt(i);
if (c == '.') {
for (TrieNode nextNode : node.next) {
if (nextNode != null && match(word, i + 1, nextNode)) {
return true;
}
}
return false;
} else {
TrieNode nextNode = node.next[c - 'a'];
return nextNode != null && match(word, i + 1, nextNode);
}
}
}

Time O(n) /
Space O(n) node creation
Time O(n) /
Space O(n) recursive call stack

## Question 7: Valid Palindrome

### Statement (leetcode: 125)

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false


### Solution

boolean isValid(char c) {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
}

boolean isPalindrome(String s) {
int i = 0;
int j = s.length() - 1;
while(i <= j) {
if (!isValid(s.charAt(i))) {
i++;
continue;
}
if (!isValid(s.charAt(j))) {
j--;
continue;
}
if (Character.toLowerCase(s.charAt(i)) == Character.toLowerCase(s.charAt(j))) {
i++;
j--;
} else {
return false;
}
}
return true;
}

Time O(n) /
Space O(1) /

## Question 8: Shortest Distance To All Stations

### Statement Given a metro map of London, find the station which is closest to all the others stations.

### Solution (Floyd–Warshall algorithm)

/** graph is a weighted undirected adjacency matrix */
int solve(double[][] graph) {
int n = graph.length;
double[][] dist = new double[n][n];

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}

/** Floyd–Warshall algorithm */
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}

double min = Integer.MAX_VALUE;
int res = -1;
for (int i = 0; i < n; i++) {
double sum = 0
for (double d : dist[i])
sum += d;
if (sum < min) {
res = i;
min = sum;
}
}
return res;
}

Time O(n ^ 3) /
Space O(n ^ 2) /

## Question 9: Equilibrium Point

### Statement (leetcode: 724)

Given an array of integers nums, write a method that returns the “pivot” index of this array.
We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.
If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

Input:
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
The sum of the numbers to the left of index 3 (nums = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Example 2:

Input:
nums = [1, 2, 3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.


### Solution

pivotIndex(int[] nums) {
int sum = 0, leftsum = 0;
for (int x: nums) sum += x;
for (int i = 0; i < nums.length; ++i) {
if (leftsum == sum - leftsum - nums[i]) return i;
leftsum += nums[i];
}
return -1;
}

Time O(n) /
Space O(1) /

## Question 10: Complete Binary Tree

### Statement

Given a complete binary tree in which each node marked with a number in level order (root = 1) and several connections are removed.
Find if the given number is still reachable from the root of the tree.

Example 1:

Input: tree = root, num = 5
1 -> root
/ \
/   \
/     \
/       \
/         \
2           3
/           / \
/           /   \
4     5     6     7
/ \   / \   / \   / \
8   9 10 11 12 13 14 15
Output: false

Example 2:

Input: tree = root, num = 6
1 -> root
\
\
\
\
\
2           3
/ \         / \
/   \       /   \
4     5     6     7
/ \   / \   / \   / \
8   9 10 11 12 13 14 15
Output: true


### Solution

boolean findInCompleteTree(TreeNode root, int n) {

while (n > 1) {
if (n % 2 == 0) {
} else {
}
n /= 2;
}

for (boolean p : path) {
if (p) root = root.left;
else root = root.right;
if (root == null) return false;
}

return true;
}

Time O(log n) /
Space O(log n) /

### Extension (leetcode: 222)

Count the number of node in a complete binary tree.

Example 1:

Input: tree = root
1 -> root
/ \
/   \
/     \
/       \
/         \
2           3
/ \         / \
/   \       /   \
4     5     6     7
/ \   / \   /
8   9 10 11 12
Output: 12

int countInCompleteTree(TreeNode root) {
TreeNode node = root;
int depthLeft = 0;
while (node != null) {
depthLeft++;
node = node.left;
}

node = root;
int depthRight = 0;
while (node != null) {
depthRight++;
node = node.right;
}

return depthLeft == depthRight ?
(1 << depthLeft) - 1 :
1 + countInCompleteTree(root.left) + countInCompleteTree(root.right);
}

Time O(log n * log n) log n calls and each call takes log n to compute depth
Space O(log n) recursive call stack

## Question 11: UTF-8 Encoding

### Statement

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

• For 1-byte character, the first bit is a 0, followed by its unicode code.
• For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

Number of bytes Bits for code point First code point Last code point Byte 1 Byte 2 Byte 3 Byte 4
1 7 U+0000 U+007F 0xxxxxxx
2 11 U+0080 U+07FF 110xxxxx 10xxxxxx
3 16 U+0800 U+FFFF 1110xxxx 10xxxxxx 10xxxxxx
4 21 U+10000 U+10FFFF 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Given a byte array which contains only UTF-8 encoded characters and an integer limit,
return the max number of bytes contains only valid UTF-8 encordings in the first limit bytes.

Example 1:

Input:
stream = | 0xxxxxxx | 110xxxxx | 10xxxxxx | 1110xxxx | 10xxxxxx | 10xxxxxx | 11110xxx | 10xxxxxx ||| 10xxxxxx | 10xxxxxx |
limit = 8

Output: 5

Example 2:

Input:
stream = | 0xxxxxxx | 110xxxxx | 10xxxxxx |
limit = 5

Output: 2


### Solution

int countUTF8Byte(byte[] stream, int limit) {
if (stream.length <= limit) {
return stream.length;
} else {
while (limit > 0 && (stream[limit] & 0xFF) >> 6 == 2) {
limit--;
}
return limit;
}
}

Time O(1) No more than 6 bytes
Space O(1) /

## Question 12: Design Rate limiter

### Statement (inspired by leetcode: 362)

Design rate limiter API based on the count limit per minute and per hour.
The granularity of timestamp is in second if needed.

class RateLimiter {

/** Initialize data structure */
public RateLimiter(long minuteCount, long hourCount)

/** Return true if the function calls exceeded either minuteCount or hourCount, otherwise return false */
public boolean isLimited()
}

RateLimiter rl = new RateLimit(100, 6000);
rl.isLimited() // return false;


### Solution

public class RateLimiter {

class HitCounter {

private int   numBucket;
private int[] time;
private int[] hit;

public HitCounter(int numBucket) {
this.numBucket = numBucket;
this.time = new int[numBucket];
this.hit = new int[numBucket];
}

public void hit(int ts) {
int bucket = ts % this.numBucket;
if (time[bucket] == ts) {
hit[bucket]++;
} else {
time[bucket] = ts;
hit[bucket] = 1;
}
}

public int count(int ts) {
int cnt = 0;
for (int i = 0; i < this.numBucket; i++) {
if (ts - time[i] < this.numBucket) {
cnt += hit[i];
}
}
return cnt;
}
}

private long       minuteLimit;
private long       hourLimit;
private HitCounter minuteCounter;
private HitCounter hourCounter;

public RateLimiter(long minuteLimit, long hourLimit) {
this.minuteLimit = minuteLimit;
this.hourLimit = hourLimit;
this.minuteCounter = new HitCounter(60);
this.hourCounter = new HitCounter(3600);
}

public boolean isLimited() {
int tsInSec = (int) (System.currentTimeMillis() / 1000);
if (this.minuteCounter.count(tsInSec) < this.minuteLimit &&
this.hourCounter.count(tsInSec) < this.hourLimit) {
minuteCounter.hit(tsInSec);
hourCounter.hit(tsInSec);
return false;
} else {
return true;
}
}

public static void main(String[] args) throws InterruptedException {
RateLimiter rl = new RateLimiter(10, 600);
int count = 0;
while (true) {
if (rl.isLimited()) {
break;
} else {
count++;
System.out.println("Limit not reached: " + count);
}
}
System.out.println("Limit exceeded: " + count);
}
}

Time O(1) /
Space O(n) number of the buckets
Time O(n) number of the buckets
Space O(n) number of the buckets

## Question 13: Design Task Scheduler (cron)

### Statement

Implement the following 3 methods. Start with scheduling part and then execution part.

public class CronScheduler {

Reference: java.util.Timer and java.util.TimerTask
// TODO