由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 被简单题给虐了。
相关主题
严格单调递增的最长子序列Leetcode 新题max points on a line
一道 facebook 电面题F家题请教
一朋友被Google的电面干掉了 (转载)google题
fb电面第一轮最长递增子array的算法
Maximum Sum of Increasing Sequencecareer cup book v4 9.7 题
面试题count # of increasing subsequences of String求解问个算法题5
微软:求一个数列中最长单调上升子列,要求O(nlogn)时间问一个经典题
说一个我自己用的题吧Longest Increasing Subsequence O(NLOG(N)) 解法
相关话题的讨论汇总
话题: me话题: longest话题: x0话题: increasing
进入JobHunting版参与讨论
1 (共1页)
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?
相关主题
面试题count # of increasing subsequences of String求解Leetcode 新题max points on a line
微软:求一个数列中最长单调上升子列,要求O(nlogn)时间F家题请教
说一个我自己用的题吧google题
进入JobHunting版参与讨论
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 的大作中提到】
: 你这样说搞的大家都很紧张的。
相关主题
最长递增子array的算法问一个经典题
career cup book v4 9.7 题Longest Increasing Subsequence O(NLOG(N)) 解法
问个算法题5数组里找最大集合,该集合排序后是序列,有漂亮解法么?
进入JobHunting版参与讨论
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
27
http://www.mitbbs.com/article_t0/JobHunting/32697579.html

【在 y***n 的大作中提到】
: 能不能推荐一下可以练手的小公司,最好和高考模拟卷一样,题型一样。
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无法求出该答案 -- 或者说我不知道怎
么得出答案:)
相关主题
看到一个longest increasing subsequence挺有意思的算法一道 facebook 电面题
分享Imo电面题一朋友被Google的电面干掉了 (转载)
严格单调递增的最长子序列fb电面第一轮
进入JobHunting版参与讨论
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吗?
相关主题
fb电面第一轮微软:求一个数列中最长单调上升子列,要求O(nlogn)时间
Maximum Sum of Increasing Sequence说一个我自己用的题吧
面试题count # of increasing subsequences of String求解Leetcode 新题max points on a line
进入JobHunting版参与讨论
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
42
mark
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:时间复杂度是多少?

1 (共1页)
进入JobHunting版参与讨论
相关主题
Longest Increasing Subsequence O(NLOG(N)) 解法Maximum Sum of Increasing Sequence
数组里找最大集合,该集合排序后是序列,有漂亮解法么?面试题count # of increasing subsequences of String求解
看到一个longest increasing subsequence挺有意思的算法微软:求一个数列中最长单调上升子列,要求O(nlogn)时间
分享Imo电面题说一个我自己用的题吧
严格单调递增的最长子序列Leetcode 新题max points on a line
一道 facebook 电面题F家题请教
一朋友被Google的电面干掉了 (转载)google题
fb电面第一轮最长递增子array的算法
相关话题的讨论汇总
话题: me话题: longest话题: x0话题: increasing