一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 8791|回复: 33
收起左侧

zenefit oa /cisco/godaddy 攒攒rp

[复制链接] |试试Instant~ |关注本帖
calvinq 发表于 2015-4-20 01:59:55 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Ciscozenefits/godaddy - Other - 技术电面 Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Zenefits OA test 3... 感觉跟大家的不太一样...也有可能我刷面经时没看见...... 鍥磋鎴戜滑@1point 3 acres
两道题目:
(1)longestchain
给一个字符串数组, 以任意一个单词开始,删除一个字母 ,如果形成的新字符串还在数组的单词堆里面,则是合法的, chain长度增加1.然后继续往下删,每删一个则长度增加1.. 鍥磋鎴戜滑@1point 3 acres
举些例子吧:(a, abcd, bcd, abd, cd, c):
abcd 删除一个字母可以变成 bcd , abd, acd,abc。但是只有bcd, acd 可以往下走,所以下面只要考虑这两个。 bcd 可以变成cd 再变成c。 但是abd删除一个单词不能变成数组的一个单词。所以停止。

返回最长的chain含有单词的数目: abcd-- bcd -- cd -- c,返回4.

这题我是直接暴力解的,只是用了一个hashset. 搜过的就不会重复搜了。 哪位大神可以提供一下更好思路哈....

(2) n-queen 小变种

这题我做傻xx了..一开始理解错题意了.... 题目超长还有背景介绍蛋疼。其实就是简单的给你一个数组,代表一个放好了queen的棋盘。 然后要返回受到威胁数最多的queen受到的威胁数。

这里有两点要注意的,这题只考虑斜着的威胁,不用考虑横竖的...第二queen不能隔着一个或几个威胁。

举例吧:给你数组[1,2,3,4,5],就代表1行1列有个queen, 2行2列....5行5列都有一个queen。 这时候最大的威胁数是2. 因为隔着不能威胁,所以1只能威胁2, 不能威胁3. 但是2受到1喝3的威胁。
这道题..后来朋友跟我说用四个flag判断来排除一个方向已经有威胁的情况。。但是感觉也挺慢的。

Cisco....投了很久了....突然叫我明天去公司聊聊...然后我就屁颠屁颠的去了。
问了各式各样的东西。算法题应该是挺常见的吧:
2个queue 实现stack, 两个stack 实现queue。但是有个比较奇怪的follow up, 假如两个queue capacity都是3, 要你先加6个数,再pop 一个,然后又push 1个。怎么不利用别的数据结构实现..有点奇怪~~
external sort.....100gb文件,内存只有5mb 怎么sort.....
去string 里重复的字母.鐣欏璁哄潧-涓浜-涓夊垎鍦
用mvc pattern 模拟处理一个网络(几个电脑啊..之类的)+一个数据库。 其实我连题目都没听懂~~~~蛋疼.... 我就没懂mvc 怎么模拟东西...。伤
还问了一些死锁,hashmap/hashtable,javascript的问题。

godaddy 1轮面试..没coding...一直问...一直问....
reverse string 的思路。
cardgames oop design。 好多个card game。然后怎么design 。 涉及deck card, hand 等等的类。
然后就说好多java 基础问题。 3个principle 之类的,非常详细。

希望能攒攒rp吧......

评分

5

查看全部评分

badweather 发表于 2016-6-1 10:51:50 | 显示全部楼层
第一题我觉得可能可以用DP,string 减一个char和加一个没有什么区别,这样先把string 按length排序,然后考虑length相邻的string 能不能加1
回复 支持 1 反对 0

使用道具 举报

liushen 发表于 2015-4-20 03:10:09 | 显示全部楼层
额??Zenefits OA换题库了嘛??楼主是software engineer 的测试test 3 嘛?
为啥我上上个星期做得test 3题目跟你完全不一样。。。我的超级简单
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-4-20 03:25:26 | 显示全部楼层
liushen 发表于 2015-4-20 03:10
额??Zenefits OA换题库了嘛??楼主是software engineer 的测试test 3 嘛?. visit 1point3acres.com for more.
为啥我上上个星期做得test 3 ...

我想是吧...所以说蛋疼......
回复 支持 反对

使用道具 举报

lby8833 发表于 2015-4-20 04:02:45 | 显示全部楼层
今天做的,跟lz一模一样。。。
回复 支持 反对

使用道具 举报

sue0927 发表于 2015-4-20 04:23:35 | 显示全部楼层
第一个是亚马逊的面经 可以用trie树做
回复 支持 反对

使用道具 举报

YY大帝 发表于 2015-4-20 04:52:02 | 显示全部楼层
sue0927 发表于 2015-4-20 04:23. 1point 3acres 璁哄潧
第一个是亚马逊的面经 可以用trie树做

请问用trie思路,能稍微解释下吗
回复 支持 反对

使用道具 举报

liushen 发表于 2015-4-20 04:52:55 | 显示全部楼层
第一题不是很清楚怎么样可以用trie做,我觉得直接暴力解吧。trie不好做啊. visit 1point3acres.com for more.
第二题。。。我不是很明白啊。。。直接看每个queen四个斜边上有没有queen不就可以了嘛?规则里面说隔着的不算,横着竖着的也不算,那最大的可能就是4了啊。。。。看看哪个queen四个角上有queen不就可以了吗。。。??还是我题意理解不对??
那个, 楼主,你的test case都过了吗?都过了,没有time' limit out就可以了,在家等phone interview吧
回复 支持 反对

使用道具 举报

hit_piggy 发表于 2015-4-20 05:39:23 | 显示全部楼层
cisco是Meraki还是Cisco本身啊。。
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-4-20 07:05:28 | 显示全部楼层
hit_piggy 发表于 2015-4-20 05:39. from: 1point3acres.com/bbs
cisco是Meraki还是Cisco本身啊。。
-google 1point3acres
好像是cisco......
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-4-20 07:07:14 | 显示全部楼层
liushen 发表于 2015-4-20 04:52
第一题不是很清楚怎么样可以用trie做,我觉得直接暴力解吧。trie不好做啊
第二题。。。我不是很明白啊。。 ...

我test case都没全过....
第一题..一直有个case不过....55
第二题..到最后才理解题意.....蛋疼...对啊.对啊..就是最大4...所以我后来觉得.用4个flag..遍历全部点..
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-4-20 07:07:33 | 显示全部楼层
sue0927 发表于 2015-4-20 04:23
第一个是亚马逊的面经 可以用trie树做

求大神指导....
回复 支持 反对

使用道具 举报

gaohannk 发表于 2015-4-20 07:12:41 | 显示全部楼层
zenefit 第二题我和同学一起做的,理解出三种意思,之前全错了,
1: 所有威胁,也就是几对互相威胁
2:有多少queen可以威胁到别的queen,不管一个Queen能威胁几个。
3 一个queen能威胁的最多的数目
所有说先知道要求什么。. 1point 3acres 璁哄潧
.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2015-4-20 07:13):
还有注意note里面不能跳子威胁。
回复 支持 反对

使用道具 举报

gaohannk 发表于 2015-4-20 07:14:12 | 显示全部楼层
gaohannk 发表于 2015-4-20 07:12. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
zenefit 第二题我和同学一起做的,理解出三种意思,之前全错了,
1: 所有威胁,也就是几对互相威胁
2:有 ...

不能竖着威胁吗?
回复 支持 反对

使用道具 举报

sue0927 发表于 2015-4-20 07:34:57 | 显示全部楼层
我写了个雏形 你们自己看着改 争取能冲破ZEF烙印的防线 输入写 pig . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

def mapCharToNum(char):
    return ord(char) - ord("a")
    -google 1point3acres
def mapNumToChar(num):
    return chr(num + ord("a"))

class Node:
    def __init__(self):
        self.count = 0
        self.next = [None for i in range(26)] #map [a-z] to [0-25]

class Trie:
    def __init__(self):-google 1point3acres
        self.root = Node()
        self.ret = {}
        
    def insert(self, word):
        cur = self.root
        
        for char in word:
            idx = mapCharToNum(char)
            if cur.next[idx] == None:
                cur.next[idx] = Node()
            cur = cur.next[idx]
        
        cur.count = cur.count + 1
   
    def search(self, word):
        cur = self.root
        
        for char in word:
            idx = mapCharToNum(char)
            if cur.next[idx] == None:
                return False
            cur = cur.next[idx]
        
        return cur.count != 0
        
tree = Trie()
tree.insert('book')
tree.insert('big'). 鍥磋鎴戜滑@1point 3 acres
tree.insert('bigbang')
tree.insert('as'). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
tree.insert('pig'). visit 1point3acres.com for more.
tree.insert('ig')
tree.insert('g')
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
candidate = raw_input("check your word")
length = 0
def check(candidate):
    global length
    if candidate!=None and (tree.search(candidate)):
        length += 1
        check(candidate[1:])
check(candidate)        
print length
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-4-20 08:33:57 | 显示全部楼层
sue0927 发表于 2015-4-20 07:34
我写了个雏形 你们自己看着改 争取能冲破ZEF烙印的防线 输入写 pig
. from: 1point3acres.com/bbs
def mapCharToNum(char):
.1point3acres缃
想问问大神.你这个不是也得把所有单词至少都搜一遍么?你是在用trie来查找那个新形成的单词存在不存在?
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-4-20 08:34:42 | 显示全部楼层
gaohannk 发表于 2015-4-20 07:12
zenefit 第二题我和同学一起做的,理解出三种意思,之前全错了,
1: 所有威胁,也就是几对互相威胁
2:有 ...

我是第一种理解....xxx的..我也是几个人在做....理解了半天....
回复 支持 反对

使用道具 举报

sue0927 发表于 2015-4-20 09:05:27 | 显示全部楼层
trie树搜索一个单词一般来说是O(1), 最多就是log(N)
但如果你要找最长的长度 那就是遍历所有形成的单词了 pig -> ig -> g 那就是O(n)
回复 支持 反对

使用道具 举报

cuiyang36 发表于 2015-4-20 10:11:43 | 显示全部楼层
我感觉第一题不用trie这么高大上的数据结构去解吧,毕竟是OA,我觉得BFS + HashSet应该就够了吧,类似于word ladder I那题
回复 支持 反对

使用道具 举报

kevinking813 发表于 2015-4-20 10:18:22 | 显示全部楼层
正在做  为啥不用考虑 横竖的威胁啊 文中没有提及
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-4-20 11:14:13 | 显示全部楼层
kevinking813 发表于 2015-4-20 10:18
正在做  为啥不用考虑 横竖的威胁啊 文中没有提及

你好好看吧...我也忘了..没有直接说不用考虑...但是我忘了...看到有个地方.就可以确定不用考虑了..... visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 22:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表