有人对大公司的面试题感兴趣吗？

cleverman

通常顶级软件/互联网公司开发和测试的面试题是类似的，只是开发对答案要求更高一些，但是从题目上来讲区别不大。而且现在，面试开发也会让你设计test cases,因为开发承担一定的测试职责，比如Unit test。面试测试当然要考coding, 因为需要编写自动化。所以，无论面试开发，还是测试准备工作都是雷同的。
如果有人对他们的面试题感兴趣，我可以发一些上来大家一起讨论。

丢了朵朵

回复 41# fuwu527751246


    最近老发现你的踪迹~嘿嘿

丢了朵朵

天~看到这些 发现差距好大啊~一点概念都没有~

fuwu527751246

wwwyhx

回复 21# cleverman

设最大可能的得分是 maxScore (可通过最高单位权值乘以长度计算)
给输入字符串编号：st0,st1,st2....stn
字符串对应的分数编号:sc0,sc2...scn
我现在从st0一个个读到stn，每遇到一个字符串无非就是选与不选两种可能
设 f(i)为i .... n的最大score，目的是求f(0)
则有公式：f(x) = max{f(x+1), f(x) + sc(x+1)} (str(x+1)不和现有的重叠) 或 f(x+1)(str(x+1)和现有的重叠)

用动态规划实现以上函数

weiwei911909

各种豆要学啊 学嘛 先学嘛啊 ~~

474241558

题目涉及的即广又精·····需要懂得东西还有很多，大公司就喜欢搞一些比较拐的题目。哎········
做不出来也不能完全决定什么啊。

wwwyhx

(转贴)
思路：

开一个二维数组d[j]来记录a0-ai与b0-bj之间的编辑距离，要递推时，需要考虑对其中一个字符串的删除操作、插入操作和替换操作分别花费的开销，从中找出一个最小的开销即为所求

具体算法：

首先给定第一行和第一列，然后，每个值d[i,j]这样计算：d[j]   =   min(d[i-1][j]+1,d[j-1]+1,d[i-1][j-1]+(s1  ==  s2[j]?0:1));  
最后一行，最后一列的那个值就是最小编辑距离



poj3356类似题目：http://acm.pku.edu.cn/JudgeOnline/problem?id=3356

c++代码：

#include <iostream>
using namespace std;

int len1,len2;//分别代表原string与目标string的长度
char s[1005],d[1005];//分别存储原string与目标string
int dp[1001][1001];

inline int Max(int a,int b)
{
return a>b?a:b;
}
inline int Min(int a,int b)
{
return a<b?a:b;
}
void Dp()
{
int i,j;
for (i = 0; i <= Max(len1,len2); i++)
{
  dp[0] = i;
  dp[0] = i;
}
for (i=1; i<=len1; i++)
  for (j=1; j<=len2; j++)
  {
   if (s[i-1]==d[j-1])
    dp[j]=dp[i-1][j-1];//不需操作
   else
    dp[j]=Min(dp[j-1]+1,Min(dp[i-1][j]+1,dp[i-1][j-1]+1));
  }
cout<<dp[len1][len2]<<endl;
}
int main(void)
{
//freopen("in.txt","r",stdin);
while (cin>>len1>>s)
{
  cin>>len2>>d;
  Dp();
}
return 0;
}

wwwyhx

edit distance解法

动态规划经常被用来作为这个问题的解决手段之一。
　　整数 Levenshtein距离(字符串 str1[1..m], 字符串 str2[1..n])
　　//声明变量， d[i , j]用于记录str1[1...i]与str2[1..j]的Levenshtein距离
　　int d[0..m, 0..n]
　　//初始化
　　for i from 0 to m
　　d[i, 0] := i
　　for j from 0 to n
　　d[0, j] := j
　　//用动态规划方法计算Levenshtein距离
　　for i from 1 to m
　　for j from 1 to n
　　{
　　//计算替换操作的代价，如果两个字符相同，则替换操作代价为0，否则为1
　　if s= t[j] then cost := 0
　　else cost := 1
　　//d[i,j]的Levenshtein距离，可以有
　　d[i, j] := minimum(
　　d[i-1, j] + 1, //在str2上j位置删除字符（或者在str1上i-1位置插入字符）
　　d[i, j-1] + 1, //在str2上j-1位置插入字符（或者在str1上i位置删除字符）
　　d[i-1, j-1] + cost // 替换操作
　　)
　　}

cleverman

回复 34# wwwyhx

很多题是没有标准答案的，或者标准答案是错的。变string的那道，是DP题，这个答案我知道了。substring的，别人给我link了，我还没怎么看太明白，只是知道个大概的意思。感觉很多时候你去面试一个公司会碰到这么一道变态的题（至少对我来说做出来的可能性基本为零，如果不事先知道题）
可能只能靠多看题才能慢慢量变到质变。
这两道题都可以brute force。不过有些变态的面试官直接就断掉你的想法了。其实就算brute force代码也不是太容易。第一道题你想知道最优解可以search "edit distance"。第二道题要用到二分法

wwwyhx

楼主几道题没给标准答案啊

KingRight

回复  欺负人


    应该要10年的时间，相当于花了400W买了这套房子
goopy 发表于 2010-10-9 23:37

10年之后这个房子涨到了518.74849202万！

KingRight

2010年27号晚,Google的2011年校园招聘宣讲会分别在北大和清华举行，其中北大本来是350
人的会场，结果去了 ...
欺负人 发表于 2010-10-9 21:17

40 * n = 200 * (1+10%)的n次方

求n,无解. 所以是永远买不起

goopy

回复 28# 欺负人


    应该要10年的时间，相当于花了400W买了这套房子

KingRight

回复 3# cleverman

将数值考虑成2进制！

cleverman

回复 26# wwwyhx
brute force不让用，
greedy, 考官明确说了不work。权值最大的未必会在结果列表里吧？
比如 1-10 10
10-11 4
11-20 10

应该返回1-10, 11-20 sum=20
按权值的话是10-11 4最大

欺负人

2010年27号晚,Google的2011年校园招聘宣讲会分别在北大和清华举行，其中北大本来是350
人的会场，结果去了大约600多人，爆满，那场面绝对是人山人海，彩旗飘飘。

经过了大约一个小时多的宣讲和问答，开始现场笔试环节，一共10个选择题和三个算法题，只有选
择题答对了8个以上的人才有机会让面试官看你后面的算法题。然后第2天下午会通知笔
试通过的人进行面试，Google的效率就像其搜索引擎一样迅速，效率可见一斑。

其中前10个选择题中有一个特别雷人的，题如下：

现在北京有一套房子，价格200万，假设房价每年上涨10%，一个软件工程师每年固定能
赚40万。如果他想买这套房子，不贷款，不涨工资，没有其他收入，每年不吃不喝不消
费，那么他需要几年才能攒够钱买这套房子？
A, 7年
B, 8年
C, 9年
D, 10年
E, 永远买不起

wwwyhx

哦，那个面试官给了个前提条件是节点非头尾.要不就无解了。

wwwyhx

最笨的方法就是穷举

聪明一点的办法就是贪婪算法吧，对每个字符串做权值计算wi = score/length,  先选择权值最大的，然后按权值递减的往下选，重叠的跳过。NP复杂问题？？

wwwyhx

我晕，桶排序在这和hashtable没什么区别吧，不也要重新分配空间