## Monday, November 30, 2015

### Google Interview Misc Part 4

O(n),n是数组大小，其实意思跟leetcode里面Longest Consecutive Sequence的意思是一样的，只不过现在不是找前后连续的了，原来找前面是cur-1，现在是cur->prev，后面试cur+1变成cur->next，可以看看discuss我再里面写了做法

static class DoublyNode {
DoublyNode prev;
DoublyNode next;
int val;
public DoublyNode(int val) {
this.val = val;
}
}

public static int nodesGroupNumber(DoublyNode[] nodes) {
if (nodes == null || nodes.length == 0) {
return 0;
}
HashSet<DoublyNode> set = new HashSet<DoublyNode>();
for (DoublyNode node : nodes) {
}
int res = 0;
for (DoublyNode node : nodes) {
System.out.println(node.val);
if (!set.contains(node)) {
continue;
}
res++;
set.remove(node);
DoublyNode cur = node.prev;
while (cur != null && set.contains(cur)) {
set.remove(cur);
cur = cur.prev;
}
cur = node.next;
while (cur != null && set.contains(cur)) {
set.remove(cur);
cur = cur.next;
}
}
return res;
}

A =【1 5 7 】. visit 1point3acres.com for more.

Nmiss = [1 3 1 9993].

Ncum = [1 4 5 9998]

1. Flip game (allPossible moves, canWin)
2. Find Camel:
Input: "FooBar", "FoBa", "FooBarFoo"
Pattern : "FBF"
Output " "FooBarFoo"
3. Run length string encoding.
4. Array of String Serialization, and deserialization
5. Top K int in a large stream (This can be done in O(n))

1. 判對是不是BST,  秒寫完，follow up BST定義具體講明，時間複雜度分析，面試官覺得我code很新奇
2. 棋盤遊戲，走過的格子不能走，寫出每一條路走到底的組合
提示過後用了dfs 但時間不太夠了面試官讓我講講想法，
(具體解法:hasBeen[i][j] = true;
recurse(i, j);.
hasBeen[i][j] = false;)

newAverage ＝ (oldAverage * windowSize - dequeue + enqueue) / windowSize

private int findMaxLengthIn1DArray(int[] nums, int target) {
int max = 0, i = 0, sta = 0, sum = 0;
while (i < nums.length) {
sum += nums;
if (sum > target) {
max = Math.max(max, i-sta);
}
while (sum > target) {
sum -= nums[sta++];
}
i++;
}
return max == 0 ? nums.length : max;
}

public int getMaxArea(int[][] nums, int target) {
int wid = nums.length, len = nums[0].length, max = 0;
for (int j1 = 0; j1 < wid; j1++) {
int[] tmp = new int[len];
for (int j2 = j1; j2 < wid; j2++) {
for (int i = 0; i < len; i++) {
tmp += nums[j2];
}
int tempMax = findMaxLengthIn1DArray(tmp, target);
max = Math.max(max, tempMax*(j2-j1+1));
}
}
return max;
}

android pin 如果输入一系列密码， 不能有重复，不能少于四个，然后看密码是不是valid。

012
345
678

1、给一个二维字符矩阵，比如
*****
**#**
*?*?*
**?**
*****

2、thesis review
3、course schedule
4、The skyline problem
5、第一题是unique paths。然后问如果随机选择一条可行路径，那么第一步往右走的概率是多少。

follow up 1: 我开始用递归写的，小哥问递归会出现什么问题，不用递归怎么写。.

follow up2: 怎么测时间是不是超过time limit？