一亩三分地论坛

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

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

Dropbox OA题目及解法

[复制链接] |试试Instant~ |关注本帖
甜筱瞳 发表于 2016-9-22 01:36:17 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Dropbox - 网上海投 - 在线笔试 |Passfresh grad应届毕业生

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

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

x
刚做完Dropbox OA, 感谢大牛们的分享,
在此贴出原题,
https://www.dropbox.com/sh/jiedm ... IQAXXyfeCeVHfa?dl=0

10个testcase全过了
解法:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
class GridIllumination:
        def checkIllumination(self, N, lamps, queries):. 鍥磋鎴戜滑@1point 3 acres
                row = {}.鏈枃鍘熷垱鑷1point3acres璁哄潧
                col = {}
                dia = {}
                rdia = {}

                S = set([])

                for lamp in lamps:
                        S.add(lamp)
                        x = lamp[0]
                        y = lamp[1]
                        row[x] = row.get(x, 0) + 1
                        col[y] = col.get(y, 0) + 1
                        dia[x-y] = dia.get(x-y, 0) + 1
                        rdia[x+y] = rdia.get(x+y, 0) + 1
.1point3acres缃
                ret = list()
                for query in queries:
                        x = query[0]
                        y = query[1]

                        xs = [x-1, x, x+1]
                        ys = [y-1, y, y+1]

                        ## turn off the light
                        for i in xs:. from: 1point3acres.com/bbs
                                if i>0 and i <= N:
                                        for j in ys:
                                                if j>0 and j <= N and (i, j) in S:
                                                        row -= 1
                                                        col[j] -= 1
                                                        dia[i-j] -= 1
                                                        rdia[i+j] -= 1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        dark = self.isDark(x, row) and self.isDark(y, col) and self.isDark(x-y, dia) and self.isDark(x+y, rdia)
                        if dark:
                                ret.append("DARK")
                        else:
                                ret.append("LIGHT")

                        ## turn on the light
                        for i in xs:. 1point 3acres 璁哄潧
                                if i>0 and i <= N:
                                        for j in ys:
                                                if j>0 and j <= N and (i, j) in S:
                                                        row += 1
                                                        col[j] += 1
                                                        dia[i-j] += 1. 1point3acres.com/bbs
                                                        rdia[i+j] += 1
                return ret                       
               
        def isDark(self, i, map):
                if i in map:
                        if map != 0: return False
                return True

if __name__ == "__main__":
        grid = GridIllumination() 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        ret = grid.checkIllumination(8, [(4, 3), (4, 4)], [(3, 4), (7, 6)])
        print ret

. 鍥磋鎴戜滑@1point 3 acres




补充内容 (2016-9-22 01:47):
求米啊,呜呜呜~~~~(>_<)~~~~
更多图片 小图 大图
组图打开中,请稍候......

评分

4

查看全部评分

wtcupup 发表于 2016-9-22 01:44:29 | 显示全部楼层
有两个issue,.鏈枃鍘熷垱鑷1point3acres璁哄潧

  1. if j>0 and j <= N and (i, j) in S:
  2.                                                         row -= 1. From 1point 3acres bbs
  3. 应该是 row[i] -=1

  4. if j>0 and j <= N and (i, j) in S:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.                                                         row += 1

  6. 应该是 row[i]+=1
复制代码
回复 支持 反对

使用道具 举报

 楼主| 甜筱瞳 发表于 2016-9-22 01:45:54 | 显示全部楼层
wtcupup 发表于 2016-9-22 01:44. 1point 3acres 璁哄潧
有两个issue,

嗯呐,粘的时候粘错了:D
回复 支持 反对

使用道具 举报

 楼主| 甜筱瞳 发表于 2016-9-22 01:46:58 | 显示全部楼层
求米啊,呜呜呜呜~~~

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

小飞侠我去 发表于 2016-9-22 02:07:22 | 显示全部楼层
甜筱瞳 发表于 2016-9-22 01:46
求米啊,呜呜呜呜~~~

楼主海投后多久收到OA的?
回复 支持 反对

使用道具 举报

 楼主| 甜筱瞳 发表于 2016-9-22 02:15:54 | 显示全部楼层
小飞侠我去 发表于 2016-9-22 02:07
楼主海投后多久收到OA的?
. 鍥磋鎴戜滑@1point 3 acres
差不多1-2天,因为邮件被分到垃圾箱了,等看到已经过期了又跟dropbox argue的。。
回复 支持 反对

使用道具 举报

cicean 发表于 2016-10-14 17:24:21 | 显示全部楼层
楼主 Java 干不了 (i, j) in S 这事啊。没法比较 int[i,j] in set<int[]> 是不是contains 啊. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
有没有亲知道怎么 存 pair 然后 search的时候 是O(1) 呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 15:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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