y***1
发帖数: 18 | 1 mountain view 两周前面的，今天电话来hiring committee没过。
（1） 中年白人： 先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看
能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不
能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不
是solvable. 写出来了， 就是用BFS,有个小bug被指出。然后问复杂度， 问如何优化。
（2） 韩国人： a) 给一个dictionary, 再给一个set of coding string （g5, goo3,
goog2, go2le.........). return all string from dictionary that can be
matched with the coding string. 要求尽量减少dictionary look up 次数。给了个
方法，但一直不满意复杂度。
（b)如何用Trie, 把问题(a)解决,要求写code 建一个Trie包
括所有字典词和coding string.不是很明白。。。凭感觉写了个。
（3） 阿三， 非常拽。。。 给一个dictionary, 一个string,找出dict 里能全部用
string里的letter 表示的所有最长的词。给了算法，死活不满意，不让我写code. 估
计被黑了。
(4）阿三。 design google calendar . 要求分析如何存data, 如何invoke user
created events, 如何handle 100000events per second, 然后要写了一部分thread
safe 的code 实现如何invoke event.
(5)年轻白人： (a)leetcode 上的coin 题， 用DP. (b)给你一个password 假定6位，
有个function 每call 一次就给你一个triplet 是password 里的随即三位，order不变
。比如google, 可能返回， ggl, goe, oog, ool, ........
问如何最有效破译这个密码，写code.
下周Facebook onsite, 求bless | c****m
发帖数: 179 | 2 第四个invoke event什么意思？ 是说同一个event同时给用户发提醒吗？这个是只读不
写吧？除了记录用户是否收到？ | l*****a
发帖数: 14598 | 3 bless
谢谢分享
化。
goo3,
【在 y***1 的大作中提到】
: mountain view 两周前面的，今天电话来hiring committee没过。
: （1） 中年白人： 先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看
: 能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不
: 能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不
: 是solvable. 写出来了， 就是用BFS,有个小bug被指出。然后问复杂度， 问如何优化。
: （2） 韩国人： a) 给一个dictionary, 再给一个set of coding string （g5, goo3,
: goog2, go2le.........). return all string from dictionary that can be
: matched with the coding string. 要求尽量减少dictionary look up 次数。给了个
: 方法，但一直不满意复杂度。
: （b)如何用Trie, 把问题(a)解决,要求写code 建一个Trie包
| t*********7
发帖数: 255 | | M*******a
发帖数: 1633 | 5 2(b)基本就是提示2a应该用trie来解了吧
密码题里面要是字母不重复还可以，有重复比较复杂 | r*****e
发帖数: 30 | 6 密码那道题有什么思路吗？感觉如果有重复可能永远也猜不出来 | s**x
发帖数: 7506 | 7
是不是跟那个 连续 4个数字(0000-9999)的密码锁类似？
for google, you need xxg, xgo, goo, oog, ogl, gle?
not sure how many circles are there yet.
好像不对 。。。
【在 r*****e 的大作中提到】
: 密码那道题有什么思路吗？感觉如果有重复可能永远也猜不出来
| x****m
发帖数: 1084 | | c********r
发帖数: 286 | | K*******g
发帖数: 26 | 10 一个想法：
大量调用function之后算字母出现的概率。
可以算出前四位字母出现在结果首位的概率比例为C(5,2):C(4,2):C(3,2):C(2,2)=10:6
:3:1
拿google为例，g和o出现在首位比例应为11:9
因为11>10,首字母为g，剩下g:o=1:9，同理可算出后续字母为o,o,g
实际算法可能还需要考虑一些极端情况
【在 r*****e 的大作中提到】
: 密码那道题有什么思路吗？感觉如果有重复可能永远也猜不出来
| | | y***1
发帖数: 18 | 11 面试官说这题用图来做， 我觉得可以用toplogical sort
【在 K*******g 的大作中提到】
: 一个想法：
: 大量调用function之后算字母出现的概率。
: 可以算出前四位字母出现在结果首位的概率比例为C(5,2):C(4,2):C(3,2):C(2,2)=10:6
: :3:1
: 拿google为例，g和o出现在首位比例应为11:9
: 因为11>10,首字母为g，剩下g:o=1:9，同理可算出后续字母为o,o,g
: 实际算法可能还需要考虑一些极端情况
| h*d
发帖数: 19309 | | m**r
发帖数: 574 | 13 Bless楼主，fb顺利！
请问这个怎么优化？
（1） 中年白人： 先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看
能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不
能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不
是solvable. 写出来了， 就是用BFS,有个小bug被指出。然后问复杂度， 问如何优化
。 | l****i
发帖数: 51 | 14 密码那道题,可以利用一个节点建立初始6度选择树. 26**6个分叉. 第一个输入共有最
多C(6, 3) * 26 * 26 * 26 选项400k个分叉, 然后一个个输入剪枝,开始应该剪得很多
. You might need to prune the whole node if nothing below.
Traverse each leaf, to save time, take input xyz as a regular expression. *X
*Y*Z, make it 6 steps to walk down and match in lenear time.
Until the last path left, that is the solution. | z******h
发帖数: 22 | 15 这个算纯暴力流吧
*X
★ 发自iPhone App: ChineseWeb 7.8
【在 l****i 的大作中提到】
: 密码那道题,可以利用一个节点建立初始6度选择树. 26**6个分叉. 第一个输入共有最
: 多C(6, 3) * 26 * 26 * 26 选项400k个分叉, 然后一个个输入剪枝,开始应该剪得很多
: . You might need to prune the whole node if nothing below.
: Traverse each leaf, to save time, take input xyz as a regular expression. *X
: *Y*Z, make it 6 steps to walk down and match in lenear time.
: Until the last path left, that is the solution.
| A*********c
发帖数: 430 | 16 bless lz！
化。
goo3,
【在 y***1 的大作中提到】
: mountain view 两周前面的，今天电话来hiring committee没过。
: （1） 中年白人： 先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看
: 能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不
: 能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不
: 是solvable. 写出来了， 就是用BFS,有个小bug被指出。然后问复杂度， 问如何优化。
: （2） 韩国人： a) 给一个dictionary, 再给一个set of coding string （g5, goo3,
: goog2, go2le.........). return all string from dictionary that can be
: matched with the coding string. 要求尽量减少dictionary look up 次数。给了个
: 方法，但一直不满意复杂度。
: （b)如何用Trie, 把问题(a)解决,要求写code 建一个Trie包
| y***1
发帖数: 18 | 17 mountain view 两周前面的，今天电话来hiring committee没过。
（1） 中年白人： 先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看
能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不
能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不
是solvable. 写出来了， 就是用BFS,有个小bug被指出。然后问复杂度， 问如何优化。
（2） 韩国人： a) 给一个dictionary, 再给一个set of coding string （g5, goo3,
goog2, go2le.........). return all string from dictionary that can be
matched with the coding string. 要求尽量减少dictionary look up 次数。给了个
方法，但一直不满意复杂度。
（b)如何用Trie, 把问题(a)解决,要求写code 建一个Trie包
括所有字典词和coding string.不是很明白。。。凭感觉写了个。
（3） 阿三， 非常拽。。。 给一个dictionary, 一个string,找出dict 里能全部用
string里的letter 表示的所有最长的词。给了算法，死活不满意，不让我写code. 估
计被黑了。
(4）阿三。 design google calendar . 要求分析如何存data, 如何invoke user
created events, 如何handle 100000events per second, 然后要写了一部分thread
safe 的code 实现如何invoke event.
(5)年轻白人： (a)leetcode 上的coin 题， 用DP. (b)给你一个password 假定6位，
有个function 每call 一次就给你一个triplet 是password 里的随即三位，order不变
。比如google, 可能返回， ggl, goe, oog, ool, ........
问如何最有效破译这个密码，写code.
下周Facebook onsite, 求bless | c****m
发帖数: 179 | 18 第四个invoke event什么意思？ 是说同一个event同时给用户发提醒吗？这个是只读不
写吧？除了记录用户是否收到？ | l*****a
发帖数: 14598 | 19 bless
谢谢分享
化。
goo3,
【在 y***1 的大作中提到】
: mountain view 两周前面的，今天电话来hiring committee没过。
: （1） 中年白人： 先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看
: 能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不
: 能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不
: 是solvable. 写出来了， 就是用BFS,有个小bug被指出。然后问复杂度， 问如何优化。
: （2） 韩国人： a) 给一个dictionary, 再给一个set of coding string （g5, goo3,
: goog2, go2le.........). return all string from dictionary that can be
: matched with the coding string. 要求尽量减少dictionary look up 次数。给了个
: 方法，但一直不满意复杂度。
: （b)如何用Trie, 把问题(a)解决,要求写code 建一个Trie包
| t*********7
发帖数: 255 | | | | M*******a
发帖数: 1633 | 21 2(b)基本就是提示2a应该用trie来解了吧
密码题里面要是字母不重复还可以，有重复比较复杂 | r*****e
发帖数: 30 | 22 密码那道题有什么思路吗？感觉如果有重复可能永远也猜不出来 | s**x
发帖数: 7506 | 23
是不是跟那个 连续 4个数字(0000-9999)的密码锁类似？
for google, you need xxg, xgo, goo, oog, ogl, gle?
not sure how many circles are there yet.
好像不对 。。。
【在 r*****e 的大作中提到】
: 密码那道题有什么思路吗？感觉如果有重复可能永远也猜不出来
| x****m
发帖数: 1084 | | c********r
发帖数: 286 | | K*******g
发帖数: 26 | 26 一个想法：
大量调用function之后算字母出现的概率。
可以算出前四位字母出现在结果首位的概率比例为C(5,2):C(4,2):C(3,2):C(2,2)=10:6
:3:1
拿google为例，g和o出现在首位比例应为11:9
因为11>10,首字母为g，剩下g:o=1:9，同理可算出后续字母为o,o,g
实际算法可能还需要考虑一些极端情况
【在 r*****e 的大作中提到】
: 密码那道题有什么思路吗？感觉如果有重复可能永远也猜不出来
| y***1
发帖数: 18 | 27 面试官说这题用图来做， 我觉得可以用toplogical sort
【在 K*******g 的大作中提到】
: 一个想法：
: 大量调用function之后算字母出现的概率。
: 可以算出前四位字母出现在结果首位的概率比例为C(5,2):C(4,2):C(3,2):C(2,2)=10:6
: :3:1
: 拿google为例，g和o出现在首位比例应为11:9
: 因为11>10,首字母为g，剩下g:o=1:9，同理可算出后续字母为o,o,g
: 实际算法可能还需要考虑一些极端情况
| h*d
发帖数: 19309 | | m**r
发帖数: 574 | 29 Bless楼主，fb顺利！
请问这个怎么优化？
（1） 中年白人： 先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看
能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不
能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不
是solvable. 写出来了， 就是用BFS,有个小bug被指出。然后问复杂度， 问如何优化
。 | l****i
发帖数: 51 | 30 密码那道题,可以利用一个节点建立初始6度选择树. 26**6个分叉. 第一个输入共有最
多C(6, 3) * 26 * 26 * 26 选项400k个分叉, 然后一个个输入剪枝,开始应该剪得很多
. You might need to prune the whole node if nothing below.
Traverse each leaf, to save time, take input xyz as a regular expression. *X
*Y*Z, make it 6 steps to walk down and match in lenear time.
Until the last path left, that is the solution. | | | z******h
发帖数: 22 | 31 这个算纯暴力流吧
*X
★ 发自iPhone App: ChineseWeb 7.8
【在 l****i 的大作中提到】
: 密码那道题,可以利用一个节点建立初始6度选择树. 26**6个分叉. 第一个输入共有最
: 多C(6, 3) * 26 * 26 * 26 选项400k个分叉, 然后一个个输入剪枝,开始应该剪得很多
: . You might need to prune the whole node if nothing below.
: Traverse each leaf, to save time, take input xyz as a regular expression. *X
: *Y*Z, make it 6 steps to walk down and match in lenear time.
: Until the last path left, that is the solution.
| A*********c
发帖数: 430 | 32 bless lz！
化。
goo3,
【在 y***1 的大作中提到】
: mountain view 两周前面的，今天电话来hiring committee没过。
: （1） 中年白人： 先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看
: 能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不
: 能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不
: 是solvable. 写出来了， 就是用BFS,有个小bug被指出。然后问复杂度， 问如何优化。
: （2） 韩国人： a) 给一个dictionary, 再给一个set of coding string （g5, goo3,
: goog2, go2le.........). return all string from dictionary that can be
: matched with the coding string. 要求尽量减少dictionary look up 次数。给了个
: 方法，但一直不满意复杂度。
: （b)如何用Trie, 把问题(a)解决,要求写code 建一个Trie包
| l*********d
发帖数: 78 | 33 用 topological sort 来做这道题，感觉还是不知道如何下手。请问有大牛有思路吗？ | T*****u
发帖数: 7103 | 34 起点和重点同时搜？
【在 m**r 的大作中提到】
: Bless楼主，fb顺利！
: 请问这个怎么优化？
: （1） 中年白人： 先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看
: 能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不
: 能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不
: 是solvable. 写出来了， 就是用BFS,有个小bug被指出。然后问复杂度， 问如何优化
: 。
| T*****u
发帖数: 7103 | 35 HMM?
【在 s**x 的大作中提到】
:
: 是不是跟那个 连续 4个数字(0000-9999)的密码锁类似？
: for google, you need xxg, xgo, goo, oog, ogl, gle?
: not sure how many circles are there yet.
: 好像不对 。。。
| f******n
发帖数: 279 | | l*********u
发帖数: 19053 | 37 bless
化。
goo3,
【在 y***1 的大作中提到】
: mountain view 两周前面的，今天电话来hiring committee没过。
: （1） 中年白人： 先在手机上演示了一个game, 就是一个球从起点开始沿着通道，看
: 能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不
: 能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不
: 是solvable. 写出来了， 就是用BFS,有个小bug被指出。然后问复杂度， 问如何优化。
: （2） 韩国人： a) 给一个dictionary, 再给一个set of coding string （g5, goo3,
: goog2, go2le.........). return all string from dictionary that can be
: matched with the coding string. 要求尽量减少dictionary look up 次数。给了个
: 方法，但一直不满意复杂度。
: （b)如何用Trie, 把问题(a)解决,要求写code 建一个Trie包
| s********i
发帖数: 74 | 38 密码那题如果不限制字母重复次数的话是必须指定概率来做了。比如六个a组成的密码
，你永远不可能100%确定密码就是六个a。
google 有可能100%确定
ggoole 不可能100%确定
gogole 有可能100%确定 | f*******r
发帖数: 976 | | x******i
发帖数: 374 | | | | f******n
发帖数: 279 | |
|
