l***u
发帖数: 26081 | 1 贡献一道MS面试题
输入：
一棵二叉树和树上的一个结点（每个节点有一个整形数据）
输出：
这棵树上的另一个节点（如果不存在返回NULL），要求这个节点的整形数据与给定节点的差距最小（如
果有多个这样的节点就返回与给定节点的树距离[1]最小的任意一个）
注：
1. 树距离定义为f(x,y)=L(x)-L(c)+L(y)-L(c)，其中L是某节点的层数，c是x和y的最小公共祖
先节点 |
|
d***d
发帖数: 99 | 2 一道大公司诡异的complete binary tree max sum of 2 nodes 题
当场 40min white board 给出了O(N2) 的解法，对方表示赞许，但是没时间optimize
了。直觉告诉我应该有NlogN的解法。大牛指点下。
具体如下：
given one complete binary tree, with positive and identical values in all
nodes.
Find 2 nodes, such that:
sum of their path nodes to root (identical nodes will count only once) are maximum. |
|
r*******g
发帖数: 1335 | 3 给定一个包含4300000000个32位整数的顺序文件，如何找一个至少出现2次得整数
有一道题是找没有出现的整数，而这道题是找重复出现两次的整数，都来自
programming pearls，这道题到底怎么弄，没看明白？
谢谢了 |
|
|
J*********n
发帖数: 370 | 5 来自主题: JobHunting版 - 请教一道题 之前的遇到过的一道面试题，还是用skype面试的，感觉很别扭。当时因为前面被问了
很多data mining的问题，答得不好，到时后面有点乱套了，代码还没写完时间就到了，
结果就挂了。。。。
从log文件里找出访问次数最多的10个url,经典的做法是用hashtable算出每个url访问
的次数，然后遍历hashtable中的每个url，用minHeap找出最大的十个。时间复杂度为O
(n+mlog10), n为log里url的数目，m为distinct url的数目，空间复杂度为O(m), 如果
扩展到最多的k个url，时间复杂度就是O(n+mlogk), 空间不变(因为k超过了m的话只能
返回m个url)。
如果有更好的解法可以把时间或者空间复杂度降下来，还望不吝赐教，多谢！ |
|
x****h
发帖数: 78 | 6 【 以下文字转载自 Statistics 讨论区 】
发信人: xyzhhh (xiaoyuanzi), 信区: Statistics
标 题: 问一道multiple linear regression的题
发信站: BBS 未名空间站 (Wed Nov 30 22:11:20 2011, 美东)
Simple linear regression S1: Y~x(1) (i.e., Y=a1*x(1)+a0); R2 (coefficient of
determination) = 0.01 ;
Simple linear regression S2: Y~x(2) (i.e., Y=b1*x(2)+b0); R2 (coefficient of
determination) = 0.02 ;
Then multiple regression M3:Y~x(1) and x(2)(i.e., Y=c2*x(2)+c1*x(1)+c0); wha
t is the min and max of the R2 for this regression?
thanks! |
|
w***z
发帖数: 1848 | 7 今天去一家小公司面试， 其他常规程序问题还好，最后结束时被问了一道问题：描述
一下从电脑接入互联网到登录某网页的整个详细过程。当时听了感觉题目比较大，我是
解释了几个会用到的protocol, 比如DHCP, BGP, TCP之类。感觉对方不太满意。请教一
下大牛这题该怎么回答？ |
|
|
S**I
发帖数: 15689 | 9 ☆─────────────────────────────────────☆
coupondeal (coupon and deal) 于 (Tue May 3 22:46:34 2011, 美东) 提到:
某公司的笔试，具体名称我就不说了，有这样一道题目
你是在公司已经工作5年的VP，最近你们公司有很多新招进来的fresh grads。
今天，已经晚上9点了，你仍然在office里面奋战。正在这时候，你抬头，
看到楼层不远的地方，有一位新来的fresh grad A 同学正因为压力太大而伏在案上啜泣
这时候，你会
A.当作什么事都没发生
B.告诉A的直接上司，希望他能够给予A心理上的辅导
C.自己走到A旁边，询问什么原因
D.因为自己和A不熟，所以找一个和A比较熟的同事B，让B过去安慰安慰A
E.其它（请注明）
问题1：从A到E的选项中，你最应该做的是什么？为什么？
问题2：从A到E的选项中，你最不应该做的是什么？为什么？
☆─────────────────────────────────────☆
Cathy2011 (rr) 于 (Tue May 3 2... 阅读全帖 |
|
g*****1
发帖数: 998 | 10 【 以下文字转载自 Programming 讨论区 】
发信人: guagua1 (), 信区: Programming
标 题: 请教一道c/c++题
发信站: BBS 未名空间站 (Fri Jan 27 22:47:12 2012, 美东)
char *m()
{
char str[50];
strcpy(str,"how are you");
return str;
}
int main()
{
char s[50];
strcpy(s,m());
printf("%s",s);
//cin.get();
return 0;
}
为什么结果可以正确输出呢？我知道return by pointer可以make copy，可是return之
后storage不是free了吗？
另外，为什么下面这个就只能由一部分正确输出？
char *m()
{
char str[20];
strcpy(str,"how are you");
return str;
}
int main()
{
printf("%s",m());
//cin.get();... 阅读全帖 |
|
k***t
发帖数: 276 | 11 我也算了个271405。不过你贴得code好像不全吧。
发信人: peking2 (myfacebook), 信区: JobHunting
标 题: Re: 一道题：number of permutation是 for a total score
发信站: BBS 未名空间站 (Tue Jan 31 06:43:11 2012, 美东)
这不是DP吗？
int MaxCount(int S)
{
if(S<0)
return 0;
if(S==0)
return 1;
int count=0;
for(int i=0;i
{
count+=(S-p[i]);
}
} |
|
k***t
发帖数: 276 | 12 我也算了个271405。不过你贴得code好像不全吧。
发信人: peking2 (myfacebook), 信区: JobHunting
标 题: Re: 一道题：number of permutation是 for a total score
发信站: BBS 未名空间站 (Tue Jan 31 06:43:11 2012, 美东)
这不是DP吗？
int MaxCount(int S)
{
if(S<0)
return 0;
if(S==0)
return 1;
int count=0;
for(int i=0;i
{
count+=(S-p[i]);
}
} |
|
m***n
发帖数: 2154 | 13 挂还分时间？
就问了一道，他说good,你还有问题吗？ |
|
a********g
发帖数: 69 | 14 【 以下文字转载自 CS 讨论区 】
发信人: ayyleaving (ayy), 信区: CS
标 题: 请教一道题的算法！！
发信站: BBS 未名空间站 (Fri Feb 24 17:25:53 2012, 美东)
给定一个数组A代表n个没刻度的水桶，a1, a2, ..., an是这n个水桶的容量（升）。给
定一个目标数字b升，要求给出一个算法，要么返回false（用这些桶不能倒出b升水）
，要么返回一系列步骤，得出最后某个水桶里正好盛了b升水。初始状态是第一个桶是
满的，其他桶都是空的。
我知道这个问题跟最大公约数有关，即b必须是a1, a2, ... an 的最大公约数的倍数才
能得到。但是跟传统倒水题目不同，可取的水不是无限多的，每个容量的桶也只有一个
。还知道这个算法可以用递归来写。有没有版上大牛帮忙看看的？万分感谢！ |
|
H***e
发帖数: 476 | 15 来自主题: JobHunting版 - 上一道题吧 大牛帮看下有明线错误吗？
》》》
发信人: Hbase (每天都进步一点点), 信区: JobHunting
标 题: Re: 上一道题吧
发信站: BBS 未名空间站 (Wed Feb 29 19:21:56 2012, 美东)
这样行不行会不会简单点：
用一个boolean[] flags 来indicate对应的括号是不是最后valid,valid就是可以组成
一对被stack pop出去
用stack来进出一遍决定此 flags (入stack的也包括括号的index,这样好写flags)
然后扫描一遍flags这个array,看连续为1的最长的连续子array， 及其个数 |
|
i***d
发帖数: 28 | 16 来自主题: JobHunting版 - 问一道老题 问一道老题，考古了但没有找到：
字符串有数字和字母，把数字放到字母的前面，但要保持原来的顺序。
例如: 1a2b3c==>123abc.
有没有比O(n^2)好的算法啊？ 谢谢！ |
|
f********1
发帖数: 24 | 17 最近电面的R&D部门的一道题目。题目很简单。和大牛们讨论下。
optimize the following code to speedup.
for(i=0;i
a[i] += c*b[i];
电面的人说有好些优化的办法，比如SIMD。
SIMD不懂，其他的优化也没有想到。大牛们说下用SIMD怎么优化，其它优化办法呢？ |
|
|
|
k*******r
发帖数: 355 | 20 就问了我这一道题，题目和职位没关系把？
（不过我在简历中确实吹过自己是算法expert,难道因为这个... 汗） |
|
s*******n
发帖数: 97 | 21 记得看到一道A的面试题，好像是计算transportation fee，不记得了。。是个算法题
目。。 |
|
w***y
发帖数: 6251 | 22 第4版里面的一道题目
19.11 Design an algorithm to find all pairs of integers within an array
which sum to a specified value.
解法不复杂, 不过看样子是不用考虑array里面有重复数字的. 这样条件就简单很多-
-当然这个题如果要考虑重复数字, 意义也不大,完全就是为了题目更繁琐一点hehe
但是如果题目没有明确说, 怎么知道要不要考虑有重复数字的? |
|
w***y
发帖数: 6251 | 23 第4版里面的一道题目
19.11 Design an algorithm to find all pairs of integers within an array
which sum to a specified value.
解法不复杂, 不过看样子是不用考虑array里面有重复数字的. 这样条件就简单很多-
-当然这个题如果要考虑重复数字, 意义也不大,完全就是为了题目更繁琐一点hehe
但是如果题目没有明确说, 怎么知道要不要考虑有重复数字的? |
|
t**i
发帖数: 314 | 24 来自主题: JobHunting版 - 一道面试题 1*n方格,n可以认为任意多，其中的两个上面有mark，2个robots，一个介于两mark的中
间某一方格上，另一个位于两mark的左边。
robot可执行三个动作：左移一步，右移一步，报告当前是否在mark上。
要求：写一个code sequence同时作用于2个robot上以保证他们肯定会相遇。
是我面试时的最后一道题，当时题目意思都没理解好被告知时间到了。这是根据我个人
的理解事后整理出来的，应该是这个意思。如果有见过这题的请补充一下或者指出我的
谬误之处。 |
|
p*****2
发帖数: 21240 | 25 yishan的这个思路很有趣。好像上次解一道题也是这种思路。不知道是学来的，还是自
己想出来的。 |
|
p*****2
发帖数: 21240 | 26 yishan的这个思路很有趣。好像上次解一道题也是这种思路。不知道是学来的，还是自
己想出来的。 |
|
s***y
发帖数: 124 | 27 【 以下文字转载自 Mathematics 讨论区 】
发信人: sfbay (sfbay), 信区: Mathematics
标 题: 问一道概率题?
发信站: BBS 未名空间站 (Sun May 13 00:48:43 2012, 美东)
N个空瓶子， 需要放入M个白球， K个黑球。 每个瓶子不能装两个或两个以上同一颜
色的球。
N, M, K 都是整数， M<=N, K<=N
最后一共有 R 个瓶子里面同时有黑球和百球的概率是多少？ |
|
p*****2
发帖数: 21240 | 28 被出了个经典题reverse linkedlist, 我说我刚刚被问道了。他说是吗？你做出来了吗
？我说做出来了。他说那你再写一遍吧，既然已经做了一次了，这次应该perfect才对
吧。然后去倒茶了，让我自己写。大概1,2分钟写完，大概这个样子。
PNode reverse(PNode head)
{
PNode newhead=null;
while(head)
{
PNode n=head;
head=head->next;
n->next=newhead;
newhead=n;
}
return newhead;
}
等了几分钟那人一进门就说，“二爷，你怎么写的这么复杂呢？你怎么用了这么多指针
呢？你能不能少用一些指针呢？“，
我说”你的意思是让我用一个指针变量来完成“，他说”是的，你用了太多指针了“。
我说”好吧，我看看“。
结果不看还好，越看越心惊，压力无限大，脑子短路，啥思路也没有，当即就跪了。
本来一道挺简单的题，咋做成个这样子呢？昨晚一晚没睡好，郁闷呀。 |
|
c*****l
发帖数: 20 | 29 我感觉有的考官在挑毛病
似乎心中已经决定拒了再找理由
呢？你能不能少用一些指针呢？“，
我说”你的意思是让我用一个指针变量来完成“，他说”是的，你用了太多指针了“。
我说”好吧，我看看“。
结果不看还好，越看越心惊，压力无限大，脑子短路，啥思路也没有，当即就跪了。
本来一道挺简单的题，咋做成个这样子呢？昨晚一晚没睡好，郁闷呀。 |
|
h****e
发帖数: 928 | 30 说实话，我的比你的更严重：重新做一道几个星期以前做出来的
题目，居然做不出来了。看看原来的code实在不明白当时怎么就
做出来了。 |
|
p*****o
发帖数: 1285 | 31 某家on-site的一道题。
Find the most frequent character in a string.
Data: strings are composed of Unicode charaters, stored in 10 sets of 5GB
files on 10 different servers each with 2GB of memory.
Constraints: network communication is expensive.
Question: find the best algorithm. |
|
b***d
发帖数: 87 | 32 请教一道leetcode的online judge题，题目一直没看懂。
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
另外还有几个列子：
/home/foo/../bar" -> "/home/bar"
"/home/foo/./.././bar" -> "/home/bar"
"/home/of/foo/../../bar/../../is/./here/." -> "/is/here" |
|
p***e
发帖数: 69 | 33 来自主题: JobHunting版 - 一道面试题 签了NDA，就不说谁家的了
给定一个大概如下的图：
+----+---------+----+
| | | |
+----+----+----+----+
| | |
| | |
| | |
+---------+---------+
| |
+-------------------+
Q1: 用什么样的data structure来表示这个图？可能有millions of vertices
Q2: 如何得到图中所有正方形的个数？比如我上面给的图形中有5个正方形，可能画得
不太标准
当时是一道raise bar的题，也没太多时间讨论，希望在这里大家讨论一下，有同遇到
过就更好了～ |
|
s****n
发帖数: 70 | 34 给了这么长一道题，光读就读了半天
Write a Java function, printTree(), which prints a given tree in depth first
format to stdout. Details:
The argument of printTree is a stream of pairs of string values.
Each string found anywhere in the input represents a unique node.
Each item in the stream is a pair indicating a parent/child relationship
in the tree. The first element in the pair is the parent. The second
element in the pair is the child.
Each parent can have many children.
The input list may con... 阅读全帖 |
|
h******2
发帖数: 13 | 35 问一道微软的面试题:
有2*N个文件，文件的大小保存在size[2*N]中。然后想要分成N份（每一份可以有1或者
多个文件),要使这N份中的文件size之和的最大值最小，如何实现? |
|
a*****n
发帖数: 682 | 36 只用过很短时间的python，面试的那家发来一些题目，其中一道是关于python的，能帮
忙解答一下吗？谢谢
There's a problem with the following Python 2.x code, please fix it.
print reduce(lambda x, y: x+y, filter(lambda x: x%2, map(lambda x: x*x,
xrange(10**6)))) = sum(x*x for x in xrange(1, 10**6, 2))
After the fix, what would be printed? Explain the result. |
|
i*********7
发帖数: 348 | 37 我也不知道。。。careercup上面就这么写的。
我怎么有印象其实这应该是一道np问题？ |
|
c******t
发帖数: 391 | 38 今天面试码工职位,被问到了一道coding题，说有一个m x n的二维矩阵Item[][]，每一
个元素都是一个Item类的object， 其中Item类定义如下:
public class Item{
public int x; //
public int y;
}
x和y分别是矩阵里的另一个元素的横纵坐标。实现一个函数，给定一个起始点的横纵坐
标startX 和startY，返回从起始点出发的traversal是否能cover矩阵里的每一个点。
我的想法是用一个hashSet，每初始化一个Item，都放入这个set， 直到遇到重复元素
或null为止，然后计算hashSet的size是否等于matrix的size。我写的基本算法:
boolean getCoverage(Item[][] items, int startX, int startY){
Item item = items[startX][starty];
HashSet- set = new HashSet
- ();
set.add(item);
while(item... 阅读全帖 |
|
C***U
发帖数: 2406 | 39 大牛
这个是你给的解答
发信人: gnahzy (hello), 信区: JobHunting
标 题: Re: 问一道算法题
发信站: BBS 未名空间站 (Thu Oct 4 16:30:52 2012, 美东)
哦，你说不优的意思是说解答不对？我还以为你说效率不好呢。你这个例子很好解决啊
。第一轮去掉那个认识所有人的。然后剩下的所有人都符合要求了，直接返回了。
如果不是我理解错你的意思了的话 你给的解答是错误的。。。。。 |
|
T**e
发帖数: 191 | 40 偶尔看到的一道算法题，不是面试的。
total
pj)] |
|
t********e
发帖数: 344 | 41 一道非常基础的题，我觉得自己是不是理解不对，请大牛们赐教。
career cup 150上的：
given a generator for random number 1 to 5, write a generator for random
number 1 to 7.
书上有很长的分析，最后给了一个有点复杂的code。
一模一样的题在leetcode上也有：http://www.leetcode.com/2010/11/rejection-sampling.html
也是长篇分享，最后有复杂的code。
我就想的特简单：同时run两个random5（），那么random5() + random5()的范围就是
2 to 10。
然后取 2 to 8这一段，除7取模，不就好了？
这样对吗？那那些个分析都什么意思呢？ |
|
g**********y
发帖数: 14569 | 42 不要妄自菲薄，任何时候版上的水平相差不大，都是正态分布，水平高的不一定爱出来
说话。
不能因为能否快速正确地解一道题来判断水平，就好像面试一样，我觉得最有效的不是
面面俱到地cover每一个题，而是在有些题上有很好的发挥，就足够impress对方了。
培训的时候教练说了一句：你面试的所有目的，是看未来的5年，你想跟这个人天天一
起工作吗？
我不会要求同事是从来都正确的圣人，但我希望他有与众不同的地方。 |
|
|
c******t
发帖数: 391 | 44 今天电面时的一道题，两张表A和B，size分别是m和n，问如何join才能使返回表的size
最大。我答曰full outer join，size是m+n。但interviewer说还有办法让结果大于m+n。
这题怎么想啊... |
|
h****e
发帖数: 928 | 45 估计要过好久才有机会面试人，就上一道我以前喜欢出的题目吧。
题意非常简单，不到一分钟就可以解释清楚，但是一次完全做对不
多见。主要是考写code的能力，而且一般不限制用什么编程语言，
让面试的人可以自由发挥，多少都能写出一些code。这样评估时就
不是简单的0/1关系。
题目：给定两个有效的表示版本号的任意长的字符串，例如"3.0",
"1.2.3"，"5.01"，"4.99.6"等，比较哪一个字符串表示的版本号高。
用的是一般公认的比较原则，上边的例子中
5.01 > 4.99.6 > 3.0 > 1.2.3。 |
|
|
s********k
发帖数: 6180 | 47 电面，主要讨论research和工作，出了一道题：
假设一家utility bill company， 分段收取utility，写程序实现charge。
这个题刚开始看起来很简单
if(usage
charge = usage*rate1;
}else if(usage> level1 && usage
charge = level1*rate1 + (usage-level1)*rate2
然后follow up，能不能优化，分别在time 和space，刚开始就想到hash，不过在build
hash function的时候卡壳了，我想的是hash是一个array，index是最大可能的usage
，然后content是level，比如{level，level，level2,....},usage 1,2 就是level1，
但是问题是usage可能随意并且无穷大，所以space可能很大。当时有点stuck在那里，
后来想到了可以用一个interval tree的变种：
node(14-30)
left(1-13).....rig... 阅读全帖 |
|
n****r
发帖数: 120 | 48 【 以下文字转载自 Topcoders 俱乐部 】
发信人: nibber (nibber), 信区: Topcoders
标 题: 讨论一道老题：分离数组中的正负数
关键字: 算法 数组 O(n) 时间复杂度分析
发信站: BBS 未名空间站 (Thu Nov 8 10:45:04 2012, 美东)
负数在前，正数在后，需要保持负数之间和正数之间的顺序不变！时间复杂度要求O(n)
,空间复杂度O(1)
下面是我的代码，空间复杂度O(1)没问题，时间复杂度分析如下，
设数组中共有负数X个，分散在K个分离的连续负数的子数组段，每个子数组段的长度为
Li，1<=Li
下面算法中K个分离的负数子数组段移到最后位置需要最多进行K次swap操作，而swap的
时间复杂度是O(n)，（这里n是子数段的长度），因此
一共的需要的时间是O(L1)+O(L2)+...+O(Lk) = O(X).因此整体的时间复杂度就是O(n)
这个分析妥不妥？请大牛们给指点一下，还有其他的时间O(n),空间O(1)解法没有？
public static void split(int[] ... 阅读全帖 |
|
b*****u
发帖数: 648 | 49 这个反例好，谢谢！
那如果记录一下5的位置，最后shuffle一道能不能解决问题呢？
也就是说，快排在这里带来的所有不稳定性，都是最后一串连续正数没参与swap带来的
，所以只要track这个位置就好了 |
|
m***k
发帖数: 946 | 50 再请教一道题：
First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
这题不是1-N的范围里缺一个数。我看了测试case，类似[1,2,6,7]是可能出现的。这样
就不能用“只有一个数出现奇数次”那种bit xor的办法来解了。
谁有什么好办法？ |
|
