一亩三分地论坛

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

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

DropBox OA

[复制链接] |试试Instant~ |关注本帖
theanois 发表于 2016-10-26 04:13:39 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 博士 实习@Dropbox - 内推 - 其他 |Pass其他

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

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

x
马上要Dropbox的一面了,发个GridIllumination  OA的code攒攒人品。缩进都乱套了,不过好在是java,大家自己动下手吧。写完代码太着急了,也没看过了多少test case。不过因为拿到面试了,估计还行吧。求各位给点大米
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.HashSet;

  4. public class GridIllumination {

  5.         public GridIllumination()
  6.         {
  7.                
  8.         }
  9.        
  10.         static class Point {
  11.         public int x;-google 1point3acres
  12.         public int y;
  13.         
  14.         public Point(int x, int y)
  15.         {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  16.             this.x = x;
  17.             this.y = y;
  18.         }
  19.         
  20.         public boolean equals(Object o)
  21.         {
  22.                 Point point = (Point)o;
  23.                
  24.                 if(this.x==point.x&&this.y==point.y)
    . from: 1point3acres.com/bbs
  25.                         return true;
  26.                
  27.                 return false;.1point3acres缃
  28.         }
  29.         . more info on 1point3acres.com
  30.         public int hashCode(). 鍥磋鎴戜滑@1point 3 acres
  31.         {
  32.                 return this.x+this.y;
  33.         }
  34.         }
  35.        

  36.         public ArrayList<String> checkIllumination(int N, ArrayList<Integer[]>lamps, ArrayList<Integer[]> queries). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  37.         {.1point3acres缃
  38.                 HashMap<Long, Integer> rows = new HashMap<Long, Integer>();
  39.                 HashMap<Long, Integer> cols = new HashMap<Long, Integer>();. more info on 1point3acres.com
  40.                 HashMap<Long, Integer> diags = new HashMap<Long, Integer>();
  41.                 HashMap<Long, Integer> otherDiags = new HashMap<Long, Integer>();.1point3acres缃
  42.                 HashSet<Point> lampSet = new HashSet<Point>();
  43.                
  44.                 ArrayList<String> ans = new ArrayList<String>();
  45.                
  46.                 for(int i = 0;i<lamps.size();++i)
  47.                 {
  48.                         Integer[] lamp = lamps.get(i);
  49.                         long row = lamp[0];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  50.                         long column = lamp[1];
  51.                        
  52.                         Point point = new Point(lamp[0], lamp[1]);
  53.                         lampSet.add(point);. 鍥磋鎴戜滑@1point 3 acres
  54.                        
  55.                         if(!rows.containsKey(row))
  56.                         {
  57.                                 rows.put(row, 1);
  58.                         }
  59.                         else {
  60.                                 rows.put(row, rows.get(row)+1);
  61.                         }
  62.                        
  63.                         if(!cols.containsKey(column))
  64.                         {
  65.                                 cols.put(column, 1);. more info on 1point3acres.com
  66.                         }
  67.                         else {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  68.                                 cols.put(column, cols.get(column)+1);
  69.                         }
  70.                        
  71.                         if(!diags.containsKey(row+column))
  72.                         {
  73.                                 diags.put(row+column, 1);
  74.                         }
  75.                         else {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  76.                                 diags.put(row+column, diags.get(row+column)+1);
  77.                         }
  78.                        
  79.                         if(!otherDiags.containsKey(row-column))
  80.                         {
  81.                                 otherDiags.put(row-column, 1); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  82.                         }. 1point3acres.com/bbs
  83.                         else {
  84.                                 otherDiags.put(row-column, otherDiags.get(row-column)+1);
  85.                         }
  86.                 }
  87.                
  88.                
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  89.                 for(int i = 0;i<queries.size();++i)
  90.                 {. 1point 3acres 璁哄潧
  91.                         Integer[] query = queries.get(i);
  92.                         int x = query[0];
  93.                         int y = query[1];
  94.                         // turn light off. 1point3acres.com/bbs
  95.                         for(long j = x-1;j<=x+1;++j).鐣欏璁哄潧-涓浜-涓夊垎鍦
  96.                         {
  97.                                 for(long k = y-1;k<=y+1;++k). Waral 鍗氬鏈夋洿澶氭枃绔,
  98.                                 {
  99.                                         if(j>0&&j<=N&&k>0&&k<=N) // valid position
  100.                                         {
  101.                                                 if(lampSet.contains(new Point((int)j,(int)k)))
  102.                                                 {
  103.                                                         rows.put(j, rows.get(j)-1);
  104.                                                         cols.put(k, cols.get(k)-1);
  105.                                                         diags.put(j+k, diags.get(j+k)-1);
    . 鍥磋鎴戜滑@1point 3 acres
  106.                                                         otherDiags.put(j-k, otherDiags.get(j-k)-1);
    . more info on 1point3acres.com
  107.                                                 }
  108.                                         }
  109.                                 }
  110.                         }
  111.                         . 1point 3acres 璁哄潧
  112.                         boolean dark= this.isDark(x, rows)&&this.isDark(y, cols)&&this.isDark(x+y, diags)&&this.isDark(x-y, otherDiags);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  113.                        
  114.                         if(dark)
  115.                                 ans.add("DARK");
  116.                         else . 鍥磋鎴戜滑@1point 3 acres
  117.                                 ans.add("LIGHT");
  118.                        
  119.                        
  120.                         // turn light on
  121.                         for(long j = x-1;j<=x+1;++j)
  122.                         {. visit 1point3acres.com for more.
  123.                                 for(long k = y-1;k<=y+1;++k)
  124.                                 {. From 1point 3acres bbs
  125.                                         if(j>0&&j<=N&&k>0&&k<=N) // valid position
  126.                                         {
  127.                                                 if(lampSet.contains(new Point((int)j,(int)k))). 1point 3acres 璁哄潧
  128.                                                 {
  129.                                                         rows.put(j, rows.get(j)+1);
  130.                                                         cols.put(k, cols.get(k)+1);
  131.                                                         diags.put(j+k, diags.get(j+k)+1);. 1point3acres.com/bbs
  132.                                                         otherDiags.put(j-k, otherDiags.get(j-k)+1);
  133.                                                 }
  134.                                         }
  135.                                 }
  136.                         }
  137.                 }
  138.                
  139.                 return ans;
  140.         }
  141.        
  142.        
  143.         public boolean isDark(long key, HashMap<Long, Integer> map)-google 1point3acres
  144.         {
  145.                 // test if there is light on this row, column, diagnals.鐣欏璁哄潧-涓浜-涓夊垎鍦
  146.                 if(map.containsKey(key))
  147.                 {
  148.                         int value = map.get(key);
  149.                         // test if the there is still some light on
  150.                         if(value>0)
  151.                                 return false;
  152.                 }
  153.                
  154.                 return true;. 1point 3acres 璁哄潧
  155.         }
  156.        
  157.        
  158.         public static void main(String[] args) {
  159.                 GridIllumination illumination = new GridIllumination();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  160.                
  161. . more info on 1point3acres.com
  162.                 // test case 1.1point3acres缃
  163.                 int N = 8;. Waral 鍗氬鏈夋洿澶氭枃绔,
  164.                 ArrayList<Integer[]> lamps = new ArrayList<Integer[]>();
  165.                 lamps.add(new Integer[]{1,6});
  166.                 lamps.add(new Integer[]{5,6});. From 1point 3acres bbs
  167.                 lamps.add(new Integer[]{7,3});
  168.                 lamps.add(new Integer[]{3,2});. visit 1point3acres.com for more.
  169.        
  170.                 ArrayList<Integer[]> queries = new ArrayList<Integer[]>();
  171.                 queries.add(new Integer[]{4,4});
  172.                 queries.add(new Integer[]{6,6});
  173.                 queries.add(new Integer[]{8,1});
  174.                 queries.add(new Integer[]{3,2});-google 1point3acres
  175.                 queries.add(new Integer[]{2,3});
  176.                
  177.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  178.                 ArrayList<String> answer = illumination.checkIllumination(N, lamps, queries);
  179.                
  180.                 for(int i = 0;i<answer.size();++i)
  181.                         System.out.println(answer.get(i));. 1point 3acres 璁哄潧
  182.         }. 1point3acres.com/bbs

  183. }
复制代码

评分

2

查看全部评分

gavin5566 发表于 2016-10-26 04:19:01 | 显示全部楼层
lz 內推 還 網申? 謝謝
回复 支持 反对

使用道具 举报

 楼主| theanois 发表于 2016-10-26 04:21:02 | 显示全部楼层
gavin5566 发表于 2016-10-26 04:19
lz 內推 還 網申? 謝謝

是找的同学帮忙内推的
回复 支持 反对

使用道具 举报

gavin5566 发表于 2016-10-26 05:33:22 | 显示全部楼层
theanois 发表于 2016-10-26 04:21. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
是找的同学帮忙内推的
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
能幫忙內推嗎 感謝!
回复 支持 反对

使用道具 举报

 楼主| theanois 发表于 2016-10-26 05:37:13 | 显示全部楼层
gavin5566 发表于 2016-10-26 05:33
能幫忙內推嗎 感謝!

同学也是找的他的认识的人,关系有点远,不好意思。
回复 支持 反对

使用道具 举报

gavin5566 发表于 2016-10-26 09:42:23 | 显示全部楼层
theanois 发表于 2016-10-26 05:37
同学也是找的他的认识的人,关系有点远,不好意思。

沒事的 謝謝lz
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 17:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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