If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
The multiples of 3 are 3,6,9,12,15,18,21,24,27,30,….
The multiples of 5 are 5,10,15,20,25,30,35,40,45,….
The intersection of these two sequences is 15,30,45,…
Code a hashmap which you would be happy to place into a production environment.
We already write 2 post before:
[Question] Implement a HashMap
[CC150v5] 8.10 Implement a Hashmap
But still, this is not an easy question when asked at an interview. It won’t harm to do a little recap:
Given a 2D array with only 1s and 0s, where each row is sorted.
Find the row with the maximum number of 1s. 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
By using a modified version of binary search, we can achieve a O(mLogn) solution where m is number of rows and n is number of columns in matrix.
However, there’s better solution that works in linear time!
Get the index of first (or leftmost) 1 in the first row.
Do following for every row after the first row:
IF the element on left of previous leftmost 1 is 0, ignore this row.
ELSE Move left until a 0 is found. Update the leftmost index to this index and max_row_index to be the current row.
The time complexity is O(m+n).
written by me
public int solution(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int p = n;
int row = -1;
for (int i = 0; i < m; i++) {
// now p is larger than 0, otherwise it's already terminated
if (matrix[i][p - 1] == 0) {
continue;
}
// p points to a 1, now search to the left direction
for (int j = p - 1; j >= 0; j--) {
if (matrix[i][j] == 1) {
p = j;
} else {
break;
}
}
// p have a new value now
if (p == 0) {
return i;
} else {
row = i;
}
}
return row;
}
给一个包含正负整数的数组，要求对这个数组中的数进行重新排列，使得其正负交替出现。首先出现负数，然后是正数，然后是负数。有多余的数的一方，就放在末尾。
如 [1, 2, 3, -4]->[-4, 1, 2, 3]，[1,-3,2,-4,-5]->[-3,1,-4,2,-5]. 要求使用O(1)的额外空间。
如果需要保持正数序列和负数序列各自原来的顺序，如何做？
如果不需要保持正数序列和负数序列各自原来的顺序，如何做？
I only solve this question if we do not have to keep the original ordering.
Basically, 2 pointers search from beginning to end. If there’re more + than -, move the extra positive values to the back of the array. Vice versa.
written by me
public void solve(int[] A) {
int len = A.length;
int neg = 0;
int pos = 1;
while (neg < len || pos < len) {
while (neg < len && A[neg] < 0) {
neg += 2;
}
while (pos < len && A[pos] > 0) {
pos += 2;
}
// neg points to a positive value
// pos points to a negative value
// swap them (if they're valid position)
if (neg >= len && pos >= len) {
return;
} else if (neg >= len) {
// neg is done, there's more - then +
// put all negative values pointed by pos to the back
int right = len - 1;
if (right % 2 == 0) {
right--;
}
while (pos < right) {
while (pos < len && A[pos] > 0) {
pos += 2;
}
while (right >= 0 && A[right] < 0) {
right -= 2;
}
// pos point to a negative value, right to positive value
if (pos > right) {
break;
} else {
swap(A, pos, right);
}
}
return;
} else if (pos >= len) {
// pos is done, there's more + then -
int right = len - 1;
if (right % 2 == 1) {
right--;
}
while (neg < right) {
while (neg < len && A[neg] < 0) {
neg += 2;
}
while (right >= 0 && A[right] > 0) {
right -= 2;
}
if (neg > right) {
break;
} else {
swap(A, neg, right);
}
}
return;
} else {
swap(A, neg, pos);
}
}
}
private void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
Given a list of words, write a program to find the longest word made of other words in the list.
EXAMPLE
Input: cat, banana, dog, nana, walk, walker, dogwalker
Output: dogwalker
Search it recursively from longest to shortest. Use HashSet to help us search for words quickly.
This question might look difficult at first, it’s actually a very classical recursive search.
public static void printLongestWord(String[] arr) {
Arrays.sort(arr, new LengthComparator());
HashSet<String> set = new HashSet<String>();
for (String str : arr) {
set.add(str);
}
for (String word : arr) {
if (canDivide(word, 0, set)) {
System.out.println(word);
return;
}
}
System.out.println("can not find such word");
}
private static boolean canDivide(String word, int from, HashSet<String> set) {
if (from == word.length()) {
return true;
}
for (int i = from; i < word.length(); i++) {
String str = word.substring(from, i + 1);
if (from == 0 && i == word.length() - 1) {
continue;
} else if (!set.contains(str)) {
continue;
}
if (canDivide(word, i + 1, set)) {
return true;
}
}
return false;
}
Given a lengthy document without spaces, punctuation, and capitalization:
eg: iresetthecomputeritstilldidntboot
Now add back in the punctation and capitalization.
Most of the words will be in a dictionary, but some strings, like proper names, will not. Given a dictionary (a list of words), design an algorithm to find the optimal way of “unconcatenating” a sequence of words (by minimizing unrecognized sequences of characters).
For example, the string “jesslookedjustliketimherbrother” would be optimally parsed as “JESS looked just like TIM her brother”. This parsing has seven unrecognized characters, which we have capitalized for clarity.
The solution given in the book is very hard to understand. It uses HashMap to memorize the previous result.
After long time of struggle, I finally solved it with traditional DP approach. The key idea is to consider: “whether I insert a space after this char, or not”.
The code is concise and easy to read.
public static int parse(String doc, Trie dict) {
int len = doc.length();
int[] dp = new int[len + 1];
// dp[i] denotes the number of special chars in first i chars of docs
for (int i = 1; i <= len; i++) {
dp[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
String str = doc.substring(j, i);
if (dict.contains(str, true)) {
// consider (i to j) a valid word
dp[i] = Math.min(dp[i], dp[j]);
} else {
// consider (i to j) special chars
dp[i] = Math.min(dp[i], dp[j] + i - j);
}
}
}
return dp[len];
}
Consider a simple node-like data structure called BiNode, which has pointers to two other nodes.
public class BiNode {
public BiNode node1, node2;
public int data;
}
The data structure BiNode could be used to represent both a binary tree (where node1 is the left node and node2 is the right node) or a doubly linked list (where node1 is the previous node and node2 is the next node). Implement a method to convert a binary search tree (implemented with BiNode) into a doubly linked list. The values should be kept in order and the operation should be performed in place (that is, on the original data structure).
At another post [LeetCode Plus] Convert BST to Circular DLL, we already discussed 2 approaches:
First approach isn’t intuitive. We will further discuss D&C approach here.
The key of the solution is how we return both HEAD and TAIL. The book suggests 3 ways:
I wrote the code for 1st and 2nd approach. And 3rd is already covered in previous post.
Approach 1
public static BiNode convert(BiNode root) {
BiNodePair res = helper(root);
return res.leftMost;
}
private static BiNodePair helper(BiNode node) {
if (node == null) {
return null;
}
BiNodePair res = new BiNodePair(node, node);
if (node.node1 != null) {
BiNodePair leftRes = helper(node.node1);
res.leftMost = leftRes.leftMost;
leftRes.rightMost.node2 = node;
node.node1 = leftRes.rightMost;
}
if (node.node2 != null) {
BiNodePair rightRes = helper(node.node2);
res.rightMost = rightRes.rightMost;
rightRes.leftMost.node1 = node;
node.node2 = rightRes.leftMost;
}
return res;
}
static class BiNodePair {
BiNode leftMost;
BiNode rightMost;
public BiNodePair(BiNode node1, BiNode node2) {
leftMost = node1;
rightMost = node2;
}
}
Approach 2
public static BiNode convert(BiNode root) {
if (root == null) {
return null;
}
return helper(root);
}
private static BiNode helper(BiNode node) {
// node is not null
BiNode newHead = node;
// do left part
if (node.node1 != null) {
newHead = helper(node.node1);
BiNode leftTail = getListTail(newHead);
leftTail.node2 = node;
node.node1 = leftTail;
}
// do right part
if (node.node2 != null) {
BiNode rightHead = helper(node.node2);
node.node2 = rightHead;
rightHead.node1 = node;
}
return newHead;
}
private static BiNode getListTail(BiNode head) {
// head is not null
while (head.node2 != null) {
head = head.node2;
}
return head;
}
Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number x (the number of values less than or equal to x).
Implement the data structures and algorithms to support these operations. That is, implement the method track(int x), which is called when each number is generated, and the method getRankOfNumber(int x), which returns the number of values less than or equal to x (not including x itself).
This question requires a special type of Data Structure. It basically is a modified BST like this:
The tree node stores both number value and the count of node on left subtree
Suppose we want to find the rank of 24 in the tree above. We would compare 24 with the root, 20, and find that 24 must reside on the right. The root has 4 nodes in its left subtree, and when we include the root itself, this gives us five total nodes smaller than 24. We set counter to 5.
Then, we compare 24 with node 25 and find that 24 must be on the left. The value of counter does not update, since we’re not “passing over” any smaller nodes. The value of counter is still 5.
Next, we compare 24 with node 23,and find that 24 must be on the right. Counter gets incremented by just 1 (to 6), since 23 has no left nodes.
Finally, we find 24 and we return counter: 6.
Refer to another post [Question] Stock Span Problem.
Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n-m (that is, find the smallest such sequence).
Referring to this guy:
找到heading的最长递增序列.
找到tailing的最长的递增序列.
After that:
用中间部分的min去shrink左边.
用中间部分的max去shrink右边.
written by me
public static void findUnsortedSequence(int[] array, int[] ans) {
int len = array.length;
ans[0] = 0;
ans[1] = 0;
// find increasing sequence on left and on right
int leftPeak = 0;
while (leftPeak < len - 1) {
if (array[leftPeak] < array[leftPeak + 1]) {
leftPeak++;
} else {
break;
}
}
if (leftPeak == len - 1) {
return;
}
int rightBottom = len - 1;
while (rightBottom > 0) {
if (array[rightBottom] > array[rightBottom - 1]) {
rightBottom--;
} else {
break;
}
}
// leftPeak and rightBottom are found, now read mid part
int midMin = Integer.MAX_VALUE;
int midMax = Integer.MIN_VALUE;
for (int i = leftPeak; i <= rightBottom; i++) {
midMin = Math.min(midMin, array[i]);
midMax = Math.max(midMax, array[i]);
}
// find left boudary and right boundary
int leftBound = leftPeak;
while (leftBound >= 0) {
if (array[leftBound] < midMin) {
break;
}
leftBound--;
}
int rightBound = rightBottom;
while (rightBound < len) {
if (array[rightBound] > midMax) {
break;
}
rightBound++;
}
// finish it up
ans[0] = leftBound + 1;
ans[1] = rightBound - 1;
}
Implement a CircularArray class that supports an array-like data structure which can be efficiently rotated.
The class should use a generic type, and should support iteration via the standard for (Object : circuLarArray) notation.
First part of the question is solved by using an array and a pointer. The solution simplifies the question by fixing the array size (not a dynamic-resizing array).
The difficult part is how to write iterator.
Note that we should support Java Generics:
class MyCircularArray<T>
Implement Iterable Interface:
public class MyCircularArray<T> implements Iterable<T> {
}
Override iterator() method:
@Override
public Iterator<T> iterator() {
return new MyIterator<T>(this);
}
Write our own Iterator Class:
class MyIterator<T> implements Iterator<T> {
}
Finish it up
public class MyCircularArray<T> implements Iterable<T> {
@Override
public Iterator<T> iterator() {
return new MyIterator<T>(this);
}
class MyIterator<T> implements Iterator<T> {
@Override
public boolean hasNext() {
}
@Override
public T next() {
}
@Override
public void remove() {
}
}
}
It might be confusing when implementing Iterable and Iterator Class.
public class MyCircularArray<T> implements Iterable<T> {
T[] items;
int head;
int cur;
public MyCircularArray(int size) {
// this is really important (casting the type)
items = (T[]) new Object[size];
head = 0;
cur = 0;
}
public void put(T item) {
items[cur++] = item;
cur = cur % items.length;
}
public T get(int i) {
int newIndex = (i + head) % items.length;
return items[newIndex];
}
public void rotate(int shiftRight) {
head += shiftRight;
head = head % items.length;
}
@Override
public Iterator<T> iterator() {
return new MyIterator<T>(this);
}
class MyIterator<T> implements Iterator<T> {
T[] items;
int head;
int count;
public MyIterator(MyCircularArray<T> array) {
this.items = array.items;
this.head = array.head;
this.count = 0;
}
@Override
public boolean hasNext() {
return this.count != items.length;
}
@Override
public T next() {
if (hasNext()) {
return items[(head + count++) % items.length];
}
return null;
}
@Override
public void remove() {
}
}
}