Sunday, June 19, 2016

Even Iterator

Question:
设计iterator, input是一个遍历1到N的iterator,你设计的iterator只返回偶数。

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

考拉茲猜想英語:Collatz conjecture),又稱為奇偶歸一猜想3n+1猜想冰雹猜想角谷猜想哈塞猜想烏拉姆猜想敘拉古猜想,是指對於每一個正整數,如果它是奇數,則對它乘3再加1,如果它是偶數,則對它除以2,如此循環,最終都能夠得到1。

取一個正整數:
  • 如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個步驟)
偶歸一猜想稱,任何正整數,經過上述計算步驟後,最終都會得到1。

n = 27時的序列分布(橫軸-步數;縱軸-運算結果)
數目少於1萬的,步驟中最高的數是6171; 數目少於1億的,步驟中最高的數是63728127,共有949個步驟; 數目少於10億的,步驟中最高的數是670617279,共有986個步驟。

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:
基本的idea是首先遍历所有的rectangle, 建立一个HashMap<Integer, List<Rectangle>>, 把所有相同height的rectangle 都 group 到一起。所以这个map, key 存的是 height, value是具有相同height的rectangle。这样做的目的是相同height的rectangle需要排列在一行,因为题目要求每一行矩形的中心都在一条直线上。

然后遍历这个map, 并且开始排列矩形。因为每一行的宽度有限,相同高度的矩形可能放不到一行里面。这里的规则是尽量用最少的行数放下这些矩形。我们这里可以采取一个贪心的算法。首先对于一个高度的所有rectangle, 可以先按照宽度从小到大排序。然后我们维护每一行剩下的宽度,然后从这个list里面选择比这个剩余宽度小的最宽的矩形。这种贪心的策略不一定总能找到最小的行数存下所有的矩形,但应该大部分时候都能work. 

我们先做一个简单的答案。假设题目并不要求所用的行数最小。这样就不用排序每行的矩形。

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, 

我们从结果可以看见第一列是height, 第二列是width。如果限定的每行最长的宽度是5. 当height = 2的时候,我们用了3行来align 这 3个box. 实际上我们可以把2, 1 以及 2, 3 merge 到一行,这样其实用2行就可以align 高度为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:
对于每一个得分N, 可能接下来的得分就是N + 3, N + 6, N + 7, N + 8. 从比分0向下递推,直到最后的得分是N。

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:
已知一个叫get_ids()的API能够耗时1s并返回100个各不相同的id(第二次call返回的和第一次的也不会有任何重复),有个待实现的函数叫get_one_id(),每秒最多被call 100次,每次call要能返回一个新的id。题目就是利用get_ids()实现get_one_id(),follow up是保证每次call get_one_id()不能等待超过1s

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 X2+Y2=r2, where r is radius.
Circle Generation


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).

Bresenham’s Algorithm


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

这是一个二维数组,不是一个heap(heap就是说这个树存在一个一维数组里,满足A的child是A[2i+1]和A[2i+2]),问题背景起源于内存分配问题
比如有N个level,第一个level有一个bit,第二个level有2个bit,第三个level有四个bit,调用第x个level的第y个bit直接用A[x][y]. 鍥磋鎴戜滑@1point 3 acres
那么A[x][y]的孩子包括A[x+1][2y] 和 A[x+1][2y+1]
题目要求完成的是:
例如ClearBits(A, 4,9) => 把第N个level的第4位到第9位清0. 当child清0之后, parent也要跟着清0,一直到root




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
            }
        }
    }
}