A list of coding interview questions that I was asked in 2018.
Question 1: Add Binary
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();
}
| Complexity | Comments | |
|---|---|---|
| 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"
Output: "/etc/hadoop"
Example 3:
Input: a = "/etc/hadoop/conf", b = "../../hive"
Output: "/etc/hive"
Example 4:
Input: a = "/etc/hadoop/conf", b = ".././conf"
Output: "/etc/hadoop/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;
}
| Complexity | Comments | |
|---|---|---|
| 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"
Output: "cbad"
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[26];
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();
}
| Complexity | Comments | |
|---|---|---|
| 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[0].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;
}
| Complexity | Comments | |
|---|---|---|
| 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);
}
| Complexity | Comments | |
|---|---|---|
| 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. */
public void addWord(String 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)
}
void addWord(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:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Solution
class WordDictionary {
class TrieNode {
TrieNode[] next = new TrieNode[26];
String word = null;
}
TrieNode root;
public WordDictionary() {
this.root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
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);
}
}
}
| add | Complexity | Comments |
|---|---|---|
| Time | O(n) | / |
| Space | O(n) | node creation |
| search | Complexity | Comments |
|---|---|---|
| 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;
}
| Complexity | Comments | |
|---|---|---|
| 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;
}
| Complexity | Comments | |
|---|---|---|
| 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[3] = 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;
}
| Complexity | Comments | |
|---|---|---|
| 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) {
List<Boolean> path = new LinkedList<>();
while (n > 1) {
if (n % 2 == 0) {
path.add(0, true);
} else {
path.add(0, false);
}
n /= 2;
}
for (boolean p : path) {
if (p) root = root.left;
else root = root.right;
if (root == null) return false;
}
return true;
}
| Complexity | Comments | |
|---|---|---|
| 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);
}
| Complexity | Comments | |
|---|---|---|
| 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;
}
}
| Complexity | Comments | |
|---|---|---|
| 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) {
Thread.sleep(1000);
if (rl.isLimited()) {
break;
} else {
count++;
System.out.println("Limit not reached: " + count);
}
}
System.out.println("Limit exceeded: " + count);
}
}
| hit | Complexity | Comments |
|---|---|---|
| Time | O(1) | / |
| Space | O(n) | number of the buckets |
| count | Complexity | Comments |
|---|---|---|
| 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 {
void schedule(TimerTask task, long delay) {}
void repeat(TimerTask t, long delay, long period) {}
void daily(TimerTask t, long delay) {}
}
Solution
Reference: java.util.Timer and java.util.TimerTask
// TODO