一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3615|回复: 29
收起左侧

Pocket Gems on-site

[复制链接] |试试Instant~ |关注本帖
anonym 发表于 2015-3-25 10:40:43 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Pocket gems - 猎头 - Onsite |Fail

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
一共四轮

第一轮俩题:
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴1. Maximum Product Subarray
2. Give a String array, return a minimum length String that satisfies the requirement that the relative orders between the chars in the output are consistent with the relative orders in every array element. Assume the output exists.
For example: { "cba", "bd", "ce", "ed" } -> "cbaed"     { "gcd", "jd", "fcj" } -> "fgcjd"

第二轮:
一个zoo的游戏,根据游戏中achievenment的requirement设计游戏的achievement系统。requirement可以有很多种,给的例子一是拿到多少个金币,二是得到多少个某种动物,满足条件就可以完成一个achievement。. from: 1point3acres.com/bbs

第三轮:
讨论一份StringToTree的代码


第四轮:.鏈枃鍘熷垱鑷1point3acres璁哄潧
You can go in four directions from the origin on a 2D surface. Given an int k, you can only reach the points where the sum of the coordinate digits is not greater than k. Return how many points you can reach.

我当时用了Map<Integer, Set<Integer>>来存储访问过点的横纵坐标。讨论了一下如果用Set<Point>存储访问过的点需要怎么办,就是要重写hashCode()和equals()。

. From 1point 3acres bbs
补充内容 (2015-3-24 21:47):
补充一下第三轮,代码是把
  1
/ \
2   3.鏈枃鍘熷垱鑷1point3acres璁哄潧
这样的String变成一个Tree。讨论了一下之后问如果String是
  1
/ \
2   3
\ /
  4
这样的这份代码还能不能构建出一个正确的Tree。

补充内容 (2015-3-25 10:45):. visit 1point3acres.com for more.
哦对了 第四轮还要求证明可达到的点的个数是有限个来着 以k=25为例证明
从(0, 0)向上走最多能够走到(0, 898),到达这个点之后无论向上向左向右都走不通了,因此相当于在y=898上画了一条边界,其他方向同理。

补充内容 (2015-3-25 10:51):
第四轮的题还问到了时间复杂度.鐣欏璁哄潧-涓浜-涓夊垎鍦
对于访问到的每个点判断是否满足小于k需要O(k),所有访问到的点形成的图形最长半径为n的话则有O(n2)个点,所以总共是O(n2*k)。

评分

2

查看全部评分

shinichish 发表于 2015-3-25 11:36:41 | 显示全部楼层
卧槽,宝石妖怪换题了!?
回复 支持 反对

使用道具 举报

hongelee 发表于 2015-3-25 11:54:32 | 显示全部楼层
请问第一轮的第二题是什么思路呀?还有最后一轮的sum of coordinate digit 是纵横坐标相加的意思吗?
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-3-25 12:45:51 | 显示全部楼层
shinichish 发表于 2015-3-24 22:36
卧槽,宝石妖怪换题了!?

其实换的不多 能有这样就该满意了 不过还是跪了。。。
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-3-25 12:49:44 | 显示全部楼层
hongelee 发表于 2015-3-24 22:54. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
请问第一轮的第二题是什么思路呀?还有最后一轮的sum of coordinate digit 是纵横坐标相加的意思吗?
. 1point 3acres 璁哄潧
用一个Map<Character, Set<Character>>记录出现在每个字母前面的所有字母,然后就有点类似拓扑排序了:
先找到Set为空的字母放在第一位,把它从Map中除去,再在所有Set中把这个字母去掉,然后就是循环找下一个Set为空的字母。

是横纵坐标每一位的数字相加,比如(28, 17)就是2+8+1+7。
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-3-25 12:50:40 | 显示全部楼层
anonym 发表于 2015-3-24 20:45
其实换的不多 能有这样就该满意了 不过还是跪了。。。

patpat。。。我也跪了,move on吧
回复 支持 反对

使用道具 举报

liuzhe1218 发表于 2015-3-25 15:13:00 | 显示全部楼层
shinichish 发表于 2015-3-25 12:50. more info on 1point3acres.com
patpat。。。我也跪了,move on吧

挫气公司,rui神还用理会。。。
回复 支持 反对

使用道具 举报

timpark4 发表于 2015-3-25 22:05:11 | 显示全部楼层
请问下楼主是什么时候投的简历? 他们家还招intern吗?
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-3-25 23:40:54 | 显示全部楼层
timpark4 发表于 2015-3-25 09:05
请问下楼主是什么时候投的简历? 他们家还招intern吗?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
好久了 intern我不了解啊
回复 支持 反对

使用道具 举报

liokumo 发表于 2015-3-26 06:29:44 | 显示全部楼层
楼主,第一轮第二题是不是遍历一遍看看顺序然后把没有的字母加上?有没有更好的法子了?
另,{ "cba", "bd", "ce", "ed" } -> "cbaed" 按照楼主的解释 是不是“cebad”或者“cbead”这样也算正确答案?

补充内容 (2015-3-26 06:55):. 鍥磋鎴戜滑@1point 3 acres
还有第四轮,k=25 (0,988)可以到么?
回复 支持 反对

使用道具 举报

苏DsL 发表于 2015-3-26 06:59:26 | 显示全部楼层
liokumo 发表于 2015-3-26 06:29. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主,第一轮第二题是不是遍历一遍看看顺序然后把没有的字母加上?有没有更好的法子了?
另,{ "cba", "bd ...

刚好我也想问这个问题。。顶一下。。
回复 支持 反对

使用道具 举报

苏DsL 发表于 2015-3-26 07:01:32 | 显示全部楼层
anonym 发表于 2015-3-25 12:49
用一个Map记录出现在每个字母前面的所有字母,然后就有点类似拓扑排序了:
先找到Set为空的字母放在第一 ...

lz,第一题第二轮建这个map有什么好办法嘛?我只想到对每个单词暴力。。你是这样做得么?
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-3-26 13:20:56 | 显示全部楼层
liokumo 发表于 2015-3-25 17:29
楼主,第一轮第二题是不是遍历一遍看看顺序然后把没有的字母加上?有没有更好的法子了?
另,{ "cba", "bd ...
. visit 1point3acres.com for more.
没太明白你的意思 你看看地下室那层我说的吧
.1point3acres缃
这两种答案都可以 只要给出一个解就行
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
走不到(0, 988)的 因为你走到(0, 898)就没法往上走了
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-3-26 13:23:37 | 显示全部楼层
苏DsL 发表于 2015-3-25 18:01. 1point3acres.com/bbs
lz,第一题第二轮建这个map有什么好办法嘛?我只想到对每个单词暴力。。你是这样做得么?

我觉得要想找到所有的相互顺序必须得暴力建吧
回复 支持 反对

使用道具 举报

liokumo 发表于 2015-3-26 20:47:07 | 显示全部楼层
anonym 发表于 2015-3-26 13:20
没太明白你的意思 你看看地下室那层我说的吧

这两种答案都可以 只要给出一个解就行
. 鍥磋鎴戜滑@1point 3 acres
谢谢楼主的回答,你其实在前面已经回答了我的问题了,就是我没看懂……

我还有一点小小的疑问,有关于第四轮的题,既然可以给出这个点能够到达有限个数的点,而且这个有限个数的点在一个大菱形里(对吧?比如k=25,界限是(0,898)(898,0)(-898,0)(0,-898)),那是否还需要遍历所有的点来求多少点能到达?只需要求一个边然后求这个菱形面积不就行了?
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-3-27 09:10:22 | 显示全部楼层
liokumo 发表于 2015-3-26 07:47
谢谢楼主的回答,你其实在前面已经回答了我的问题了,就是我没看懂……

我还有一点小小的疑问,有关于 ...

如果还是不明白的话可以看看LintCode上的Topological Sorting. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
你说的对 可以用纯数学的方法做这道题
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-3-27 12:32:35 | 显示全部楼层
liokumo 发表于 2015-3-26 07:47
谢谢楼主的回答,你其实在前面已经回答了我的问题了,就是我没看懂……
.1point3acres缃
我还有一点小小的疑问,有关于 ...

写了写发现不对,k>=9的时候就不是菱形了。. 1point3acres.com/bbs
比如k=9的时候,(0, -9) (0, 9) (-9, 0) (9, 0)围成了一个菱形,再往外走x=10的时候y可以从-8取到8,又是一个新的三角形,所以用纯数学实在不好算……
回复 支持 反对

使用道具 举报

liokumo 发表于 2015-3-27 20:37:53 | 显示全部楼层
anonym 发表于 2015-3-27 12:32
写了写发现不对,k>=9的时候就不是菱形了。
比如k=9的时候,(0, -9) (0, 9) (-9, 0) (9, 0)围成了一个菱 ...

K=9的时候不是可以走到18么?边界是(18,0)(-18,0)(0,18)(0,-18)?不对么?
回复 支持 反对

使用道具 举报

 楼主| anonym 发表于 2015-3-28 11:19:17 | 显示全部楼层
liokumo 发表于 2015-3-27 07:37
K=9的时候不是可以走到18么?边界是(18,0)(-18,0)(0,18)(0,-18)?不对么?

边界是18 但是全部边界围成的不是一个菱形啊 只有9围成的是一个菱形 你画下图看看
回复 支持 反对

使用道具 举报

liokumo 发表于 2015-3-28 23:33:22 | 显示全部楼层
anonym 发表于 2015-3-27 22:19
边界是18 但是全部边界围成的不是一个菱形啊 只有9围成的是一个菱形 你画下图看看

我不怎么会画,拿起笔来只能画出一个由(18,0)(-18,0)(0,18)(0,-18)四个点组成的菱形。菱形范围内是所有可以经过点

                               
登录/注册后可看大图

我不是很明白你的意思,你在之前说:再往外走x=10的时候y可以从-8取到8,又是一个新的三角形
为什么会是一个新的三角形?(10,-8)和(10,8)是在菱形范围里的,是可以经过的点啊,就是我画的那条黑线
我可能理解的有些偏差?能不能麻烦帮忙你画个图?

补充内容 (2015-3-28 10:48):
这个图显示不出来,下一页又可以显示出来的。
非常感谢楼主如此耐心的为我解答,真的非常感谢
另,上一次回复我按错了,怎么删啊
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 22:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表