https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=463515
follow up是如果你是A,就是第一个选node的人,你选择哪个node可以赢。follow up只说了想法没有写code,优化到O(n)
第二轮是典型背包问题,给一些task,以及每个task的priority和需要用cpu的个数,假设有10个cpu,
求问能达到的最大priority的和,follow up是返回这个combination
第三轮是leetcode扒以吴,我用的bfs,问了下怎么优化hashmap少用一点空间,没想出来
第四轮是给两个string,source和target,求问最少需要repeat source几次才可以得到target,repeat完的string可以删除任意character。先是暴力解然后优化的。
报个timeline,9月中旬内推,9.25收到OA,10月底收到onsite,11.19面,12.6通知过hc
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=491317
我发现面试官都要把我的代码在电脑里记录下来,他们说feedback的时候要填。第五轮iterator那一轮,我和面试官讨论的比较多,在白板上把代码改的乱七八糟的,最后面试官照了一张白板的照片走了, 我感觉他回去之后也懒得去仔细看了,这轮要栽的样子。
楼主,按照定理来说,他给的这个离散点矩阵,其中任意一个点,在这个矩阵中都能找到一个点,把这个矩阵一分为二,对于每一个新的点,按照我刚post上去的数学公式判断是否在上边或者下边,就可以了,这样时间复杂度就是O(N^2)
follow up是如果你是A,就是第一个选node的人,你选择哪个node可以赢。follow up只说了想法没有写code,优化到O(n)
第二轮是典型背包问题,给一些task,以及每个task的priority和需要用cpu的个数,假设有10个cpu,
求问能达到的最大priority的和,follow up是返回这个combination
第三轮是leetcode扒以吴,我用的bfs,问了下怎么优化hashmap少用一点空间,没想出来
第四轮是给两个string,source和target,求问最少需要repeat source几次才可以得到target,repeat完的string可以删除任意character。先是暴力解然后优化的。
报个timeline,9月中旬内推,9.25收到OA,10月底收到onsite,11.19面,12.6通知过hc
四轮都是华人面孔 第一轮是一个国人妹子,一上来愉快地闲聊了一会,然后到时间开始coding。有一个game是在binary tree里occupy尽可能多的node算是胜利, 有玩家A和B,除了第一次每一次只能选择和自己选过的node相连的node,假设已知A选择的node,求问B应该选择哪个node才能occupy最多的node。 | 想问一下第一题就是算出左子树,右子树,以及整个树的节点-左-右=父节点的节点树,最后选取最大的吗 | 请问一下第二题DP以后怎么找最佳方案的combination呢? | 我没想出来如何从DP的三维数组中找到这个path。只有再次DFS了 | dp在计算的时候同时要记录你的最佳值的来源。这样最后可以从dp[item][cpu]倒着推回去。 |
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=491317
- 一个坐标系,上面有一堆的点point(x, y), 选出其中的两个点,这两个点连成的线,可以把坐标系里的点分成两半,两边的点的个数相同。这位大哥的口音太重了,我跟他交流的过程中完全听不太懂。先提出了暴力解法,最后再提示下想到了优化的方法:找出bottom left most point, 固定这个点选出的线,肯定能平分两半。
- 一个tic-tac-toe游戏,输出所有可能的结果,具体输出什么样子自己定义。我是把所有的结果都encode成string.
- 这轮算是唯一幸运的一轮了,面经中的那个MyLogger, 有个startTime, endTime. 最后按顺序把log打印出来
- 午餐
- 设计一个iterator. ['foo', 'foo', 'foo', 'bar] 第一个next() 返回('foo', 3). 再call 一遍 next(), 返回(‘bar', 1)
- reducieble string. 这轮我也没怎么搞明白,对不住大家了。
我发现面试官都要把我的代码在电脑里记录下来,他们说feedback的时候要填。第五轮iterator那一轮,我和面试官讨论的比较多,在白板上把代码改的乱七八糟的,最后面试官照了一张白板的照片走了, 我感觉他回去之后也懒得去仔细看了,这轮要栽的样子。
第二轮是所有有一方win的结果吗?
是的,有win, 或者平局。invalid的局不考虑,比如说Player1已经赢了,Player2还在继续下
请问第一题怎么判断点在线的上部还是下部呢?
我没写完,面试官说这个helper function可以不用写,估计是嫌我太慢了吧
| |
这一题我后来仔细写了一下,终于理解了烙印给的提示, 最下面最左边的点,可以保证其余点在这个点的一侧,然后对其余所有点按照斜率排序,如果斜率<0, 则 加上一个非常大的数,然后取中值,则一定满足条件。 完全不用写判断在哪侧的函数...
附上代码和测试用例。 测试用例我随即了1000次,每次随即100个点, 用leetcode maxpoint on one line的方法保证没有三个点在同一直线。测试用例全过。
我取了最下面最左边的点作为start point,保证了其余所有点在上半侧,然后将其余点按照斜率排序(注意负数加上一个很大的数保证),然后去中点。为了测试,我加上了判断哪侧的函数,实际这个函数用不到。
补充内容 (2019-3-7 14:55):
如果按照烙印的说法最左边最下面的点,那么斜率是负数似乎也不用加一个很大的值,直接按照斜率排序就好。
总的来说,这题刚出来很容易被这个"判断哪侧"搞慌...但是换个思路就柳暗花明了。
def
split_points(points):
# 去最左边最下面的点
st
=
[
1
<<
32
,
1
<<
32
]
st_idx
=
None
for
i, (px, py)
in
enumerate
(points):
if
px < st[
0
]
or
px
=
=
st[
0
]
and
py < st[
1
]:
st
=
px, py
st_idx
=
i
points.pop(st_idx)
INF
=
1
<<
31
def
cmp
(p):
k
=
(p[
1
]
-
st[
1
])
*
1.0
/
(p[
0
]
-
st[
0
])
if
p[
0
] !
=
st[
0
]
else
INF
return
k
# 按照斜率排序
points
=
sorted
(points, key
=
cmp
)
mid
=
points[
len
(points)
/
2
]
return
st, mid