## Sunday, June 19, 2016

### Even Iterator

Question:

e.g. If N = 7, output 2, 4, 6

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
private Iterator<Integer> it;
Integer top = null;

public Solution (Iterator<Integer> it) {
this.it = it;
}

public boolean hasNext() {
if (top != null) {
return true;
}

if (!it.hasNext()) {
return false;
}

Integer curr = it.next();
if (curr % 2 == 0) {
top = curr;
return true;
} else {
if (!it.hasNext()) {
return false;
} else {
top = it.next();
}
}

return true;
}

public Integer next() {
Integer result = null;
if (top == null) {
return null;
} else {
result = top;
top = null;
}

return result;
}

public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
int n = 7;
for (int i = 1; i <= 10; i++) {
list.add(i);
}

Solution sol = new Solution(list.iterator());

while (sol.hasNext()) {
System.out.println(sol.next());
}
}
}


## Friday, June 17, 2016

### Collatz Conjecture

${\displaystyle f(n)={\begin{cases}n/2&{\mbox{if }}n\equiv 0\\3n+1&{\mbox{if }}n\equiv 1\end{cases}}{\pmod {2}}.}$

• 如n = 6，根據上述公式，得出序列6, 3, 10, 5, 16, 8, 4, 2, 1。(步驟中最高的數是16，共有8個步驟)
• 如n = 11，根據上述公式，得出序列11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1。(步驟中最高的數是52，共有14個步驟)
• 如n = 27，根據上述公式，得出序列
{ 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 }（步驟中最高的數是9232，共有111個步驟）

n = 27時的序列分布（橫軸－步數；縱軸－運算結果）

Question:
Given a positive number n >= 1, ask how many times the number, n, need to change in order to get to 1. e.g. n = 6, return 8, because there are 8 steps to transform 6 to 1.

Brute force solution:
import java.io.*;
import java.util.*;

public class Solution {
public int collatzConjecture(int n) {
if (n < 1) {
throw new IllegalArgumentException("n must be greater or equal to 1");
}

int count = 0;

while (n != 1) {
if ((n & 1) == 1) {
n = n * 3 + 1;
} else {
n /= 2;
}
count++;
}

return count;
}

public int collatzConjectureRecursive(int n) {
if (n < 1) {
throw new IllegalArgumentException("n must be greater or equal to 1");
}

if (n == 1) {
return 0;
}

if (n % 2 == 0) {
return 1 + collatzConjectureRecursive(n / 2);
} else {
return 1 + collatzConjectureRecursive(n * 3 + 1);
}
}

public static void main(String[] args) {
Solution sol = new Solution();
int result = sol.collatzConjecture(27);
System.out.println(result);

result = sol.collatzConjectureRecursive(27);
System.out.println(result);
}
}


Discussion:
1. Be very careful about the integer overflow problem. For large integers, where n is odd, 3 * n + 1 can easily get overflow. Clarify this problem with the interviewer. We may also use long instead of int to expand the size of n.
Follow-up:
What if we call the function with different n many times. Can we do it faster?

The answer is yes. Implementing a recursive algorithm is probably the simplest way to calculate the length, but seemed to me like an unnecessary waste of calculation time. Many sequences overlap; take for example 3's Hailstone sequence:
3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
This has length 7; more specifically, it takes 7 operations to get to 1. If we then take 6:
6 -> 3 -> ...
We notice immediately that we've already calculated this, so we just add on the sequence length of 3 instead of running through all those numbers again, considerably reducing the number of operations required to calculate the sequence length of each number.

I tried to implement this in Java using a HashMap (seemed appropriate given O(1) probabilistic get/put complexity).

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
private static Map<Integer, Integer> map;

public Solution() {
map = new HashMap<>();
map.put(1, 0); // NOTE that we need to put 1 into the cache as the base case
}

public int collatzConjectureCached(int n) {
if (n < 1) {
throw new IllegalArgumentException("n must be greater or equal to 1");
}

if (n == 1) {
return 0;
}

int count = 0;
int m = n;

while (true) {
if (map.containsKey(n)) {
count += map.get(n);
map.put(m, count);

return count;
} else if (n % 2 == 0) {
n /= 2;
} else {
n = n * 3 + 1;
}
count++;
}
}

public static void main(String[] args) {
Solution sol = new Solution();

System.out.println(sol.collatzConjectureCached(3));
System.out.println(sol.collatzConjectureCached(6));
System.out.println(sol.collatzConjectureCached(6));

for (Integer key : map.keySet()) {
System.out.println(key + ", " + map.get(key));
}

}
}

Follow-up:
what if we call this function many times with different n, then it could consume lots of memory to save the HashMap. What if the memory is not largely enough to hold the entire HashMap, what can we do?

One possible solution is instead of building an unlimited sized cache(implemented as a HashMap), we can build a fixed sized cache. For example, a LRU cache with a fixed capacity. The capacity is less than the memory size of the machine. We can maintain such a LRU cache in memory. In this case, some numbers which are not frequently used might be evicted from the cache. This is a trade-off between time and space. How to implement a LRU cache? Check out the LC problem: LRU cache.

### Reverse Large String

Question:
Reverse a string byte by byte. However, the string is too large to fit into memory, so it is stored in a file on disk. How do you reverse that string?

Analysis:
Since the string is stored on disk, if each time we load one character from front and end of the string, from the disk to memory, swap and store it back, it will involve too many I/O operations. So the idea is to load the string chunk by chunk.

Code (Java):
public class Solution {
public String reverseString(String s) {
if (s == null || s.length() == 0) {
return "";
}

final int chunkSize = 3;
char[] temp = s.toCharArray();
int len = s.length();

int start = 0;
int end = len - chunkSize;

while (start < end) {
int len1 = Math.min(chunkSize, end - start);
int len2 = chunkSize;
char[] buf1 = new char[len1];
char[] buf2 = new char[len2];
fread(temp, buf1, start, len1);
fread(temp, buf2, end, len2);

reverse(buf1, buf2);

fwrite(temp, buf1, start, len1);
fwrite(temp, buf2, end, len2);

// update start and end
start += len1;
end -= len2;
}

if (start >= end) {
end += chunkSize - 1;
char[] buf = new char[end - start + 1];
fread(temp, buf, start, end - start + 1);
reverse(buf);
fwrite(temp, buf, start, end - start + 1);
}

return new String(temp);
}

// Read size of len bytes from the starting index, from s to buf
private void fread(char[] s, char[] buf, int start, int len) {
for (int i = 0; i < len; i++) {
buf[i] = s[i + start];
}
}

// Write size of len bytes from the staring index, from buf to file s
private void fwrite(char[] s, char[] buf, int start, int len) {
for (int i = 0; i < len; i++) {
s[i + start] = buf[i];
}
}

// Reverse the chars in the two bufs
private void reverse(char[] buf1, char[] buf2) {
int start = 0;
int end  = buf2.length - 1;

for (start = 0; start < buf1.length; start++) {
char temp = buf1[start];
buf1[start] = buf2[end];
buf2[end] = temp;
end--;
}

if (end > 0) {
start = 0;
while (start < end) {
swap(buf2, start, end);
start++;
end--;
}
}
}

// Revserse the chars in one buf
private void reverse(char[] buf) {
int start = 0;
int end = buf.length - 1;

while (start < end) {
swap(buf, start, end);
start++;
end--;
}
}

private void swap(char[] buf, int i, int j) {
char temp = buf[i];
buf[i] = buf[j];
buf[j] = temp;
}
}


Follow-up: What if the system is crashed/down in the meanwhile, how can we know the position we need to re-start next?
One possible solution could use a transaction log. Specifically, when we read two chunks from the file, we may log
START
start = xxx
end = xxx
And AFTER we finish writing the reversed string into the file, we log an END, e.g.
START
start = xxx
end = xxx
END

So the next time when the system gets restarted, it first checks if the pair of  <START, END> is completed. If not, we re-wind the position and reverse the chunk again.

But this solution is not 100% safe. If it safe if the system is crashed before wring the final results. In this case, since the final reversed chunks are not written into disk i.e., the original string has not been changed, it is safe to re-play and reverse the chunk again.

But what if the system is crashed when we write the result into file. e.g.
ABC DE FGH
after we reverse the first and the last chunk, the two chunks become
HGF and CBA, and then we should write the two chunks into the file.
If the system is down right after we write the H and C, it is not correct to rewind the start and end pointer and reverse the chunks again because the string has been already partially reversed.

There could be two solutions to solve this issue. One solution is do out-of-place reverse, that is, store the reversed string into a new file. In this case, since the input string has not been modified, it's always safe to re-wind the start and end pointer and reverse the chunk again.

Another solution could be do a more detailed transaction log. That is, instead of logging right before and after the chunk is loaded and stored, we log the position of start and end after each character in the chunk has been stored into the disk. So if the system is crashed in the meanwhile, we know the last position we have successfully reversed the string.

## Wednesday, June 15, 2016

### Aligned Malloc and Free

Question:

Write an aligned malloc & free function. Which takes number of bytes and aligned byte (which is always power of 2)
Ex. align_malloc (1000,128);
it will return memory address multiple of 128 of the size 1000.
aligned_free();

it will free memory allocated by align_malloc.

Code (Java):
#include <stdio.h>
#include <stdlib.h>

/*************************************************
Name  :- aligned_malloc
Arguments:- number of bytes & Alignment Boundry
Return :- NULL on error
valid pointer on success

Working  :- It will allocate memory with starting address
multiple of alignment passed and returns pointer
to it on success.

Ex.
aligned_malloc(50,128);
This will allocate 50 bytes of memory with
starting address multiple of 128.

*************************************************/

void *aligned_malloc(size_t bytes, size_t alignment)
{
void *p1 ,*p2; // basic pointer needed for computation.

/* We need to use malloc provided by C. First we need to allocate memory
of size bytes + alignment + sizeof(size_t) . We need 'bytes' because
user requested it. We need to add 'alignment' because malloc can give us
any address and we need to find multiple of 'alignment', so at maximum multiple
of alignment will be 'alignment' bytes away from any location. We need
'sizeof(size_t)' for implementing 'aligned_free', since we are returning modified
memory pointer, not given by malloc ,to the user, we must free the memory
allocated by malloc not anything else. So I am storing address given by malloc just above
pointer returning to user. Thats why I need extra space to store that address.
Then I am checking for error returned by malloc, if it returns NULL then
aligned_malloc will fail and return NULL.
*/
if((p1 =(void *) malloc(bytes + alignment + sizeof(size_t)))==NULL)
return NULL;

/*  Next step is to find aligned memory address multiples of alignment.
By using basic formule I am finding next address after p1 which is
multiple of alignment.I am storing new address in p2.
*/
size_t addr=(size_t)p1+alignment+sizeof(size_t);

p2=(void *)(addr - (addr%alignment));

/*  Final step, I am storing the address returned by malloc 'p1' just "size_t"
bytes above p2, which will be useful while calling aligned_free.
*/
*((size_t *)p2-1)=(size_t)p1;

return p2;
}

/************************************************
Name  :- aligned_free
Arguments  :- pointer to be freed
Returns  :- Nothing

*************************************************/

void aligned_free(void *p )
{
/*  Find the address stored by aligned_malloc ,"size_t" bytes above the
current pointer then free it using normal free routine provided by C.
*/
free((void *)(*((size_t *) p-1)));
}


### Align Rectangle

Question:给你a list of rectangle 让你把它们放在一个坐标平面上并align，从左往右放矩形，最右边有一个边界，不能超界，每个矩形提供getLength(), getWidth()，要保证每一行矩形的中心都在一条直线上，一行放不满另起一行，但是不能有overlap.

Solution:

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
List<List<Box>> alignBox(List<Box> boxes, int width) {
List<List<Box>> result = new ArrayList<>();

if (boxes == null || boxes.size() == 0 || width <= 0) {
return result;
}

// step 1: group all the same-height boxes together
Map<Integer, List<Box>> map = new HashMap<>();
for (Box box : boxes) {
if (map.containsKey(box.height)) {
List<Box> list = map.get(box.height);
list.add(box);
map.put(box.height, list);
} else {
List<Box> list = new ArrayList<>();
list.add(box);
map.put(box.height, list);
}
}

// step 2: align the box, put the boxes with the same height in the same row, if it cannot fit
// one row, put into another
for (Integer height : map.keySet()) {
List<Box> rowBoxes = map.get(height);
List<Box> alignedBoxes = new ArrayList<>();
int currWidth = 0;
for (Box box : rowBoxes) {
if (currWidth + box.width <= width) {
alignedBoxes.add(box);
currWidth += box.width;
} else {
// First add the previous row into the reuslt and clear the row
result.add(new ArrayList<>(alignedBoxes));
alignedBoxes.clear();
currWidth = 0;

// Then add the box to next row
alignedBoxes.add(box);
currWidth += box.width;

}
}

// put the current row into the result, for the case the total width of the
// current row is less than the given width
result.add(alignedBoxes);
}

return result;
}

public static void main(String[] args) {
Solution sol = new Solution();
List<Box> boxes = new ArrayList<>();

boxes.add(new Box(2, 1));
boxes.add(new Box(2, 5));
boxes.add(new Box(1, 4));
boxes.add(new Box(1, 3));
boxes.add(new Box(4, 2));
boxes.add(new Box(2, 3));
boxes.add(new Box(5, 2));
boxes.add(new Box(1, 3));
boxes.add(new Box(5, 2));

List<List<Box>> result = sol.alignBox(boxes, 5);

for (List<Box> row : result) {
for (Box box : row) {
System.out.print(box.height + ", " + box.width + ", ");
}

System.out.println("");
}
}
}

class Box {
public int height;
public int width;

public Box(int height, int width) {
this.width = width;
this.height = height;
}
}


The output:
1, 4,
1, 3,
1, 3,
2, 1,
2, 5,
2, 3,
4, 2,

5, 2, 5, 2,

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
List<List<Box>> alignBox(List<Box> boxes, int width) {
List<List<Box>> result = new ArrayList<>();

if (boxes == null || boxes.size() == 0 || width <= 0) {
return result;
}

// step 1: group all the same-height boxes together
Map<Integer, List<Box>> map = new HashMap<>();
for (Box box : boxes) {
if (map.containsKey(box.height)) {
List<Box> list = map.get(box.height);
list.add(box);
map.put(box.height, list);
} else {
List<Box> list = new ArrayList<>();
list.add(box);
map.put(box.height, list);
}
}

// step 2: align the box, put the boxes with the same height in the same row, if it cannot fit
// one row, put into another
for (Integer height : map.keySet()) {
List<Box> rowBoxes = map.get(height);
// Sort the box according to the width
Collections.sort(rowBoxes, new MyBoxComparator());

List<Box> alignedBoxes = new ArrayList<>();
int widthLeft = width;
while (!rowBoxes.isEmpty()) {
if (widthLeft > 0) {
int nextBoxIndex = findNextBox(rowBoxes, widthLeft);
if (nextBoxIndex != -1) {
Box nextBox = rowBoxes.get(nextBoxIndex);
alignedBoxes.add(nextBox);
rowBoxes.remove(nextBoxIndex);
widthLeft -= nextBox.width;
} else {
widthLeft = 0;
}
} else {
result.add(new ArrayList<>(alignedBoxes));
alignedBoxes.clear();
widthLeft = width;
}
}

// put the current row into the result, for the case the total width of the
// current row is less than the given width
result.add(alignedBoxes);
}

return result;
}

class MyBoxComparator implements Comparator<Box> {
@Override
public int compare(Box a, Box b) {
return a.width - b.width;
}
}

// Find the box with width equal to the target,
// if does not exist, return the one just smaller than the target
int findNextBox(List<Box> boxes, int width) {
int lo = 0;
int hi = boxes.size() - 1;

while (lo + 1 < hi) {
int mid = lo + (hi - lo) / 2;
if (boxes.get(mid).width == width) {
return mid;
} else if (boxes.get(mid).width > width) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}

if (boxes.get(hi).width <= width) {
return hi;
} else if (boxes.get(lo).width <= width){
return lo;
} else {
return -1;
}
}

public static void main(String[] args) {
Solution sol = new Solution();
List<Box> boxes = new ArrayList<>();

boxes.add(new Box(2, 1));
boxes.add(new Box(2, 5));
boxes.add(new Box(1, 4));
boxes.add(new Box(1, 3));
boxes.add(new Box(4, 2));
boxes.add(new Box(2, 3));
boxes.add(new Box(5, 2));
boxes.add(new Box(1, 3));
boxes.add(new Box(5, 2));

List<List<Box>> result = sol.alignBox(boxes, 5);

for (List<Box> row : result) {
for (Box box : row) {
System.out.print(box.height + ", " + box.width + ", ");
}

System.out.println("");
}
}
}

class Box {
public int height;
public int width;

public Box(int height, int width) {
this.width = width;
this.height = height;
}
}


Output:
1, 4,
1, 3,
1, 3,
2, 5,
2, 3, 2, 1,
4, 2,

5, 2, 5, 2,

### Football Game

Question:
football题，比赛得分可能得3分，也可能得6分，如果得了6分得话，后面还可以选择什么touch down或者kick，分别又是得1分或2分，然后如果给你一个N分，问你有几种可能.

DFS Solution:

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
private int result = 0;
public int getScore(int n) {
if (n < 3) {
return 0;
}

getScoreHelper(n);

return result;
}

private void getScoreHelper(int n) {
if (n == 0) {
result++;
return;
}

if (n < 3) {
return;
}

getScoreHelper(n - 3);
getScoreHelper(n - 6);
getScoreHelper(n - 7);
getScoreHelper(n - 8);
}

public static void main(String[] args) {
Solution sol = new Solution();

int n = 11;
int result = sol.getScore(n);
System.out.println(result);
}
}


The DP Solution:
Define dp[n + 1], where dp[i] is the number of possible ways for score i.
dp[i] = dp[i - 3] + dp[i - 6] + dp[i - 7] + dp[i - 8];

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
public int getScoreDP(int n) {
if (n < 3) {
return 0;
}

int[] dp = new int[n + 1];
dp[3] = 1;
dp[6] = 2;
dp[7] = 1;
dp[8] = 1;

for (int i = 9; i <= n; i++) {
dp[i] = dp[i - 3] + dp[i - 6] + dp[i - 7] + dp[i - 8];
}

return dp[n];
}

public static void main(String[] args) {
Solution sol = new Solution();

int n = 45;
int result = sol.getScoreDP(n);
System.out.println(result);
}
}


### Fast ID Generator

Question:

Solution:
Use a queue to store 100 IDs. Once the queue is empty, refill the queue by calling the get_ids().

Code(Java):
import java.io.*;
import java.util.*;

public class Solution {
Queue<Integer> queue;

public Solution() {
queue = new LinkedList<>();
}

public Integer get_one_id() {
// Take 1 sec
if (queue.isEmpty()) {
List<Integer> ids = get_ids();
for (Integer id : ids) {
queue.offer(id);
}
}

return queue.poll();
}

public List<Integer> get_ids() {
List<Integer> result = new ArrayList<>();
Random randomGenerator = new Random();

// Generate 100 ids which takes 1 sec
for (int i = 0; i < 100; i++) {
result.add(randomGenerator.nextInt(1000));
}

// Sleep 1 sec
try {
Thread.sleep(1000);                 //1000 milliseconds is one second.
} catch(InterruptedException ex) {
Thread.currentThread().interrupt();
}

return result;
}

public static void main(String[] args) {
Solution sol = new Solution();

// Call 100times get_one_id()
for (int i = 0; i < 200; i++) {
Integer result = sol.get_one_id();
System.out.println(result);
}
}
}


Follow-up: What if each time we call get_one_id(), the waiting time is on longer than 1s?
In the previous solution, if the queue is empty, we have to call get_ids() to get 100 ids which takes 1s. In order to shorten the waiting time, we need to overlap those two processes.

The idea is to use two threads. One thread calls get_one_id(), which consumes the IDs, another thread call get_ids(), which feeds the queue. The threshold is 100, i.e., when the queue has 100 IDs, the get_ids() will be triggered and feed 100 IDs into the queue. Since get_one_id() is called no more than 100 times per second, in this way calling the get_one_id() will not be blocked any more.

In fact, this is a classic producer/consumer problem.

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
public static void main(String[] args) {
BlockingQueue bq = new BlockingQueue();
Producer p1 = new Producer(bq);
Consumer c1 = new Consumer(bq);

p1.start();
c1.start();
}
}

class BlockingQueue {
private Queue<Integer> queue;
private int threshold = 100;

public BlockingQueue() {
queue = new LinkedList<>();
// feed 100 ids first
List<Integer> ids = get_ids();
for (Integer id : ids) {
queue.offer(id);
}
}

public synchronized void put() throws InterruptedException {
while (queue.size() != threshold) {
wait();
}

// feed 100 ids
List<Integer> ids = get_ids();
for (Integer id : ids) {
queue.offer(id);
}

notifyAll();
}

public synchronized Integer take() throws InterruptedException {
while (queue.size() == 0) {
wait();
}

Integer result = queue.poll();
notifyAll();

return result;
}

public List<Integer> get_ids() {
List<Integer> result = new ArrayList<>();
Random randomGenerator = new Random();

// Generate 100 ids which takes 1 sec
for (int i = 0; i < 100; i++) {
result.add(randomGenerator.nextInt(1000));
}

// Sleep 1 sec
try {
Thread.sleep(1000);                 //1000 milliseconds is one second.
} catch(InterruptedException ex) {
Thread.currentThread().interrupt();
}

return result;
}
}

class Consumer extends Thread {
private BlockingQueue bq;
public Consumer(BlockingQueue bq) {
this.bq = bq;
}

public void run() {
// print 500 ids
for (int i = 0; i < 1000; i++) {
try {
Integer result = bq.take();
System.out.println(result);
} catch (InterruptedException ex) {
Thread.currentThread().interrupt();
}
}
}
}

class Producer extends Thread {
private BlockingQueue bq;

public Producer(BlockingQueue bq) {
this.bq = bq;
}

public void run() {
try {
bq.put();
} catch (InterruptedException ex) {
Thread.currentThread().interrupt();
}
}
}


## Tuesday, June 14, 2016

### In-place Stencil

Question:
Given a m*n matrix with integers, calculate the average value based on its 8 neighbors. Do it in-place.

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
public void computeAverageInplace(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return;
}

int m = matrix.length;
int n = matrix[0].length;

int[][] padMatrix = new int[m + 2][n + 2];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
padMatrix[i + 1][j + 1] = matrix[i][j];
}
}

int t1 = 0;
int t2 = 0;

// step 1: compute the accumulation in row order
for (int j = 1; j < n + 1; j++) {
for (int i = 1; i < m + 1; i++) {
if (i == 1) {
t1 = padMatrix[i][j];
padMatrix[i][j] += padMatrix[i + 1][j];
} else if (((i - 1) & 1) == 0) {
if ((i - 1) % 4 == 0) {
t1 = padMatrix[i][j];
padMatrix[i][j] = padMatrix[i - 1][j] - t2 + padMatrix[i + 1][j];
} else {
t2 = padMatrix[i][j];
padMatrix[i][j] = padMatrix[i - 1][j] - t1 + padMatrix[i + 1][j];
}
} else {
if ((i - 1) % 4 == 1) {
padMatrix[i][j] += t1 + padMatrix[i + 1][j];
} else {
padMatrix[i][j] += t2 + padMatrix[i + 1][j];
}
}
}
}

// step 2: compute the accumatlion in col order
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (j == 1) {
t1 = padMatrix[i][j];
padMatrix[i][j] += padMatrix[i][j + 1];
} else if (((j - 1) & 1) == 0) {
if ((j - 1) % 4 == 0) {
t1 = padMatrix[i][j];
padMatrix[i][j] = padMatrix[i][j - 1] - t2 + padMatrix[i][j + 1];
} else {
t2 = padMatrix[i][j];
padMatrix[i][j] = padMatrix[i][j - 1] - t1 + padMatrix[i][j + 1];
}
} else {
if ((j - 1) % 4 == 1) {
padMatrix[i][j] += t1 + padMatrix[i][j + 1];
} else {
padMatrix[i][j] += t2 + padMatrix[i][j + 1];
}
}
}
}

// Copy the padMatrix back to matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = padMatrix[i + 1][j + 1];
}
}
}

public int[][] computeAverageOutOfPlace(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;

int[][] padMatrix = new int[m + 2][n + 2];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
padMatrix[i + 1][j + 1] = matrix[i][j];
}
}

int[][] result = new int[m][n];

for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
for (int p = i - 1; p <= i + 1; p++) {
for (int q = j - 1; q <= j + 1; q++) {
result[i - 1][j - 1] += padMatrix[p][q];
}
}
}
}

return result;
}

public static void main(String[] args) {
Solution sol = new Solution();

int m = 17;
int n = 20;
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = (i * j) % 10;
}
}

int[][] outOfPlace = sol.computeAverageOutOfPlace(matrix);

System.out.println("Out of place result: ");
for (int[] rows : outOfPlace) {
for (int e : rows) {
System.out.print(e + " ");
}

System.out.println("");
}

System.out.println("");
System.out.println("In place result: ");
sol.computeAverageInplace(matrix);

for (int[] rows : matrix) {
for (int e : rows) {
System.out.print(e + " ");
}

System.out.println("");
}
}
}


### O(1) Map

Question:
Design a Map so that it supports the following operations:
1. add(int val), O(1) time
2. remove(int val), O(1) time
3. contains(int val), O(1) time
4. clear(), O(1) time
5. iterate(), O(num of elements)

Analysis:
If we just use a randomized array, i.e, a hash map, add(), remove(), and contains() operations take O(1) time. The clear() takes O(size of array) time (NOT SURE), and iterate takes O(size of array) time. Note that iterate() takes O(size of array) time instead of O(num of elements) because of the implementation of a hash map is usually an array or array + list. So it needs to iterate all elements of the array no matter if it is taken or not.

If we only use a sequential accessed array, i.e, an ArrayList in Java, the add() takes O(1), but remove() and contains() takes O(num of elements) time. clear() takes O(1) ?? not sure.
iterate() takes O(num of elements) time as well.

So the idea is to combine the two data structures together.

Method 1: HashMap + Array
Code (Java):
import java.io.*;
import java.util.*;

class Solution implements Iterable<Integer> {
private int[] list;
private Map<Integer, Integer> map;
private int size;
private final int INIT_CAPACITY = 4;

public Solution() {
list = new int[INIT_CAPACITY];
map = new HashMap<>();
size = 0;
}

public void add(int val) {
if (size == list.length) {
resize(2 * list.length);
}

map.put(val, size);
list[size] = val;
size++;
}

public void remove(int val) {
if (!map.containsKey(val)) {
throw new NoSuchElementException();
}

// step 1: get the index of the val to be removed
int idxToRemove = map.get(val);

// step 2: move the last element to the index to be removed
int lastE = list[size - 1];
list[idxToRemove] = lastE;
//list[size - 1] = null;

size--;
map.remove(val);
map.put(lastE, idxToRemove);

// shrink the array
if (size > 0 && size == list.length / 4) {
resize(list.length / 2);
}

}

public boolean contains(int val) {
return map.containsKey(val) &&
map.get(val) < size &&
val == list[map.get(val)];
}

public void clear() {
size = 0;
}

@Override
public Iterator<Integer> iterator() {
return new MyListIterator();
}

private class MyListIterator implements Iterator<Integer> {
private int i = 0;

@Override
public boolean hasNext() {
return i < size;
}

@Override
public Integer next() {
Integer result = 0;
if (hasNext()) {
result = (Integer) list[i];
i++;
}

return result;
}

@Override
public void remove() {
throw new UnsupportedOperationException();
}
}

private void resize(int newSize) {
int[] newList = new int[newSize];
newList = Arrays.copyOf(list, size);
list = newList;
}

public static void main(String[] args) {
Solution sol = new Solution();
sol.add(1);
sol.add(3);

sol.clear();

sol.add(4);
sol.add(5);

System.out.println(sol.contains(3));

Iterator<Integer> it = sol.iterator();
while (it.hasNext()) {
int val = it.next();
System.out.println(val);
}
}
}


Method 2: Use two arrays
Use two arrays, map[n] and list[n], where for the map[i], the index stores the val of the data, and its value stores the index of the data in the list array. The real value is stored in the list array as well for the convenience of iterator() in O(num of elements) time.

The basic idea of this solution is very close the method 1, just to use the map[] array to simulate a hash map. Therefore here we assume that the size of the map[] array is unlimited and the value of the data to be stored is never out of boundary.

Code (Java):
import java.io.*;
import java.util.*;

class Solution implements Iterable<Integer> {
private Integer[] map;
private Integer[] list;

private int size;
private final int INIT_CAPACITY = 4;
private final int MAP_CAPACITY = 1000;

public Solution() {
list = new Integer[INIT_CAPACITY];
map = new Integer[MAP_CAPACITY];
this.size = 0;
}

public void add(int val) {
if (size == list.length) {
resize(2 * list.length);
}

map[val] = size;
list[size] = val;
size++;
}

public void remove(int val) {
if (!contains(val)) {
throw new NoSuchElementException();
}

// step 1: get the index of the val to be removed
int idxToRemove = map[val];

// step 2: move the last element to the index to be removed
int lastE = list[size - 1];
list[idxToRemove] = lastE;
list[size - 1] = null;

size--;

map[lastE] = idxToRemove;
map[val] = null;

// shrink the array
if (size > 0 && size == list.length / 4) {
resize(list.length / 2);
}
}

public boolean contains(int val) {
return map[val] != null &&
map[val] < size &&
val == list[map[val]];
}

public void clear() {
size = 0;
}

@Override
public Iterator<Integer> iterator() {
return new MyListIterator();
}

private class MyListIterator implements Iterator<Integer> {
private int i = 0;

@Override
public boolean hasNext() {
return i < size;
}

@Override
public Integer next() {
Integer result = 0;
if (hasNext()) {
result = list[i];
i++;
}

return result;
}

@Override
public void remove() {
throw new UnsupportedOperationException();
}
}

private void resize(int newSize) {
Integer[] newList = new Integer[newSize];
for (int i = 0; i < size; i++) {
newList[i] = list[i];
}
list = newList;
}

public static void main(String[] args) {
Solution sol = new Solution();
sol.add(1);
sol.add(3);

//sol.add(5);

//System.out.println(sol.contains(3));

sol.clear();

sol.add(4);
sol.add(5);

System.out.println(sol.contains(3));

//sol.remove(3);

Iterator<Integer> it = sol.iterator();
while (it.hasNext()) {
int val = it.next();
System.out.println(val);
}

}
}


## Sunday, June 12, 2016

### Draw a Circle

Question:
Given a parameter r2, where the equation x^2 + y^2 = r2 holds. Return a list of points that
1. x and y are both integers
2. fits the circle equations.

Drawing a circle on the screen is a little complex than drawing a line. There are two popular algorithms for generating a circle − Bresenham’s Algorithm and Midpoint Circle Algorithm. These algorithms are based on the idea of determining the subsequent points required to draw the circle. Let us discuss the algorithms in detail −
The equation of circle is ${X}^{2}+{Y}^{2}={r}^{2},$ where r is radius.

Method 1: Bresenham’s Algorithm
We cannot display a continuous arc on the raster display. Instead, we have to choose the nearest pixel position to complete the arc.

From the following illustration, you can see that we have put the pixel at (X, Y) location and now need to decide where to put the next pixel − at N (X+1, Y) or at S (X+1, Y-1).

This can be decided by the decision parameter d. -- If d <= 0, then N(X+1, Y) is to be chosen as next pixel. -- If d > 0, then S(X+1, Y-1) is to be chosen as the next pixel.

### Algorithm

Step 1 − Get the coordinates of the center of the circle and radius, and store them in x, y, and R respectively. Set P=0 and Q=R.
Step 2 − Set decision parameter D = 3 – 2R.
Step 3 − Repeat through step-8 while X < Y.
Step 4 − Call Draw Circle (X, Y, P, Q).
Step 5 − Increment the value of P.
Step 6 − If D < 0 then D = D + 4x + 6.
Step 7 − Else Set Y = Y + 1, D = D + 4(X-Y) + 10.
Step 8 − Call Draw Circle (X, Y, P, Q).
Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
public static void drawCircle(int centerX, int centerY, int radius) {
int d = 3 - 2 * radius;
int x = 0;
int y = radius;

do {
setPixel(centerX + x, centerY + y);
setPixel(centerX + x, centerY - y);
setPixel(centerX - x, centerY + y);
setPixel(centerX - x, centerY - y);
setPixel(centerX + y, centerY + x);
setPixel(centerX + y, centerY - x);
setPixel(centerX - y, centerY + x);
setPixel(centerX - y, centerY - x);

if (d <= 0) {
d += 4 * x + 6;
} else {
d += 4 * (x - y) + 10;
y--;
}
x++;
} while (x <= y);
}

private static void setPixel(int x, int y) {
System.out.println(x + ", " + y);
}

public static void main(String[] args) {
drawCircle(0, 0, 100);
}
}


Method 2: Mid-point algorithm:

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {

public static void drawCircleMidPoint(int centerX, int centerY, int radius) {
int d = 1 - radius; // Or d = (5 - radius * 4) / 4
int x = 0;
int y = radius;

do {
setPixel(centerX + x, centerY + y);
setPixel(centerX + x, centerY - y);
setPixel(centerX - x, centerY + y);
setPixel(centerX - x, centerY - y);
setPixel(centerX + y, centerY + x);
setPixel(centerX + y, centerY - x);
setPixel(centerX - y, centerY + x);
setPixel(centerX - y, centerY - x);

if (d <= 0) {
d += 2 * x + 3;
} else {
d += 2 * (x - y) + 5;
y--;
}
x++;
} while (x <= y);
}

private static void setPixel(int x, int y) {
System.out.println(x + ", " + y);
}

public static void main(String[] args) {
drawCircleBresenham(0, 0, 10);

System.out.println("");

drawCircleMidPoint(0, 0, 10);

}
}


### Buddy System

Question:
Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold:
1. A node's value is 1 iff and only if all its subtree nodes' value are 1
2. A leaf node can have value either 1 or 0.

Implement the following 2 APIs:
set_bit(offset, length), set the bits at range from offset to offset + length - 1
clear_bit(offset, length), clear the bits at range from offset to offset + length - 1

e.g.                 0

/       \
0         0
/   \      /   \
1   0    1    0
/ \   / \   / \   / \
1 1 1 0 1 1 0 0

After calling the clear_bit(1, 3), the binary tree becomes

0

/       \
0         0
/   \      /   \
0   0    1    0
/ \   / \   / \   / \
1 0 0 0 1 1 0 0

For this tree, after call set_bit(1, 5), the binary tree becomes:

Understand the problem:

What's a buddy system? Here the link gives good explanation:
https://www.cs.fsu.edu/~engelen/courses/COP402003/p827.pdf

Code (Java):
import java.io.*;
import java.io.*;
import java.util.*;

/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/

public class Solution {
private int[][] bits;
private int n;
private int numNodesLastLevel;

public Solution (int n) {
this.n = n;
this.numNodesLastLevel = (int) Math.pow(2, n - 1);
bits = new int[n][numNodesLastLevel];

}

public void clearBits(int offset, int len) {
if (offset < 0 || offset + len > numNodesLastLevel) {
throw new IndexOutOfBoundsException();
}
clearBitsHelper(n - 1, offset, offset + len - 1);
}

private void clearBitsHelper(int level, int start, int end) {
if (level < 0 || start > end) {
return;
}

boolean containsOne = setToZero(level, start ,end);
if (containsOne) {
clearBitsHelper(level - 1, start / 2, end / 2);
}
}

public void setBits(int offset, int len) {
if (offset < 0 || offset + len > numNodesLastLevel) {
throw new IndexOutOfBoundsException();
}
setBitsHelper(n - 1, offset, offset + len - 1);
}

private void setBitsHelper(int level, int start, int end) {
if (level < 0 || start > end) {
return;
}

setToOne(level, start, end);

// if start index is odd
if ((start & 1) == 1) {
start--;
}

// if end index is even
if ((end & 1) == 0) {
end++;
}

// determine the start position of the next level
int nextStart = Integer.MAX_VALUE;
for (int i = start; i < end; i += 2) {
if (bits[level][i] == 1 && bits[level][i + 1] == 1) {
nextStart = i / 2;
break;
}
}

// determien the end position of the next level
int nextEnd = Integer.MIN_VALUE;
for (int i = end; i > start; i -= 2) {
if (bits[level][i] == 1 && bits[level][i - 1] == 1) {
nextEnd = i / 2;
break;
}
}

setBitsHelper(level - 1, nextStart, nextEnd);
}

private void setToOne(int level, int start, int end) {
for (int i = start; i <= end; i++) {
bits[level][i] = 1;
}
}

private boolean setToZero(int level, int start, int end) {
boolean containsOne = false;
for (int i = start; i <= end; i++) {
if (bits[level][i] == 1) {
containsOne = true;
}

bits[level][i] = 0;
}

return containsOne;
}

private void printTree() {
int nodes = 1;
for (int[] level : bits) {
for (int i = 0; i < nodes; i++) {
System.out.print(level[i] + ", ");
}

System.out.println("");
nodes *= 2;
}
System.out.println("");
}

public static void main(String[] args) {
Solution sol = new Solution(4);

sol.setBits(1, 5);
sol.printTree();

sol.clearBits(2, 6);
sol.printTree();
}
}


Several thoughts and optimizations:
1. Why we set and clear bits in level order instead of heap order? That is, for each bit, we set and update its parent and so on, then repeat for the next bit. T

hat is because data is stored continuous in one level of tree. So if we read one level and process then move to its parent level, it can achieve better data locality.

2. For the clear_bits(), actually we don't have to repeat until we reach to the root. We can stop the recursion if all bits in the current level is zero. That's a prune of a recursion.

## Friday, June 10, 2016

### Leetcode: 319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:
Given n = 3.

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].

So you should return 1, because there is only one bulb is on.

Code (Java):
public class Solution {
public int bulbSwitch(int n) {
return (int) Math.sqrt(n);
}
}


### Leetcode: 320. Generalized Abbreviation

Write a function to generate the generalized abbreviations of a word.
Example:
Given word = "word", return the following list (order does not matter):
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Understand the problem:
A classic dfs + backtracking problem. A trick here is if we've already abbrivate part of a word, we must jump at least a character.

Code (Java):
public class Solution {
public List<String> generateAbbreviations(String word) {
List<String> result = new ArrayList<>();

result.add(word);
generateHelper(0, word, result);

return result;
}

private void generateHelper(int start, String s, List<String> result) {
if (start >= s.length()) {
return;
}

for (int i = start; i < s.length(); i++) {
for (int j = 1; i + j <= s.length(); j++) {
String num = Integer.toString(j);
String abbr = s.substring(0, i) + num + s.substring(i + j);
result.add(abbr);
generateHelper(i + 1 + num.length(), abbr, result); // skip 1b
}
}
}
}