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 的大作中提到】
: 在本版收益颇多，发个狗狗面经，赞个人品
: 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 的大作中提到】
: Cft，挺牛的啊。
: 请问一下，机器1传string到机器2，怎么判断到了String的end啊？不是看'\0'这么简
: 单吧。
: 还有，判断pattern的lgn算法是怎么弄的啊?
|
r****o
发帖数: 1950 | 4 多谢，
那如果字符串是abcabcabc，怎么在O(lgn)的时间内找出pattern呢?
【在 s********l 的大作中提到】
: interviewer说不是 c_string 说以没有'\0'
: 我的solution是，结尾想unix里面表示\那样 来表示结尾
: 就是说 一个\表示结束
: \表示字符\
: 如果一个String是某个pattern的循环
: 那他就是这个pattern的整数倍
: 然后你就按倍数check
|
b******v
发帖数: 1493 | 5 多谢分享详细面经
祝你搞定下一家onsite
【在 s********l 的大作中提到】
: 在本版收益颇多，发个狗狗面经，赞个人品
: 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 的大作中提到】
: 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 的大作中提到】
: 对 我写错了
: nlgn
: lgn 不可能
: 反正我当时 能想出来的最好算法
: 就是先计算string长度
: 然后从长度1的开始 遇到不是重复就结束 //长度指的是pattern的长度
: 然后长度x 先用length%x 看length是不是这个长度的倍数
: 是就check不是就下一个长度 直到长度到length的一半
: interviewer好像很高兴 这个就是他要的答案
: 兴高采烈的让我coding~
|
s********l
发帖数: 998 | 9 我当时 就只想出这个了~
interviewer好像就是要的这个
他管这叫nlgn。。。
【在 n*****0 的大作中提到】
: 请问这个方法为什么是O(nlgn)的?
|
r****o
发帖数: 1950 | 10 请问这个长度递增顺序是1,2,3,4...
还是1,2,4,8...?
【在 s********l 的大作中提到】
: 我当时 就只想出这个了~
: interviewer好像就是要的这个
: 他管这叫nlgn。。。
|
|
|
s********l
发帖数: 998 | 11 这个是自己要check这个string是不是某个pattern的周期
所以 我用的1 2 3 4...
【在 r****o 的大作中提到】
: 请问这个长度递增顺序是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 的大作中提到】
: 这个是自己要check这个string是不是某个pattern的周期
: 所以 我用的1 2 3 4...
|
s********l
发帖数: 998 | 13 m是pattern的长度？
你要是遇到不是周期的马上停了就成~
【在 r****o 的大作中提到】
: 多谢。
: 假如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 的大作中提到】
: m是pattern的长度？
: 你要是遇到不是周期的马上停了就成~
|
s********l
发帖数: 998 | 15 interviewer管这个叫nlgn
我当时也觉得confused
不过 他满意 我就不argue了 呵呵
【在 r****o 的大作中提到】
: 那要是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 | |
