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 对正经学过算法的人不算难，但要拿来为难外行，只能显出烙印的狭隘。拿个教材里的
数学题来问这种烙印就足够把他们折腾死了。 |
