s********l 发帖数: 998 | 1 在本版收益颇多,发个狗狗面经,赞个人品
onsite 3周前的, 最近一直比较忙,所以一直拖到现在
很久很久以前 本着投了总比不投好的原则 我网上投了狗狗,虽然心理觉得没什么得到
面试的机会
很久很久以后,突然某一天,狗狗给我发个信说想考虑我的application
让我填一堆表 ,看看有没有group对我感兴趣
3周后,给我email,安排第一个interview
Q1. 给你一个string 不是c_string 从机器1传到机器2,如何判断到了String的end
Q2. 2个sorted integer array 找kth number
第二题答的不是很好,于是开始等拒信
3天后,收到hr email, 我开始找关键字“unfortunately”& “regret”
结果很意外的发现, 给我onsite~
于是兴高采烈的 和 hr安排了具体时间
结果2小时候后,hr又给我打电话说, 你才phone interview 1次,我们一般都2次,你
再phone一次吧。。。。。。
第二次phone interview
先问了些,都会什么算法 复杂度等问题
然后Code: Rota |
r****o 发帖数: 1950 | 2 Cft,挺牛的啊。
请问一下,机器1传string到机器2,怎么判断到了String的end啊?不是看'\0'这么简
单吧。
还有,判断pattern的lgn算法是怎么弄的啊?
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 在本版收益颇多,发个狗狗面经,赞个人品 : onsite 3周前的, 最近一直比较忙,所以一直拖到现在 : 很久很久以前 本着投了总比不投好的原则 我网上投了狗狗,虽然心理觉得没什么得到 : 面试的机会 : 很久很久以后,突然某一天,狗狗给我发个信说想考虑我的application : 让我填一堆表 ,看看有没有group对我感兴趣 : 3周后,给我email,安排第一个interview : Q1. 给你一个string 不是c_string 从机器1传到机器2,如何判断到了String的end : Q2. 2个sorted integer array 找kth number : 第二题答的不是很好,于是开始等拒信
|
s********l 发帖数: 998 | 3 interviewer说不是 c_string 说以没有'\0'
我的solution是,结尾想unix里面表示\那样 来表示结尾
就是说 一个\表示结束
\表示字符\
如果一个String是某个pattern的循环
那他就是这个pattern的整数倍
然后你就按倍数check
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Cft,挺牛的啊。 : 请问一下,机器1传string到机器2,怎么判断到了String的end啊?不是看'\0'这么简 : 单吧。 : 还有,判断pattern的lgn算法是怎么弄的啊?
|
r****o 发帖数: 1950 | 4 多谢,
那如果字符串是abcabcabc,怎么在O(lgn)的时间内找出pattern呢?
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : interviewer说不是 c_string 说以没有'\0' : 我的solution是,结尾想unix里面表示\那样 来表示结尾 : 就是说 一个\表示结束 : \表示字符\ : 如果一个String是某个pattern的循环 : 那他就是这个pattern的整数倍 : 然后你就按倍数check
|
b******v 发帖数: 1493 | 5 多谢分享详细面经
祝你搞定下一家onsite
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 在本版收益颇多,发个狗狗面经,赞个人品 : onsite 3周前的, 最近一直比较忙,所以一直拖到现在 : 很久很久以前 本着投了总比不投好的原则 我网上投了狗狗,虽然心理觉得没什么得到 : 面试的机会 : 很久很久以后,突然某一天,狗狗给我发个信说想考虑我的application : 让我填一堆表 ,看看有没有group对我感兴趣 : 3周后,给我email,安排第一个interview : Q1. 给你一个string 不是c_string 从机器1传到机器2,如何判断到了String的end : Q2. 2个sorted integer array 找kth number : 第二题答的不是很好,于是开始等拒信
|
P********l 发帖数: 452 | 6 1. It is O(nlgn).
2. How about 7 cycles?
1234123L1234123L1234123L1234123L1234123L1234123L1234123L
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : interviewer说不是 c_string 说以没有'\0' : 我的solution是,结尾想unix里面表示\那样 来表示结尾 : 就是说 一个\表示结束 : \表示字符\ : 如果一个String是某个pattern的循环 : 那他就是这个pattern的整数倍 : 然后你就按倍数check
|
s********l 发帖数: 998 | 7 对 我写错了
nlgn
lgn 不可能
反正我当时 能想出来的最好算法
就是先计算string长度
然后从长度1的开始 遇到不是重复就结束 //长度指的是pattern的长度
然后长度x 先用length%x 看length是不是这个长度的倍数
是就check不是就下一个长度 直到长度到length的一半
interviewer好像很高兴 这个就是他要的答案
兴高采烈的让我coding~ |
n*****0 发帖数: 133 | 8 请问这个方法为什么是O(nlgn)的?
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对 我写错了 : nlgn : lgn 不可能 : 反正我当时 能想出来的最好算法 : 就是先计算string长度 : 然后从长度1的开始 遇到不是重复就结束 //长度指的是pattern的长度 : 然后长度x 先用length%x 看length是不是这个长度的倍数 : 是就check不是就下一个长度 直到长度到length的一半 : interviewer好像很高兴 这个就是他要的答案 : 兴高采烈的让我coding~
|
s********l 发帖数: 998 | 9 我当时 就只想出这个了~
interviewer好像就是要的这个
他管这叫nlgn。。。
【在 n*****0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问这个方法为什么是O(nlgn)的?
|
r****o 发帖数: 1950 | 10 请问这个长度递增顺序是1,2,3,4...
还是1,2,4,8...?
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我当时 就只想出这个了~ : interviewer好像就是要的这个 : 他管这叫nlgn。。。
|
|
|
s********l 发帖数: 998 | 11 这个是自己要check这个string是不是某个pattern的周期
所以 我用的1 2 3 4...
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问这个长度递增顺序是1,2,3,4... : 还是1,2,4,8...?
|
r****o 发帖数: 1950 | 12 多谢。
假如m=1,2,3,4,...n/2
那每次都要比较n个元素吧,
我觉得复杂度是O(n^2).
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个是自己要check这个string是不是某个pattern的周期 : 所以 我用的1 2 3 4...
|
s********l 发帖数: 998 | 13 m是pattern的长度?
你要是遇到不是周期的马上停了就成~
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 多谢。 : 假如m=1,2,3,4,...n/2 : 那每次都要比较n个元素吧, : 我觉得复杂度是O(n^2).
|
r****o 发帖数: 1950 | 14 那要是str="aaaaaaaaaaab",n=12
m=1的时候要检查到str[11],failed
m=2,3,4的时候也要检查到str[11],failed
m=5的时候不查,
m=6的时候检查到str[11],failed
这复杂度还是O(n^2)啊。
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : m是pattern的长度? : 你要是遇到不是周期的马上停了就成~
|
s********l 发帖数: 998 | 15 interviewer管这个叫nlgn
我当时也觉得confused
不过 他满意 我就不argue了 呵呵
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那要是str="aaaaaaaaaaab",n=12 : m=1的时候要检查到str[11],failed : m=2,3,4的时候也要检查到str[11],failed : m=5的时候不查, : m=6的时候检查到str[11],failed : 这复杂度还是O(n^2)啊。
|
c******f 发帖数: 2144 | |
d*****a 发帖数: 38 | 17 如果字符串长度是n,pattern长度就是n的约数,约数的个数是log(n) |
m*****f 发帖数: 1243 | |