l********e
发帖数: 3632 | 1 geometrically convex function has upper lever set convex. Hence your convex
set is the intersection of all convex set with your properties. which is
also called convex-hull. Use the definition of convex-hull you can see
easily that your answer is correct.
You can also prove algebraically which is even more trivial, since you
already has one convex function constructed, then if the sup is not your
function, a easy contradiction can be derived from the fact if some point in
(0, a) has larger value... 阅读全帖 |
|
d**e
发帖数: 6098 | 2 ☆─────────────────────────────────────☆
travelodge (travelodge) 于 (Fri Aug 31 00:46:34 2012, 美东) 提到:
总觉得山寨淘宝的research scientist很鸡肋， 工资跟sde一样，但基本不
发paper,
这样怎么来评定该不该升级。 不发paper又不经常写code那就等于没法跳槽，万一被裁
员别家的research scientist还是看paper的吧。
至于山寨百度的SDE(T4), 又担心他们家高手如云， 很难升级， 会不会做万年sde(最多
升到5）
钱上其实账目上差不多， 扣掉免税州的低房价， 不过淘宝少了很多福利
对于fresh phd来说
RSII: 125k + 40k sign-on /2 + 55k RSU / 4 = 158.75K
SDE 127k + 15% bonus + 160 RSU/4 = 170K
有没有过来人给点建议。。。。
面经，记不清了
山寨淘宝/京东
onsite有个job talk,
然后有五六轮聊天面试吧，题目... 阅读全帖 |
|
r******7
发帖数: 58 | 3 我不牛。说说体会
1. 可微分convex函数总可以找到全局最优解。SDP的全局最优解不一定能找到。
2. SDP的关键是约束条件以可是任何函数。convex programming的objective function
and constraints都要是convex才行。
3. 能用convex programming解的问题都可以用SDP解。凡是convex programming能找到
的解一定不比SDP差。
一句话：尽量用convex programming。实在不行再用SDP。 |
|
k*******d
发帖数: 1340 | 4 这个问题in general不是那么好解的啊
很简单的non-linear function也可能不是convex或者concave的
要想简单地解min max （max min 加个负号倒过来）问题，要求函数f1,f2,f3要是
convex的，如果是convex的话，max()就是convex的，这样好办，可以用log sum exp去
逼近
如果不是convex的，而且这个函数又不是continous的，那可能就麻烦些了，可能要用
到subgradient method?我也不大清楚
参考Boyd的convex optimization
和Bertsekas的nonlinear programming |
|
s***h
发帖数: 487 | 5 Optimization theory 里把 convex 和 concave 都笼统叫 convex，因为 concave 给
upside down 翻过来还是男上女下 convex，trivial difference。
既不是 convex 也不是 concave 叫 nonconvex 。
如果我没有记错。
: 你弄错了，梯度为0，hessian不正定是鞍点，说明此驻点不是极值点。
: hessian矩阵是对应一维函数时在驻点的二阶导数的*绝对值*，所以hessian正定
包括
: convex和concave两种情况。
: which
|
|
发帖数: 1 | 6 The distance to a point is a convex function.
Sum of convex functions is a convex function.
Within the confine of a convex polygon,
the max of a convex function lies on a vertex.
On vertex A of polygon ABCD, the sum of distances is
S=AB+DA+AC.
AC
S<(AB+BC+CD+DA) + (AB+DA-BC-CD)/2 |
|
y*w
发帖数: 238 | 7 第一个问题还是很难回答，因为不知道P（sigma）的property，而且看起来P(sigma）
都没有close form。
一般来说都是用下面这条来判定least square的是不是convex。所以最好知道P对于
sigma是不是convex的，这个你可以先直观的plot几个点，算几个value出来看看，对于
P长的什么样子有个idea以后再考虑是不是要继续证明convex
If f and g are convex functions and if g is increasing, then h(x) = g(f(x))
is convex.
transform这里看来不太可能了，因为你的P没有close form
第二个你先把相邻2X2的点的sigma都设成一样，变量就少1/4了，然后用这个解做下一
次的starting point；当然这是一个heuristic，成功性没啥保证 |
|
W******r
发帖数: 789 | 8 option的gamma和theta之间有一个trade-off。如果你买option，那么你有convexity的
优势，但是要go against time decay。如果你卖option，那么你有time decay的优势
，但是要go against convexity。似乎大部分option的书和网上的资料都是认为time
decay比convexity重要，主张以卖为主。但是我个人的经验却似乎不是这样。虽然卖
option有time decay的优势，但是因为go against convexity，一旦错了会输得很惨。
大家对此怎么看？ |
|
v***o
发帖数: 51 | 9 在分析一个VALUE FUNCTION关于STATE VARIABLE的二阶导数时，要看一个函数期望值关
于其分布均值和方差的二阶。稍微想了想，如果分布是正态的，这个函数是连续递增和
CONVEX的，那么这个函数的期望值对于分布均值（和方差）应该也是CONVEX的（因为函
数右端CONVEX地发散至无限Dominate了其他因素）。好像如果是CONCAVE的函数就难说
了。
想更多地了解一下各种函数期望值关于其分布概率参数的性质（如单调和CONVEXITY/
CONCAVITY，即E[f(x）|theta]关于theta（x分布的参数） 的各阶导数。哪位大牛指导
一下哪些文献可以参考？ |
|
v***o
发帖数: 51 | 10 想更多地了解一下各种函数期望值关于其分布概率参数的性质（如单调和CONVEXITY/
CONCAVITY，即E[f(x）|theta]关于theta（x分布的参数） 的各阶导数。
在分析一个VALUE FUNCTION关于STATE VARIABLE的二阶导数时，要看一个函数期望值关
于其分布均值和方差的二阶。稍微想了想，如果分布是正态的，这个函数是连续递增和
CONVEX的，那么这个函数的期望值对于分布均值（和方差）应该也是CONVEX的（因为函
数右端CONVEX地发散至无限Dominate了其他因素）。好像如果是CONCAVE的函数就难说
了。
哪位大牛指导
一下哪些文献可以参考？ |
|
h******g
发帖数: 33 | 11 convex和joint convex的区别，我认为是
如果将其它变量看作常数，只验证其中一个变量，为凸则为convex
如果将多变量看作一个向量，验证凸性，则为joint convex |
|
b***k
发帖数: 2673 | 12 ☆─────────────────────────────────────☆
fishdaddy (无) 于 (Mon Apr 7 12:30:01 2008) 提到:
先考了几个BS model和volatility的基本问题
然后当场看SPY的IV curve和open interest curve
解释为啥call和put相同strike的IV不一样
解释为啥某些地方不smooth，有小小的fluctuate
解释为啥大部分地方vol skew看起来是convex的，但有些地方不是convex的
☆─────────────────────────────────────☆
Jadeson (Jadeson) 于 (Mon Apr 7 13:06:04 2008) 提到:
解释为啥大部分地方vol skew看起来是convex的，但有些地方不是convex的
这个问题，原来我看过，也有相关的解答，但问题在于那个解答是手写的,实在难以辨
认。哪个高手给翻译一下呢？
http://www.wilmott.com/blogs/kurtosis/enclosur |
|
i**w
发帖数: 71 | 13 Is the following argument natural?
From the perspective of a market maker, whenever he sells a call, he needs
to set up a hedging portfolio, which contains delta shares of stocks and
certain amount of funding balance. The cost to set up such a portfolio is
the price that he quotes for the buyer. (What he actually quotes will of
course includes a premium on top, to make money. but let's forget about the
making money part.)
-(Perfect) Black Scholes world
If he lives in a (perfect) Black-Scholes wo... 阅读全帖 |
|
y****d
发帖数: 432 | 14 【7】【Springer】GTM美国研究生数学书籍全集
LIST：
1 Introduction to Axiomatic Set Theory, Gaisi Takeuti, W. M. Zaring
2 Measure and Category, John C. Oxtoby
3 Topological Vector Spaces, H.H. Schaefer, M.P. Wolff
4 A Course in Homological Algebra, Peter Hilton, Urs Stammbach
5 Categories for the Working Mathematician, Saunders Mac Lane
6 Projective Planes, Hughes, Piper
7 A Course in Arithmetic, Jean-Pierre Serre
8 Axiomatic Set Theory, Gaisi Takeuti, Zaring
9 Introduction to Lie Algebras and Representation The... 阅读全帖 |
|
x******a
发帖数: 6336 | 15 In 1611, Johannes Kepler described how a telescope could be made with a
convex objective lens and a convex eyepiece lens and by 1655 astronomers
such as Christiaan Huygens were building powerful but unwieldy Keplerian
telescopes with compound eyepieces. Hans Lippershey is the earliest person
documented to have applied for a patent for the device.[1]
Isaac Newton is credited with building the first "practical" reflector in
1668[citation needed] with a design that incorporated a small flat diagona... 阅读全帖 |
|
T*******x
发帖数: 8565 | 16 谢谢。你给这个链接不错。这个证明我以前没见过。
看来functional equation可能还需要一个convex条件才能得出唯一的函数。在gamma函
数的例子中，如果没有这个ln(f)的convex条件，可能还得不出必为gamma的结论，至少
这个证明不成立了。
不过我还是觉得functional equation已经是非常非常强的限制了，再加上解析函数的
要求，即使没有某种convex条件，这么强的限制下还能有什么腾挪的空间吗？如果有，
那这个空间也挺有意思的。
你的回帖有一点小错误：如果C=ln(gamma)的话，C(p)=C(p-1)+ln(p-1).
我这个题是有例子的：
let A(p)=integral of x^p ln(1-x) over (0,1)
let B(p)=A(p-1)
let C(p)= -p B(p)
这个C(p)就有我说的性质：解析函数，满足我说的functional equation.
我确实是想知道它是不是唯一的。 |
|
发帖数: 1 | 17 那应该是不行的。
否则c(x) 加上一个周期为1的周期函数就是一个新的解。
比如c(x)加sin(2pi*x)。。
: 谢谢。你给这个链接不错。这个证明我以前没见过。
: 看来functional equation可能还需要一个convex条件才能得出唯一的函数。在
gamma函
: 数的例子中，如果没有这个ln(f)的convex条件，可能还得不出必为gamma的结论
，至少
: 这个证明不成立了。
: 不过我还是觉得functional equation已经是非常非常强的限制了，再加上解析
函数的
: 要求，即使没有某种convex条件，这么强的限制下还能有什么腾挪的空间吗？如
果有，
: 那这个空间也挺有意思的。
: 你的回帖有一点小错误：如果C=ln(gamma)的话，C(p)=C(p-1) ln(p-1).
: 我这个题是有例子的：
: let A(p)=integral of x^p ln(1-x) over (0,1)
|
|
j******l
发帖数: 1068 | 18 有做discrete convex的吗？这是个算新的领域，有不少东东可作。
M-Convex Functions and L-Convex Functions |
|
t********e
发帖数: 1169 | 19 onsite有个job talk,
然后有五六轮聊天面试吧，题目有难的有简单的
记得的问题有
1. Given a set of 10,000 popular search queries every month, find a unique
page on the Amazon website to target for each keyword -- given page types:
detail, browse, search
2. How would you implement a queue with two stacks
3. Given an array of points in 2D, find the subset of the points on the
convex hull. The convex hull is the minimal convex polygon that encloses all
the points.
4. How would you store a your NeuralNetwork structure to a file? |
|
t********e
发帖数: 1169 | 20 onsite有个job talk,
然后有五六轮聊天面试吧，题目有难的有简单的
记得的问题有
1. Given a set of 10,000 popular search queries every month, find a unique
page on the Amazon website to target for each keyword -- given page types:
detail, browse, search
2. How would you implement a queue with two stacks
3. Given an array of points in 2D, find the subset of the points on the
convex hull. The convex hull is the minimal convex polygon that encloses all
the points.
4. How would you store a your NeuralNetwork structure to a file? |
|
r*g
发帖数: 186 | 21 先生成convex hull
然后考虑边界点的两两距离
convex hall生成算法是O(nlogn)
然后在convex hull上寻找两两最长点 复杂度是O(nlogn)
合计复杂度O(nlogn) |
|
t******l
发帖数: 10908 | 22 我前面证明了。前面是证明细节，我这里写一下证明思路便于理解。
这个证明思路，是观察 体积和液面高度的函数关系。
对于 B 杯，体积和液面高度的函数关系是一条直线。
对于 C 杯，体积和液面高度是一条连续的 convex 曲线（因为二阶导数是一个正实数
）。
而 B 杯 和 C 杯的 体积-液面高度曲线，存在两个交点。一个是初始点，高度和液面
体积都相同，一个放完点，体积和液面高度都是零。。。这样就形成 直线 和 convex
曲线相割的情况，前面两个交点就是相割点，这样就不存在第三个交点，而在两割点内
，该 convex 曲线永远在直线的右下方。QED。
：”对于相同的体积时，C 的液面高度一定比 B 高“，不一定，取决于横截面积。
：【 在 timefall (时光崩塌) 的大作中提到: 】 |
|
h**********c
发帖数: 4120 | 23 我对图形方面的问题比较感兴趣,以下几点探讨一下
1. 20面体的mesh,能不能简化成为20 个planar polygons
2. 20面体是不是convex的.
3. 如果是convex可以对每一个面做ray tracing,有更好的办法ray tracing
4. 不是convex的,可以divide and conque.
5. 有很多mesh lib,我知道一个open source --GTS ,应该有你要的功能
"为数不多的几行命令"恐怕不太现实. |
|
d******e
发帖数: 7844 | 24 convex optimization里绝大部分算法都可以可以保证收敛到全局最优，速度都比较快。
Quasi-Convex问题，比如特征值问题，一些特殊结构可以直接求出closed form
solution，或者构造一个求解路径达到全局最优，速度一般。
一些linear constrained的non-convex问题可以用outer approximation来拿到全局最
优，速度非常慢。 |
|
p***o
发帖数: 1252 | 25 Sounds like if you are given a convex polygon, it means
the points are given in either clockwise or counter
clockwise order. Otherwise, you just have a point set,
where many polygon can be constructed with the same
vextex set but being non-convex. In such case, you have
to generate the convex hull first ... |
|
t****g
发帖数: 715 | 26 Do you assume x is normally distributed? When you say concave/convex, do you
mean strictly concave/convex(e.g. f(x)=x is concave as well as convex)?I
doubt this general question you raised has a specific answer.
concave |
|
b****t
发帖数: 114 | 27 Hi all,
I am solving a quasi-convex optimization problem, which is minimizing a
piecewise linear function (nonlinear indeed). The objective function is
quasi convex in it's domain. Can anyone suggest me some methods to solve
this type of problems? Any general methods can solve quasi-convex
optimization problems that have nice convergence properties?
Thanks a lot,
Beet |
|
h**********c
发帖数: 4120 | 28 牛顿法也许很好，但是但是用来解方程的。
它不能用来生成一个椭圆或者类似的convex shape，也就是不是一个表达椭圆的办法。
在计算几何里,convex hull是不连续的，没法求导的。而convex hull是可以用2维矢量
空间的一个generating set 来近似。
当然本贴只是想引起相关方向上的人士的兴趣。如果愿意的话我可以把２０页的pdf发
过去。
my point may be niave. 但是，您必须证明您是serious的.
严格讲，计算几何都是numerical guy这点我们是应该承认的。加减乘除越简单越好。
另外，我没有找到求椭圆到点距离的现成文章或程序例题。再找找，如果哪位有，请提
供出处。
我没有发过任何文章，不太清楚过程，还望赐教。 |
|
Q***5
发帖数: 994 | 29 Don't know about the NPC property.
But, for P>1, L_P norm often leads to convex problem, therefore, effecient
numberical methods can be used to find the optimal solution.
When P = 1, it is still convex -- but the smoothness of the problem is poor,
therefore, need more care and computing time.
For P<1 (including 0), the problem is generally non-convex, ordinary
numerical routine (e.g. gradient descent) can only leads to local optimal
solution. Finding the global optimal solution can be charllengi |
|
g****t
发帖数: 31659 | 30 看来我没记错，一般的L0是NP hard。
ref:
http://www.computer.org/portal/web/csdl/doi/10.1109/ICASSP.2009.4960346
Don't know about the NPC property.
But, for P>1, L_P norm often leads to convex problem, therefore, effecient
numberical methods can be used to find the optimal solution.
When P = 1, it is still convex -- but the smoothness of the problem is poor,
therefore, need more care and computing time.
For P<1 (including 0), the problem is generally non-convex, ordinary
numerical routine (e.g. gradient desc |
|
b****t
发帖数: 114 | 31 Hi all,
I have a discrete function g: X -> R, which is "convex" in the
sense that I piecewiselinearly interpolate the function on the grid pionts in X, I got aconvex function on a convex set X'. Suppose the domain X is a finite set (e.g. a bounded subset of Z^n), I use piecewise linear interpolation to construct a continuous function f, so that f=g on X,and f is convex on X'.
My question is how to prove if I add small amount noises to the
function g, so now g' is very close to g on X, |g-g'| < \ |
|
b***k
发帖数: 2673 | 32 ☆─────────────────────────────────────☆
songh2 (George) 于 (Tue May 13 12:27:49 2008) 提到:
If you are long a FRA (Forward Rate Agreement) and short a ED (Eurodollar)
future with the same fixing dates, do you have positive convexity or
negative convexity?
☆─────────────────────────────────────☆
Ithink (牛夫人) 于 (Tue May 13 15:38:01 2008) 提到:
negative convexity, given future is positively correlated with interest rate.
☆─────────────────────────────────────☆
matrixIII (matrixIII) 于 (Tue |
|
d********i
发帖数: 7 | 33 看上去是整数规划中的Majorization问题，可以用多个Schur-Convex函数as the fmin
objective. Note that the separable-convex functions like power moments are
Schur-convex examples. |
|
D**u
发帖数: 204 | 34 Let's think about the case of n=2.
To maximize \sum(f(t(i))
(1) if t(1)*t(2) > 1, you want t(1) and t(2) to be as apart as possible.
(2) if t(1)*t(2) < 1, you want t(1)=t(2) (or as close as possible when there
are constraints)
(3) if t(1)*t(2) = 1, then it doesn't matter because f(t)+f(1/t)=1.
This is mainly due to the convexity of function g(x)=1/(1+e^x), which is
convex when x>1, but concave when x<1. This inconsistancy in convexity makes it hard even to conjecture
what the final t(i) might be |
|
A*****s
发帖数: 13748 | 35 挖坟了不好意思
按照Joshi的解释
对于任何convex pay-off的derivative
只要有jump，不管up还是down，value都高于没有jump的？
因为jump导致hedging pf价值沿切线移动，无论如何都在convex curve以下了。。。
还有，put option也是convex，那也会因为jump的存在导致价值提高？
总的说来jump就是提高了uncertainty，所以option value就是会提高了？ |
|
n******t
发帖数: 4406 | 36 含n个点的平面点集的convex hull可以在O(nlog(n))解出来,然后包住it的最小圆可以
在O(n)时间内解出来。所以你的方法还是work的。不过，如果都想到这里，自然就会发
现没有必要解convex hull了,因为从convex hull到找最小园的用的思路也就是这个问
题的优化算法的思路了。 |
|
h*******i
发帖数: 4386 | 37 non-linear is not the issue, convexity is.
we have good solvers for all convex problems.
non-linearity is not an issue anymore. |
|
发帖数: 1 | 38 linear，nonlinear，convex，你平时也写不了啊，还不是调裤？
除了特别简单有解析解的
: 说 DP 简单的，拿下 ACM-ICPC 里面的 DP 竞赛题，再说简单不迟。否则的话，
丢人。
: 。。
: 再说工业界里，除了 dynamic programming, convex programming, nonlinear
: programming,外加一些 metaheuristic，更高端的要么直接调库 black box
tuning，
: 要么基本不用。
: 当然数学系老讲师，尽管拿一大堆高端数学算法，但也不能掩饰其 USAMO 拿零
蛋的事
: 实，记忆默写历年考题不算哈哈哈哈哈哈。
: |
|
j******u
发帖数: 1968 | 39 俺是作stochastic／convex optimization的，现在这个领域有很好的课题，呵呵。
写proposal的时候不发愁idea，但是对education这方面就抓瞎了，我教过几门
optimization的课程，
学生感觉很慢，根本不能follow，很郁闷，听别的学校同事说也都这个德行，于是想行
为艺术一把，弄个
survey，放在proposal里面装一装酷，其实主要是了解学生的需要，这样说话更有分量
一些。
http://www.uncertaintylab.com/survey/index.html
主要想弄清如下几点（下面的问题仅仅是中文的摘要，英文原文看上面的link）
1。在engineering里面optimization到底有多重要
2。当你碰到一个非常恶心的model的时候是用heuristic还是试图找到最优解？
3。你对现在的optimization package满意不？
4。如何才能提高学习效率？
5。你有没有想过用convex的方法来model你的问题？
6。你知不知道现在的内点算法已经非常成熟了，大规模的问题可以用内点来解决？
刚刚设计了一 |
|
t**********t
发帖数: 12071 | 40 我正好下个学期要教convex optimization
1。在engineering里面optimization到底有多重要
灰长灰长重要。我们处理问题一般是MODEL成优化问题，下面就是纯优化问题了。
2。当你碰到一个非常恶心的model的时候是用heuristic还是试图找到最优解？
这要看我晚饭吃饱了没有
3。你对现在的optimization package满意不？
还好吧
4。如何才能提高学习效率？
晚饭少吃点
5。你有没有想过用convex的方法来model你的问题？
经常使用。不过stochastic control如何进行decomposition似乎还很难？如果能够
decompose，我们这一行里用处大大地有。
6。你知不知道现在的内点算法已经非常成熟了，大规模的问题可以用内点来解决？
知道。 |
|
j******l
发帖数: 1068 | 41 Discrete Convex 你没有听说不奇怪,这是最新的东东。日本的几个搞数学的搞出来
的，论文主要发在SIAM，Mathematical Prog等偏数学的杂志上。我最近正在学这个东
西，准备用到我的论文上。
你既然搞logistics，Operations。就该知道Zipkin。Duke的Inventory 大牛。他最近应用Discrete Convex在OR上发了篇论文。
On the structure of lost-sales inventory models, Operations Research. |
|
e******e
发帖数: 421 | 42 I'm doing applied research.
I used some mathamtical tools to solve a practical problem with practical
constraints (other people solved similar problems but neglected some
important constraints).
Clearly, the mathematical tools are not my contribution. Then, my
contribution is modeling a practical problem and solving it. However, this
seems not sufficient. How should I highlight my research?
Moreover, if I want to show some technical depth of my research, is it good
to show the mathematical deriv... 阅读全帖 |
|
d****2
发帖数: 6250 | 43
刚看到这个，一看就是没有真正用过好刀的人，借过别人用了5分钟的不算。你的理论
不成立，convex edge维护起来更麻烦，这也是我不喜欢global刀的原因，他家的刀是
convex edge的。 |
|
z*******e
发帖数: 122 | 44 对于第3个题目，找包含所有点的最小圆的半径，我觉得可以先找到一个convex hall
包含所有的点（在CLRS上有nlogn的算法）,然后求这个convex hall的外接圆。 |
|
S**I
发帖数: 15689 | 45 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 46 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
x********o
发帖数: 25 | 47 对每个点找离它最远的是logn。
因为是convex hull，距离变化是一个严格凸函数。2分查找的时候check相邻的三点是
否满足两边的小于中间，如果是则返回，不是的话就接着2分。
convex hull能理解，后一步怎么在NlogN时间里找到hull上最远的两点？最坏情况下所
有点都在hull上 |
|
v********o
发帖数: 67 | 48 这个convex hull定义不是这样的吧，你看(0，0)(1，1)(1.1,0)(1,-1)也是convex
hull，但其余三点(0，0)的距离不是两边小于中间啊 |
|
b*****1
发帖数: 23 | 49 感觉难度不亚于G
第一题
2D matrix 1D形式的transpose O(1) space.
比如 [1, 2, 3, 4, 5, 6]表示
[1, 2, 3]
[4, 5, 6]
转置后
[1, 4]
[2, 5]
[3, 6]
返回
[1, 4, 2, 5, 3, 6]
完全不会
第二题 convex hull
勉强写了code
但是面试官都是manager级的，说convex hull的时候她们也不太懂，不知道想什么 |
|
m*******a
发帖数: 2947 | 50 嘿，我以前还真的有个算法解决的就是这个问题，如果这个函数是convex的话，有唯一
的快速算法。
可惜社会问题本身太复杂，不可能是convex的，而且utility不好定义。 |
|
