B*******1
发帖数: 2454 | 1 1.Find the first non-repeating character in a string
这个是不是一定要Scan第一遍记录下所有Character出现的次数，然后在Scan第2遍
得到第一个不重复的啊？
2. Return the sum two largest integers in an array
这个是不是就是找出数组里面最大的2个数就可以了啊？但是又似乎不是这么简单。
3.Sum n largest integers in an array of integers where every integer is
between 0 and 9
这个完全没有头绪
请指教，
Thanks |
s********y
发帖数: 3811 | 2 lz准备面试多长时间了？
【在 B*******1 的大作中提到】
: 1.Find the first non-repeating character in a string
: 这个是不是一定要Scan第一遍记录下所有Character出现的次数，然后在Scan第2遍
: 得到第一个不重复的啊？
: 2. Return the sum two largest integers in an array
: 这个是不是就是找出数组里面最大的2个数就可以了啊？但是又似乎不是这么简单。
: 3.Sum n largest integers in an array of integers where every integer is
: between 0 and 9
: 这个完全没有头绪
: 请指教，
: Thanks
|
B*******1
发帖数: 2454 | 3 刚开始，问题很弱，是不是阿。
【在 s********y 的大作中提到】
: lz准备面试多长时间了？
|
s********y
发帖数: 3811 | 4 都有个开始，去搜careercup 从那里开始吧。
【在 B*******1 的大作中提到】
: 刚开始，问题很弱，是不是阿。
|
B*******1
发帖数: 2454 | 5 早搜索过了，但是看了很多人的做法，似乎都不是最好的。
【在 s********y 的大作中提到】
: 都有个开始，去搜careercup 从那里开始吧。
|
l******w
发帖数: 106 | 6 这些题目能有什么trick么？
【在 B*******1 的大作中提到】
: 1.Find the first non-repeating character in a string
: 这个是不是一定要Scan第一遍记录下所有Character出现的次数，然后在Scan第2遍
: 得到第一个不重复的啊？
: 2. Return the sum two largest integers in an array
: 这个是不是就是找出数组里面最大的2个数就可以了啊？但是又似乎不是这么简单。
: 3.Sum n largest integers in an array of integers where every integer is
: between 0 and 9
: 这个完全没有头绪
: 请指教，
: Thanks
|
B*******1
发帖数: 2454 | 7 可能我想多了，谢谢。
【在 l******w 的大作中提到】
: 这些题目能有什么trick么？
|
c*****e
发帖数: 210 | 8
one scan is enough. use an array of size 256 to record whether a character
has occured or not. Print it out iff it is the first time.
use an array count[10], scan and count. Based on the counts on each of 0...9
, you get the answer.
【在 B*******1 的大作中提到】
: 1.Find the first non-repeating character in a string
: 这个是不是一定要Scan第一遍记录下所有Character出现的次数，然后在Scan第2遍
: 得到第一个不重复的啊？
: 2. Return the sum two largest integers in an array
: 这个是不是就是找出数组里面最大的2个数就可以了啊？但是又似乎不是这么简单。
: 3.Sum n largest integers in an array of integers where every integer is
: between 0 and 9
: 这个完全没有头绪
: 请指教，
: Thanks
|
b**********r
发帖数: 46 | |
f**e
发帖数: 1269 | 10 why? Scan once can get you the 2 largest numbers so you are done.
【在 b**********r 的大作中提到】
: for (2), n+lgn
|
|
|
S*********g
发帖数: 5298 | 11 O(n+log n) = O(n)
【在 b**********r 的大作中提到】
: for (2), n+lgn
|
a**********s
发帖数: 588 | 12 His point is that the number of comparisons can be as low as n+lg(n), which
is a nice thought.
【在 f**e 的大作中提到】
: why? Scan once can get you the 2 largest numbers so you are done.
|
g*******y
发帖数: 1930 | 13 成对的比较，找到最大数后，再比较所有跟最大数比较过的数？但空间呢? 可以做到O(
1)吗？如果空间做不到O(1)，2n -> n+lgn的改进也没什么意义吧。
当然，光看最少的比较次数，那这个是不错的。
【在 b**********r 的大作中提到】
: for (2), n+lgn
|
n********u
发帖数: 194 | 14 我也有一个问题昨天看到的，自己想了以后觉得很混乱，理不出个头绪，不知道有谁有
比较好的解法。
问题：painting a cube with different 3 colors, how many ways? |
f**e
发帖数: 1269 | 15 我准备的时候使劲钻研难题，结果面试尽遇到基本题了。现在我就学乖了，一个题钻不
出来我就不去想它了。把基本功弄扎实最重要。
【在 n********u 的大作中提到】
: 我也有一个问题昨天看到的，自己想了以后觉得很混乱，理不出个头绪，不知道有谁有
: 比较好的解法。
: 问题：painting a cube with different 3 colors, how many ways?
|
n********u
发帖数: 194 | 16 呵呵，我也不想那个题了，开始看其他题目了。
【在 f**e 的大作中提到】
: 我准备的时候使劲钻研难题，结果面试尽遇到基本题了。现在我就学乖了，一个题钻不
: 出来我就不去想它了。把基本功弄扎实最重要。
|
g*******y
发帖数: 1930 | 17 我当时不知道有个针对这个问题的定理的时候，是枚举各种情况做的。不会花很长时间
，如果你熟悉对称性的话。
后来搜careercup上，发现有一个以某人名字命名的定理/公式，ft，敢说没人能在面试
的时间内把这个定理发现出来，所以枚举应该算是最佳的方法了。
【在 n********u 的大作中提到】
: 我也有一个问题昨天看到的，自己想了以后觉得很混乱，理不出个头绪，不知道有谁有
: 比较好的解法。
: 问题：painting a cube with different 3 colors, how many ways?
|
n********u
发帖数: 194 | 18 是啊，wiki上的那个定理给我看我都不太懂，个人感觉还是枚举比较可以接受些。
【在 g*******y 的大作中提到】
: 我当时不知道有个针对这个问题的定理的时候，是枚举各种情况做的。不会花很长时间
: ，如果你熟悉对称性的话。
: 后来搜careercup上，发现有一个以某人名字命名的定理/公式，ft，敢说没人能在面试
: 的时间内把这个定理发现出来，所以枚举应该算是最佳的方法了。
|
c******a
发帖数: 198 | 19
one scan is enough. use an array of size 256 to record whether a character
has occured or not. Print it out iff it is the first time.
How to determine which one of the characters that occur once is the first
one in the string?
use an array count[10], scan and count. Based on the counts on each of 0...9
, you get the answer.
【在 c*****e 的大作中提到】
:
: one scan is enough. use an array of size 256 to record whether a character
: has occured or not. Print it out iff it is the first time.
: use an array count[10], scan and count. Based on the counts on each of 0...9
: , you get the answer.
|
z*******y
发帖数: 578 | 20 同感那，呵呵
准备了好多难题，结果到了Microsoft一个弱组，全问的简单的问题，挂了
简单的代码写的不够好，还是基本功重要对
【在 f**e 的大作中提到】
: 我准备的时候使劲钻研难题，结果面试尽遇到基本题了。现在我就学乖了，一个题钻不
: 出来我就不去想它了。把基本功弄扎实最重要。
|
|
|
y*r
发帖数: 590 | 21
I guess using hash here is more straightforward.
.9
【在 c******a 的大作中提到】
:
: one scan is enough. use an array of size 256 to record whether a character
: has occured or not. Print it out iff it is the first time.
: How to determine which one of the characters that occur once is the first
: one in the string?
: use an array count[10], scan and count. Based on the counts on each of 0...9
: , you get the answer.
|
H*****9
发帖数: 29 | |
j*****j
发帖数: 115 | 23 完全赞成~
【在 f**e 的大作中提到】
: 我准备的时候使劲钻研难题，结果面试尽遇到基本题了。现在我就学乖了，一个题钻不
: 出来我就不去想它了。把基本功弄扎实最重要。
|
