r**u
发帖数: 1567 | 1 这个当然有关系了, data structure越多, 如果多个thread都操作这些data structure
, 每个data structure都要加锁保护.
可以把data structure合并, 减少lock的数目. 但是, 锁起来的code越多, delay就越
大, there is some trade-off.
后最后问了这一个mutex的题，我实在答不上来，就问他应该怎么做，很简单的回答我
用hashtable，完了上网搜也没搜到答案，来这里问问，希望大牛给指点指点 |
|
x****k
发帖数: 2932 | 2 这题版上讨论过，用dp做，具体答案不记得了，我重新做了一下，有错请指出。
设 F(i,j)为先取者从ai ~ aj取出来的最大sum，则
F(i,j) = max(ai + min(F(i+2,j), F(i+1,j-1)), aj + min(F(i,j-2), F(i+1,j-1))) |
|
x**y
发帖数: 70 | 3 面试题不会要求这么复杂的CODE的... 应该有简单写的. |
|
c*e
发帖数: 15 | 4 因为没见过这个题，所以想了好半天才答上来
面试感觉一般，答得不顺利，move on了
一个很长的text文档，怎样遍历一边，随机输出其中的一行
限制：
1.只能遍历一边
2.随机均匀分配
================
我的答案是：
保存已经遍历的行中的一个preLine
每读入第n行，在line_n和preLine中选一个，update preLine.
line_n的概率是1/n, preLine的概率是(n-1)/n
读到文件尾return preLine. |
|
a***o
发帖数: 24 | 5 我没有正确答案。 我只是感觉上面那位仁兄的算法好像是对的，细节方面，我在仔细
研究。
这是我刚才用笔写的，应该是对的
n=7, m=7, AAAAAAA
n=8, m=9, AAA23444
n=9, m=12, AAAA23444, or AAA234444
n=10, m=16, AAAA234444
n=11, m=20, AAAA2344444, or AAAAA234444
n=12, m=25, AAAAA2344444,
n=13, m=30, AAAAA23444444, or AAAAAA2344444,
n=14, m=36, AAAAAA23444444,
n=15, m=48, AAAA23444234444,
n=16, m=64, AAAA234444234444, |
|
b***e
发帖数: 1419 | 6 丁页！
如果我是interviewer的话，我会最终像要一个这样的答案或思路，而不仅仅是naive
DP. 因为
当n很大的时候，naive DP是做不出来的。就像是计算fib(n)，最终的理想是O(log(n))
的算
法。
Some more clarifications to help understanding:
1. It's easy to see for any k >= 10, (k-2) * f(n-k) pattern is not
needed because, (k/2 - 2)^2 > k - 2. So instead of the k-pattern, you
can always apply 2 consecutive (k/2)-patterns.
2. Note that all the steps are commutable. If you have a 4-pattern and
9-pattern, it doesn't matter which one you apply first. That's why if
you have 6... 阅读全帖 |
|
h**6
发帖数: 4160 | 7 关于背包问题，我再补充一点：
有重量为w1, w2, ..., wn的若干包裹，其价值为v1, v2, ..., vn。现在不限个数的取以上包裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
已知包裹 i 的单位重量价值最高，是否存在一个 W，对于所有 M≥W，f(M+wi) = f(M)+vi
前面已经求出 W = [sum(w)-wi]*(wi-1)，对于 M>W 的情况，可以先使用 DP，后用包裹 i 作补充，凑出总重量 M，并求出总价值。
但是当 sum(w) 非常大的时候，W 可能超出计算范围。使用复杂度为 O(W) 的 DP 算法求出 1~W 之间的所有解也不现实。这时候注意观察，我们需要的只是 1~W 之间与 M 关于 wi 的模相等的解，
x ≡ M (MOD wi)
只有这些 x 才能构造出总重量为 M 的情况。其余值的解与所求问题无关。
求出所有的 x 处的解，及相对应 M 处的总价值，然后取其最大者就可以了。
当然，条件是 M>W，否则仍然只能老老实实用 DP 求出答案。 |
|
c*******t
发帖数: 1095 | 8 "abcadabb"
答案应该是"bcad"吧
你的测出来不对 |
|
n********y
发帖数: 66 | 9 挺这个答案，或者是
power(n,3) - power(n,2) - 2 * (4n - 4)
即认为倒数第三层最外一圈的cube的下面一条边是碰到水的。。 |
|
|
z*s
发帖数: 209 | 11 我申请的职位是Software Engineer New Grad。
第一个人的寻找后继节点问题，可以使用parent指针；关于二叉树的旋转，只需要描述
一下过程就行了，不需要写代码。面试官当时只让我描述了一种旋转的情况（我只学过
AVL tree，一共有四种旋转的情况）。
关于网络方面的知识，我也很意外；我觉得开放性问题并没有标准答案，而且就我的能
力，当时只能想到一些网络方面的东西，所以就说了；面试官当时也没有提出反对的意
见。
第三个人的问题我是在read2类中定义了一个char buffer[]，表示缓冲区；同时定义两
个整型变量start和end，表示缓冲区中数据的起止位置；read函数每次先从缓冲区中读
取数据；若读完后还不够需要的字节数，再调用read4096，此时要先将读出的数据写入
这个自定义的缓冲区，在读取需要的字节数。 |
|
z*s
发帖数: 209 | 12 服务器那个题我答的不好，因为老是不知道他在问什么，他想要的答案是什么。反正他
给了我很多提示，比如可以用交替使用两台机器，还需要一个load balancer，这样可
以在一台服务器挂的时候正好用上另一台正常工作的服务器，再重启挂的这个机器。
文件找重复的那道题我觉得可以用hashtable，也可以external sorting。hashtable有
个问题是如果内存中放不下这个哈希表的话怎么办？我说可以使用多台机器，每台存放
一定范围内的数字（类似于MapReduce中map的过程），然后再分别对每个机器处理。 |
|
m****v
发帖数: 84 | 13 这种ood的题目，真不知道人家要的是什么答案，请高手赐教 |
|
z*s
发帖数: 209 | 14 我在Bloomberg的网站上投的简历，Financial Software Developer。几天以后就收到
了在线测试的邮件，四种编程语言选一种进行测试：C、C++、Java和C#，我选的C。一
共三十道题，都是五选一的选择题，每题限时三分钟。通过后接到电话面试的通知。
电话面试：
面试官是印度人，他说他在家用手机打的，我估计是当时纽约下大雪，上不了班了。然
后他又说他手里没有我的简历，让我先自我介绍一下。问的题大部分都是概念题。
1、进程、线程。
2、C语言存储空间的布局，堆、栈、静态存储区等等。问了一个具体的问题：
char *str = "Hello World"; /* 1 */
memset(str, 'a', 100); /* 2 */
第1句中的字符串和指针分别存储在什么地方？第2句会产生什么问题？他想要的答案是
Segmentation fault。
3、操作系统内存管理的一些问题，包括虚拟内存、页表、缺页处理等等。
4、网络，介绍一些你知道的网络协议，比较TCP和UDP，比较路由器和交换机，它们分
别工作在哪一层。
5、数据结构，链表、树、平衡二叉树等等。
6、... 阅读全帖 |
|
b*******a
发帖数: 68 | 15 N×N矩阵，每个CELL或黑或白，要求找出最大正方形，边全部是黑的
感觉是Dynamic Programming, 但正方形似乎与矩形完全不同，请教正确答案，谢谢！ |
|
s*****y
发帖数: 897 | 16 今天刚在careerup看到的一个很牛的答案，但是看不懂思路，但是结果肯定是对的。
int main()
{
int B[] = {1,1,1,3,3,3,20,4,4,4};
int ones = 0 ;
int twos = 0 ;
int not_threes;
int x ;
for( i=0; i< 10; i++ )
{
x = B[i];
twos |= ones & x ;
ones ^= x ;
not_threes = ~(ones & twos) ;
ones &= not_threes ;
twos &= not_threes ;
}
printf("\n unique element = %d \n", ones );
return 0;
} |
|
D*****d
发帖数: 1307 | 17 这样的话， 复杂度有O(n^2)吧
一般情况下， 这种算法的面试题答案的复杂度重不重要？
正在找实习中。。。 |
|
i*******g
发帖数: 100 | 18 我到最后了，跟imusic的答案类似
1） recursive, 判定leaf的exit point，我们讨论了一下
2） 比较多方法，随后发信给interviewer了
3） 我当时解释了，由于1）的算法选择，因此序列化的时候如果能够按tree的level存
储会达到比较好的save space的效果，但没有详述
4） zip后distribute, 另外可以map reduce, 不过他让提自己的方案，也是简述，主
要是考虑要用尽运算时的I/O
不过人还是没让进下一轮,但是并没有放到block list只是说找了别人，另外是要找js的
人，吐了一升血，做js，却问我这么多其他~~~ |
|
h**t
发帖数: 1678 | 19 看来是我复习的不到家。。。嗯哪里能找到这些面试题？精华区？careercup? |
|
h**t
发帖数: 1678 | 20 看来是我复习的不到家。。。嗯哪里能找到这些面试题？精华区？careercup? |
|
v***n
发帖数: 5085 | 21 HR部门天天看CareerCup和GlassDoor
据说现在凡是写出那个上面答案的都会被标记出来
现在公司召集了一票码工（25个人） 规定每个人出10题做题库用来测试
好像目标是做到每半年更新一次题库 |
|
H******7
发帖数: 1728 | 22 http://programmers.stackexchange.com/questions/64132/interestin
投票最高的答案说的很简略 有人给解释解释不？
Today I was asked this question. We have 2 cases with code blocks A, B and C. These code block don't share
any resources except an iterator (int i).
Please give 3 possible reasons why case 1 could be faster than case 2, and 3 possible reasons why case 2
could be faster than case 1:
case 1
for (i=0; i
A;
B;
C;
}
case 2
for (i=0; i
A;
}
for (i=0; i
B;
}
for (i=0; i
C;
} |
|
g*******s
发帖数: 490 | 23 我觉得那个答案解释挺清楚的
reasons for case 1 faster than case2
(1)执行loop的每次循环本身有有cost,即时你loop里什么code也没有。case 1是N次循
环，case 2是3N次循环
(2)方便并行计算
(3)A,B,C依次运行，他们虽然不share resources,但是他们的code某些部分可以被共用
，例如:假设每一次循环中，A,B,C都需要读取同一个input,这部分的代码就可以共用，
然后即时A，B，C用来存储这些input的object不同，但是类似i/o buffer之类的都可以
被重用
reasons for case 2 faster than case 1
(1) 寄存器，在case 1中，每一次循环要执行3个code block，这些代码段的load都是
有cost的，等于每一次循环有3次的transition,这样就是3N次，而case 2等于只有2次
，因为一段代码连续执行N个循环，就没有这个反复load，包括寄存器参数恢复的cost
(2)http://en.wikipedia.org/wiki/Loop... 阅读全帖 |
|
|
c*****l
发帖数: 879 | 25 在一个2维平面上有很多机器人 一共有2类 绿色和蓝色的
机器人都比较笨 不知道自己的颜色 也不能相互交流
现在有一个发信号的机器 可以给所有的机器人发信号 所有的机器人必须执行同样的命
令 （可以带条件的指令）
问如何在2个命令下 让绿色 蓝色机器人分组
ps： 我的答案是先让所有的机器人站成一排
然后当机器人在队列头的时候插入到 另一数组中 每次插入的位置为已经在队
列中的绿色蓝色机器人之间
BBGG
插入B就是变成BBBGG |
|
j**f
发帖数: 7403 | 26 想知道答案。。
给你两分钟回答出古埃及人造金字塔的时候怎样确保底座是水平的？ |
|
g***s
发帖数: 3811 | 27 再删除了一些不必要的clone，速度提高了近3倍（家里电脑，没改前是90秒左右）
算出答案是26s，全部扫描完是32s。
Answer: (running time from start : 26396ms)
4 13 5 4 13 6 8 12 16 9 13 13 13 16
9 2 6 5 6
4
Total running time : 32052 ms, count of dfs=100342 |
|
g***s
发帖数: 3811 | 28 再删除了一些不必要的clone，速度提高了近3倍（家里电脑，没改前是90秒左右）
算出答案是26s，全部扫描完是32s。
Answer: (running time from start : 26396ms)
4 13 5 4 13 6 8 12 16 9 13 13 13 16
9 2 6 5 6
4
Total running time : 32052 ms, count of dfs=100342 |
|
f**********t
发帖数: 1001 | 29 对synchronization没啥基础。看了看career cup。
. Give a class foo, inside, it has a synchronized method. We have two
objects of foo, called, f1 and f2, if f1 and f2 are concurrently running,
can we guarantee the synchronized method being accessed by only one thread?
答案是不是yes？因为method已经是synchronized了，只能被一个thread所执行？ |
|
b******d
发帖数: 27 | 30 俺模糊的记得synchronization要synchronize一个object. default 的object 是this.
f1 和 f2 是不同的object, 所以答案是no.不知道对不对。 |
|
h**********d
发帖数: 4313 | 31 有一种synchronization可以on class， 那样答案可以是yes |
|
x***i
发帖数: 585 | 32 以下为标准答案：
非static 方法 lock 当前对象。
static方法lock 该class.
所以只有两个方法都是static才可以同步，否则不行。 |
|
B*******1
发帖数: 2454 | 33 仔细看了一下你的code，似乎有这么个问题
譬如
a
/ \
b c
/ \ / \
d e f g
假如a的左子树b的最大值是通过b+d+e而来的，而不是b+e来的，那么你的答案就已经
set了啊，
就是说，
1.你可以用a 加上左子树一个路径+右子树一个路径
2. 你可以用a + 两个路径都来自左子树
3.你可以用a + 两个路径都来自右子树
但是你的递归，似乎是如果左子树已经选择了2个路径，还可以往右子树再选择2个路径
。
); |
|
B*******1
发帖数: 2454 | 34 帮忙看看我的code能否处理一个孩子的情况？
测试树：
8
/ \
/ \
/ \
/ \
/ \
0 14
/ \ / \
/ \ / \
/ \ 11 5
17 24 \ \
\ / \ 12 45
34 / \
19 28
答案: 28 和 45
最大和124
typedef pair Item;
Item MaxpathSum(Tree *node, int &CurMaxSum, int SumToNow, Tree *&ln, Tree *&rn)
{
if (node->left && !node->right) {
Item leftPathMax = MaxpathSum(node->left, Cur... 阅读全帖 |
|
x******2
发帖数: 546 | 35 DP？
S(a,b)表示恰用了A[a]到A[b]中最长所含有的B的长度，且必须满足A[a]=B[1],A[b]为
该最长字串的最后一个字符。
则S(a,b)=min(k=a...b-1){ S(a,k)+1 | A[b]=B[S[a,b-1]+1] }
最后答案应该在所有的S(a,b)对中找出满足S(a,b)=m且b-a+1最小的那个。
这个复杂度是O(N^3)，不知道有没有更好的 |
|
c******g
发帖数: 69 | 36 感觉跟编译词法分析很像，构造NFA，转化成DFA，得到状态转移表，匹配字符串。每一
步都有标准算法的，不过不确定是不是expect这个答案啊。
and
了？ |
|
P**********c
发帖数: 3417 | 37 我觉得这个应该就是答案，不过implement起来挺繁的。 |
|
P**********c
发帖数: 3417 | 38 那个的回答我看过，很简单的说了一句。不知道是不是就是答案。 |
|
I*********9
发帖数: 15 | 39 非常感谢上面两位的回复。真的是SQL达人。
SQL scirpts work well!结果完全正确。正是我要的答案。真是高人阿。就是给出了答
案，我还有些不明白，比如，为什么要用sum function等等。我辈需要进一步学习啊。
SQL ANALYTIC FUNCTIONS还没有试， 这个functions我以前没有用过。
再次感谢两位SQL高人！ |
|
l****o
发帖数: 924 | 40 这是个decision making 的问题，考的是leadership to get things done.
问题的实质是，你的plan A不行了，你该怎么办。
答案列举backup plan就好了。
可以trouble shoot
可以call for help
可以 find another printer
可以开车去外面staples打
都可以。只要result driven就行了。 |
|
W**********r
发帖数: 8927 | 41 我的答案：
if(用快慢指针从A的头出发测A是不是有环 == Yes) {
if (用快慢指针分别从A和B的头出发测是否相遇 == Yes) {
确认相交；
追上的一点肯定在环上，以此可以遍历环，再分别从A和B出发依次比较是不是在环上的话，最后可以确定分别的交点。
}
else {
确认不相交；
}
}
else {
if(用快慢指针从B的头出发测B是不是有环 == Yes) {
确认不相交；
}
else {
遍历两个链表，得到长度m和n，然后得到长度差abs(m-n)，较长的链表先走abs(m-n)这么多个点，然后两边一起走，第一个相同的就是交点。始终不同就没交点。
}
} |
|
c****p
发帖数: 6474 | 42 没理解错的话，如果A conform to A'，那么A'中为1的位，A对应地必须为1；A'中为0的
位，A对应地可以为1或者0。
如果令ones(A)=A中1的位数（对于30-bit unsigned有O(1)算法），
则A'的可能数为2^(30-ones(A))。
令f(A) = A'的可能数，
那么答案应该是：
f(A) + f(B) + f(C) -f(A&B) - f(A&C) - f(B&C) + f(A&B&C)
=====
囧，，，，和例子验证了一下，好像不对。。。。
=====
上式改成
f(A) + f(B) + f(C) -f(A|B) - f(A|C) - f(B|C) + f(A|B|C)
one |
|
f**********l
发帖数: 1191 | 43 思路是对的，我的理解跟你一样，不过稍微有点变化。
令 zeros(A) = A中0的位数
A'的可能数为2^zeros(A)
f(A) = A'的可能数，
则答案是：
f(A) + f(B) + f(C) - f(A|B) - f(A|C) - f(B|C) + f(A|B|C)
对着例子算了一下，返回是11
觉得象是排列组合的题，这门课我学的不好，:-(
0的 |
|
f*******t
发帖数: 7549 | 44 前面还有别的帖讨论过，in-place+O(n)不可能
上面提到的dinohound的答案用的是divide-and-conquer，时间复杂度是O(nlogn) |
|
|
d****n
发帖数: 130 | 46 我当时可能想多了，因为我想很多container的algorithm要用到assignment op.
他们面试很怪，你说了答案，他们什么也不说，没什么交流，感觉挺没劲的。 |
|
d****n
发帖数: 130 | 47 你觉得bloomberg的人水平这么低？难道我真高看他了？他最后舍不得说出答案，当宝贝
似的，估计准备用来忽悠下一个人。 |
|
d****n
发帖数: 130 | 48 构造map也是nlogn吧。对了，当时他说比如一个数组特别长，另一个数组特别短，我说
在长的数组里binary search短的数组里的元素。他说但那长数组还要排序啊。他说我已
经很接近答案了。 |
|
d****n
发帖数: 130 | 49 嗯，这应该就是答案了，多谢。这个题以前看到无数遍，确实没细想过。 |
|
r********g
发帖数: 1351 | 50 有的是我面的，有的是听来的。。。detail我也不知道（或者没弄明白），大家自由发
挥吧。。
最讨厌的是开放题，实在无从下手（如果事先没准备的话）
1. 数据结构for spreadsheet
2. 实现 G+ search
3. 一个app需要用cache，怎么实现thread safe
老题：
找minimum snippet (这个很诡异，据说它家的答案是把每个character的index找出来)。
找regexp （含有*和.两个特殊字符，这个递归吧？） |
|
