s*********d
发帖数: 19 | 1 遇到求解一个复杂函数的最优解问题
设F(T)是一个关于多维的向量T的复杂函数表达式，现在想求取最优T值，s.t. min(F(T
))达到最小值
按照最初的设想是：
a) 求出F(T)对于T的gradient decent表达式F'(T)，给定一个T的初始值T_0，step
size K 和tolerance value M，
b) 将T_0代入F'(T)并normalization（F_n'(T_0)=F'(T_0)/|F'(T_0)|）
c) 更新T为T_1(T_1=T_0-K*F_n'(T_0)),依此做iterarion，直到T的两次值T_n,T_n+1的
变化小于M
按照上述方法我尝试了一下，做了20次iteration后，F(T)的值是变小了，但是变化速
度很慢，比较费时间，有没有比较快速一些求解方法？ |
|
Y********d
发帖数: 1478 | 2 好了，别删了，我再仔细想了想，给定目标和约束，你这个最优解也确实没什么好挑剔
的。
寻找解的过程也算造福外人了，最后的解也算是可执行的冰箱贴了。
至于目标是什么，也不是我在那边车轱辘，浪费的也不是你一个人的时间和感情。
等会儿要上课了，不来和你斗嘴怄气了，这世上，谁能斗得过你 ？ :-)
晚安吧。 |
|
b***y
发帖数: 14281 | 3 不能。这个问题我想过。困难在于数学问题每走一步都无法判断到底是离解近了还是远
了，这是和围棋最大的区别。围棋你可以判断局面优劣来取舍，选择最优解，解数学问
题在直到解出来之前你无法知道哪一个方向最有机会成功。有时候明明看着就差一步一
遥，在命题空间里这两个点看着近，但实际可能很遥远。
★ 发自iPhone App: ChineseWeb 16
★ 发自iPhone App: ChineseWeb 16 |
|
|
g**********y
发帖数: 14569 | 5 你还真不死心 :-)
不行！
这是个不定长的sequence, 随便你找多少种和出来，数学上都能构造出反例，只不过构
造起来困难点。
这个题正解应该是类似那几篇paper的思路，有O(N)甚至更低阶的解法，不过那些不是
面试范围内的。
等哪个大牛出来给个面试时间可用的O(N)解吧。 |
|
U*********y
发帖数: 54 | 6 题目: transform one word into another, 1 letter at a time, each step must
be
in the dictionary.
CareerCup的BFS解看起来很麻烦, 既然没要求最短距离转换或得出所有可能转换, 就写
了个DFS+backtracking的解, 请指教!
[code]
unordered_set dict; //dictionary
bool validTran(string &a, string &b, int d, unordered_map
string> &path) {
if(a == b) {
return 1;
}
if(d == b.size()) return 0;
if(a[d] == b[d]) { //no change at this position is needed
return validTran(a, b, d+1, path);
}
for(char ... 阅读全帖 |
|
b**d
发帖数: 1174 | 7 应该先装傻充愣一会儿，再慢慢解。
我被问了5个算法题，4个都是做过的，每个都磨了最少3分钟，先给错误、猥琐的答案
，再给出最优解。没办法，有时候面试就像演戏，即使大家心里都有数，面子上也得过
得去。 |
|
V**n
发帖数: 560 | 8 Here u go.
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 女生怎样找到好BF（本文同样也适合gg找mm……）
发信站: BBS 未名空间站 (Sat Dec 21 18:14:26 2013, 美东)
之前看到梦版讨论，一个女的同时date好多男的，然后试图从中选一个敲定。
我结合一下本学期学到的知识来说明一下，这个策略效率是非常低的……
女生都想找到高富帅、性格合得来、又体贴的好gg，这就是一个Optimization Process
。每个女生肯定都会给自己心仪的男生打分，这个分数就是Objective Function f(x)
。找合适gg的过程就是去找 max f(x)。由于现实社会的复杂性，没有一种
Optimization Algorithm能够保证找到最优解，因此各位mm在找gg的时候，心里要有个
度（有限次迭代），否则一辈子都找不到的。
那么之前大家讨论的广撒网的方法，其实类似于Genetic Algorithm，mating pool都是
随机选取的，通过广泛的选择，并且通过交往过程中的随机的变故（变异）判断gg的... 阅读全帖 |
|
t******l
发帖数: 10908 | 9 这可能跟人类解 AMC / AIME / USAMO 的路数也差不多。因为解题的最终目的是赢，所
以能用小学排列组合解的基本就不会去用微积分泰勒展开，虽然泰勒展开可能会少几步
、有定式。
其实我觉得阿狗还是在学人类。
：问题是空的大小本身就是由风险带来的。拿第五局举例，人计算白100围中间得利更多
：，也没啥风险。但是阿九段去底下拆一。 |
|
k********k
发帖数: 5617 | 10 发信人: jojoshan (), 信区: Piebridge
标 题: 诚心征一名公民或者485男
发信站: BBS 未名空间站 (Thu May 4 16:14:59 2017, 美东)
我，34岁，目前在东部，身高165，体重98斤，典型的巨蟹女，
外在条件还不错，脾气性格也好，
**********但是偶尔会发小脾气，**********
喜欢运动，音乐，厨艺,旅行，
是一个内心简单而又单纯的小女人，
是一个可以安心在家照顾家庭的女人.
希望你，年龄在40岁以上，成熟有责任心，幽默，是个有趣有故事的人，
**********希望你能包容我偶尔的小任性，**********
虽然爱情加上某些要求就可能会变质，
**********但是目前我没有身份确认是我一个很大的困扰，**********
所以我加了这一个附加条件，希望能得到大家的理解.
无论怎么样，我想表明的是我是个对待感情很认真的人，
爱玩的，在感情中喜欢冷战的，
**********没有结婚打算的就不要给我发信息了,**********
**********我是计划今年结婚的.**********
我的邮箱[emai... 阅读全帖 |
|
|
|
|
l***m
发帖数: 339 | 14 俺觉得 和相等，乘积相等应该就是最优的吧。XOR有很多特殊情况是处理不了的。比如
22222，33333。 |
|
S****h
发帖数: 115 | 15 嗯，看来greedy确实是最优解法O(n),贴个code:
public int jump(int[] A) {
int jumpCount = 0;
int index = 0;
int limit = 0;
while (limit < A.length - 1) {
jumpCount++;
int temp = limit;
for (int i = index; i <= limit; i++) {
if (A[i] + i > temp)
temp = A[i] + i;
}
// can not progress
if (limit == temp)
return -1;
// progress
index = limit + 1;
limit = temp;
... 阅读全帖 |
|
d*****8
发帖数: 38 | 16 这个稍微不同于最少硬币找零, greedy算法，
1. 目标是最多的满桶;
2. 可以溢出桶
不满足greedy的条件：当前的最优解不受子问题影响.
像用在traveling salesman problem，
反例：
50， 70， 50， 31
用50+50, 70+31。最多2个桶 |
|
C***U
发帖数: 2406 | 17 能说下你的反例得意思吗？
这个稍微不同于最少硬币找零, greedy算法，1. 目标是最多的满桶;2. 可以溢出桶不
满足greedy的条件：当前的最优解不受子问题影响.像用在traveling sale........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite |
|
C***U
发帖数: 2406 | 18 明白你的意思了。 但是我的解法刚好可以解决你的问题。 不是反例。
每个桶需要的水量数组是A： 30，50， 50，69
每个桶现有水量得数组B：31， 50， 50， 70
从31开始， 把A里面第一桶满了。从A和B里面去掉，然后第二个桶去填充A里面剩下得
不是他自己得桶。
这个稍微不同于最少硬币找零, greedy算法，1. 目标是最多的满桶;2. 可以溢出桶不
满足greedy的条件：当前的最优解不受子问题影响.像用在traveling sale........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite |
|
|
O******i
发帖数: 269 | 20 面官后来反馈说，the best O(1) solution I know so far is to use a trie
真的能用trie达到O(1)么？如何实现？
*******************************************************************
给定一个大整数N,比如N = 100, 有如下的初始有序序列位于[0, N - 1]之间
[0 1] [4 5 6] [9 10 11] [20] [50] [90] [95 96] [98 99]
请设计一个数据结构保存这个初始序列，然后写一个函数，接受一个input参数x, 满足
0 <= x <= N - 1
1) 假如x在该结构中不存在，出错处理
2) 假如x在该结构中存在，返回x之后第一个不存在的数，并把该数写入结构中
例如
x = 8, 出错，初始序列中没有8
x = 5, 返回7， 序列变为
[0 1] [4 5 6 7] [9 10 11] [20] [50] [90] [95 96] [98 99]
x = 4, 返回8, 序列变为
[0 1] [4... 阅读全帖 |
|
a****l
发帖数: 8211 | 21 你的最优是什么意思?速度最快?空间最小?程序代码最短? |
|
a****l
发帖数: 8211 | 22 你的最优是什么意思?速度最快?空间最小?程序代码最短? |
|
|
e****e
发帖数: 418 | 24 feiw217, 谢谢你贴出解法。这个解法空间和时间上都不是最优。swap的方法表面是看
是swap, 其实是recursion的思路.再次感谢你的解法。 |
|
k*****o
发帖数: 1972 | 25 谢谢回复，
感觉在20~30分钟内，
特定问题上，写个没bug的最优解，
会比较忙乱。毕竟分析也要时间 |
|
|
c*******e
发帖数: 621 | 27 至少可以3d dp using n2 space
并且可以处理数重复的情况
不知道还能不能更优 |
|
发帖数: 1 | 28 楼上说的没错。以我的经验也是，两轮coding的面试官会有不同的侧重，一个在于分析
问题的能力，最优解法，另一个方法会简单一些而更侧重code要写的简洁、modular，
还有测试。 |
|
G*******n
发帖数: 3144 | 29 基本情况:
准备大概2月1号 -- 2月20号左右回国3个礼拜吧, 过春节.
家在深圳, 所以飞香港比较方便(Hong Kong International Airport).
纽约JFK/Laguardia/Newark出发都可以.
希望直飞.
我平常用的基本的方案: 国泰直飞往返大概$1200--$1300,这是直接买票的方案.
另外我现在有80k Chase的点数和50+k UA的点数.希望利用看看
碰碰运气看看有没有点数达人能比直接$$买机票更优的方式
能划算的体验下商务舱甚至头等舱也可以(哈哈 不知道这点点数够不够干嘛,加点钱也
可以)
50个包子奖励我采纳的方案(直接用$$国泰买的不算哦)
如有疑问欢迎补充.
谢谢!!!!!!!! |
|
G*******n
发帖数: 3144 | 30 基本情况:
准备大概2月1号 -- 2月20号左右回国3个礼拜吧, 过春节.
家在深圳, 所以飞香港比较方便(Hong Kong International Airport).
纽约JFK/Laguardia/Newark出发都可以.
希望直飞.
我平常用的基本的方案: 国泰直飞往返大概$1200--$1300,这是直接买票的方案.
另外我现在有80k Chase的点数和50+k UA的点数.希望利用看看
碰碰运气看看有没有点数达人能比直接$$买机票更优的方式
能划算的体验下商务舱甚至头等舱也可以(哈哈 不知道这点点数够不够干嘛,加点钱也
可以)
50个包子奖励我采纳的方案(直接用$$国泰买的不算哦)
如有疑问欢迎补充.
谢谢!!!!!!!! |
|
|
a***g
发帖数: 3377 | 32 这才是正解。
普京只要开放远东让中国移民。很快远东就是他们的粮仓。大批的粮食可以和美国粮食
一战。 |
|
S*******l
发帖数: 4637 | 33 中共是19，20世纪世界共产主义运动的一个部分。国共争夺是美苏代理人争夺。
其实没有中共，常凯申一样统一中国，带领中国人民走上富强的道路。
不过是两家公司谁更aggressive赶走了另一家独占市场，其实两家的长远目标是一样的。
胜者王侯败者寇，就讲非我共不可。其实不是唯一解。 |
|
发帖数: 1 | 34 只要土共存在，永远没有其他解，因为其他出路都被土共堵死了 |
|
发帖数: 1 | 35 退让二代子女的利益要受损，上坦克屠城二代子女的利益还是要受损，和89年还不一样
了，89年杀学生是对官倒二代的利益最优解，但现在无论怎么干，二代子女都要受到损
失，这是不能容忍的。 |
|
u*l
发帖数: 1943 | 36 我就奇怪了,短短45分钟,怎么可能又解出一个好算法,还写出Bug-Free的Code?
我看那些问题的难度,光想出算法45分钟都不错了;
或者面试官给算法,面试者写出Code来也不错;
更何况经常还要连问两道题!
反过来大侠们讲讲, 准备充分,题目都碰到的,就一定拿到Offer?!
我是好奇. |
|
G**********s
发帖数: 70 | 37 Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
哪位仁兄给一个 反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！ |
|
i**********e
发帖数: 1145 | 38 第一题我也想知道有没有 O(N) 解和 O（1） space 那么神奇的方法。
第二题是 reservoir sampling. |
|
g**********y
发帖数: 14569 | 39 (1, 5, 6) vs (2, 3, 7)
1 + 5 + 6 = 12 = 2 + 3 + 7
1 + 25 + 36 = 62 = 4 + 9 + 49
在(1..100)的空间里，对k=3，可以算一堆这种解出来。 |
|
p*****y
发帖数: 529 | 40 这个证明不完全， 因为还有这样的情况：
ai+k, aj-m, ak+m-k
需要不满足：
(ai+k)^2 + (aj-m)^2 + (ak+m-k) ^ 2 = ai ^ 2 + aj ^ 2 + ak ^ 2
given any integer k and m.
然后是4个数， 5个数...., n个数。
这道题其实就是n个变量， 两个方程， 再加上限制条件每个变量时整数， 然后证明有
没有唯一解得问题。 我觉得是没有的， 但还没想出证明方法。
k)： |
|
f**********t
发帖数: 1001 | 41 记得数学老师说过 方程组：
x1 + x2 + ... + x10 = Z
square(x1) + square(x2) + ... + square(x10) = Y
不是唯一解
k)： |
|
p*****2
发帖数: 21240 | 42
个值
背包问题是求最优解。这个是一个组合问题呀。就是看那种组合满足条件就可以了。没
什么dp的关系呀，感觉。 |
|
h****e
发帖数: 928 | 43 多谢各位的回复。看来可以认为O(M+N)是面试时候能给出的最优解了。 |
|
p*****2
发帖数: 21240 | 44
每一道题都直接给最优解。30分钟4,5道难题，活生生的例子。 |
|
a*****n
发帖数: 158 | 45 想再问一下，，直接给最优解，如果对方问你是不是见过这道题，，怎么回答啊？？？ |
|
p*****2
发帖数: 21240 | 46
我真不认可。你说人家都给最优解，你给暴力的，难道给你offer不给别人？ |
|
|
f********4
发帖数: 988 | 48 以失败者的经验教训告诉你，最好还是自己想。。可惜我都看过一遍答案了
因为现在面试官都挺精明的，onsite直接原题的情况不是太多了，很多都是没见过的
做题把解记住这种，最快见效的就是电面，因为见过了马上能写出来。但是很多时候其
实思考的过程也蛮重要的。
总是一看题目，有思路的直接写，没思路的直接看答案，遇到没见过的题的时候，就歇
菜了。。因为这样做题就是熟悉了api，你会的可能现在bug free了，你不会的，需要
写个递归动动脑子的题，还是不会 |
|
m*******g
发帖数: 410 | 49 我的一个思路是：
把字典里面单词保存起来，找到字词的最长长度，然后长字符串进行滑窗处理，每个滑
窗对所有的单词进行搜索，找到是否有字典中的单词，这貌似不是最优解。 |
|
