r****o
发帖数: 1950 | 1 DP问题可以用来解决背包问题，硬币问题这种题目。
但通常都只能返回一个最优的sum数，如果想打印出哪些物品或硬币构成这个最优解，
就得要用二维数组或多维数组来存储那些sub-problem的解。这样的话，DP的空间复杂
度岂不是很高。不知道还有没有其他办法可以打印出构成最优解的物品或硬币。请大侠
指教。 |
|
g****n
发帖数: 431 | 2 这个题不能用DP，因为不具备DP的性质。比如对于k长度的子集，最优解是ans(i, j, k
)，那么去掉
最优解中的一个元素后，剩下的k-1个元素并不是在(i,j)范围里子集长度为k-1的最优
解。虽然你可以
遍历去掉哪个元素，但只要不具备这个性质，用DP做就是错的。 |
|
t****a
发帖数: 1212 | 3 抛砖引玉：
DP, 复杂度O(n^3), n为第一个数组长度
1、设立表格Error: 2n x n，表格中每个单元(x, y)代表table1[1..y]与table2[1..x]
的比对最优解（误差平方和最小）.
2、最优解Error[2n, n] = Min (Error[2n-i, n-1] + (table1[n]-table2[2n]
)^2), in which 0 < i < n and i is int.
3. 记录最优解的路径
此解法可改进为O(n^2) |
|
d*******l
发帖数: 338 | 4 这题其实我觉得和很久之前讨论的那个给定a[i]，每个a[i]代表一个高度为a[i]的木板
，问最多能装多少水的题很像。思路就是先从a[0]开始找一个降序的序列作为start
point的candidates，很容易证明不在这个序列中的点不可能得到最优解：加入某个a[k
]不在这个序列中，那就存在a[i] <= a[k], i < k。假如存在j，使a[k] < a[j]，那必
然有a[i] < a[j]，而j-k < j-i，所以a[k]就不可能是最优解的起点。
于是我们只要尝试这个序列中的所有点c[i]，假设每个c[i]对应的最优解的end point
是d[i]，很容易看出d[i]是一个非降的序列，所以可以从数组c的末尾开始向前循环，j
初始值是n-1，对于每一个c[i]，j向前移动到合适的位置，根据d[i]的单调性，j是可
以不回退的，这样总共的复杂度就是O(n)。
惟一的concern是，如果是递减的序列，最大的j-i似乎是-1，如果这个也要考虑的话要
单独处理下，如果序列所有元素的相等，结果又没有定义。不过这些都是细节的问题了 |
|
p*****2
发帖数: 21240 | 5
这题是要返回需要几步，bfs可以更快得到最优解。第一个解一定是最优的。dfs需要遍
历所有的节点才可以得出最优解。 |
|
S**********r
发帖数: 284 | 6 来自主题: JobHunting版 - G 家面经 问题
一个 m x n 二维区域，每个点上有一定数量的钱，考虑路径 : 从坐下角
(m-1, 0)出发，终点是 右上角(0, n-1), 在每个点只能向右或者向上走，
现在有两个人，从起点出发，走到终点，问怎么样求出这两个人能拿到
的钱的和的最大值.
为了叙述方便，改成从左上（0,0） 走到 右下 (m-1, n-1)
分析
三维 DP ，有点烦琐，我也没有验证过，自己感觉是对。这个问题的重点就是，每走一
步都会破原来的状态。 通过分析，可以知道，最优解中，两个人走的线路，不可能有
任何的重合。 证明方法是，只要有重合，总能通过修改一条线路，去掉重合而达到更
优的解。 也就是说，要得到最优解的话，如果某个位置的金币被人拿走了，这个位
置，另一个人就不能再去走。 还可以观察到，在任何一层 i， 这两个人所处的位
置 j 和 k， j < k 总成立.
A 是 m x n 的matrix，假设所有数都非负数
C 是 m x m x n 的 3d matrix, C[i][j][k] 表... 阅读全帖 |
|
S**********r
发帖数: 284 | 7 来自主题: JobHunting版 - G 家面经 问题
一个 m x n 二维区域，每个点上有一定数量的钱，考虑路径 : 从坐下角
(m-1, 0)出发，终点是 右上角(0, n-1), 在每个点只能向右或者向上走，
现在有两个人，从起点出发，走到终点，问怎么样求出这两个人能拿到
的钱的和的最大值.
为了叙述方便，改成从左上（0,0） 走到 右下 (m-1, n-1)
分析
三维 DP ，有点烦琐，我也没有验证过，自己感觉是对。这个问题的重点就是，每走一
步都会破原来的状态。 通过分析，可以知道，最优解中，两个人走的线路，不可能有
任何的重合。 证明方法是，只要有重合，总能通过修改一条线路，去掉重合而达到更
优的解。 也就是说，要得到最优解的话，如果某个位置的金币被人拿走了，这个位
置，另一个人就不能再去走。 还可以观察到，在任何一层 i， 这两个人所处的位
置 j 和 k， j < k 总成立.
A 是 m x n 的matrix，假设所有数都非负数
C 是 m x m x n 的 3d matrix, C[i][j][k] 表... 阅读全帖 |
|
h*****a
发帖数: 1718 | 8 我个人意见，如果明明知道最优解还上来先给次优解甚至brute force的不优解是无谓
的浪费时间，甚至有可能有很大的负效果让对方觉得你不够smart。是不是直接上写bug
free的code就最好呢？当然不是，而是要注意和面试官的交流，把自己的思路清晰展
示出来。
如果同样在60分钟内，一个人能perfect解决3道面试题，另一个人只能解决一道，那我
想两个人的差别是明显的。
处. |
|
h*****a
发帖数: 1718 | 9 Well，certainly he is very successful already and he doesn't have to know DP
to get a job. 我只是想说，这道题至少DP是经典的solution之一，你最多可以说DP
实际上不见的最好。就算他不知道那个著名的blog，但要是问这道题却不知道DP的
solution只能说真的是很偶然。
以前就有人在BBS上问过，如果被面到一道题，你知道初级做法和高级做法，那是上来
先给初级的然后再渐进到高级呢，还是直接给最优解。我一直都觉得直接给最优解好，
因为这样可以多做一道题节省时间。但很偶然的情况下，如果对方不理解最优解就弄巧
成拙了。不过，从面试官角度来说，出一道题有责任把各种常见的solution了解清楚，
否则是多少有点失职了。 |
|
k*******r
发帖数: 355 | 10 shicong，你的nlogn解法好像不能保证最优解吧，因为你的算法是对每k个x坐标连续的
点，算出覆盖这k个点的矩形最小面积。
但既然你没有遍历所有可能的k个点，就不能保证你漏掉的那些矩形candidate不含更优
的解啊。 换句话说，最优解矩形含的那k个点，他们在x坐标未必连续啊 |
|
f******n
发帖数: 198 | 11 刷没刷过题很容易看出来。你要是觉得先写个非最优解可以帮助你写出最优解，你当然
可以这么做，但是一定要和面试官说清楚。你要是就想妆模作样写个非最优解让面试官
以为你没见过这题，那只会适得其反让面试官很不爽，本来想放水的也不放了。说到底
，想放你水怎么都可以放，不想放水怎么都可以让你死。 |
|
C*7
发帖数: 234 | 12 首先两个分离元素换到一起至少执行一次交换，该交换配成两对的情况一定是包含在最
优解的。唯一有更优解的情况可能是，当前交换只配成一对，而先进行其他交换可以使
当前交换配成两对。这种情况的模式为ab。。。cbca，如果用我的方法先配a对，变成
aa。。。cbcb，第二次交换可配成两对，依然是最优解。感觉要用到什么定律法则，暂
时说不上来，不是很严格的证明。当然也可能考虑不全，欢迎指正 |
|
l****u
发帖数: 1764 | 13 想到一个用dp的方法，如果slices数量比较小（小于30），可以用一个整形数组表示
sub problem，比如dp[111111111]表示完整pizza（9个slices）的最优解，dp[
111110001]表示第2个slice被拿掉的最优解，dp[100010001]表示第2个slice和第6个
slice被拿掉的最优解
数组下标是二进制表示，最多可以表示30个slice的问题
如果要超过30个（一个pizza切30块也差不多了吧？），那可能就得用string做下标，
存在hashmap里面了
base case 是只剩3个slice的时候(可以用位操作判断这个条件)，dp[0.a.b.c.0] =
max(dp[0.a.0],dp[0.b.0],dp[0.c.0]) |
|
l********r
发帖数: 221 | 14 同意面试中和面试官交流自己的思维和想法很好，其实就该这样。你见过刷过的题甚至
都背出来了当然做到bug free的几率大很多，可是并不能反应你真正的水平。
要我是面试官，我不是死板要求最优解。有自己见解能解释清楚为啥这么coding，有啥
算法用到哪种数据结构，更能面试者反映思维敏捷程度和编程算法功底。
但是， 面试是个双向过程。奈何 很多时候对没见过的题说了自己想法和思路，当时不
是时间或是空间最优解，可是为啥交流过程中人不care，care你要没有一点间歇流利写
出bug free的code, 还要他心里的那一种解，其他的他未必明白。遇到这种面试官自己
水平不咋样的也坑爹.
说穿了 面试就是运气很大成分，遇到你拿手的题还有好的nice面试官，offer成功在望
。就像尼玛不是搞图像的，被面试时非得要做某些几何画图题还从没见过的题，还要你
bug free最优做出来 可想而知offer 已经完蛋。 |
|
t******l
发帖数: 10908 | 15 优化算法的目的就是在给定资源条件下如何找到更优解。。。被一个 metric 给 DNF
不是事儿，关键是 weighted sum 更优化。。。
刚才市场部又跳进来说。。。“你们这帮学究我受不了了。。。神马狗屁更优解。。。
就是在给定资源条件下如何让客户开更大的支票。。。你你还有你。。。更优解能给你
们开支票么？人生最重要的是搞搞清楚是谁在开支票！！！”
：呵呵
：这个反抗，是指反抗所谓的pushy mama的强压 |
|
f**d
发帖数: 2494 | 16 不明白要干啥在实战的时候有优势啊。本来你想的好好的，对手下了一步你不知道要干
啥的棋，重新算一遍。下了几手，突然对手又下了一步没算过得，只好再算一遍。
当然两日制，时间充沛，下出最优解就更重要一些。但一日制，下出次优解，但对手没
算过得，不比最优解效果差。 |
|
s***y
发帖数: 357 | 17 我觉得现在这些很多人包括职业棋手都已经被alpha go 吓傻了，甚至到了已经不敢客
观评棋的地步。
首先 对任何棋类来说，最后都是比拼的是计算，围棋的状态数太多，所以不论是计算
机还是人类都是算不清的， 不存在alphago 都算清的这种说法，实际上将来真有什么
量子计算机吧围棋都算清了，那可能还可以说是颠覆性的 –现在的alpha go说穿了就
是一个解决围棋的较优解的 程序， 和人类的智能/逻辑没有什么关系。而人类和计算
机计算的关键就是 剪枝的过程， 人类是通过逻辑和经验 把选点减少到2~3种，而
alpha go可能能够剪枝到10 ~20种，然后凭借计算的优势来找到最优解。既然计算机计
算肯定是比人类强的，那么，最有“智能”的部分就是怎么样找这样的选点，以及如何
判断局势的问题。 如果它的１０～２０总能包括人类想到的２～３种，并且局势判断
差不多的话，那么人类理论上是必败的。
那么alpha go怎么的解决的呢－神经网络， 用人类自己下的棋去训练。说穿了就是一
个函数拟合的问题。这个好比就是计算机的图像识别，把输入输出拟合一下。这个过程
和人类智慧不是一回事。也就是说，对于棋... 阅读全帖 |
|
s***y
发帖数: 357 | 18 我觉得现在这些很多人包括职业棋手都已经被alpha go 吓傻了，甚至到了已经不敢客
观评棋的地步。
首先 对任何棋类来说，最后都是比拼的是计算，围棋的状态数太多，所以不论是计算
机还是人类都是算不清的， 不存在alphago 都算清的这种说法，实际上将来真有什么
量子计算机吧围棋都算清了，那可能还可以说是颠覆性的 –现在的alpha go说穿了就
是一个解决围棋的较优解的 程序， 和人类的智能/逻辑没有什么关系。而人类和计算
机计算的关键就是 剪枝的过程， 人类是通过逻辑和经验 把选点减少到2~3种，而
alpha go可能能够剪枝到10 ~20种，然后凭借计算的优势来找到最优解。既然计算机计
算肯定是比人类强的，那么，最有“智能”的部分就是怎么样找这样的选点，以及如何
判断局势的问题。 如果它的１０～２０总能包括人类想到的２～３种，并且局势判断
差不多的话，那么人类理论上是必败的。
那么alpha go怎么的解决的呢－神经网络， 用人类自己下的棋去训练。说穿了就是一
个函数拟合的问题。这个好比就是计算机的图像识别，把输入输出拟合一下。这个过程
和人类智慧不是一回事。也就是说，对于棋... 阅读全帖 |
|
k********k
发帖数: 5617 | 19 发信人: fromspace (), 信区: Piebridge
标 题: 【NYC】女- 征人结婚
发信站: BBS 未名空间站 (Thu May 11 22:56:01 2017, 美东)
★性别:女
★出生年份: 85年
★所在地(至少明确state): NYC
★职业情况(学生还是工作): 工作
★简单的物理参数(身高/体重): 165/匀称
☆单身，未婚
★联系方式(email/IM/站内): 站内
目前在纽约工作，东挑西捡蹉跎了很多时间。现在30出头了，想找人尽快安定下来。
在美国或者一起回中国都行。
为人善良，性格随和，各种菜式都还算精通。样貌中等偏上，眼缘应该是有的。
希望你也是以婚姻为目的交友，并且想要3个月以内闪婚，结束一个人单身的日子，有
人作伴。
如有意，请私信联系，谢谢。 谢谢大家。
===================================
《寻找“次优解”》第一版，作者：sabina7377 年龄：33
《寻找“次优解”》第二版，作者：jojoshan 年龄：34
《寻找“次优解”》第三版，作者：fromspace 年龄：... 阅读全帖 |
|
k********k
发帖数: 5617 | 20 发信人: fromspace (), 信区: Piebridge
标 题: 【NYC】女- 征人结婚
发信站: BBS 未名空间站 (Thu May 11 22:56:01 2017, 美东)
★性别:女
★出生年份: 85年
★所在地(至少明确state): NYC
★职业情况(学生还是工作): 工作
★简单的物理参数(身高/体重): 165/匀称
☆单身，未婚
★联系方式(email/IM/站内): 站内
目前在纽约工作，东挑西捡蹉跎了很多时间。
现在30出头了，想找人尽快安定下来。
在美国或者一起回中国都行。
为人善良，性格随和，各种菜式都还算精通。
样貌中等偏上，眼缘应该是有的。
希望你也是以婚姻为目的交友，
并且想要3个月以内闪婚，结束一个人单身的日子，
有人作伴。
如有意，请私信联系，谢谢。 谢谢大家。
===================================
《寻找“次优解”》第一版，作者：sabina7377 年龄：33
《寻找“次优解”》第二版，作者：jojoshan 年龄：34
《寻找“次优解”》第三版，作者：fromspace ... 阅读全帖 |
|
S********I
发帖数: 618 | 21 力学专家。江苏苏州人。1964年毕业于北京大学数学力学系，1980年获
丹麦技术大学固体力学博士学位。大连理工大学校长。从事工程力学、计算
力学和结构优化的研究。70年代参加研究结构分析的群论方法并成功地应用
于水塔支架分析，研究汽轮机基础的动力分析。对实心弹性薄板的研究表明，
为了得到全局最优解，必须扩大设计空间，包括由无限细的密肋加强的板设
计，这项工作被认为是近代布局优化的先驱。提出并实现了结构响应灵敏度
分析的半解析法，与丹麦学者共同研究了误差分析和提高精度的方法。指出
结构拓扑优化中奇异最优解的本质，并给出了可行区的正确形状，在此基础
上给出求解奇异最优解的拓扑优化问题算法。最近研究网格生成及在灾害载
荷下的基于可靠度的结构优化。
1995年当选为中国科学院院士。
（一）主要学历及工作经历
程耿东教授。男，1941年9月出生，江苏苏州人。毕业于北京大学
数学力学系。现任大连理工大学校长。
1958-1964北京大学数理力学系固体力学专业，本科
1964-1968 大连工学院数理力学系，研究生
1968-1969 黑龙江省３１８５农场，
1969-1973 沈阳八十八中 |
|
z****e
发帖数: 54598 | 22 并发上万，意味着你需要在上万个并发中找出最优解
这个如果不考虑，你直接给一个最差解，全部拒掉所有票不就行了？
反正最优实现不了，做个最差的跟次优解也没啥本质上的区别嘛
现在看懂了为啥要求你实现并发的原因了？
拜托，一开始打的小算盘谁看不出来 |
|
z****e
发帖数: 54598 | 23
10
显然还是有问题
举个最简单例子
两个座位
三个航段123
四个人抢
其中一个人要航段123
另外一个人要12
还有人要3
最后一个要23
假设这四个人同时发送请求过来
那么期待组合是
123，12，3
但是如果票发送到的顺序是
123，23，12，3
那么就只会通知前两个人，你买到票了
剩下两个人会被拒掉
然后剩下123和23，两个人怎么搭配都无法实现最优解
航段1会有一个座位空出来
还是老问题，顺序如果一开始就决定了的话，这个最优解就是出不来
最优解是从pool中选组合，而不是固定顺序
丢给外围不外围都是一样的
强制顺序排队是一个死结，不打开这个，你就会有空位出现
至于具体什么座位号，那谁在乎？ |
|
x*****n
发帖数: 3422 | 24 补充一点，“能控制到最接近极限的”其实很难，不光是技术和反应，还有策略。而且
，我越来越觉得有不止一个最优解（也就是所谓的style）.
这么说吧，就算我们会克塞（好老土，呵呵）的时间停止特技，然后一直按pause键玩
慢动作，我们还是会输给职业车手，因为我们的很多细微之处的决断是不合理的。
"实际上不可能正好做到“最大静摩擦力”，所以比赛中会有少量漂移，"
不同意这个说法，很多情况有一点drift angle是最优解（不能称之为漂移），并非力求做到“最大静摩擦力”。
你用“静摩擦力 > 滑动摩擦力”来解释这个问题，过于简化了。因为：
maintain“最大静摩擦力”并无法直接推导到“最短时间通过赛道”。最极端的反例你我都举了，拉力赛。其他形式比赛最优解的drift angle(t)函数，也不恒为零。即使是轮胎接触面积极为变态的F1,同样drift angle(t) ！= 0, 当然drift angle本身很小，旁观很难注意到。
skip barber的说法是一般比赛，drift angle控制在5度以下。我觉得他的说法是经验之谈，不久未来的计算机模拟，应该就可以量化这个函数。 |
|
c****0
发帖数: 993 | 25 各个文明给的解并不同啊，中华文明的解是最优的，西方文明的解和阿拉伯/土耳其的
半斤八两所以斗了个你死我活难分胜负。现在边界条件重新稳定下来，中国解又要成为
最优解了，西方的免煮石油马上就要过时了吧 |
|
L**G
发帖数: 2602 | 26 我家里电脑上有一个围棋AI，自称可以达到业余五段（实际并没有）的棋力，我有时候
会和它下两盘，虽然大部分时候都轻松获胜，却也有时会在局部战斗中因为随手受到很
严厉的追究。这个时候的心情是很糟糕的。
在刚刚结束的一局里，开局李世石主动求变，走了一步在大局观训练题中通常会得到低
分的棋。但李世石棋风怪异，对他来说，这也不足为奇。随后AlphaGo立刻出现了有疑
问的一手，这个时候相信很多棋友的心情都和我一样呵呵了。虽然这步棋并非那种大是
大非的错误，但似乎显示出AlphaGo对棋型的判断力存在一定问题。几步之后李世石之
前的低分棋就显得生动起来了。如果这样下去，一定是李小胜的棋。因为围棋比赛你一
步我一步，棋型效率高的一方必然会取得胜利。但要命的是AI对于棋型的漠视或者说无
知也是它厉害的地方，就在几步之后，李世石一次看起来毫无问题的腾挪遭到了猛烈的
反击。从李世石赛后接受的采访看，他并没有意料到电脑会以这种方式来求战。这时候
一种熟悉的感觉袭来，我想起了家里那个愚蠢又有力的AI。
业棋手常说“气势的一手”，意为到了某些关头，即使你看不清楚局势的变化，也不得
不鼓起勇气和对方硬上。李世石当... 阅读全帖 |
|
|
g******d
发帖数: 511 | 28 我的惨痛教训是:
Interview exposed和careercup上面的每道题,要写N遍.不能只看N遍.简单道要想多想
加上限制条件.
现在的面试条件:一遍写出没有bug的时间最优解,然后再讨论空间最稳定解,加限制条件
最优解,thread-safe解,大数据量解,等等. |
|
Z*****Z
发帖数: 723 | 29 嗯，看看这样想行不行：
先扫一遍T，把所有字符出现的次数存到一个hashtable（记做ht）里。
然后再弄另外一个hashtable(ht2)用于计数。
接下来用两个指针head和tail同时扫描S，先寻找初始解，再寻找最优解。
（1）在寻找初始解阶段，不停地advance head，每遇到一个S中的T字符就把ht2的相应
count++，直到ht2中每个key的count都比ht中相应key大（至少不小）。
然后不停地advance tail，每遇到一个S中的T字符就把ht2的相应count--，直到ht2中某
一个key的值恰好等于ht中相应key的值。
这就是初始解，记录之。
（2）寻找最优解。这时tail指向的就是T中最靠前的字符，advance head寻找它，同时
更新ht2，逻辑同（1）。找到之后再更新tail，逻辑也同（1）
不知道说清楚了没有。。。 |
|
f*****d
发帖数: 2285 | 30 版上把L家的国人面试官黑的太狠。说说我1年半前L家的面试经历。
两次店面，第二次店面是个国人大哥，一开始闲聊了30分中喜欢什么project，后30分
钟做一个非常简单的题。依稀记得是实现memcopy，当时一直做leetcode，突然让写
memcopy的实现，一下子也没有思路。国人大哥基本一路提示，教我如何正确写代码
。。。 但是店面结束，心想一定挂了，结果第二天，recruiter发邮件说要onsite，心
里也是很感谢国人大哥的。
L家Onsite。面的infrastructure组，一共面了7轮(不算午饭)。从早上10点到晚上6点
半。。。为啥会是到6点半呢？因为最后一轮，实在太累了，好心的面试官给了1个半小
时的时间。。。。
说说On-Site的过程，
1面，和infrasture的director talk。基本属于闲聊，主要聊project，director会问
问project的细节。
2面，国人大哥+美国小哥，L家的面试都是两个人，一个人讲话，一个人做记录，这轮
是美国小哥讲话，国人大哥做笔记，美国小哥，第一题挺容易的，第二题作为第一题的
展开就难了，考得是data... 阅读全帖 |
|
M****z
发帖数: 1058 | 31 其实框架是帮助你理顺关系的，属于方法论一类
如果没有框架的指引，做这些事情就是松散的，不成系统的，不成合力的，也就是你投
入的资源获取的回报会大大减少
当你看清楚周围环境并且想清楚方向后，你做执行的时候就知道为什么这么做，那一步
棋如何走。三步棋单从每一步看，各有各的最优解，但合到一起，你会发现其实最优解
并不是追求每一步棋的最优，而是整体的最优。
如果要给你一个具体的建议，那就是第一步，定位，你产品的定位是什么，往大了说，
你品牌的定位是什么，这个定位如何能让你在竞争中不落于劣势。这个定位和你后面的
一切工作都相关，既是面对消费者的有力武器，也是搞定中间商的有力武器。常规
sales那一套渠道什么的，我就不扯了。
做大众消费品，定位是你的起点，越早做，越好 |
|
p**f
发帖数: 3549 | 32 芯片界没有阴谋 谈Intel酷睿融聚AMD的镭
回首这十年的PC芯片行业，SIS默默无闻，S3归于威盛终成中国兆芯的一部分，Matrox
和Imagination被外人融合已经没有了灵魂，老兵不断凋零。有很多好事者将这种演变
类比成汉三国诡谲争斗故事，仿佛残存的Intel、AMD、NVIDIA都是高度人格化的宫斗专
家。这种故事性的解读其实是比较无趣的。
处理器芯片行业是半导体行业的桂冠，这其中的此消彼长并无多少“人情”"阴谋"因素
存在。“我消灭你，与你何干”，“数字规律决定一切，算法技术扭转乾坤”，这才是
处理器行业发展的法则。
在处理器业界，公司利润来源于软硬生态，软硬生态依附于基础设计，技术设计用硬实
力说话。不管下场的选手如何折冲樽俎、纵横捭阖，都绕不过基础实力的博弈。就像最
近的Intel AMD 联合大戏，从根本上来说，是典型的阳谋，没有任何需要粉饰的东西。
我们今天在这里要来谈谈IntelAMD 在异构CPU方面的问题，并且简要回答如下：
问题一：CPUGPU异构融合的必要性有多大？
回答：对于游戏图形来说意义不大，对于AI、云计算上来说前景不明。
其二：CPUGPU异... 阅读全帖 |
|
s******s
发帖数: 13035 | 33 首先不是infinite的gamble，其次maximize expected profit的话显然就是最优解。
你说的，不过是降低输光的概率而已，当然这个条件下的最优解显然不是全局最优。
所以我说的，这个完全取决于你对最优的定义 |
|
f********t
发帖数: 6999 | 34 【 以下文字转载自 JobHunting 讨论区 】
发信人: mudhoof (正在长牙的羊), 信区: JobHunting
标 题: 这么热闹, 我也报Google offer
发信站: BBS 未名空间站 (Tue Feb 23 12:32:47 2010, 美东)
今天刚刚通知的, 特别感谢一起讨论的krone, geniusxsy, hnm, 特别是blaze教了我很
多, 还要特别感谢mitbbs59的总结帖
一起报offer, 好事成三, 大吉大利, 包子分光为止
贴下我的复习材料
题目大全:
http://www.spellscroll.com/viewquestions/?tag=algorithm
http://www.thecareerplus.com/?page=resources&cat=10
http://interviewcyclopedia.blogspot.com/
http://www.doctorinterview.com/A.html
http://toptechnotes.blogspot.com/search/label/algorith... 阅读全帖 |
|
r******7
发帖数: 58 | 35 我不牛。说说体会
1. 可微分convex函数总可以找到全局最优解。SDP的全局最优解不一定能找到。
2. SDP的关键是约束条件以可是任何函数。convex programming的objective function
and constraints都要是convex才行。
3. 能用convex programming解的问题都可以用SDP解。凡是convex programming能找到
的解一定不比SDP差。
一句话：尽量用convex programming。实在不行再用SDP。 |
|
O******2
发帖数: 2739 | 36 我们民主国家的优势，并不在于每一件事都能做到最优解，但是，制度优势保证我们不
会出现最差解。
你们专制国家也许短时间内连续最优解，但是一次最差解就万劫不复了。 |
|
x****r
发帖数: 99 | 37 同问 + 请问这个问题出处？
我的想法是，对当前最优解，组合的种类是唯一的，那如果为每一个最优解加一个已选
了哪几个的信息，那么以后的DP过程中如果这类已经选完了，那么就在DP判断的时候排除这一个解
例如: 如果有1， 5两种面值
DP[105] = Min (DP[100] + 1, DP[104] + 1)
however如果DP[100].Used = 5 * 20 但面值5的只有20张，那么就只能选DP[104] + 1了
不知道这样可不可行，会不会丢掉解 :P |
|
S**I
发帖数: 15689 | 38 ☆─────────────────────────────────────☆
fengzhongdi (fzd) 于 (Fri May 27 14:30:18 2011, 美东) 提到:
A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bian... 阅读全帖 |
|
c**********y
发帖数: 38 | 39 由于签了NDA，不方便直说是哪家，不过，公司名称来源于南美洲一片很出名的丛林，
在西雅图做网购业务，你懂得。
小弟EE的new grad弱屌丝，没有电面就让去onsite了，很奇怪，面的是market 组，周
一面的，面经呈上：
1.老印manager，口水题，是否是相同的树，然后，设计一个通讯录
2.隔壁mobile组的老印manager，上来把我的简历里面每个project都问了一遍，然后提
了一些sql的问题，最后没时间问coding，很奇怪，感觉sql的问题答得他不是很满意，
幸好他应该不是做决定那个人，做决定的应该是前面那个老印
3.老美，上来先客套一下然后问coding，一个string，里面写了一些页码范围然后打印
机要打这些范围的页，用逗号分割，然后输出最后要打哪些页，比如“1，2-5，3-4”
，最后应该输出1，2，3，4，5，思路很简单，把string split，然后逐个sub扫描，结
果里面存在的就啥也不做，没有的就加进去，中间要考虑很多invalid的情况，比如多
个字母或者多个符号，由于上一轮的老印占用太多时间，这轮就只问了这一个问题。
4.老美小胖，小胖问... 阅读全帖 |
|
c**********y
发帖数: 38 | 40 由于签了NDA，不方便直说是哪家，不过，公司名称来源于南美洲一片很出名的丛林，
在西雅图做网购业务，你懂得。
小弟EE的new grad弱屌丝，没有电面就让去onsite了，很奇怪，面的是market 组，周
一面的，面经呈上：
1.老印manager，口水题，是否是相同的树，然后，设计一个通讯录
2.隔壁mobile组的老印manager，上来把我的简历里面每个project都问了一遍，然后提
了一些sql的问题，最后没时间问coding，很奇怪，感觉sql的问题答得他不是很满意，
幸好他应该不是做决定那个人，做决定的应该是前面那个老印
3.老美，上来先客套一下然后问coding，一个string，里面写了一些页码范围然后打印
机要打这些范围的页，用逗号分割，然后输出最后要打哪些页，比如“1，2-5，3-4”
，最后应该输出1，2，3，4，5，思路很简单，把string split，然后逐个sub扫描，结
果里面存在的就啥也不做，没有的就加进去，中间要考虑很多invalid的情况，比如多
个字母或者多个符号，由于上一轮的老印占用太多时间，这轮就只问了这一个问题。
4.老美小胖，小胖问... 阅读全帖 |
|
发帖数: 1 | 41 题目要求最优解……
：那是求最优解。这个题目求个可行解就行了，可以relax成linear programming，然后
：再round up/down，应该可以比较快解出来（polynomial） |
|
e*******s
发帖数: 1979 | 42 LC 365 Water and Jug Problem
最优解是用最大公约数
1. 如果用最优解, 即使知道答案这种解, 全部证明依然写3页, 之前没有遇到过几乎不
可能面试的时候现场想出来的. (想到最大公约数容易, 但是要证明互质容量的桶一定
能reach到范围[0,sum]内所有的答案, 不容易, 第一次做的时候想到了这个猜想, 但是
没有信心证明下去)
2. 用DP
3. 直接和面试官说我以前见过这个题, 这个题的最有解是balabala
那种方法最好? |
|
w***g
发帖数: 5958 | 43 人无完人，解无完解。
问题规模越大，能出瑕疵的地方就越多。都是次优解，瑕疵各不一样，
要比出个最优解来就难。
数学原理叫curse of dimensionality。 |
|
d******5
发帖数: 355 | 44 我想卖的物品:
$15 AT&T iPhone官方解锁服务, iPhone 2, 3g, 3gs, 4, 4s, iPhone 5。在合
约内，
或者跳出合约都可以解。简单的说，只要是AT&T的iphone我们就能解。量大有优
惠。AT
&T内部专业人士解锁。我们提供直接解锁服务。任何人都欢迎使用我们的服务。
我们是
direct source。量大的话我们match板上任何价格。对于iPhone 5合约机，通过
我们的
解锁就可以当裸机出售，无需激活。
可接受价格(必须明码标价！):
$15一台。
可以解iphone 2, 3g, 3gs, iphone4, iphone 4s, iphone 5任何版本的ios
firmware
。永久解锁，解锁成功后以后升级无忧。解锁失败全额无条件退款。可以批量解
锁，一
天解500台也没问题。
请按以下格式发信到d******[email protected]。量大的请附上excel。
Subject:[解锁] iphone（） - Your id
BBSID: xxxxx，
IMEI: yyyyyyyyyyyyyyy
总金额: (... 阅读全帖 |
|
d******5
发帖数: 355 | 45 我想卖的物品:
$15 AT&T iPhone官方解锁服务, iPhone 2, 3g, 3gs, 4, 4s, iPhone 5。在合
约内，
或者跳出合约都可以解。简单的说，只要是AT&T的iphone我们就能解。量大有优
惠。AT
&T内部专业人士解锁。我们提供直接解锁服务。任何人都欢迎使用我们的服务。
我们是
direct source。量大的话我们match板上任何价格。对于iPhone 5合约机，通过
我们的
解锁就可以当裸机出售，无需激活。
可接受价格(必须明码标价！):
$15一台。
可以解iphone 2, 3g, 3gs, iphone4, iphone 4s, iphone 5任何版本的ios
firmware
。永久解锁，解锁成功后以后升级无忧。解锁失败全额无条件退款。可以批量解
锁，一
天解500台也没问题。
请按以下格式发信到d******[email protected]。量大的请附上excel。
Subject:[解锁] iphone（） - Your id
BBSID: xxxxx，
IMEI: yyyyyyyyyyyyyyy
总金额: (... 阅读全帖 |
|
m***y
发帖数: 14763 | 46 都有练兵这个过程啊，其实练的不光是兵，也是将自己啊。反例就是宋，大家都知道它
一个问题是，兵不知将，将不知兵。穿越小说里面，“窃明”系的都是学的近代操典，
就是军队标准化，这样兵将之间对对方的预期都有一个底线，有common sense。不然，
就象赵括一样，嗯，最优解是这样的，你们当兵的就这么执行吧。知兵的就会把自己军
队的条件代入作为constraints，这样某个次优解就成了这些受限条件下的局部最优了。
回到孙庞那个例子，魏军是庞自己练出来的，所以他能自己带着。孙到了齐，身体不能
练兵了，所以只能给田忌出主意，最后的执行，还是得靠田忌操盘。
这也是，经常看军师出个上中下三策，头却只能用中策的原因。纸上谈兵的上策往往不
可行。 |
|
m***y
发帖数: 14763 | 47 都有练兵这个过程啊，其实练的不光是兵，也是将自己啊。反例就是宋，大家都知道它
一个问题是，兵不知将，将不知兵。穿越小说里面，“窃明”系的都是学的近代操典，
就是军队标准化，这样兵将之间对对方的预期都有一个底线，有common sense。不然，
就象赵括一样，嗯，最优解是这样的，你们当兵的就这么执行吧。知兵的就会把自己军
队的条件代入作为constraints，这样某个次优解就成了这些受限条件下的局部最优了。
回到孙庞那个例子，魏军是庞自己练出来的，所以他能自己带着。孙到了齐，身体不能
练兵了，所以只能给田忌出主意，最后的执行，还是得靠田忌操盘。
这也是，经常看军师出个上中下三策，头却只能用中策的原因。纸上谈兵的上策往往不
可行。 |
|
w********r
发帖数: 1971 | 48 这个得多13才能得出这个结论，人类文明发展后，配偶权的争夺竞争早就不是优胜劣汰
的主要方面了，只有禽兽才适用配偶权竞争来遗传优良基因而适应自然。人类的主要优
胜劣汰是在智力方面的竞争，而禽兽配偶权的自然态竞争早就可以用现在科学医疗来解
决了。而智力的
社会分布是正态分布和随机态的，只有一夫一妻制才能保证社会智力资源样本的最优分
布，才能是最优解。 回复这样的人真是自残。 |
|
