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

cleverman

有一个输入的字符串，和一组substring,每一个substring 包括
1. start (开始位置）
2. end (结束位置）
3. score (得分）
substring有可能有overlap,并且score 和substring的位置，长度，内容完全没有关系。
问题是，返回所有的没有overlap的substrings, 使的他们的sum最大。

cleverman

回复 10# wwwyhx

有人说用bucket sort, 根据int 32位分为32个bucket。然后在分组sort。

cleverman

我来给几个微软的面试题：
1.二叉搜索树找给定两个节点的最近公共父节点
2.只知道一个指针指向某链表的一 ...
wwwyhx 发表于 2010-10-7 22:12

知不知道如果指向的是最后一个节点怎么办？

jerry_sky

看了挺惭愧的，这些题目很多都不懂

wwwyhx

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

wwwyhx

最笨的方法就是穷举

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

wwwyhx

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

欺负人

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

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

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

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

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最大

KingRight

回复 3# cleverman

将数值考虑成2进制！

goopy

回复 28# 欺负人


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

KingRight

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

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

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

KingRight

回复  欺负人


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

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

wwwyhx

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

cleverman

回复 34# wwwyhx

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

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 // 替换操作
　　)
　　}

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;
}

474241558

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

weiwei911909

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

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)和现有的重叠)

用动态规划实现以上函数