v*****k
发帖数: 7798 | 1 1. n个词以空格间隔，对于每个词每逢第五个字母后插入<\br>.注意如果正好有5的整
数倍个字母则不插入最后一个。
2. 平面上n个点，求所有三点或三点以上共线的情况。要求O（n)。 死在这个上面了
3. 实现乘法。两个数都用string 表示
4. LRU 实现及讨论 |
b***e
发帖数: 383 | 2 bless,多谢分享。
对于第四题，可否直接用linkedhashmap来实现，还是自己必须写一个类似
linkedhashmap的类出来？ |
s******n
发帖数: 3946 | |
r*******g
发帖数: 1335 | 4 第二题居然可以O(n)??????
【在 v*****k 的大作中提到】
: 1. n个词以空格间隔，对于每个词每逢第五个字母后插入<\br>.注意如果正好有5的整
: 数倍个字母则不插入最后一个。
: 2. 平面上n个点，求所有三点或三点以上共线的情况。要求O（n)。 死在这个上面了
: 3. 实现乘法。两个数都用string 表示
: 4. LRU 实现及讨论
|
s******n
发帖数: 226 | 5 是啊 排个序都要超了
【在 r*******g 的大作中提到】
: 第二题居然可以O(n)??????
|
L*****R
发帖数: 56 | 6 第二个O(n)怎么做啊？个人觉得不可能，呼唤大牛！ |
H****s
发帖数: 247 | |
w****x
发帖数: 2483 | 8 我想问一下第一题怎么inplace??
有inplace的要求吗?? |
b******e
发帖数: 52 | 9 第二题就算可能，也不是我能想出来的，就像直方图题目一样。 |
p*****2
发帖数: 21240 | 10
应该不用inplace吧，不过inplace也不算麻烦吧。
【在 w****x 的大作中提到】
: 我想问一下第一题怎么inplace??
: 有inplace的要求吗??
|
|
|
v*****k
发帖数: 7798 | 11 不用inplace
【在 w****x 的大作中提到】
: 我想问一下第一题怎么inplace??
: 有inplace的要求吗??
|
v*****k
发帖数: 7798 | 12 这个每个人要求不同吧
【在 b***e 的大作中提到】
: bless,多谢分享。
: 对于第四题，可否直接用linkedhashmap来实现，还是自己必须写一个类似
: linkedhashmap的类出来？
|
v*****k
发帖数: 7798 | 13 我当时就shock了，然后死菜
【在 r*******g 的大作中提到】
: 第二题居然可以O(n)??????
|
m******s
发帖数: 165 | 14 2 duality+arrangement大概可以O(n^2)
【在 v*****k 的大作中提到】
: 1. n个词以空格间隔，对于每个词每逢第五个字母后插入<\br>.注意如果正好有5的整
: 数倍个字母则不插入最后一个。
: 2. 平面上n个点，求所有三点或三点以上共线的情况。要求O（n)。 死在这个上面了
: 3. 实现乘法。两个数都用string 表示
: 4. LRU 实现及讨论
|
p*****2
发帖数: 21240 | |
a********m
发帖数: 15480 | |
q****x
发帖数: 7404 | 17 2不可能。死也不会是这个。
【在 v*****k 的大作中提到】
: 1. n个词以空格间隔，对于每个词每逢第五个字母后插入<\br>.注意如果正好有5的整
: 数倍个字母则不插入最后一个。
: 2. 平面上n个点，求所有三点或三点以上共线的情况。要求O（n)。 死在这个上面了
: 3. 实现乘法。两个数都用string 表示
: 4. LRU 实现及讨论
|
w****x
发帖数: 2483 | 18 刚才想起来了, inplace可以把字符串反转 |
w****x
发帖数: 2483 | 19 第二题要是有O(n)的解我从学校图书馆楼顶上跳下去 |
b***e
发帖数: 383 | 20
就因为你这句话，即便有人解出来了也不敢贴出来，呵呵。
【在 w****x 的大作中提到】
: 第二题要是有O(n)的解我从学校图书馆楼顶上跳下去
|
|
|
v*****k
发帖数: 7798 | 21 死定了。见得人不够多。最后一个基本就是敷衍了事
【在 p*****2 的大作中提到】
: 你还没fail吧？
: 出第二题的是烙印吗？
|
v*****k
发帖数: 7798 | 22 问题是三哥就是这么要求的，还笑嘻嘻的说回去当家庭作业吧
【在 q****x 的大作中提到】
: 2不可能。死也不会是这个。
|
s******n
发帖数: 3946 | 23 可能是看你的临场反应，能不能证明O(N)是不可能的？
【在 v*****k 的大作中提到】
: 死定了。见得人不够多。最后一个基本就是敷衍了事
|
a********m
发帖数: 15480 | 24 是呀。感觉很玄呀。 如果你知道n个点的解，如果有o(n),计算第n+1个点可以用常数时
间？ |
f*********5
发帖数: 576 | 25 你们学校图书馆只有一层？
【在 w****x 的大作中提到】
: 第二题要是有O(n)的解我从学校图书馆楼顶上跳下去
|
a**********2
发帖数: 340 | 26 worst case应该不能做到O（N）
【在 a********m 的大作中提到】
: 是呀。感觉很玄呀。 如果你知道n个点的解，如果有o(n),计算第n+1个点可以用常数时
: 间？
|
p*****2
发帖数: 21240 | 27
看来我猜对了。我就被Bing的烙印黑过。我感觉由于Bing的老大是中国人，所以Bing的
烙印很仇视中国人。总是下绊子。别的组的烙印还没这么黑。
【在 v*****k 的大作中提到】
: 问题是三哥就是这么要求的，还笑嘻嘻的说回去当家庭作业吧
|
a********m
发帖数: 15480 | 28 期望的case也不容易呀。题目还是找到所有的解，不是简单的问有木有。。。。
【在 a**********2 的大作中提到】
: worst case应该不能做到O（N）
|
a********m
发帖数: 15480 | 29 这种"临场反应"对工作木有任何意义呀。
【在 s******n 的大作中提到】
: 可能是看你的临场反应，能不能证明O(N)是不可能的？
|
z****c
发帖数: 602 | 30 I don't think 2 can be solved by O(n), I can do O(n^2) by hash mapping the
parameter of the line from any of the two points, wonder if there is an O(
nlogn) |
|
|
a********m
发帖数: 15480 | 31 按x排序nlgn. 然后hash+斜率也许有机会，还没完全想好。
【在 z****c 的大作中提到】
: I don't think 2 can be solved by O(n), I can do O(n^2) by hash mapping the
: parameter of the line from any of the two points, wonder if there is an O(
: nlogn)
|
n*******w
发帖数: 687 | 32 inplace也不难。
先从头扫到尾，统计多少个词。然后从尾到头移动。
第二题O(n)完全没思路。O(n^2)倒可以，都不简单。
【在 w****x 的大作中提到】
: 我想问一下第一题怎么inplace??
: 有inplace的要求吗??
|
w****x
发帖数: 2483 | 33
是从尾到头没错, 但这题不是明显的像replace空格 with "%20"
从尾到头每个单词就不是那个位置了.
一个办法是reverse, 然后再算需要扩充多少, 然后从尾到头, 然后再reverse back
现场这种代码不好写的
【在 n*******w 的大作中提到】
: inplace也不难。
: 先从头扫到尾，统计多少个词。然后从尾到头移动。
: 第二题O(n)完全没思路。O(n^2)倒可以，都不简单。
|
z****c
发帖数: 602 | 34 关于2，那个小印不会以为Hough transform是O(n)的算法吧，虽然对所有的点只扫一遍
。 |
z****c
发帖数: 602 | 35 排序应该没有必要，因为点在一条直线上和点的位置顺序没有关系。
【在 a********m 的大作中提到】
: 按x排序nlgn. 然后hash+斜率也许有机会，还没完全想好。
|
x*******7
发帖数: 223 | 36 我觉得他就是想问hough transform.
【在 z****c 的大作中提到】
: 关于2，那个小印不会以为Hough transform是O(n)的算法吧，虽然对所有的点只扫一遍
: 。
|
a********m
发帖数: 15480 | 37 恩。木有帮助。应该是不行。
【在 z****c 的大作中提到】
: 排序应该没有必要，因为点在一条直线上和点的位置顺序没有关系。
|
a********m
发帖数: 15480 | 38 。。。。。能觉得hough transform是o(n)也太弱了点。还不如那个“压力测试”的理
由靠谱。
【在 x*******7 的大作中提到】
: 我觉得他就是想问hough transform.
|
H***e
发帖数: 476 | 39 hough transform这种是图像处理的课里面才有的
根本不是一般cs的基础课
【在 x*******7 的大作中提到】
: 我觉得他就是想问hough transform.
|
v*****k
发帖数: 7798 | 40 尼玛我在MS也做过两个实习了，认识里面的人无数，没听说过面试的时候有压力测试的
。三哥太坏了
【在 a********m 的大作中提到】
: 。。。。。能觉得hough transform是o(n)也太弱了点。还不如那个“压力测试”的理
: 由靠谱。
|
|
|
t******e
发帖数: 98 | |
w****x
发帖数: 2483 | |
v*****k
发帖数: 7798 | 43 算了反正是备胎
【在 t******e 的大作中提到】
: 这个就是面试官的问题，可以向HR投诉。
|
a********m
发帖数: 15480 | 44 这个看公司了。俺觉得压力测试类似 puzzle题目。有的公司禁止这类问题，有的公司
喜欢这类问题。
【在 t******e 的大作中提到】
: 这个就是面试官的问题，可以向HR投诉。
|
c**********e
发帖数: 2007 | 45 由2.联想到的问题：有一个一维整数数组，问有没有两个相等的。
【在 v*****k 的大作中提到】
: 1. n个词以空格间隔，对于每个词每逢第五个字母后插入<\br>.注意如果正好有5的整
: 数倍个字母则不插入最后一个。
: 2. 平面上n个点，求所有三点或三点以上共线的情况。要求O（n)。 死在这个上面了
: 3. 实现乘法。两个数都用string 表示
: 4. LRU 实现及讨论
|
m*****k
发帖数: 731 | 46 3 我觉得就是翻版的sum up 2 integers represented by 2 single linked lists 嘛。
google 了一下，
http://stackoverflow.com/questions/4446326/string-multiplicatio 显然没考虑大数overflow。
【在 v*****k 的大作中提到】
: 1. n个词以空格间隔，对于每个词每逢第五个字母后插入<\br>.注意如果正好有5的整
: 数倍个字母则不插入最后一个。
: 2. 平面上n个点，求所有三点或三点以上共线的情况。要求O（n)。 死在这个上面了
: 3. 实现乘法。两个数都用string 表示
: 4. LRU 实现及讨论
|
