w****x
发帖数: 2483 | 1 算法导论上的一道, 觉得蛮好的...
/*
Consider a sorting problem in which the numbers are not known exactly.
Instead, for each number, we know an interval on the real line to which it
belongs.
That is, we are given n closed intervals of the form [ai, bi], where ai ≤
bi.
The goal is to fuzzy-sort these intervals, i.e., produce a permutation 〈i1,
i2,..., in〉
of the intervals such that there exist , satisfying c1 ≤ c2 ≤ ··· ≤ cn.
Design an algorithm for fuzzy-sorting n intervals.
Your algorithm should have the gen... 阅读全帖 |
|
p*****2
发帖数: 21240 | 2
不要谦虚了。我觉得你做到你这一步，已经不是时间的问题了，完全是实力的体现。追
求精益求精的精神也十分罕见。
你说的面试20分钟写好bug free的code一般是做过这题，或者做过类似的题。这也是为
什么要搞题海战术了。如果一道比较难的新题，除了那些ACMer，一般可能都不会做的
很顺利。能把code写完整，没有什么bug就已经很不错了。 |
|
j*****I
发帖数: 2626 | 3 前几天有人问过career cup 150的一道题，跟这个很像啊。 |
|
s*******r
发帖数: 2697 | 4 我解了一下 这是一道多解题，一共有8组解
这个数满足形式yz (其中y是17位整数，x是个位数)
该数只要满足 y=5263157894736842*x即可
比如x=2时，y=10526315789473684，这个多位数的解是 105263157894736842
同理，x=3,4,5,6,7,8,9 都有对应解 |
|
d****r
发帖数: 80 | 5 一道面试题：
给定一个整数数组。怎样能将其分为三组（不要求个数相等），使每组值的总和相等。
不能分的时候返回空值。能分的时候给出一个解就行。
我只能想到三进制，有没有更优化的方法？ |
|
d*k
发帖数: 207 | 6 MTV的onsite，总体很简单，悲剧原因有2：一是最后一面（第五个）的时候已经太累了
，一个老美问了个设计题，其实很简单，但当时又渴又饿又累，大脑已经不转了，估计
老美给了个strong reject。另一个是一个烙印的一道题：
输入是一个双向链表，链表的元素是一个整数，输出这些整数所构成的区间。例如输入是
5 10 1 6 2 4 11 7 3
输出是
1-6
7
10-11
我只想到排序后扫描的办法，不知道怎么利用“双向链表”这个条件。烙印后来试图给
提示，但我没明白他的意思。欢迎大家讨论。
经验教训：累了千万说话，硬撑悲剧后没人可怜你，最后一面的时候哪怕给我一杯水或
者让我出去溜达十分钟呼吸下新鲜空气，结果可能就不一样了。在那个不通风的小屋子
里连着好几个小时真心受不了。其实题目算不上难，我前两面都很好，只好是两个hire
。后面累的和sb一样，结果悲剧了。
祝大家好运。 |
|
m******s
发帖数: 165 | 7 为啥不是1-7 10-11。。。
其实休息这个事儿也要分情况的。。。貌似G家休息的时间是算在你面试时间里的，我
面的时候不知道这点轮轮休息，结果5轮只coding了4道题（除了discussion以外一轮一
道）。不过运气比较好面的都是非主流难题（最后留下的时间都是连一道水题都来不及
的）所以最后没有悲剧。。。
入是 |
|
s*****1
发帖数: 134 | 8 title公司少了两个字母，自己猜~
onsite, 太郁闷了，总共三轮面试，两轮烙印，没有coding，就是关于C++/Java等犄角
旮旯的问题，感觉就是要fail 我。现有一道我实在做不出，就猜了，大家看看吧：
C++的。假设父类有一个method叫foo（没有virtual）,子类有一个method，override了
那个foo. 然后子类指针（注意是子类指针）,指向父类空间，然后call 那个foo,调用
的是父类还是子类的foo?
我的回答是子类指针到父类需要cast的，而且也没一定可以行啊。他说假设可以，
然后我就猜了个子类的，其实我也不知道，回来一想可能是父类的，因为cast成功了。
然后他们看到我简历上写着C#，就问了个C#的术语，神马是Box 和 UnBox. 晕~
供参考，就当积攒RP吧~ |
|
c********t
发帖数: 5706 | 9 是Text Justification吗？一道我做吐血的题
word. |
|
c***w
发帖数: 134 | 10 请问一道题，我的程序就是不能全过large test case。
代码如下：
public class Solution {
public boolean isPalindrome(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if (s == null) {
return false;
}
if (s.length() == 0) {
return true;
}
s = s.toLowerCase();
int start = 0;
int end = s.length() - 1;
while (start <= end) {
char first = s.c... 阅读全帖 |
|
m**********w
发帖数: 60 | 11 来自主题: JobHunting版 - 请教一道题 小弟请教一道电面题：
给一个整数数组， 找到其中包含最多连续数的子集，
比如给：15, 7, 12, 6, 14, 13, 9, 11
则返回: 5:[11, 12, 13, 14, 15]
最简单的方法是sort然后scan一遍，但是要o(nlgn). 有什么O(n)的方法吗？ |
|
h**6
发帖数: 4160 | 12 来自主题: JobHunting版 - 请教一道题 想起来前几年一道竞赛题，求最短连续数串的最长长度。
那题跟打麻将差不多，有时候需要牺牲较长数串，帮助较短数串延伸长度。 |
|
l*********8
发帖数: 4642 | 13 如果必须要swap一次，而且swap的两个values不同的话， 还是挺容易写错的一道题目
。 |
|
a*s
发帖数: 425 | 14 来自主题: JobHunting版 - 请教一道题 请教一道题
和hanoi tower有点像，不过有点不一样
有N个stack, 每个stack都有几个数字，
每次，可以从其中的一个stack里取出一个或者几个数，然后放到另外一个stack里，
比如
stack_1里，有数字 4,3,6,2
stack_2里,有5，7,8
那么一次操作，可以从stack_1里，取6,2，然后放入stack_2,
那么，
stack_1里就成了4，3，
stack_2里变成了5,7，8,6,2
或者，可以从stack_1里，去3,6,2 放入 stack_2
那么，
stack_1里就变成了4，
stack_2里就变成了5,7,8,3,6,2
现在的问题是，给定一个初始的状态，一个最终的状态，通过上面的移数规则，找出最
少的移数步骤，
一个简单的例子，
初始状态：
stack_1:3,1,4
stack_2:2,5,
stack_3:(empty)
最终状态：
stack_1:(empty)
stack_2:（empty)
stack_3：1,2,3,4,5
那么最少的移动步骤是5步
1:move 5 from stack_2 to stack_1
2... 阅读全帖 |
|
d**********x
发帖数: 4083 | 15 题目叙述太模糊了。。。
如果是只有inverted index，那貌似就完全是另外一道题了。。 |
|
c*****g
发帖数: 33 | 16 网上看到一道题 求O(n)的解法. n是document中的word数
You have a dictionary, D, that stores the positions of words in a document
by mapping words (strings) to positions in the document (arrays of ints.)
You also have a list of words, L. Your job is to find the shortest sequence
of words in the document that contains all the words in L.
E.g., if the document is "a b a c d x b a", then
D["a"] = [0 2 7]
D["b"] = [1 6]
...
If we are given that L=["a", "c", "x"]
Then we should return the start and end point of the sho... 阅读全帖 |
|
g********o
发帖数: 30 | 17 问大家一道题，CISCO的。说是要实现一个myMalloc（），每次分配固定的size。固定
的size做起来应该简单不少。解法应该是用两个list，一个记录用过的，一个记录free
的，如果free的有，就把free的头结点去掉，加到used list的头部。假设可以用
malloc一次分配一个MAX_SIZE的大block，如何实现myMalloc和myFree？
这方法是我在事后想到的，不过我在如何初始化这个free list的时候卡住了。请问记
录free list如何初始化，是用n个结点的data来记录每一块内存的位置吗？ |
|
f*********m
发帖数: 726 | 18 如何做？
大牛贴过了这题，我怕被大家的讨论淹没了，单独把他列出来。这题好像是
Introduction to algorithm的一道课后题。
(2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
，求这张纸所能剪出的最大值。 |
|
w*********m
发帖数: 4740 | 19 靠，这是我面试别人的一道题的2D version。
我的题是，有一句话，和一个词典（记录着每个词的权重，假设每个可能的词都有），
如何把这句话分成词，让最后之和最大。没一个人能答出来。因为我面的都是烙印 |
|
f*********m
发帖数: 726 | 20 如何做？
大牛贴过了这题，我怕被大家的讨论淹没了，单独把他列出来。这题好像是
Introduction to algorithm的一道课后题。
(2)给一张L*W的纸，给一堆 l(i)* w(i)的模板，每个size的模板有各自的price p(i)
，求这张纸所能剪出的最大值。 |
|
w*********m
发帖数: 4740 | 21 靠，这是我面试别人的一道题的2D version。
我的题是，有一句话，和一个词典（记录着每个词的权重，假设每个可能的词都有），
如何把这句话分成词，让最后之和最大。没一个人能答出来。因为我面的都是烙印 |
|
a******e
发帖数: 124 | 22 题目见图片，是一道面试题目，不知道byte是怎么操作的，谢谢！ |
|
f*********d
发帖数: 140 | 23 来自主题: JobHunting版 - 问一道题~ 考古到了一道老题~ 不会做~
给定一个数字数组，其中每个元素是从末端数小于原数组中该元素的个数。
求原数组。原数组中元素是从1到n。
Example:
原数组:4,1,3,2
Count array:3,0,1,0 |
|
u*****o
发帖数: 1224 | 24 LZ，你这个问一道题系列一共多少题啊。。。现在已经出了8了。。 |
|
s***e
发帖数: 403 | 25 别搞笑了
132道题目，一道题目就算10分钟搞定，那也要22个小时。
不过那种明显知道思路的题目跳过去的话也许还可以。 |
|
H*****l
发帖数: 1257 | 26 我觉得吧，练习20遍之后，肯定可以熟悉到看到题目直接敲代码3-5分钟一道题；一整
天从早弄到晚上的话，还真的可以搞的定。。。 |
|
d****n
发帖数: 233 | 27 link里的跟这题不是一道题。 这是最大黑边矩形问题。 |
|
s*w
发帖数: 729 | 28 要有人觉得有所帮助，给发个包子
【 以下文字转载自 Programming 讨论区 】
发信人: saw (句子熊), 信区: Programming
标 题: Re: 一道count frequency of all words的面试题 (转载)
发信站: BBS 未名空间站 (Mon Sep 23 00:28:12 2013, 美东)
又琢磨了两天，看了不少相关东西，终于搞定了，觉得自己对这个多线程的理解加强了
很多。思考比单纯的看人说原理更刻骨铭心。
这个问题我设计的用一个 producer 多个 consumer 的架构，上个版本的是两头用
condition_variable, 一个通知 producer 有空间了开始干活生产，另一个通知
consumer 有库存了开始消费。参见上篇里面的 wait 和 notify_all,notify_one 语
句。 这个思路对于单 producer 单 consumer 没问题，可是不适用于 多 consumer.
因为所有的 consumer 可能同时睡觉（没空存），同时醒来（有库存）,结果只有一个
能抢占mutex(拿到库存)，... 阅读全帖 |
|
|
u*****o
发帖数: 1224 | 30 请教大家最近碰到的一道题，两个大数，存在string里，return their sum as
another string.
我当时先把两个string reverse，12345--》 54321； 6789=>9876
然后把短的那个补足0，9876=》98760
然后54321和98760相加，一个个存在string里，最后再reverse result.
面试官说不efficient，让我另外想，我又说了个用两个stack分别装string里的数，
然后一个个pop出来，pop的时候相加，按顺序存到最后的string里。
我两个solution都写了，他还是不满意。请教大家这题还有什么更有效的办法吗？
大数相加不是leetcode的题吧？我不记得哪里做过，如果在cc150里，也请大家告诉我
一声，我没怎么翻过那本书。
谢谢了先！ |
|
z*****4
发帖数: 12 | 31 这题是电面的其中一道。题目不难，不需要写代码，只是从来没见过这么问的，一上来
有点晕，搞了挺长时间才答出来。
什么样的排序算法时间复杂度最差。先说的冒泡排序，O(n^2)。再次的想了一会。发现
通过决策树的方式可以推出来最坏情况是n!。对方问怎么排序才能达到这么次的情况。
想了半天想不出来，后来终于在一再提示下打出来了。就是列举所有可能的情况，知道
其中的一种是排序好的……
时候想想其实也不难，不知是不是刷题脑子刷木了，稍微绕点小弯就想不出来了。 |
|
n****o
发帖数: 239 | 32 【 以下文字转载自 Database 讨论区 】
发信人: niudao (牛鼻子老道), 信区: Database
标 题: 问一道Facebook面试题目：
发信站: BBS 未名空间站 (Sat Dec 7 18:22:08 2013, 美东)
一点头绪没有，大家有没有什么想法。。
"How would add new Facebook members to the database of members, and code
their relationships to others in the database?" |
|
l******6
发帖数: 340 | 33 问一道题～
2D knapsack
class rect{
public:
int width;
int height;
int area;
};
input: vector source , int canvasWidth , int canvasHeight
no overlap allowed , no rotate allowed, each rect int source and be used as
many times as
possible (area = width * height , setting area as another val will be a
similar problem)
compute the max coverage of canvas using the rects int the source
a dp solution
maxCover[row][col] = max (maxCover[subRow][col] + maxCover... 阅读全帖 |
|
f******s
发帖数: 25 | 34 我也遇到这道题了 高频题啊
就是输出non-decreasing的序列来避免重复。
还有一道设计题
点一个amazon.com上的一个link, 弹出一个网页显示商品的信息， 用户的信息，
review的信息。
问怎么设计这样一个系统 |
|
|
|
c******0
发帖数: 260 | 37 这题是之前版上的面经，其实也是他家的codesprint 的一道题。
原题见：
http://get-that-job-at-google.blogspot.com/2013/02/rocketfuel-c
一个deque，但是只支持pushBack，pushFront，popBack， 没有popFront
给一个1-N的排列，问能否把1-N按照从小到大的顺序push到deque，pop的时机可以任选
，使得pop出的顺序刚好是给定的排列
比如： 给定 23145， 那么对12345对应的操作序列是pushBack，pushBack，popBack，
pushBack，popBack，popBack，pushBack，popBack，pushBack，popBack
要求如果可能，输出任意一个可能的操作序列，如果没有可能的操作序列，输出
impossible
下面是版上的一个大牛给出的答案，不过我太弱，完全无法理解大神的思路。。。求大
家提供点思路~~
//return operations, empty if impossible
vector getOps(str... 阅读全帖 |
|
h*****h
发帖数: 1392 | 38 我去Apple应聘，本身我就有相关经验，又做了充分的准备（甚至拿他们的产品自己做
了点测试），英语、表达什么的都没问题，一线经理的phone interview和一群工程师
的on-site interview都很顺利，连recruiter都夸我做得很成功。然后一道手续就是二
线经理跟我phone interview一下，按说就过关了，我的推荐人都说，这只不过是一个
手续而已，一般没大问题。
然而问题就在这儿。这人是个老印。电话里阴阳怪气的，给人感觉就是冷漠、阴、挑刺
，口吻好像他是大法官，你是囚犯在祈求他似的。放下电话我就感觉不对劲，我认识里
面人多就了解了一下，得知老印二线老板枪毙掉下边看好的candidates绝对是有的，而
且做的太明显了，就是让印度人过，卡住非印度人。而且据说再好的非印，这些二线老
板都能找到理由拒绝。赶上印度人，哪怕再不行，也是“他有潜力”；赶上老中，哪怕
再行，也是“人无完人，他哪儿哪儿不够格”。
果然，Apple拖了好几天，告诉我，我落选了。我从内部打听，就是出在高级经理那一
关上。我对recruiter说，你们公司这样不行，这是种族歧视，说出去是有大麻... 阅读全帖 |
|
h*****h
发帖数: 1392 | 39 本人Update：由于我对Apple recruiter强硬表态说：“我怀疑你们公司的招聘过程中
存在对非印度人的种族歧视”，对方比较惊慌。招人的部门、HR的老板等等都给惊动了
。最后HR的一位高级经理给我专门来了一个电话了解情况，态度很好。当然，大家要知
道，他所能做的无非是解释安抚否认。他不可能承认。他说“我在Apple做这个七年了
，这是第一次赶上有人做这种投诉。”我就不信这是真的，但是作为他，难道能说“我
在Apple做这个七年了，这是第185次收到类似投诉”？那就是惹祸上身了。他想套套我
，看我有没有真凭实据，我说我有内部的人，但我不能告诉你。肯定不是你知道的人。
他解释说，是上面三个老板有否决权，其中枪毙我机会的那个不是老印。这种话，你也
就听听而已，因为内部的事情，全凭他一张嘴。我不管你谁在黑暗的角落里让我白忙活
面试一场，我只知道后来最后一轮据说是“象征性的”电话面试是跟一个老印，而且那
老印态度冷淡。所以我认准了是这个老印。本来应该顺顺当当通过的，人家那么多人都
面试我通过了，你拦一道？就算你怎么说不是他，不是老印给我麻烦的，他电话里那种
高高在上好像掌握施舍大权、而... 阅读全帖 |
|
h*****h
发帖数: 1392 | 40 补充：那个HR的高级经理还说了一堆铺垫话，比如Apple会招很多很多人啊，岗位很多
啊，你始终有机会什么的。这种同样是人事人员的贯口活，不用太认真听。他们内部如
何你不知道，工作只有落到你手里才是真的。他们这些屁话都是糊弄善良的人的。你有
成千上万岗位，没给我就是没给我，装孙子就是装孙子，而且我已经不是第一次被
Apple这样在最后一关涮了。这件事让我觉得这帮人太流氓、太不要脸了。吃一堑长一
智的话，我就给那些应聘去Apple的人一点忠告：
一、心理准备：我前面说了，歧视存在，而且是以隐性的方式，所以要抱持一个平常心
，别太把Apple当回事。说白了，如果机会不是公平给你的，如果这里不确定因素太多
，这个机会就不值那么多，你得不到不说明你不行，别人得到不说明他们比你强。
二、On-site面试：就我跟Apple两次面试打交道的经验看，他们里面的人不一定很强，
至少没提过几个难倒我的问题，所以我才有顺利过关走到最后一步的经历。你准备面试
的时候，除了专业知识外，注意结合Apple的产品来做准备。强调你熟悉他们的产品，
也专门做过学习研究。好比你是做硬件的，你说“我拆开看过，你们的电路板如... 阅读全帖 |
|
h*****h
发帖数: 1392 | 41 我去Apple应聘，本身我就有相关经验，又做了充分的准备（甚至拿他们的产品自己做
了点测试），英语、表达什么的都没问题，一线经理的phone interview和一群工程师
的on-site interview都很顺利，连recruiter都夸我做得很成功。然后一道手续就是二
线经理跟我phone interview一下，按说就过关了，我的推荐人都说，这只不过是一个
手续而已，一般没大问题。
然而问题就在这儿。这人是个老印。电话里阴阳怪气的，给人感觉就是冷漠、阴、挑刺
，口吻好像他是大法官，你是囚犯在祈求他似的。放下电话我就感觉不对劲，我认识里
面人多就了解了一下，得知老印二线老板枪毙掉下边看好的candidates绝对是有的，而
且做的太明显了，就是让印度人过，卡住非印度人。而且据说再好的非印，这些二线老
板都能找到理由拒绝。赶上印度人，哪怕再不行，也是“他有潜力”；赶上老中，哪怕
再行，也是“人无完人，他哪儿哪儿不够格”。
果然，Apple拖了好几天，告诉我，我落选了。我从内部打听，就是出在高级经理那一
关上。我对recruiter说，你们公司这样不行，这是种族歧视，说出去是有大麻... 阅读全帖 |
|
h*****h
发帖数: 1392 | 42 本人Update：由于我对Apple recruiter强硬表态说：“我怀疑你们公司的招聘过程中
存在对非印度人的种族歧视”，对方比较惊慌。招人的部门、HR的老板等等都给惊动了
。最后HR的一位高级经理给我专门来了一个电话了解情况，态度很好。当然，大家要知
道，他所能做的无非是解释安抚否认。他不可能承认。他说“我在Apple做这个七年了
，这是第一次赶上有人做这种投诉。”我就不信这是真的，但是作为他，难道能说“我
在Apple做这个七年了，这是第185次收到类似投诉”？那就是惹祸上身了。他想套套我
，看我有没有真凭实据，我说我有内部的人，但我不能告诉你。肯定不是你知道的人。
他解释说，是上面三个老板有否决权，其中枪毙我机会的那个不是老印。这种话，你也
就听听而已，因为内部的事情，全凭他一张嘴。我不管你谁在黑暗的角落里让我白忙活
面试一场，我只知道后来最后一轮据说是“象征性的”电话面试是跟一个老印，而且那
老印态度冷淡。所以我认准了是这个老印。本来应该顺顺当当通过的，人家那么多人都
面试我通过了，你拦一道？就算你怎么说不是他，不是老印给我麻烦的，他电话里那种
高高在上好像掌握施舍大权、而... 阅读全帖 |
|
h*****h
发帖数: 1392 | 43 补充：那个HR的高级经理还说了一堆铺垫话，比如Apple会招很多很多人啊，岗位很多
啊，你始终有机会什么的。这种同样是人事人员的贯口活，不用太认真听。他们内部如
何你不知道，工作只有落到你手里才是真的。他们这些屁话都是糊弄善良的人的。你有
成千上万岗位，没给我就是没给我，装孙子就是装孙子，而且我已经不是第一次被
Apple这样在最后一关涮了。这件事让我觉得这帮人太流氓、太不要脸了。吃一堑长一
智的话，我就给那些应聘去Apple的人一点忠告：
一、心理准备：我前面说了，歧视存在，而且是以隐性的方式，所以要抱持一个平常心
，别太把Apple当回事。说白了，如果机会不是公平给你的，如果这里不确定因素太多
，这个机会就不值那么多，你得不到不说明你不行，别人得到不说明他们比你强。
二、On-site面试：就我跟Apple两次面试打交道的经验看，他们里面的人不一定很强，
至少没提过几个难倒我的问题，所以我才有顺利过关走到最后一步的经历。你准备面试
的时候，除了专业知识外，注意结合Apple的产品来做准备。强调你熟悉他们的产品，
也专门做过学习研究。好比你是做硬件的，你说“我拆开看过，你们的电路板如... 阅读全帖 |
|
|
s****e
发帖数: 1180 | 45 一道面试题，向本版求教一下。有一些 social data, data 是从 facebook, twitter
上找来的，是关于一些人有否喜欢一件产品，有这些人的 gender, age, country,而且
这些人都在 facebook, twitter 上表明他们喜欢这个产品了。 想根据这些数据，用一
些算法在数据上（或类似的东西），从而判别market 应该 target 哪个 group? group
是根据人的gender, age, country 分的，如 10-20, 20-40,40-60 age, sex, male
female, country usa, china, ...
向本版请教一下。多谢！：） |
|
m*****n
发帖数: 2152 | 46 假设a b c d e f 是password字符的位置，而 x y z 是返回字符的位置。
x 可能是{a,b,c,d}
y 可能是{b,c,d,e}
z 可能是{c,d,e,f}
所有的组合是C(6,3) = 20种。
每个字符pos出现的概率表如下：
x y z
a 10/20 0 0
b 6/20 4/20 0
c 3/20 6/20 1/20
d 1/20 6/20 3/20
e 0 4/20 6/20
f 0 0 10/20
所以在均匀完全随机的情况下，password每个位置出现的概率是50%。所以call 20次
function的，某一个位置完全不出现的概率是0.5^20 ~ 10^(-6)，几乎可以认为不可能。
建一个二维的histogram，x axis是char，y axis是char在password的bucket的
position。
... 阅读全帖 |
|
c********l
发帖数: 8138 | 47 【 以下文字转载自 Programming 讨论区 】
发信人: coupondeal (Coupon Deal), 信区: Programming
标 题: 求问一道动态规划的题目
发信站: BBS 未名空间站 (Mon Apr 28 13:16:18 2014, 美东)
Google code jam上的算法题：
我目前能想到的算法是O(k * 2^n * 2^n)
也就是说，求出所有组合在k=1, k=2, k=3....直到k=k时的最小正方形覆盖
但这个复杂度实在太大了，有没有更简便的算法？
Problem
You are given n points in the plane. You are asked to cover these points
with k squares.
The squares must all be the same size, and their edges must all be parallel
to the coordinate axes.
A point is covered by a square if it lies inside... 阅读全帖 |
|
l**********g
发帖数: 16 | 48 请教一道DP问题，大概是这样的：
有一个长为L的木料需要割开，切的位置在一个数组里A[0...N]，从一个地方切开的
cost是当前所切木料的长度。按不同的顺序切割，得到的total cost是不一样的，问怎
么切cost最
小。
我对题意的理解是，比如一个木料现在10米长，然后切的位置是2米处，4米处和7米处
（就是说arr A里A[0]是2，A[1]是4， A[2]是7）。那么比如先切2米，那么得到cost是
10（因为现在木料长度为10），然后切4米处，那么cost变成10 + 8(因为8是现在切的
时候木料的长度)。然后切7米处，cost变成10 + 8 + 6。那么这种切法总共的cost是24。
这题DP应该怎么写？递推关系是什么？谢谢！ |
|
c****f
发帖数: 28 | 49 请教一道设计题：facebook的查找好友功能, 还有假设在一个服务器高峰时间，来的查
询量很大，你怎么handle?
谢谢 |
|
c*******r
发帖数: 610 | 50 最近看到一道题，没什么特别好的思路，请教各位大神：
Given a string s, remove duplicate adjacent characters from s recursively.
For example:
Input: "abbac"
Output: "c", first remove adjacent duplicated 'b's, then remove adjacent
duplicated 'a'.
Input: "acbbcad"
Output" "d", first remove 'b', then remove 'c', then remove 'a'.
Input: "acbbcda"
Output: "ada"
Do it with one pass over the string.
Thx! |
|
