Zenifits 面经 | Hello World
下面是搜集的online assessment的题目
1. longest chain：
类似word ladder，对于一个单词删掉任何一个字母，如果新单词出现在给的词典里 那么就形成一个 chain： old word -> new word -> newer word, 求最长长度(return int) 比如给vector w = {a,ba,bca,bda,bdca} 最长是4： bdca->bda->ba->a;
思路和word ladder一样，我们可以先sort这个set， 然后从最长的开始。（或者我们建立一个hashMap， 单词长度作为key，单词存进一个list作为value， 这样也可以从最长的开始），然后遍历删除每个字母检查是否在字典中，如果在的话可以把max++, 然后把单词从字典中删除（如果从长度最大的单词一次往下遍历，删除是合理的，因为这个单词肯定已经在最长的list里算过了）， 最后return max即可。
2 N queen 变种
题目巨长输入格式是
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
1号和3号queen的受威胁次数都是1， 2号是2（被1和3） 所以答案是2
简单的做法就是每个queen都遍历两个对角线，只要碰到有一个threat，threat就++， threat最多只能有四个。
我还能想到另外一种做法，就是用mask，以上面的例子为例，每一行做一个mask，然后当mask往下移动一行的话就需要left shift（right shift for another diag）再和下一行queen的位置or作为新的mask， 如果mask和当前queen的位置and是大于1的话，说明有thread，从上到下扫一遍只能找到上面的diagnal，对于每一行要记录当前行从上到下的thread，然后再从下到上用同样方法扫一遍就可以了。
Onsite题：
1.Design a service that returns a unique integer for each request.
可以用timestamp + machineid + thread_id + cnt
2.find median of two sorted array
这道题是leetcode题，注意边界条件，先讨论General情况，然后考虑边界条件。注意start， end和k的关系，start和end应该是坐标，而k是从start开始算的数。
brain teaser
一副扑克牌52张，你从里面抽5张，看了牌之后你放回去一张，剩下的4张按顺序排放
给你的朋友看，你和你的朋友实现约定好如何encode/decode这四张牌，问如何decode、encode才能让你的朋友猜出来放回牌堆的是哪张牌
首先我们可以知道的是5张牌一定是有两张同花色的，然后我们挑小的那一张放进去，大的那一张留下用来表示花色。最后剩下的3张做permutation，可以有6种方法，然后用这六个编码表示小的那张牌到大的那张牌的offset。
Read full article from Zenifits 面经 | Hello World
下面是搜集的online assessment的题目
1. longest chain：
类似word ladder，对于一个单词删掉任何一个字母，如果新单词出现在给的词典里 那么就形成一个 chain： old word -> new word -> newer word, 求最长长度(return int) 比如给vector w = {a,ba,bca,bda,bdca} 最长是4： bdca->bda->ba->a;
思路和word ladder一样，我们可以先sort这个set， 然后从最长的开始。（或者我们建立一个hashMap， 单词长度作为key，单词存进一个list作为value， 这样也可以从最长的开始），然后遍历删除每个字母检查是否在字典中，如果在的话可以把max++, 然后把单词从字典中删除（如果从长度最大的单词一次往下遍历，删除是合理的，因为这个单词肯定已经在最长的list里算过了）， 最后return max即可。
2 N queen 变种
题目巨长输入格式是
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
1号和3号queen的受威胁次数都是1， 2号是2（被1和3） 所以答案是2
简单的做法就是每个queen都遍历两个对角线，只要碰到有一个threat，threat就++， threat最多只能有四个。
我还能想到另外一种做法，就是用mask，以上面的例子为例，每一行做一个mask，然后当mask往下移动一行的话就需要left shift（right shift for another diag）再和下一行queen的位置or作为新的mask， 如果mask和当前queen的位置and是大于1的话，说明有thread，从上到下扫一遍只能找到上面的diagnal，对于每一行要记录当前行从上到下的thread，然后再从下到上用同样方法扫一遍就可以了。
Onsite题：
1.Design a service that returns a unique integer for each request.
可以用timestamp + machineid + thread_id + cnt
2.find median of two sorted array
这道题是leetcode题，注意边界条件，先讨论General情况，然后考虑边界条件。注意start， end和k的关系，start和end应该是坐标，而k是从start开始算的数。
brain teaser
一副扑克牌52张，你从里面抽5张，看了牌之后你放回去一张，剩下的4张按顺序排放
给你的朋友看，你和你的朋友实现约定好如何encode/decode这四张牌，问如何decode、encode才能让你的朋友猜出来放回牌堆的是哪张牌
首先我们可以知道的是5张牌一定是有两张同花色的，然后我们挑小的那一张放进去，大的那一张留下用来表示花色。最后剩下的3张做permutation，可以有6种方法，然后用这六个编码表示小的那张牌到大的那张牌的offset。
Read full article from Zenifits 面经 | Hello World
