Reverse Integer

Tags

Math

To check for overflow/underflow, we could check if ret > 214748364 or ret < –214748364 before multiplying by 10.

public int reverse(int x) {
int ret = 0;
while (x != 0) {
// handle overflow/underflow
if (Math.abs(ret) > 214748364) {
return 0;
}
ret = ret * 10 + x % 10;
x /= 10;
}
return ret;
}

String to Integer (atoi)

Tags

Math

To deal with overflow, inspect the current number before multiplication. If the current number is greater than 214748364, we know it is going to overflow. On the other hand, if the current number is equal to 214748364, we know that it will overflow only when the current digit is greater than or equal to 8.

private static final int maxDiv10 = Integer.MAX_VALUE / 10;

public int atoi(String str) {
int n = str.length();
int i = 0;
while (i < n && Character.isWhitespace(str.charAt(i))) i++;
int sign = 1;
if (i < n && str.charAt(i) == '+') {
i++;
} else if (i < n && str.charAt(i) == '-') {
sign = -1;
i++;
}
int num = 0;
while (i maxDiv10 || num == maxDiv10 && digit >= 8) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
num = num * 10 + digit;
i++;
}
return sign * num;
}

Implement strStr()

Tags

Two Pointers

O(nm) runtime, O(1) space – Brute force:

You could demonstrate to your interviewer that this problem can be solved using known efficient algorithms such as Rabin-Karp algorithm, KMP algorithm, and the Boyer- Moore algorithm. Since these algorithms are usually studied in an advanced algorithms class, it is sufficient to solve it using the most direct method in an interview – The brute force method.

public int strStr(String haystack, String needle) {
for (int i = 0; ; i++) {
for (int j = 0; ; j++) {
if (j == needle.length()) return i;
if (i + j == haystack.length()) return -1;
if (needle.charAt(j) != haystack.charAt(i + j)) break;
}
}
}

Valid Palindrome

Tags

Two Pointers

O(n) runtime, O(1) space:

The idea is simple, have two pointers – one at the head while the other one at the tail. Move them towards each other until they meet while skipping non-alphanumeric characters.

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

Evaluate Reverse Polish Notation

Tags

Stack

The optimal approach:
Observe that every time we see an operator, we need to evaluate the last two operands. Stack fits perfectly as it is a Last-In-First-Out (LIFO) data structure.

private static final Set OPERATORS =
new HashSet(Arrays.asList("+", "-", "*", "/"));

public int evalRPN(String[] tokens) {
Stack stack = new Stack();
for (String token : tokens) {
if (OPERATORS.contains(token)) {
int y = stack.pop();
int x = stack.pop();
stack.push(eval(x, y, token));
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}

private int eval(int x, int y, String operator) {
switch (operator) {
case "+": return x + y;
case "-": return x - y;
case "*": return x * y;
default: return x / y;
}
}

Reverse Words in a String

Tags

String

One simple approach is a two-pass solution: First pass to split the string by spaces into an array of words, then second pass to extract the words in reversed order.

We can do better in one-pass. While iterating the string in reverse order, we keep track of a word’s begin and end position. When we are at the beginning of a word, we append it.

public String reverseWords(String s) {
StringBuilder reversed = new StringBuilder();
int j = s.length();
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == ' ') {
j = i;
} else if (i == 0 || s.charAt(i - 1) == ' ') {
if (reversed.length() != 0) {
reversed.append(' ');
}
reversed.append(s.substring(i, j));
}
}
return reversed.toString();
}

Maximum Product Subarray

Tags

Dynamic Programming

Besides keeping track of the largest product, we also need to keep track of the smallest product. Why? The smallest product, which is the largest in the negative sense could become the maximum when being multiplied by a negative number.

Let us denote that:

f(k) = Largest product subarray, from index 0 up to k.
Similarly,

g(k) = Smallest product subarray, from index 0 up to k.
Then,

f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] )
g(k) = min( g(k-1) * A[k], A[k], f(k-1) * A[k] )
There we have a dynamic programming formula. Using two arrays of size n, we could deduce the final answer as f(n-1). Since we only need to access its previous elements at each step, two variables are sufficient.

public int maxProduct(int[] A) {
assert A.length > 0;
int max = A[0], min = A[0], maxAns = A[0];
for (int i = 1; i < A.length; i++) {
int mx = max, mn = min;
max = Math.max(Math.max(A[i], mx * A[i]), mn * A[i]);
min = Math.min(Math.min(A[i], mx * A[i]), mn * A[i]);
maxAns = Math.max(max, maxAns);
}
return maxAns;
}

Find Minimum in Rotated Sorted Array II

Tags

Binary Search

For case where AL == AM == AR, the minimum could be on AM’s left or right side (eg, [1, 1, 1, 0, 1] or [1, 0, 1, 1, 1]). In this case, we could not discard either subarrays and therefore such worst case degenerates to the order of O(n).

public int findMin(int[] A) {
int L = 0, R = A.length - 1;
while (L = A[R]) {
int M = (L + R) / 2;
if (A[M] > A[R]) {
L = M + 1;
} else if (A[M] < A[L]) {
R = M;
} else { // A[L] == A[M] == A[R]
L = L + 1;
}
}
return A[L];
}

Two Sum

Tags

Hash Table

O(n) runtime, O(n) space – Hash table:

We could reduce the runtime complexity of looking up a value to O(1) using a hash map that maps a value to its index.

public int[] twoSum(int[] numbers, int target) {
Map map = new HashMap();
for (int i = 0; i < numbers.length; i++) {
int x = numbers[i];
if (map.containsKey(target - x)) {
return new int[] { map.get(target - x) + 1, i + 1 };
}
map.put(x, i);
}
throw new IllegalArgumentException("No two sum solution");
}

Min Stack

Tags

Data Structure

O(n) runtime, O(n) space – Minor space optimization:

If a new element is larger than the current minimum, we do not need to push it on to the min stack. When we perform the pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the min stack too.

class MinStack {
private Stack<Integer> stack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();

public void push(int x) {
stack.push(x);
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
}

public void pop() {
if (stack.pop().equals(minStack.peek())) minStack.pop();
}

public int top() {
return stack.peek();
}

public int getMin() {
return minStack.peek();
}
}