主题：【纪事】失败的苹果面试（上） -- landlord
家园 握手，就是这样想的，也是按这么解决的。
家园 这是属于npc的 但是如果假定所有的weight都是整数却可以多项式求解。这题类似于http://people.csail.mit.edu/bdean/6.046/dp/
中的第七题，即balanced partition。楼主如果对dynamic programming不熟的话，可以看看这十多个例题。搞定之后相信你对基本的dynamic programming问题都可以搞定。
家园 dynamic programming This is a typical dynamic programming question.
The key is to avoid redundant work by reusing partial results. You can find lots of tutorials and examples on the web.
本帖一共被 1 帖 引用 (帖内工具实现)家园 去网上找个能生成组合或叫子集的算法 你这个问题其实是这样，对一个n个数的集合，求他从C(1,n)到C(n,n)的所有组合，或者说是不包括空集的所有子集，一共是2的n次方减1个。
比如三个数的集合{a,b,c},他的所有组合或者所有子集就是{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}。
然后再验证这些子集的和是否等于N，也就是
a=N?
b=N?
c=N?
a+b=N?
b+c=N?
a+c=N?
a+b+c=N?
只要能生成所有子集，求和验证很简单吧。
有些语言可能本身带的函数库就有这个功能，像C++的STL？自己写一个，我想了想好像稍微有一点麻烦，我的手也比较生了，网上找这么一个算法很容易。
家园 给个思路。 首先对n集合排序（a1,a2,a3,..an）。
考虑所有比N小的数。
用N减去对于n集合中最大的数(an)，如果差为0，递归/循环结束。
如果差不为0，那么使用递归，对N-an求解。
家园 也说说我在微软的一个面试 前两年在微软有过一次面试，曾被问过这么一个问题：
用算法模拟一个N层嵌套的循环，每层循环次数为M。
这个算法用递归的方式很容易，我当时就给出了。但面试人接着要求用非递归方式再写一个。结果我试了几次都没成。
回到旅馆后总觉得不甘心，静下心再仔细想了大约十分钟，结果就出来了。当时面试时我其实是有时间的，每个面试人出题后都给半小时的时间做题。但我发觉我不能在被人注视着的场合下进行深度的思考，当时脑子迟钝得一塌糊涂，顶多有平时的20%。
因此，尽管微软和孤狗都允许被面试者一年后再申请，我还是决定和它们彻底拜拜了，实在不想再受那份煎熬。一天被六七个人轮番面试，到最后脑子真的都不转了。
家园 用栈不就可以了吗 非递归用栈模拟，算法书里有例子啊，最典型的就是inorder traversal。
家园 【纪事】失败的苹果面试（下） 有上有中当然得有下，这不自找么，以后干脆用一二三好了，教训啊。。。
++++++++自吹自擂的下，不喜勿入++++++++
面试已经失败了，但还有一些问题需要思考。比如说，如果苹果要了我，我能不能胜任那个职位呢？还有，我是不是一个好员工呢？
对第一个问题，我的答案是肯定的。对第二个，那就得先谈谈好员工的标准问题了。
如果以工作是否努力作为标准，那我绝对称不上一个好员工，别说“好”了，就连合格都称不上。
看到有些河友列的其他标准：“做的好的员工，一天没上班都会有人问。”---这个我更不成了；我经常连续几天，甚至几个礼拜嘛活儿不干，专心上网看小说。
还有的河友说是好员工有绝活，让公司离了就活不了的那种。这个和我的想法正好相反，我自己有个莫名其妙的工作目标，那就是一旦离职，对公司的影响（impact）争取做到最小。为了达到这个目标，我做出的测试软件都精益求精，目标是易操作、皮实无虫；而程序原码要求横平竖直，易懂易改。我的工作座右铭就是：“Quality is not an art, it is a habit.－－追求品质不应成为艺术，而应成为习惯。”
我认为的好员工标准就是：他对公司的贡献应该远远大于公司对他的付出。当然，这个贡献值的测量不太好办。对于一个自动测试工程师而言，在不降低测试效果的前提下，能为公司省下多少工时，就是衡量我对公司的贡献有多大。如果用这个标准，不谦虚的说，我就算不是“极品”，至少也能算是“精品”了。某位公司大头对我说过：“如果按照你替公司省的工时给你钱，你就发财了。”我深以为然。
我觉着我最强的能力在于归纳，既找出事物的共通性。
对于一个全新的测试，如果平均设计时间需要100小时，我可能会需要80～100小时；
第二个类似的测试，估计平均需要80～90小时，我是70～90；
第三个，平均70～90，我还是70～90。
一般来说，第二个就可以开始归纳了，而经过第三个，归纳完成度往往能达到80%以上。
以后呢，一般人大概能做到30～50%就是极限了，我能做到小于10%、5%，甚至更小。举两个例子。C公司买了个新公司，把我招回去更新一个我以前写的程序，把新生产线整合进去。工时给了我80小时，实际呢？我用了不到两小时！我在P公司写的对手机塔站的测试系统，就是测那些GSM、EVDO、CDMA、 W-CDMA等protocol，加一个新频段（band）公司问我要几周，我当场做好，不到5分钟！
正因为如此，我在公司只要一呆久了，就非常非常非常闲。。。
做多了自动测试，发现行业之间的区别也不大。不过就是拿个电脑控制一个或多个仪器、摄像头、机械手之流的测东西。步骤也无非是：1.初始化，既准备测试；2.开始测，采集数据；3.分析数据；4.展示结果（存数据、生成报告、画图、报警。。。）。不管是测芯片还是薯片，都这么回事儿。可大多数招聘的不这么想，他们会说：“无行业经验者，暂不予考虑。”（参见《风清扬故事》面试一）
再说测试仪器，我用过的就算没上百，几十种还是有的。用多了也熟了，顺便给个仪器，简单的一俩小时，复杂的一两天，极端的也就一周吧，都能给您搞出来（比如您手动整一次，我记着，立马给您自动化了）。编程语言呢？好家伙，我刚才一算，大大小小的用过10种以上了。其实也不用多，学个3、4种，你就明白了：“语言虽多，但算法数据结构没啥变化，不熟悉的语言，查查帮助文档，也能很快上手”。学多了也有害处，比如现在你让我写个C的For Loop，我一准儿出syntax error。
我这儿是给归纳了，招聘的照例不理。我经常被问到“懂这个仪器么”，“这个语言的这个函数名是什么”，每次我都郁闷的一塌糊涂。（参见《风清扬故事》面试二）
这还没完，不少面试的还想找个全才，为此我曾经被要求分析电路图，讲解傅立叶变换，背诵一些最新潮流的名词解释。。。（参见《风清扬故事》面试三）
我觉着自己已经差不多到“无招胜有招”的地步了，可我不是令狐冲或张无忌，苹果的大牛们更不是风清扬或张三丰，所以，我再一次的，败了。
唉，知音少啊，弦断了N次了，有谁TMD听啊？擦一擦嘴唇，看着天上的白云，悠悠的说：俺吐的不是血，是寂寞～～～
