有一个输入的字符串，和一组substring,每一个substring 包括
1. start (开始位置）
2. end (结束位置）
3. score (得分）
substring有可能有overlap,并且score 和substring的位置，长度，内容完全没有关系。
问题是，返回所有的没有overlap的substrings, 使的他们的sum最大。
回复 10# wwwyhx
有人说用bucket sort, 根据int 32位分为32个bucket。然后在分组sort。
我来给几个微软的面试题：
1.二叉搜索树找给定两个节点的最近公共父节点
2.只知道一个指针指向某链表的一 ...
wwwyhx 发表于 2010-10-7 22:12 http://bbs.51testing.com/images/common/back.gif
知不知道如果指向的是最后一个节点怎么办？
看了挺惭愧的，这些题目很多都不懂
我晕，桶排序在这和hashtable没什么区别吧，不也要重新分配空间
最笨的方法就是穷举
聪明一点的办法就是贪婪算法吧，对每个字符串做权值计算wi = score/length,先选择权值最大的，然后按权值递减的往下选，重叠的跳过。NP复杂问题？？
哦，那个面试官给了个前提条件是节点非头尾.要不就无解了。
2010年27号晚,Google的2011年校园招聘宣讲会分别在北大和清华举行，其中北大本来是350
人的会场，结果去了大约600多人，爆满，那场面绝对是人山人海，彩旗飘飘。
经过了大约一个小时多的宣讲和问答，开始现场笔试环节，一共10个选择题和三个算法题，只有选
择题答对了8个以上的人才有机会让面试官看你后面的算法题。然后第2天下午会通知笔
试通过的人进行面试，Google的效率就像其搜索引擎一样迅速，效率可见一斑。
其中前10个选择题中有一个特别雷人的，题如下：
现在北京有一套房子，价格200万，假设房价每年上涨10%，一个软件工程师每年固定能
赚40万。如果他想买这套房子，不贷款，不涨工资，没有其他收入，每年不吃不喝不消
费，那么他需要几年才能攒够钱买这套房子？
A, 7年
B, 8年
C, 9年
D, 10年
E, 永远买不起
回复 26# wwwyhx
brute force不让用，
greedy, 考官明确说了不work。权值最大的未必会在结果列表里吧？
比如 1-10 10
10-11 4
11-20 10
应该返回1-10, 11-20 sum=20
按权值的话是10-11 4最大
回复 3# cleverman
将数值考虑成2进制！
回复 28# 欺负人
应该要10年的时间，相当于花了400W买了这套房子
2010年27号晚,Google的2011年校园招聘宣讲会分别在北大和清华举行，其中北大本来是350
人的会场，结果去了 ...
欺负人 发表于 2010-10-9 21:17 http://bbs.51testing.com/images/common/back.gif
40 * n = 200 * (1+10%)的n次方
求n,无解. 所以是永远买不起
回复欺负人
应该要10年的时间，相当于花了400W买了这套房子
goopy 发表于 2010-10-9 23:37 http://bbs.51testing.com/images/common/back.gif
10年之后这个房子涨到了518.74849202万！
楼主几道题没给标准答案啊
回复 34# wwwyhx
很多题是没有标准答案的，或者标准答案是错的。变string的那道，是DP题，这个答案我知道了。substring的，别人给我link了，我还没怎么看太明白，只是知道个大概的意思。感觉很多时候你去面试一个公司会碰到这么一道变态的题（至少对我来说做出来的可能性基本为零，如果不事先知道题）
可能只能靠多看题才能慢慢量变到质变。
这两道题都可以brute force。不过有些变态的面试官直接就断掉你的想法了。其实就算brute force代码也不是太容易。第一道题你想知道最优解可以search "edit distance"。第二道题要用到二分法
edit distance解法
动态规划经常被用来作为这个问题的解决手段之一。
整数 Levenshtein距离(字符串 str1, 字符串 str2)
//声明变量， d用于记录str1与str2的Levenshtein距离
int d
//初始化
for i from 0 to m
d := i
for j from 0 to n
d := j
//用动态规划方法计算Levenshtein距离
for i from 1 to m
for j from 1 to n
{
//计算替换操作的代价，如果两个字符相同，则替换操作代价为0，否则为1
if s= t then cost := 0
else cost := 1
//d的Levenshtein距离，可以有
d := minimum(
d + 1, //在str2上j位置删除字符（或者在str1上i-1位置插入字符）
d + 1, //在str2上j-1位置插入字符（或者在str1上i位置删除字符）
d + cost // 替换操作
)
}
(转贴)
思路：
开一个二维数组d来记录a0-ai与b0-bj之间的编辑距离，要递推时，需要考虑对其中一个字符串的删除操作、插入操作和替换操作分别花费的开销，从中找出一个最小的开销即为所求
具体算法：
首先给定第一行和第一列，然后，每个值d这样计算：d = min(d+1,d+1,d+(s1==s2?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,d;//分别存储原string与目标string
int dp;
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 = i;
dp = i;
}
for (i=1; i<=len1; i++)
for (j=1; j<=len2; j++)
{
if (s==d)
dp=dp;//不需操作
else
dp=Min(dp+1,Min(dp+1,dp+1));
}
cout<<dp<<endl;
}
int main(void)
{
//freopen("in.txt","r",stdin);
while (cin>>len1>>s)
{
cin>>len2>>d;
Dp();
}
return 0;
}
题目涉及的即广又精·····需要懂得东西还有很多，大公司就喜欢搞一些比较拐的题目。哎········
做不出来也不能完全决定什么啊。
:dizzy:各种豆要学啊 学嘛 先学嘛啊 ~~
回复 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)和现有的重叠)
用动态规划实现以上函数
