logo
Redian新闻
>未名空间
>pets - 心有所宠
>
喵窝招志愿者哦
avatar
喵窝招志愿者哦# pets - 心有所宠
c*5
1 楼
一周前在狗狗MTV面的onsite，求一下bless
一面 白男 popular number
还好面试前的晚上看到了这题，用sliding window 和 在几个指定位置进行二分查找的
方式做了，中间进行了一些优化方面的讨论
二面 白男
矩阵寻找和最大的路径，从左上角到右下角，每一步都可以向左向右或者向下，但不可
以回头
开始用dp做，但是发现有难度，马上改成用dfs做，写完后拍照，问了一下复杂度，我
说指数级，这时还有好多时间，讨论了一下dp的做法，在提示下写了recurrence，最后
又拍一次，感觉这一轮要崩
三面 白男 加 国男 shadow （听说是什么reverse shadow，不懂什么意思）
给一个很大的文件，按行读取，把每一行的文本根据当前行第二个字符的值存到对应的
文件中，用map reduce写了简单代码，主要是在讨论，给了很多情况，面试官好像满意
四面 老印
给一个很大矩阵，判断矩阵中有多少3*3的矩阵满足行列对角线和相等http://en.wikipedia.org/wiki/Magic_square，讨论了一下解法，我说有比较快的做法，老印说不用，就用最简单的写，写完后指出了两个错误改了，这一轮感觉也不太好，题目比较简单疑似被黑
recruiter 说这周送hire committee
求bless！
avatar
s*7
2 楼
OC irvine 短租1B1B, 2005新房。生活方便，步行去大华。带洗衣机烘干机，家具，
拎包即可入住，房东女。月费$550包水电网煤。
可提供折叠床和写字台。
希望是卫生习惯良好，无不良嗜好，女生。
有兴趣的请联系我: 8509804103。
谢谢～
avatar
m*g
3 楼
只要你有下面任何一个特长都可以申请加入喵窝的队伍。
1. 中文或者英文写作，帮助我们推广领养平台和科学喂养理念
2. accounting，救助医疗捐助之类款项做帐
3. front line救助，第一线救助人员
4. 运输，帮忙做food drive
5. events coordinator，帮助组织领养等活动
6. public relations，帮助我们跟其他组织合作，跟媒体建立关系
还有如果你有其他特长，也可以跟我们联络。在线填表http://meowroof.org/volunteer/，或者直接微信DaphneMeow 联系。喵窝欢迎你的加入。
avatar
f*l
4 楼
Big Bless
avatar
b*n
5 楼
帮楼主顶一下
avatar
F*7
6 楼
友情支持一下。
avatar
c*n
7 楼
最后一题除了 NxN 个 小方形都检查一遍， 还有什么更快的办法？ 即使有快， 那
个小方形是固定的， 只不过差个常数而已

【在 c********5 的大作中提到】
: 一周前在狗狗MTV面的onsite，求一下bless
: 一面 白男 popular number
: 还好面试前的晚上看到了这题，用sliding window 和 在几个指定位置进行二分查找的
: 方式做了，中间进行了一些优化方面的讨论
: 二面 白男
: 矩阵寻找和最大的路径，从左上角到右下角，每一步都可以向左向右或者向下，但不可
: 以回头
: 开始用dp做，但是发现有难度，马上改成用dfs做，写完后拍照，问了一下复杂度，我
: 说指数级，这时还有好多时间，讨论了一下dp的做法，在提示下写了recurrence，最后
: 又拍一次，感觉这一轮要崩
avatar
S*p
8 楼
支持
avatar
c*n
9 楼
bless!一定行

【在 c********5 的大作中提到】
: 一周前在狗狗MTV面的onsite，求一下bless
: 一面 白男 popular number
: 还好面试前的晚上看到了这题，用sliding window 和 在几个指定位置进行二分查找的
: 方式做了，中间进行了一些优化方面的讨论
: 二面 白男
: 矩阵寻找和最大的路径，从左上角到右下角，每一步都可以向左向右或者向下，但不可
: 以回头
: 开始用dp做，但是发现有难度，马上改成用dfs做，写完后拍照，问了一下复杂度，我
: 说指数级，这时还有好多时间，讨论了一下dp的做法，在提示下写了recurrence，最后
: 又拍一次，感觉这一轮要崩
avatar
T*e
10 楼
顶。
avatar
c*5
11 楼
这道题我记得一个生成magic square的算法，我跟烙印说生成以后就四种情况，然后当
做pattern去match就可以了，这样每次匹配都可以算作是O(1)，烙印说假设我们不知道
这个算法

【在 c******n 的大作中提到】
: 最后一题除了 NxN 个 小方形都检查一遍， 还有什么更快的办法？ 即使有快， 那
: 个小方形是固定的， 只不过差个常数而已
avatar
f*p
12 楼
可以欺负猫咪么！？...
avatar
n*n
13 楼
向左向右或向下，不就是可以回头吗？

【在 c********5 的大作中提到】
: 一周前在狗狗MTV面的onsite，求一下bless
: 一面 白男 popular number
: 还好面试前的晚上看到了这题，用sliding window 和 在几个指定位置进行二分查找的
: 方式做了，中间进行了一些优化方面的讨论
: 二面 白男
: 矩阵寻找和最大的路径，从左上角到右下角，每一步都可以向左向右或者向下，但不可
: 以回头
: 开始用dp做，但是发现有难度，马上改成用dfs做，写完后拍照，问了一下复杂度，我
: 说指数级，这时还有好多时间，讨论了一下dp的做法，在提示下写了recurrence，最后
: 又拍一次，感觉这一轮要崩
avatar
n*n
14 楼
你是假定1到9排列？全0矩阵算吗？

【在 c********5 的大作中提到】
: 这道题我记得一个生成magic square的算法，我跟烙印说生成以后就四种情况，然后当
: 做pattern去match就可以了，这样每次匹配都可以算作是O(1)，烙印说假设我们不知道
: 这个算法
avatar
c*n
15 楼
可以说一下第一题是什么意思吗？

【在 c********5 的大作中提到】
: 一周前在狗狗MTV面的onsite，求一下bless
: 一面 白男 popular number
: 还好面试前的晚上看到了这题，用sliding window 和 在几个指定位置进行二分查找的
: 方式做了，中间进行了一些优化方面的讨论
: 二面 白男
: 矩阵寻找和最大的路径，从左上角到右下角，每一步都可以向左向右或者向下，但不可
: 以回头
: 开始用dp做，但是发现有难度，马上改成用dfs做，写完后拍照，问了一下复杂度，我
: 说指数级，这时还有好多时间，讨论了一下dp的做法，在提示下写了recurrence，最后
: 又拍一次，感觉这一轮要崩
avatar
c*5
16 楼
在特定的一条路径中，走过的地方不能再走了，但是没走过的地方可以左右或者向下
举个例子：
1 1 1 0 0
0 0 1 0 0
0 1 1 0 0
0 1 0 0 0
0 1 1 1 1

【在 n******n 的大作中提到】
: 向左向右或向下，不就是可以回头吗？
avatar
c*5
17 楼
magic square就是说1到n^2,所以这道题里面需要检查矩阵里是不是1到9各出现一次

【在 n******n 的大作中提到】
: 你是假定1到9排列？全0矩阵算吗？
avatar
c*5
18 楼
给定一个有序数组，长度n，判断里面是否有一个数字出现的次数大于n/4次

【在 c******n 的大作中提到】
: 可以说一下第一题是什么意思吗？
avatar
n*n
19 楼
听着就是数独加强版？

【在 c********5 的大作中提到】
: magic square就是说1到n^2,所以这道题里面需要检查矩阵里是不是1到9各出现一次
avatar
S*5
20 楼
bless，楼主加油
avatar
c*5
21 楼
感觉难度差不多

【在 n******n 的大作中提到】
: 听着就是数独加强版？
avatar
c*5
22 楼
感谢！

【在 S**********5 的大作中提到】
: bless，楼主加油
avatar
l*c
23 楼
bless，楼主拿大offer！
avatar
S*w
24 楼
这什么题
popular number
avatar
S*w
25 楼
dp还是可以的
比较烦点

【在 c********5 的大作中提到】
: 这道题我记得一个生成magic square的算法，我跟烙印说生成以后就四种情况，然后当
: 做pattern去match就可以了，这样每次匹配都可以算作是O(1)，烙印说假设我们不知道
: 这个算法
avatar
c*5
26 楼
在一个长度为n的有序数组里寻找是否有一个数出线次数大于n/4次
请问你拿到狗狗offer了吗？

【在 S***w 的大作中提到】
: 这什么题
: popular number
avatar
c*5
27 楼
怎么dp啊？ 每个窗口应该还是要扫描的？

【在 S***w 的大作中提到】
: dp还是可以的
: 比较烦点
avatar
S*w
28 楼
对行
A[i][j] 表示 Matrix[i][j] + Matrix[i][j + 1] + Matrix[i][j + 2]的和
A[i][j+1] = A[i][j] + Matrix[i][j + 3] - Matrix[i][j]
这样就不用重复计算了
对列也有
对角线复杂点
avatar
S*w
29 楼
bless

【在 c********5 的大作中提到】
: 一周前在狗狗MTV面的onsite，求一下bless
: 一面 白男 popular number
: 还好面试前的晚上看到了这题，用sliding window 和 在几个指定位置进行二分查找的
: 方式做了，中间进行了一些优化方面的讨论
: 二面 白男
: 矩阵寻找和最大的路径，从左上角到右下角，每一步都可以向左向右或者向下，但不可
: 以回头
: 开始用dp做，但是发现有难度，马上改成用dfs做，写完后拍照，问了一下复杂度，我
: 说指数级，这时还有好多时间，讨论了一下dp的做法，在提示下写了recurrence，最后
: 又拍一次，感觉这一轮要崩
avatar
S*w
30 楼
没有
lol
基本不能出错吧

【在 c********5 的大作中提到】
: 在一个长度为n的有序数组里寻找是否有一个数出线次数大于n/4次
: 请问你拿到狗狗offer了吗？
avatar
S*w
31 楼
你用sliding window?
lintcode有类似题目 majority number,
挺巧的 O(N)

【在 c********5 的大作中提到】
: 在一个长度为n的有序数组里寻找是否有一个数出线次数大于n/4次
: 请问你拿到狗狗offer了吗？
avatar
c*5
32 楼
我用的二分查找，这个跟majority number不太一样，这道题是有序数组，不太需要用
voting的算法
这里是在n/4 2n/4 3n/4的位置做二分查找，如果存在popular number的话，一定在这
几个位置会出现
希望不要这么崩吧，一点错误都不能犯

【在 S***w 的大作中提到】
: 你用sliding window?
: lintcode有类似题目 majority number,
: 挺巧的 O(N)
avatar
S*w
33 楼
你这个怎么做的？
找到 3n/4的数， 再二分着 起点，终点， 看是否 > 4/n?
n/4, n/2 类似?

【在 c********5 的大作中提到】
: 我用的二分查找，这个跟majority number不太一样，这道题是有序数组，不太需要用
: voting的算法
: 这里是在n/4 2n/4 3n/4的位置做二分查找，如果存在popular number的话，一定在这
: 几个位置会出现
: 希望不要这么崩吧，一点错误都不能犯
avatar
c*n
34 楼
我觉得你那个o(1) 跟最直接的办法区别其实就是 o(9) vs (1), 只差常数而已

【在 c********5 的大作中提到】
: 这道题我记得一个生成magic square的算法，我跟烙印说生成以后就四种情况，然后当
: 做pattern去match就可以了，这样每次匹配都可以算作是O(1)，烙印说假设我们不知道
: 这个算法
avatar
c*5
35 楼
哦对，想起来了，当时和面试官讨论过时间复杂度的问题，就是O(mn)，时间久了有点
不记得了

【在 c******n 的大作中提到】
: 我觉得你那个o(1) 跟最直接的办法区别其实就是 o(9) vs (1), 只差常数而已
avatar
c*5
36 楼
是的，假设从第一个数开始就是popular那么到n/4这个位置也一定是，假设n/4位置的
数不是popular，那么下一个可能的位置就是n/2

【在 S***w 的大作中提到】
: 你这个怎么做的？
: 找到 3n/4的数， 再二分着 起点，终点， 看是否 > 4/n?
: n/4, n/2 类似?
avatar
S*w
37 楼
super smart

【在 c********5 的大作中提到】
: 是的，假设从第一个数开始就是popular那么到n/4这个位置也一定是，假设n/4位置的
: 数不是popular，那么下一个可能的位置就是n/2
avatar
S*w
38 楼
直接 不止9吧

【在 c******n 的大作中提到】
: 我觉得你那个o(1) 跟最直接的办法区别其实就是 o(9) vs (1), 只差常数而已
avatar
t*3
39 楼
bless.

【在 c********5 的大作中提到】
: 一周前在狗狗MTV面的onsite，求一下bless
: 一面 白男 popular number
: 还好面试前的晚上看到了这题，用sliding window 和 在几个指定位置进行二分查找的
: 方式做了，中间进行了一些优化方面的讨论
: 二面 白男
: 矩阵寻找和最大的路径，从左上角到右下角，每一步都可以向左向右或者向下，但不可
: 以回头
: 开始用dp做，但是发现有难度，马上改成用dfs做，写完后拍照，问了一下复杂度，我
: 说指数级，这时还有好多时间，讨论了一下dp的做法，在提示下写了recurrence，最后
: 又拍一次，感觉这一轮要崩
avatar
n*n
40 楼
为何不能向上？

【在 c********5 的大作中提到】
: 在特定的一条路径中，走过的地方不能再走了，但是没走过的地方可以左右或者向下
: 举个例子：
: 1 1 1 0 0
: 0 0 1 0 0
: 0 1 1 0 0
: 0 1 0 0 0
: 0 1 1 1 1
avatar
c*5
41 楼
要求不能向上，如果向上的话也没多大差别，面试官的意思是要记录上一个的位置以便
确定下一步的可能走法

【在 n******n 的大作中提到】
: 为何不能向上？
avatar
S*w
42 楼
2 dp
不是很简单
还可以优化成 O(N) space, O(M * N) time

【在 c********5 的大作中提到】
: 一周前在狗狗MTV面的onsite，求一下bless
: 一面 白男 popular number
: 还好面试前的晚上看到了这题，用sliding window 和 在几个指定位置进行二分查找的
: 方式做了，中间进行了一些优化方面的讨论
: 二面 白男
: 矩阵寻找和最大的路径，从左上角到右下角，每一步都可以向左向右或者向下，但不可
: 以回头
: 开始用dp做，但是发现有难度，马上改成用dfs做，写完后拍照，问了一下复杂度，我
: 说指数级，这时还有好多时间，讨论了一下dp的做法，在提示下写了recurrence，最后
: 又拍一次，感觉这一轮要崩
avatar
c*5
43 楼
第二题怎么做啊？

【在 S***w 的大作中提到】
: 2 dp
: 不是很简单
: 还可以优化成 O(N) space, O(M * N) time
avatar
c*5
45 楼
实际上允许向左的话比这个复杂一些，二维dp恐怕解决不了
avatar
S*w
46 楼
噢 没看到向左

【在 c********5 的大作中提到】
: 实际上允许向左的话比这个复杂一些，二维dp恐怕解决不了
avatar
c*n
47 楼
N/k most frequent number, there is a published paper (within last 15 years)
google top k frequent problem
there are about 3--4 papers covering this topic.
if a number is guaranteed to have > N/k frequencies, max storage needed is k

【在 c********5 的大作中提到】
: 在一个长度为n的有序数组里寻找是否有一个数出线次数大于n/4次
: 请问你拿到狗狗offer了吗？
avatar
m*g
48 楼
谢谢分享，bless!
avatar
c*5
49 楼
Top k frequent不是另一道题吗

)
k

【在 c******n 的大作中提到】
: N/k most frequent number, there is a published paper (within last 15 years)
: google top k frequent problem
: there are about 3--4 papers covering this topic.
: if a number is guaranteed to have > N/k frequencies, max storage needed is k
avatar
c*n
50 楼
hehe, just search that paper as I said, u will see
it's the same as "majority number"

【在 c********5 的大作中提到】
: Top k frequent不是另一道题吗
:
: )
: k
avatar
c*5
51 楼
我看paper能力不太行，不过看起来data stream里面是无序的，那样的话是要用堆加
count的，只是时间复杂度做不到O(lgn)
这里是有序数组，如果是n/k的话时间复杂度O(klgn)，空间复杂度本来就是O(k)啊
这里这道题比paper里面的简单吧，如果是那道题我应该写不出完整代码的，heapify什
么都没有写过

【在 c******n 的大作中提到】
: hehe, just search that paper as I said, u will see
: it's the same as "majority number"
avatar
t*m
52 楼
同崩，move on吧

【在 c********5 的大作中提到】
: 我看paper能力不太行，不过看起来data stream里面是无序的，那样的话是要用堆加
: count的，只是时间复杂度做不到O(lgn)
: 这里是有序数组，如果是n/k的话时间复杂度O(klgn)，空间复杂度本来就是O(k)啊
: 这里这道题比paper里面的简单吧，如果是那道题我应该写不出完整代码的，heapify什
: 么都没有写过
avatar
c*5
53 楼
简直无情，最近没面试了啊

【在 t****m 的大作中提到】
: 同崩，move on吧
avatar
x*m
54 楼
感觉你回答也不差呀， 不知道为什么拒你
我昨天面了 G 有一轮感觉不好， 求 bless

【在 c********5 的大作中提到】
: 简直无情，最近没面试了啊
avatar
c*5
55 楼
说是feedback完全没问题，但hc觉得我代码不够好

【在 x****m 的大作中提到】
: 感觉你回答也不差呀， 不知道为什么拒你
: 我昨天面了 G 有一轮感觉不好， 求 bless
avatar
b*a
56 楼
第二题有问题吧
如果第一行从左到右第二行从右到左
这样依次下来不就所有格子都走到了？
avatar
r*x
57 楼
要最大路径和，全走到不能说明啥吧，如果有负数就囧了

【在 b********a 的大作中提到】
: 第二题有问题吧
: 如果第一行从左到右第二行从右到左
: 这样依次下来不就所有格子都走到了？
avatar
x*n
58 楼
没看懂。。。方便讲讲怎么排除一部分数字的？
我想到的最基本的解法：从左往右扫，判断nums[i] == num[i+n/4]。等于的话就是所
找的数了。

【在 S***w 的大作中提到】
: 你这个怎么做的？
: 找到 3n/4的数， 再二分着 起点，终点， 看是否 > 4/n?
: n/4, n/2 类似?
avatar
b*a
59 楼
题目没说有没有负数
你说全走到不能说明啥我不同意
全走到至少说明这题在没有负数的情况下是没意义的

【在 r***x 的大作中提到】
: 要最大路径和，全走到不能说明啥吧，如果有负数就囧了
avatar
c*5
60 楼
面试时候提一句就行了，这道题没说非负，所以没问题

【在 b********a 的大作中提到】
: 题目没说有没有负数
: 你说全走到不能说明啥我不同意
: 全走到至少说明这题在没有负数的情况下是没意义的
avatar
c*5
61 楼
假设存在popular
即使从第一个数字开始就popular，至少出现n/4次，那么n/4的位置就必然也是popular
，这就是第一个需要检查的位置
对其进行两个二分查找，找到左右边界，如果它不是popular
那么即使从它后面那个数开始就是popular，下一次最早能出现popular的位置至少是n／
以此类推

【在 x*****n 的大作中提到】
: 没看懂。。。方便讲讲怎么排除一部分数字的？
: 我想到的最基本的解法：从左往右扫，判断nums[i] == num[i+n/4]。等于的话就是所
: 找的数了。
相关阅读
限制级，渗入置顶的petsmart $5off$25 Q的链接打印不了怎么回事？The Purrrr....fect NesteggPALA 你在哪里？小T刚才在公园发飙了你们家猫抓苍蝇么？牛牛三岁 ：-）猫咪的哮喘【参加活动】胖兔子皮皮和胖兔子粥粥靠，大傻吃了一只苍蝇[参加活动]我爱小鼠宝宝男猫就是比女猫大方爆笑视频：猫咪的交谈 （不知发过没有？）南瓜－想当年我还是奶猫的时候视频-逗Ayli玩。跳起来落地怎么还彭的一声。哎。太胖了死胖子我们家大耳朵JUJU求助：neuter后用的防止感染的Litter叫什么？PETSMART　GROOMING　SALON现在有5OFF到7月25日长周末出去玩的照片
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。