m*********1 发帖数: 204 | 1 我前面发过一道题了,就是String 找repeat特征那道,要求算法复杂度为O(n),第二
题也是超级难。我都放上来。注意我的面试是SDE intern职位
第一题是一个口音极其重的烙印,几乎听不懂,还好是算法考试,要是纯聊天更完蛋。
题目如下:
1.有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
2,输入一个String写代码返回T或者F
例子:
"abcabcabc" Ture 因为它把abc重复3次构成
"bcdbcdbcde" False 最后一个是bcde
"abcdabcd" True 因为它是abcd重复2次构成
"xyz" False 因为它不是某一个String重复
"aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
要求算法复杂度为O(n)
public boolean isMultiple(String s){
}
这道题因为我开了一个单独贴了,就不在这里讨论了
第二个45分钟面试,是另外一个烙印,这个烙印的口音更重,更听不懂,但是他说话态
度nice一点,比前面一个感觉好一些。至少愿意重复问题。
2.有1 billion个Integer,要找出前100个最大的,并分析复杂度
这个题,我问了数据的大小范围,他说任何大小都有可能
我开始想用Radix排序,位移法
但是他好像觉得不合适。
他帮我算了一下,说1 B个整数正好是4G,然后让我继续想
我后来觉得是Heap sort,但是当时想不到 |
r****c 发帖数: 2585 | |
d**e 发帖数: 6098 | 3 尼玛的,这真的是在害人,真tmd老印!
intern居然还考这么难的!
少为
【在 m*********1 的大作中提到】 : 我前面发过一道题了,就是String 找repeat特征那道,要求算法复杂度为O(n),第二 : 题也是超级难。我都放上来。注意我的面试是SDE intern职位 : 第一题是一个口音极其重的烙印,几乎听不懂,还好是算法考试,要是纯聊天更完蛋。 : 题目如下: : 1.有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为 : 2,输入一个String写代码返回T或者F : 例子: : "abcabcabc" Ture 因为它把abc重复3次构成 : "bcdbcdbcde" False 最后一个是bcde : "abcdabcd" True 因为它是abcd重复2次构成
|
h******6 发帖数: 2697 | 4 我觉得作为intern的面试挺难的了这些题 除非之前看到过 |
m********l 发帖数: 791 | 5 第一题要求线性是很BT
第二题很难吗?
我觉着就是maintain一个size 100 的minHeap啊
复杂度nlogK
还是有什么需要注意的? |
c******0 发帖数: 260 | 6 第二题应该用双层桶。我觉得他家全职也没这么难…
少为
【在 m*********1 的大作中提到】 : 我前面发过一道题了,就是String 找repeat特征那道,要求算法复杂度为O(n),第二 : 题也是超级难。我都放上来。注意我的面试是SDE intern职位 : 第一题是一个口音极其重的烙印,几乎听不懂,还好是算法考试,要是纯聊天更完蛋。 : 题目如下: : 1.有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为 : 2,输入一个String写代码返回T或者F : 例子: : "abcabcabc" Ture 因为它把abc重复3次构成 : "bcdbcdbcde" False 最后一个是bcde : "abcdabcd" True 因为它是abcd重复2次构成
|
m********l 发帖数: 791 | 7 能不能解释下 minHeap为什么不行?
【在 c******0 的大作中提到】 : 第二题应该用双层桶。我觉得他家全职也没这么难… : : 少为
|
w*******i 发帖数: 186 | 8 minheap达不到线性时间,注意这里是整数,范围有限。其实还有种不断调用类似于快
排中partition的方法,可以线性时间求解,搜下top k就知道了。
【在 m********l 的大作中提到】 : 能不能解释下 minHeap为什么不行?
|
j*d 发帖数: 96 | 9 第二题 用radix sort为什么不行, 是因为空间开销太大吗? |
h**k 发帖数: 3368 | 10 1B的整数正好是4G是什么意思?
少为
【在 m*********1 的大作中提到】 : 我前面发过一道题了,就是String 找repeat特征那道,要求算法复杂度为O(n),第二 : 题也是超级难。我都放上来。注意我的面试是SDE intern职位 : 第一题是一个口音极其重的烙印,几乎听不懂,还好是算法考试,要是纯聊天更完蛋。 : 题目如下: : 1.有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为 : 2,输入一个String写代码返回T或者F : 例子: : "abcabcabc" Ture 因为它把abc重复3次构成 : "bcdbcdbcde" False 最后一个是bcde : "abcdabcd" True 因为它是abcd重复2次构成
|
|
|
m********l 发帖数: 791 | 11 1B的整数就是有1 billion个int
1 int = 4 bytes
1 billion int = 4 billion bytes ~ 4GB
就是大概需要4GB的内存来存储1 billion个int
【在 h**k 的大作中提到】 : 1B的整数正好是4G是什么意思? : : 少为
|
m********l 发帖数: 791 | 12 topK的minheap算法不就是线性时间吗? 复杂度nlogK 这道题说了K=100远小于n,所以
就是线性的啊,而且就算K很大,logK也大不到哪里去。所以我觉得TopK的这个算法最
好用了。
另外我们不用计数排序的话,就跟范围没关系了吧,每次和minHeap的top比较就行了
快速选择那种解法比较复杂,要用到median of medians什么的才能保证worst case 是
O(n), 但是这个要写代码难度很大(对我来说)。我不懂这个方法比minheap相比好在
哪里,节省空间?
【在 w*******i 的大作中提到】 : minheap达不到线性时间,注意这里是整数,范围有限。其实还有种不断调用类似于快 : 排中partition的方法,可以线性时间求解,搜下top k就知道了。
|
w********s 发帖数: 1570 | 13 第二题第一反应就是heap sort
少为
【在 m*********1 的大作中提到】 : 我前面发过一道题了,就是String 找repeat特征那道,要求算法复杂度为O(n),第二 : 题也是超级难。我都放上来。注意我的面试是SDE intern职位 : 第一题是一个口音极其重的烙印,几乎听不懂,还好是算法考试,要是纯聊天更完蛋。 : 题目如下: : 1.有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为 : 2,输入一个String写代码返回T或者F : 例子: : "abcabcabc" Ture 因为它把abc重复3次构成 : "bcdbcdbcde" False 最后一个是bcde : "abcdabcd" True 因为它是abcd重复2次构成
|
g**4 发帖数: 863 | 14 第2题是glassdoor上他们家的原题啊,intern类别
算是比较经典了,微软也考过
少为
【在 m*********1 的大作中提到】 : 我前面发过一道题了,就是String 找repeat特征那道,要求算法复杂度为O(n),第二 : 题也是超级难。我都放上来。注意我的面试是SDE intern职位 : 第一题是一个口音极其重的烙印,几乎听不懂,还好是算法考试,要是纯聊天更完蛋。 : 题目如下: : 1.有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为 : 2,输入一个String写代码返回T或者F : 例子: : "abcabcabc" Ture 因为它把abc重复3次构成 : "bcdbcdbcde" False 最后一个是bcde : "abcdabcd" True 因为它是abcd重复2次构成
|
T*U 发帖数: 22634 | 15 第二题不难吧,不是o(n)吗
少为
【在 m*********1 的大作中提到】 : 我前面发过一道题了,就是String 找repeat特征那道,要求算法复杂度为O(n),第二 : 题也是超级难。我都放上来。注意我的面试是SDE intern职位 : 第一题是一个口音极其重的烙印,几乎听不懂,还好是算法考试,要是纯聊天更完蛋。 : 题目如下: : 1.有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为 : 2,输入一个String写代码返回T或者F : 例子: : "abcabcabc" Ture 因为它把abc重复3次构成 : "bcdbcdbcde" False 最后一个是bcde : "abcdabcd" True 因为它是abcd重复2次构成
|
s****u 发帖数: 1433 | 16 什么是HEAP SORT?
就是选个百人队排序,然后把剩下的每个数字跟百人里面
最小的比较一下,优胜劣汰? |
F********9 发帖数: 44 | 17 第二题也算是提示你用bitmap了吧:
说1 B个整数正好是4G, |
l*******b 发帖数: 2586 | 18 build heap + pull k times = n + k log n 可能比 n log k 强点
【在 s****u 的大作中提到】 : 什么是HEAP SORT? : 就是选个百人队排序,然后把剩下的每个数字跟百人里面 : 最小的比较一下,优胜劣汰?
|
P****o 发帖数: 1173 | 19 面试问难题无非是冠冕堂皇的不要你,你被烙印玩了。
少为
【在 m*********1 的大作中提到】 : 我前面发过一道题了,就是String 找repeat特征那道,要求算法复杂度为O(n),第二 : 题也是超级难。我都放上来。注意我的面试是SDE intern职位 : 第一题是一个口音极其重的烙印,几乎听不懂,还好是算法考试,要是纯聊天更完蛋。 : 题目如下: : 1.有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为 : 2,输入一个String写代码返回T或者F : 例子: : "abcabcabc" Ture 因为它把abc重复3次构成 : "bcdbcdbcde" False 最后一个是bcde : "abcdabcd" True 因为它是abcd重复2次构成
|
j********p 发帖数: 9680 | 20 这是做样子给HR看的,黑的就是你,
谁让你不是印度人?
老印把事情做绝了,会有报应的. |
|
|
c**y 发帖数: 172 | 21 我怎么也感觉第二题就是用bitmap呢?O(n) |
H*********a 发帖数: 34 | 22 lz说他问了这些数大小没有范围的,这样的话,bitmap是不能使用的吧。因为你不知道
需要多少个bit来表达数字。大家觉得呢?
【在 F********9 的大作中提到】 : 第二题也算是提示你用bitmap了吧: : 说1 B个整数正好是4G,
|
s*******z 发帖数: 83 | 23 我觉得还好,不能算是故意刁难.
有一点是面试里面听不懂一定要求他说清楚, 没有说清楚是他的责任, 但是听不清楚就
做题是你的责任了, 就是平时间deliver东西一个道理, 你不做都比assign给你以后不
完成要强的.
第二个应该heapsort和bitmap都是比较好的法子了. |
p***y 发帖数: 637 | |
e**********n 发帖数: 359 | 25 对正经学过算法的人不算难,但要拿来为难外行,只能显出烙印的狭隘。拿个教材里的
数学题来问这种烙印就足够把他们折腾死了。 |