r*****l
发帖数: 2859 | 1 第二道题也是一样的做法。
其实我想很多人都知道答案的。只不过他们没时间回答或还没看到你的贴子。 |
|
A*********n
发帖数: 637 | 2 N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了.
not
sorted
in |
|
s*****y
发帖数: 897 | 3 N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了. |
|
s*****y
发帖数: 897 | 4 第2题，careercup 150上面有，把1000 pack到1024个number
就是pack 1001， 1002 。。。1024 number上去
然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。 |
|
|
|
h**t
发帖数: 1678 | 7 两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b， 把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
还是希望能拿到on site...
——————————————————————————
应该算很简单的，我实在是比较水，学艺不精：
1) a big array with a thousand elements storing integers from 1 to 1000, not
sorted. One number is duplicated. How do you find the duplicated number
most efficiently.
2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
. one number is ... 阅读全帖 |
|
f***g
发帖数: 214 | 8 确实经典。
不过第一题是不是描述的有点问题：
既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？ |
|
h**t
发帖数: 1678 | 9 赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
redBull啊。。。是cs,ee背景的？
第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
的间接方法... |
|
r*****l
发帖数: 2859 | 10 第二道题也是一样的做法。
其实我想很多人都知道答案的。只不过他们没时间回答或还没看到你的贴子。 |
|
A*********n
发帖数: 637 | 11 N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了.
not
sorted
in |
|
s*****y
发帖数: 897 | 12 N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了.
---------------------------------
你这样子就是一定要遍历n个element，我记得经典做法是
假设array是A[0]----A[5]
array是 2，1，1，0，4，3
A[0] = 2， 把A[0]和A[2]换，array变成 1， 1， 2， 0， 4， 3
如何A[i]=i，就可以跳过，继续看A[0]， A[0]=1， detect到A[1]已经有1了，
找到Duplicate是1。
我这里number从0开始，从1开始的数稍微改动一下。 |
|
s*****y
发帖数: 897 | 13 第2题，careercup 150上面有，把1000 pack到1024个number
就是pack 1001， 1002 。。。1024 number上去
然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。 |
|
|
|
Y**B
发帖数: 144 | 16 如果第一题按照原题意，1000个元素有一个是重复的，那么你们的加加减减的方法根本
不好使。面试管的答案才是他的题目的正解。
注意审题！！ |
|
|
w********n
发帖数: 13 | 18 1. n个球,n很大 > 1billion, k个颜色, k相对小， 比如10. 要求in space sort最
efficient的做法 白板coding. （hint, k<< n 所以最后算法争取比nlog(n)小)
该题的第二问 k = 1000 实现比nlogn 更efficient的in space的算法
另外 还有elevator设计 不同楼层多个button都按下了 如何处理 多个电梯 如何处理 |
|
g*********s
发帖数: 1782 | 19
第二个题，抽象成调度问题：
当前的电梯状态用楼层和方向描述。每个请求也用楼层和方向描述。找最优方案。
但是这里有几个问题：
1. 如何度量最优？是电梯总移动距离最短，还是平均等待时间最短？
2. 如果在执行当前方案时又有请求来了怎么办？继续执行当前方案，还是加入新请求
重新考虑？如果是
后者，公平性可能有问题。 |
|
i**9
发帖数: 351 | 20 来自主题: JobHunting版 - 一到电面题 void reversePairsOfLinkList(Node*& head) {
}
[] => []
[A,B] => [B, A]
[A, B, C] => [B, A, C]
[A, B, C, D, E, F, G] => [B, A, D, C, F, E, G]
这道题有些trick,我自己在白板上写的有些问题，在提示是下才写对。试试你能不能一
次写的无错误。(指定要对pointer操作，不能touch data) |
|
d*******l
发帖数: 338 | 21 我当时是类似这样的一题。似乎他想要的并不是更好的方法，而是只是想让你写出朴素
的方法，然后考虑整数溢出的情况，把函数写的健壮一点。把细节都弄到位他应该就满
意了。fib数列确实有logn的做法，但不太易于实现。另外用通项会有乘方运算，其实
也并不是O(1)的，应该还是logn的 |
|
m****t
发帖数: 555 | 22 来自主题: JobHunting版 - A家电面题 这种题出的很无聊，因为构成的图没有特殊规律。实际上就是一个给定无向图，判断是
否存在hamilton路径。是NP完全问题。 |
|
w**h
发帖数: 34 | 23 来自主题: JobHunting版 - A家电面题 我也觉得这题出的无聊，不过总觉得这老印想要的不会就是这么个ＮＰＣ的答案吧
不知道还有没有更好的方法呢 |
|
O*2
发帖数: 178 | 24 来自主题: JobHunting版 - 一个电面题 给你一个数列，不知道长度，一个一个给，其中一个数出现次数超过半数
（如果数列长度2N+1，这个数出现不少于N+1，但是N事先未知）
怎么样找出这个数？
似乎听说过这个题，有提示吗？多谢 |
|
g**********y
发帖数: 14569 | 25 来自主题: JobHunting版 - 一个电面题 hint:思路类似一个array所有的数even只有一个是odd.
那是什么题？ |
|
a**********2
发帖数: 340 | 26 都是老题，攒攒人品
1.分层打印二叉树
2.strstr（）
3.count words
4.tic-tac toe winning条件，如何update board
5.hash table和 BST的优劣势，什么时候该用什么结构。 |
|
c*********t
发帖数: 2921 | 27 问问第二题中的 “*”：
"*" means repeat previous char 0 or any times
可是在下面的链接中：
'*' (zero of more arbitrary char match).
http://www.mitbbs.com/article_t/JobHunting/31713505.html
到底"*"指的是什么？ "*"作用于它前面的字符？
你的例子：
match("aab", "c*a*b") ->true
我的理解是：
第一个*把它前面的给消掉
第二个*把它前面的a重复两次
结果就是aab了。所以match, 对吗？
谢谢！
means |
|
g*****i
发帖数: 2162 | 28 这链接里是wildcard,楼主的题目是regex,还是不一样.
这题我觉得用递归可能好点,不用递归的话我觉得难点在于一下这些特殊pattern
c*cba (*前后一样),
c*.ba (*后面是"."),
.* (*前面是".")
c*c*.*c* (同一个字符和"."的*连续出现)
谁能给点思路吗? |
|
c*********t
发帖数: 2921 | 29 问问第二题中的 “*”：
"*" means repeat previous char 0 or any times
可是在下面的链接中：
'*' (zero of more arbitrary char match).
http://www.mitbbs.com/article_t/JobHunting/31713505.html
到底"*"指的是什么？ "*"作用于它前面的字符？
你的例子：
match("aab", "c*a*b") ->true
我的理解是：
第一个*把它前面的给消掉
第二个*把它前面的a重复两次
结果就是aab了。所以match, 对吗？
谢谢！
means |
|
g*****i
发帖数: 2162 | 30 这链接里是wildcard,楼主的题目是regex,还是不一样.
这题我觉得用递归可能好点,不用递归的话我觉得难点在于一下这些特殊pattern
c*cba (*前后一样),
c*.ba (*后面是"."),
.* (*前面是".")
c*c*.*c* (同一个字符和"."的*连续出现)
谁能给点思路吗? |
|
c*******n
发帖数: 63 | 31 写个简单的第二题
void OR(Bits *out, const Bits &in1, const Bits &in2)
{
unsigned int sntnl = 1;
assert(out);
out->known = 0;
out->value = 0;
while(sntnl >0)
{
if( (in1.known&sntnl && in1.value&sntnl)
|| (in2.known&sntnl && in2.value&sntnl) )
{
out->value |= sntnl;
out->known |= sntnl;
}
else if(in1.known&sntnl && in2.known&sntnl)
{
out->known |= sntnl;
}
sntnl <<= 1;
}
} |
|
f*******t
发帖数: 7549 | 32 第二题，有两种情况下输出的值是确定的
1.in1->known = 1, in2->known = 1
2.某个inX->known = 1，以及inX->value = 1，因为是or操作，所以输出必然是1
我觉得答案是：
out->known = (in1.known & in1.value) | (in2.known & in2.value) | (in1.known & in2.known);
out->value = in1.value | in2.value; |
|
l**********d
发帖数: 29 | 33 第二题,这样如何?
out->known = in1.known | in2.known;
out->value = (in1.value&in1.known) | (in2.value&in2.known); |
|
r*******g
发帖数: 1335 | 34 看不懂第二题，物理意义是什么，到底是or两个known部分还是or两个value部分？
貌似Bits这个struct维护的就是哪些bit对应有value，这样的话貌似结果就是known的&
和value的|就行了？ |
|
c*********n
发帖数: 1371 | 35 第一题能仔细说说么？没看明白string 再怎么转换成vector。
function |
|
f*********5
发帖数: 576 | 36 需要明确每次返回什么样的number.
如果随便的话
1)这个题跟实现LRU有点像
doubly linked list+hashtable
use hashtable to judge whether the number is in them
use linked list to add new number and return a number
2)也可以用stack+hashtable
each time just push/pop stack and update hashtable
You
in |
|
b*****c
发帖数: 1103 | 37 第一题用2个hashtable，现在的和曾经取出过的，O(1） |
|
d*******l
发帖数: 338 | 38 第一个我觉得只要一个trie就可以，保存所有沒使用过的的电话号码。IsNumberTaken(
phone #)只要在trie里面找这个号码，找到了就是没被taken。
GiveMeANumber()，在trie里找最左边的那个叶节点就可以。删除这个节点。
ReturnBackANumber() ，把这个number重新放回trie中。
每个操作的代价都是号码的长度。这个其实比hashtable省空间和时间。
第二题我觉得上面说的先分成k份各自shuffle，再随机merge是对的。 |
|
d*******u
发帖数: 186 | 39 我回答第一题：
我假定a bunch of phone numbers是可用的电话号码。
初始化： 读入所有的电话号码建Trie (只需要十个分支，0～9).
IsNumberTaken(phone #) {
用phone #查询Trie如果能走到叶子，说明phone #可用，not taken,
return false.
else true.
}
GiveMeANumber() {
//从Trie中取出最左边的号码，返回该号码。
//也可以从Trie中取出随机的号码，返回该号码。
//对每一级节点，随机选一个分支。
//从Trie删除该号码。
}
ReturnBackANumber(phone #) {
把phone # 插入Trie中。
}
You
in |
|
f*********5
发帖数: 576 | 40 需要明确每次返回什么样的number.
如果随便的话
1)这个题跟实现LRU有点像
doubly linked list+hashtable
use hashtable to judge whether the number is in them
use linked list to add new number and return a number
2)也可以用stack+hashtable
each time just push/pop stack and update hashtable
You
in |
|
b*****c
发帖数: 1103 | 41 第一题用2个hashtable，现在的和曾经取出过的，O(1） |
|
d*******l
发帖数: 338 | 42 第一个我觉得只要一个trie就可以，保存所有沒使用过的的电话号码。IsNumberTaken(
phone #)只要在trie里面找这个号码，找到了就是没被taken。
GiveMeANumber()，在trie里找最左边的那个叶节点就可以。删除这个节点。
ReturnBackANumber() ，把这个number重新放回trie中。
每个操作的代价都是号码的长度。这个其实比hashtable省空间和时间。
第二题我觉得上面说的先分成k份各自shuffle，再随机merge是对的。 |
|
d*******u
发帖数: 186 | 43 我回答第一题：
我假定a bunch of phone numbers是可用的电话号码。
初始化： 读入所有的电话号码建Trie (只需要十个分支，0～9).
IsNumberTaken(phone #) {
用phone #查询Trie如果能走到叶子，说明phone #可用，not taken,
return false.
else true.
}
GiveMeANumber() {
//从Trie中取出最左边的号码，返回该号码。
//也可以从Trie中取出随机的号码，返回该号码。
//对每一级节点，随机选一个分支。
//从Trie删除该号码。
}
ReturnBackANumber(phone #) {
把phone # 插入Trie中。
}
You
in |
|
y******u
发帖数: 804 | 44 第一题难道不可以这样？
电话号码没多少吧，北美电话就10位，也算长了。而且都是整数
就建boolean数组Taken，存这个号码是否正在使用。比如
号码 1234567890 就是 Taken[1234567890]=true
其实就是extreme的hash，哈哈～
这样建好二值数组，3个函数就要操作了吧。 |
|
|
|
a**********2
发帖数: 340 | 47 来自主题: JobHunting版 - 问个电面题 这题假定没有重复的point对吧？要不worst case是O(n) |
|
i**********e
发帖数: 1145 | 48 你这样写貌似复杂了些，面试不会写那么复杂的代码的。
这题可以用 flood fill 的啊，递归十多行就能搞定。
基本就用一个二维数组记录哪些格子是访问过的，然后每一个格子如果还没访问过就进
行flood fill。
increase |
|
z****u
发帖数: 104 | 49 第二题是不是这个思路
假设我们只需要找出 connected component 的数目：从左上角开始扫描，如果遇到 1
的话，cc 数目 + 1，同时递归的把它的值为 1 的邻居置 0。继续扫描直到末尾。
扫描一遍就够了。同时每个点最多被扫描两次，值为 1 时一次，为 0 时一次，复杂度
应该是 O(n) |
|
b***e
发帖数: 15201 | 50 第2题我看到的基本解法是从左上开始，对任意元素，查找正上和左边的邻居，然后依
照一些rule来决定当前元素的label值。如果你把邻居都标0的话，恐怕会影响后续元素
的标定。因为一个很重要的rule就是当正上和左边都是相邻元素，但是标定值不同，那
这两个label就是等价的，而当前元素取二者label的最小值。
1 |
|
