Zenefits OA3 换题库了吗这是

Zenefits OA test 3。。。
这周是换题库了吗？ 打开完全不是说好的good value 和 stock变种啊。。 准备了半天。。
因为是新题库就简单说下题目和思路，防止认出来。

1 longestchain
类似word ladder，对于一个单词删掉任何一个字母，如果新单词出现在给的词典里 那么就形成一个 chain： old word -> new word -> newer word, 求最长长度(return int) 比如给vector<string> w = {a,ba,bca,bda,bdca} 最长是4： bdca->bda->ba->a;
思路: 建一个map<长度，set<string>> 根据长度把输入的字典放到set里，然后从最长的长度所在的map[长度] 开始枚举每个单词并缩减然后进行recursive call， 比如bdca 那么就可能缩成dca,bca,bda 然后去map[3]里找，类推直到 word.size()==1 或找不到， 放个全局int去记最大长度。
注意找到后从字典里删除和word ladder一样 否则只能过4个case 会超时。

2 N queen 变种
题目巨长输入格式是

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

因为换题临时比较匆忙，方法不好还请大家指出，就当抛砖引玉攒RP了。
大家找工作加油 干死印度人。


补充内容 (2015-4-20 12:23):
hashset存最近的上一个queen就好了这样不用追踪回去浪费时间

我也遇到了这个。。之前没看到这个帖子。 第二题楼主给的应该是最优解了。不过第一题是可以用DP做的，思路和楼主的也差不多. 只不过hashmap里存的是另一个word->maxchain的hashmap，然后从length=1时开始往上build,如果相邻的两个length差距超过1就跳过

ohohgod 发表于 2015-5-6 01:46
楼主能上代码么

思路可以共享 代码不开源

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

新手求大米。。。没人理。。

我大概两周前做的时候还不是这个题，估计是换题了吧，多谢分享！

顶楼主，按照楼主的方法过了OA，但是1有个问题，假如最长的单词和其他的单词不是连起来的 比如vector<string> w = {a,ba,bca,bda,bdca,adsasdasda}这样最长的长度所在的map[长度] 开始枚举就不行了

但是OA里面是可行的 lol

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

是的，我也做的这个。这两道题还算简单。

ManitobaFarmer 发表于 2015-4-26 11:33
是的，我也做的这个。这两道题还算简单。

请问第二题是不是只要遇到一个queen受到4个方向的威胁就可以返回了，因为最多威胁也就是4，对吗？

refurbish 发表于 2015-4-26 15:41
请问第二题是不是只要遇到一个queen受到4个方向的威胁就可以返回了，因为最多威胁也就是4，对吗？

是的 最多4

refurbish 发表于 2015-4-26 15:41
请问第二题是不是只要遇到一个queen受到4个方向的威胁就可以返回了，因为最多威胁也就是4，对吗？

6个吧。上下和四个斜面。

ManitobaFarmer 发表于 2015-5-1 01:38
6个吧。上下和四个斜面。

好像题目的输入方式决定了每列每行只有1个queen