zenefit 电面面经整合

原帖地址:一亩三分地

之前面试zenefit整理地理的面经,希望对要面的同学有帮助,虽然这家跪了,求人品
stack
expression evalution
. Waral 鍗氬鏈夋洿澶氭枃绔 有点像 reverse polish notation 的变种,计算一个表达式的值的。要求自行设计表达式的数据结构并计算表达式的值。

有几种特殊情况
1. 单输入一个数,比如 [0],是合法,结果为0;-google 1point3acres
2. 单输入一个运算符也是合法的。 无数字运算的 ‘+’, ‘-‘, ‘/’ 结果为 0, 单个 ‘*’ 的结果为 1.
3. 一个运算符可以有好几个计算数字。 比如输入为 [‘+’, 1, 2, 3],结果为1 + 2 + 3 = 6
4. 表达式可嵌套,[‘+’, 1, 2, [‘*’, 1, 3]],这样结果为 1 + 2 + 1 * 2 = 5.
输入一定合法,不用考虑给了两个连续数字却没有运算符的情况,也不用考虑除数为0的情况。
我的做法为新建一个 Expression 类,用于解决输入包含运算符,数字,或者expression三种情况,这样输入就可以为一个Expresssion 的List,再用一个Queue来决定问题。不知道有没有大神有更好的做法。
use two stack to store the operation, nums. if cur operation is small or equal to previous one, the
3 sum smaller
input 為兩個輸入
1. integer
2. list
計算 list中滿足 三個值的和 小於或等於 integer 的數目

e.q.
integer = 8
list = [1, 2, 3, 4, 6]
ifonly need the count of result, then build segment tree to store who many uniq nums in each segment. the time complexity is n^2 log N
if need to return all combination, the time complexity is n^3.
public static ArrayList<ArrayList<Integer>> threeSumEqualOrLess(int[] data, int target) {
ArrayList<ArrayList<Integer>> output = new ArrayList<>();
if(data == null || data.length == 0) {
return output;
}
Arrays.sort(data);
for(int i = 0; i < data.length – 2; i++) {
if(i == 0 || data != data[i – 1]) {
int sum = target – data;
int start = i + 1;
int end = data.length – 1;
while(start < end) {
if(data[start] + data[end] <= sum) {
//need to dedup with merge backWords
ArrayList<ArrayList<Integer>> temp = mergeAllEndBackwardsResult(data, i, start, end);
output.addAll(temp);.1point3acres缃

start++;
while (start < end data[start] == data[start – 1])
start++;
} else {
end–;
}
}
}
}.1point3acres缃
return output;
}

public static ArrayList<ArrayList<Integer>> mergeAllEndBackwardsResult(int[] data, int i, int j, int k) {
ArrayList<ArrayList<Integer>> output = new ArrayList<>();
while(j < k) {
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(data);
temp.add(data[j]);
temp.add(data[k]);
output.add(temp);
System.out.println("mergeToAResult" + Arrays.toString(temp.toArray()));

k–;
//avoid duplicate solutions
while (j < k data[k] == data[k + 1])
k–;

}
return output;
}

super stack
操作有push, pop。 还有一个是inc a b。实现stack的bottom a个数都加b
use dequeue, push pop in one side and inc(a,b) in another side

实现一个数据结构包含三个功能,push, pop, getmin,time complexity均要为O(1), 不可以调用API,自己实现了double linkedlist,而且要求只用一个list
push the element in one side and the minimum element in another side.

HashMap
LRU Cache
Queue
题目巨长输入格式是. 1point3acres.com/bbs
1
2.
就是说 第1行第1个是queen 第2行第2个是queen,并保证输入的数字不重复,这样可以得出一个结论:同一行 同一列不会出现2个queen。
题目要求是求出 对于每个Queen, 最大的威胁次数,威胁指只要一个queen所能移动的范围内有别的queen就算威胁 P.S.同一方向上有2个queen威胁你 只算最近的那个。
由于同一行 同一列不会出现2个queen。(由于输入限制)所以只要考虑对角线 和逆对角线。
举个例子: 棋盘是:
100 —- 1号 queen
010 —- 2号 queen
001 —- 3号 queen