m*****n 发帖数: 2152 | 1 现在还不会,怎么办?
二维平面上面n个点,要求找出一个最多点的集合,满足集合中任意两点的连线的斜率
大于等于0,返回这个集合中点的个数。
要求写code,时间复杂度 nlog(n)。
加个hint,说白就是两个点i和j,当x_i >= x_j的时候,y_i >= y_j,等号不同时成立。
follow up:三维空间的时候,怎么办?m维空间的时候怎么办? |
l*********8 发帖数: 4642 | 2 longest increasing subsequence? |
T*******e 发帖数: 4928 | 3 I think so. sort by x. 然后用longest increasing subsequence 的greedy解法.
【在 l*********8 的大作中提到】 : longest increasing subsequence?
|
m********o 发帖数: 26 | 4 大于3个点的时候,满足的集合只能是大部分点共线了吧。
立。
【在 m*****n 的大作中提到】 : 现在还不会,怎么办? : 二维平面上面n个点,要求找出一个最多点的集合,满足集合中任意两点的连线的斜率 : 大于等于0,返回这个集合中点的个数。 : 要求写code,时间复杂度 nlog(n)。 : 加个hint,说白就是两个点i和j,当x_i >= x_j的时候,y_i >= y_j,等号不同时成立。 : follow up:三维空间的时候,怎么办?m维空间的时候怎么办?
|
g*********e 发帖数: 14401 | 5
re
【在 l*********8 的大作中提到】 : longest increasing subsequence?
|
g*********e 发帖数: 14401 | 6
立。
三维空间斜率怎么表示?
【在 m*****n 的大作中提到】 : 现在还不会,怎么办? : 二维平面上面n个点,要求找出一个最多点的集合,满足集合中任意两点的连线的斜率 : 大于等于0,返回这个集合中点的个数。 : 要求写code,时间复杂度 nlog(n)。 : 加个hint,说白就是两个点i和j,当x_i >= x_j的时候,y_i >= y_j,等号不同时成立。 : follow up:三维空间的时候,怎么办?m维空间的时候怎么办?
|
m*****n 发帖数: 2152 | 7 我的理解是x_i>=x_j && y_i >= y_j && z_i>=z_j。
【在 g*********e 的大作中提到】 : : 立。 : 三维空间斜率怎么表示?
|
g*********e 发帖数: 14401 | 8
cc150上有一道叠箱子的题目跟这差不多。
【在 m*****n 的大作中提到】 : 我的理解是x_i>=x_j && y_i >= y_j && z_i>=z_j。
|
b***y 发帖数: 177 | 9 为什么你觉着这题简单呢?
立。
【在 m*****n 的大作中提到】 : 现在还不会,怎么办? : 二维平面上面n个点,要求找出一个最多点的集合,满足集合中任意两点的连线的斜率 : 大于等于0,返回这个集合中点的个数。 : 要求写code,时间复杂度 nlog(n)。 : 加个hint,说白就是两个点i和j,当x_i >= x_j的时候,y_i >= y_j,等号不同时成立。 : follow up:三维空间的时候,怎么办?m维空间的时候怎么办?
|
g*********e 发帖数: 14401 | 10
大牛 看你这么多贴 感觉你的水平 flgt随便灭了 赶紧出手吧
【在 l*********8 的大作中提到】 : longest increasing subsequence?
|
|
|
l***i 发帖数: 1309 | 11 同意glowinglake,这个做题水平比flg的bar还高一些吧。估计要上ACM ICPC的
interviewer才能测出水平了。 |
y***n 发帖数: 1594 | 12 觉得你很厉害。。
【在 l*********8 的大作中提到】 : longest increasing subsequence?
|
h**6 发帖数: 4160 | 13 多维空间时,分别对每一维坐标排序,得到M个数组,把其中一个数组标为1,2,3...n,
别的数组与之求longest common subsequence可以转化为longest increasing
subsequence,最终复杂度O(Mnlog(n))。 |
f********x 发帖数: 2086 | 14
大牛一语中的
【在 l*********8 的大作中提到】 : longest increasing subsequence?
|
a**********0 发帖数: 422 | 15 我猜你的意思是按照x排序之后 再找longest increasing subsequence吧
【在 l*********8 的大作中提到】 : longest increasing subsequence?
|
l*********8 发帖数: 4642 | 16 谢谢大家鼓励!
不过我已经被flg都拒了,关小黑屋呢。。。 现在我都不敢投了。 再准备一下吧。
在bbs上看题跟面试还是不一样。 bbs上心情放松些。 面试的时候,两三分钟没好的思
路就紧张了。
【在 g*********e 的大作中提到】 : : 大牛 看你这么多贴 感觉你的水平 flgt随便灭了 赶紧出手吧
|
l*********8 发帖数: 4642 | 17 yes, like what TimeValue said.
【在 a**********0 的大作中提到】 : 我猜你的意思是按照x排序之后 再找longest increasing subsequence吧
|
y***n 发帖数: 1594 | 18 你这样说搞的大家都很紧张的。
【在 l*********8 的大作中提到】 : 谢谢大家鼓励! : 不过我已经被flg都拒了,关小黑屋呢。。。 现在我都不敢投了。 再准备一下吧。 : 在bbs上看题跟面试还是不一样。 bbs上心情放松些。 面试的时候,两三分钟没好的思 : 路就紧张了。
|
a**********0 发帖数: 422 | 19 我也觉得他很牛
【在 y***n 的大作中提到】 : 你这样说搞的大家都很紧张的。
|
l*********8 发帖数: 4642 | 20 平常练习要多些紧迫感。 面试的时候,就算暂时不顺利,也争取保持好心态。
【在 y***n 的大作中提到】 : 你这样说搞的大家都很紧张的。
|
|
|
y***n 发帖数: 1594 | 21 你的背景如何?有时候感觉没有好的学校或工作经历就会被问得很惨。 |
l*********8 发帖数: 4642 | 22 恩,可能跟我背景不强有关。
【在 y***n 的大作中提到】 : 你的背景如何?有时候感觉没有好的学校或工作经历就会被问得很惨。
|
c*******y 发帖数: 98 | 23 花了几个小时勉强写出第一问,高维的还要改code structure。要是面试都这样我真的
没法投了。 |
m*****n 发帖数: 2152 | 24 高维为什么要改structure?
用两维的套不可以吗?
【在 c*******y 的大作中提到】 : 花了几个小时勉强写出第一问,高维的还要改code structure。要是面试都这样我真的 : 没法投了。
|
l*****a 发帖数: 14598 | 25 can't agree more
现场做题跟在这里随便说说差别/自己做LC差别还是太大了
所以需要先找小公司练手,找感觉
【在 l*********8 的大作中提到】 : 谢谢大家鼓励! : 不过我已经被flg都拒了,关小黑屋呢。。。 现在我都不敢投了。 再准备一下吧。 : 在bbs上看题跟面试还是不一样。 bbs上心情放松些。 面试的时候,两三分钟没好的思 : 路就紧张了。
|
y***n 发帖数: 1594 | 26 能不能推荐一下可以练手的小公司,最好和高考模拟卷一样,题型一样。 |
l*****a 发帖数: 14598 | |
l*********8 发帖数: 4642 | 28 三维或者更高维空间没有“斜率”的定义。 面试官可能指的是高维空间的直线在每个
二维空间上的投影的斜率, 也就是你说的这样。
【在 m*****n 的大作中提到】 : 我的理解是x_i>=x_j && y_i >= y_j && z_i>=z_j。
|
l*********8 发帖数: 4642 | 29 请问是哪道叠箱子的题目? 在oj上吗?
【在 g*********e 的大作中提到】 : : 大牛 看你这么多贴 感觉你的水平 flgt随便灭了 赶紧出手吧
|
l*********8 发帖数: 4642 | 30 han6大牛,好像有些问题。
以三维空间为例:
假如x,y坐标对应的数组分别如下:
1 2 3 4
3 2 4 1
1 2 4 3
答案应该是x坐标最小的第一个和第三个,但LCS无法求出该答案 -- 或者说我不知道怎
么得出答案:) |
|
|
l*********8 发帖数: 4642 | 31 我知道了,我搞错了。 学习了。
【在 l*********8 的大作中提到】 : han6大牛,好像有些问题。 : 以三维空间为例: : 假如x,y坐标对应的数组分别如下: : 1 2 3 4 : 3 2 4 1 : 1 2 4 3 : 答案应该是x坐标最小的第一个和第三个,但LCS无法求出该答案 -- 或者说我不知道怎 : 么得出答案:)
|
m*****n 发帖数: 2152 | 32 完全被虐死了,中间恨不得把电话给扔了。
下面说说过程,首先说明,全程面试官从来没说过我的任何回答是对还是错,我下面的
回答可能很多是错的。
一个西亚或者印度(口音不太像)面试官 A,一开始聊了一下background,然后丫说先
给你一道简单题做做吧,就是一楼的题。
一开始,听到二维平面,最多点,斜率,还以为是那到最多点共线的问题呢?心中一喜
,然后自己重复问题的时候,A 感觉完全不知道我在说什么。丫又重复了一遍问题,这
时才听懂。
当时第一反应是对一个维度排序,然后DP,说给A听了。
A:时间复杂度是多少?
me: O(n^2)
A: 不行,要nlog(n)。
me: (心理一紧,完蛋了,DP都不行)嘴上说好像可以剪枝。
A: How?
me: (心理说我怎么知道),胡说半天,说什么用tree啦,找parent啦,连我自己都不知
道在说什么。
A: 好吧,假设你有2维的nlogn的算法了,3维怎么办?
me: 先找一个2维最多的点集,再对这个点集的第3维在做一次这个算法。
A: M维怎么办?
me: 依次类推。
A: 时间复杂度多少?
me: 大概是最坏是m*n*logn吧。
A: 太慢了,你能不能再想办法提高速度。
me: (心理想,我连nlogn的算法都不知道,怎么提高速度,刚想回答不知道,突然想
到)可以并行。
A: 怎么并行?
me: 比如3维 (x0,x1)和(x0,x2)分别找,然后求交集。
A: M维的时候,怎么办?
me: 一样啊,(x0, x1),(x0, x2), (x0, x3)....(x0, xm),然后求交集。
A: 你要多少个并行?
me: M-1个。
A: 用什么design pattern?
me: boss/employer, peer, blablabla。
A: 要减少并行规模,你有什么方法吗?
me: (想了半天)可以减到M/2个,比如(x0, x1), (x2, x3).... ,然后再交集。
A: 还是太高了,还有什么方法?
me: (想了半天)可以((x0,x1),x2),((x3,x4),x5)之类的,
A: 用的什么design pattern?
me: pipeline(废话,唯一一个没说的)。
A: 如果处理过程中,突然加一个维度,怎么办?
me: 再多做一遍呗。
A: 如果处理过程中,突然想drop掉其中一维不用,怎么办?
me: (想扔电话了)那部分的job重新做。
A: 如果n太大,不能一次读入,怎么办?
me: 分块读入,然后再做。
A: 说的具体点....
me: (想把电话扔到丫脸上去)blabla,我都不知道自己胡说些什么。
然后又聊了一下别的,就结束了。 |
b***y 发帖数: 177 | 33 靠,他自己不知道答案,能答出来吗?更别说电话上
【在 m*****n 的大作中提到】 : 完全被虐死了,中间恨不得把电话给扔了。 : 下面说说过程,首先说明,全程面试官从来没说过我的任何回答是对还是错,我下面的 : 回答可能很多是错的。 : 一个西亚或者印度(口音不太像)面试官 A,一开始聊了一下background,然后丫说先 : 给你一道简单题做做吧,就是一楼的题。 : 一开始,听到二维平面,最多点,斜率,还以为是那到最多点共线的问题呢?心中一喜 : ,然后自己重复问题的时候,A 感觉完全不知道我在说什么。丫又重复了一遍问题,这 : 时才听懂。 : 当时第一反应是对一个维度排序,然后DP,说给A听了。 : A:时间复杂度是多少?
|
d**k 发帖数: 797 | 34 什么公司?
下次我绕着走
立。
【在 m*****n 的大作中提到】 : 现在还不会,怎么办? : 二维平面上面n个点,要求找出一个最多点的集合,满足集合中任意两点的连线的斜率 : 大于等于0,返回这个集合中点的个数。 : 要求写code,时间复杂度 nlog(n)。 : 加个hint,说白就是两个点i和j,当x_i >= x_j的时候,y_i >= y_j,等号不同时成立。 : follow up:三维空间的时候,怎么办?m维空间的时候怎么办?
|
y***n 发帖数: 1594 | 35 每个公司都有这样的人,你这么办?
这个不是公司,是人的问题。 |
c**********9 发帖数: 12 | 36 same ask.
【在 d**k 的大作中提到】 : 什么公司? : 下次我绕着走 : : 立。
|
d**k 发帖数: 797 | 37 那你说怎么办
打电话给recruiter complain面试官?
说他问题不明确,态度不友好,要求随时变?
【在 y***n 的大作中提到】 : 每个公司都有这样的人,你这么办? : 这个不是公司,是人的问题。
|
P**********k 发帖数: 1629 | 38 sort (xi, yi) based on xi,
then find the longest increasing subsequence in {yi}...
立。
【在 m*****n 的大作中提到】 : 现在还不会,怎么办? : 二维平面上面n个点,要求找出一个最多点的集合,满足集合中任意两点的连线的斜率 : 大于等于0,返回这个集合中点的个数。 : 要求写code,时间复杂度 nlog(n)。 : 加个hint,说白就是两个点i和j,当x_i >= x_j的时候,y_i >= y_j,等号不同时成立。 : follow up:三维空间的时候,怎么办?m维空间的时候怎么办?
|
U***A 发帖数: 849 | 39 这个算法的复杂度应该是n^2吗?
【在 T*******e 的大作中提到】 : I think so. sort by x. 然后用longest increasing subsequence 的greedy解法.
|
c*******r 发帖数: 610 | 40 先对X坐标或者Y坐标排序,然后用patience sort 对Y 坐标(X坐标) 求longest
increasing subsequence 的长度吧
排序O(nlogn)
LIS with patience sorting O(nlogn). http://wordaligned.org/articles/patience-sort.html
电面要求这样的复杂度有点要求太高了吧。
除非还有更加有效的几何解法?
【在 U***A 的大作中提到】 : 这个算法的复杂度应该是n^2吗?
|
|
|
U***A 发帖数: 849 | 41 这是哪个变态公司啊?
【在 c*******r 的大作中提到】 : 先对X坐标或者Y坐标排序,然后用patience sort 对Y 坐标(X坐标) 求longest : increasing subsequence 的长度吧 : 排序O(nlogn) : LIS with patience sorting O(nlogn). http://wordaligned.org/articles/patience-sort.html : 电面要求这样的复杂度有点要求太高了吧。 : 除非还有更加有效的几何解法?
|
c****l 发帖数: 1280 | |
s*******n 发帖数: 196 | 43 LIS 有nlog(n) 算法.
【在 c*******r 的大作中提到】 : 先对X坐标或者Y坐标排序,然后用patience sort 对Y 坐标(X坐标) 求longest : increasing subsequence 的长度吧 : 排序O(nlogn) : LIS with patience sorting O(nlogn). http://wordaligned.org/articles/patience-sort.html : 电面要求这样的复杂度有点要求太高了吧。 : 除非还有更加有效的几何解法?
|
r*******k 发帖数: 1423 | 44 你挺牛了
心理素质真好
【在 m*****n 的大作中提到】 : 完全被虐死了,中间恨不得把电话给扔了。 : 下面说说过程,首先说明,全程面试官从来没说过我的任何回答是对还是错,我下面的 : 回答可能很多是错的。 : 一个西亚或者印度(口音不太像)面试官 A,一开始聊了一下background,然后丫说先 : 给你一道简单题做做吧,就是一楼的题。 : 一开始,听到二维平面,最多点,斜率,还以为是那到最多点共线的问题呢?心中一喜 : ,然后自己重复问题的时候,A 感觉完全不知道我在说什么。丫又重复了一遍问题,这 : 时才听懂。 : 当时第一反应是对一个维度排序,然后DP,说给A听了。 : A:时间复杂度是多少?
|