一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1014|回复: 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 {. From 1point 3acres bbs

  5.         public GridIllumination()
  6.         {
  7.                
  8.         }
  9.        
  10.         static class Point {
  11.         public int x;
  12.         public int y;
  13.         . 1point 3acres 璁哄潧
  14.         public Point(int x, int y)
    . 1point 3acres 璁哄潧
  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). visit 1point3acres.com for more.
  25.                         return true;
  26.                
  27.                 return false;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  28.         }
  29.         . from: 1point3acres.com/bbs
  30.         public int hashCode()
  31.         {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  32.                 return this.x+this.y;. 鍥磋鎴戜滑@1point 3 acres
  33.         }
  34.         }
  35.        

  36.         public ArrayList<String> checkIllumination(int N, ArrayList<Integer[]>lamps, ArrayList<Integer[]> queries).鐣欏璁哄潧-涓浜-涓夊垎鍦
  37.         {
  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>();
  42.                 HashSet<Point> lampSet = new HashSet<Point>();
  43.                 . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  44.                 ArrayList<String> ans = new ArrayList<String>();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  45.                
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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];-google 1point3acres
  51.                        
  52.                         Point point = new Point(lamp[0], lamp[1]);
  53.                         lampSet.add(point);
  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);
  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.                         }
    . more info on 1point3acres.com
  75.                         else {
  76.                                 diags.put(row+column, diags.get(row+column)+1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  77.                         }
  78.                        
  79.                         if(!otherDiags.containsKey(row-column)). 鍥磋鎴戜滑@1point 3 acres
  80.                         {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  81.                                 otherDiags.put(row-column, 1);
  82.                         }
  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.                 {
  91.                         Integer[] query = queries.get(i);
  92.                         int x = query[0];. 1point 3acres 璁哄潧
  93.                         int y = query[1];
  94.                         // turn light off
  95.                         for(long j = x-1;j<=x+1;++j).鏈枃鍘熷垱鑷1point3acres璁哄潧
  96.                         {
  97.                                 for(long k = y-1;k<=y+1;++k)
  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);.1point3acres缃
  105.                                                         diags.put(j+k, diags.get(j+k)-1);
  106.                                                         otherDiags.put(j-k, otherDiags.get(j-k)-1);
  107.                                                 }
  108.                                         }
  109.                                 }
  110.                         }
  111.                        
  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).鏈枃鍘熷垱鑷1point3acres璁哄潧
  115.                                 ans.add("DARK");-google 1point3acres
  116.                         else
  117.                                 ans.add("LIGHT");
  118.                         . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  119.                         . visit 1point3acres.com for more.
  120.                         // turn light on
  121.                         for(long j = x-1;j<=x+1;++j)
  122.                         {. From 1point 3acres bbs
  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.1point3acres缃
  126.                                         {
  127.                                                 if(lampSet.contains(new Point((int)j,(int)k)))
  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);
  132.                                                         otherDiags.put(j-k, otherDiags.get(j-k)+1);
  133.                                                 }-google 1point3acres
  134.                                         }
  135.                                 }
  136.                         }. more info on 1point3acres.com
  137.                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  138.                 .1point3acres缃
  139.                 return ans;
  140.         }. From 1point 3acres bbs
  141.        
  142.        
  143.         public boolean isDark(long key, HashMap<Long, Integer> map)
  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). 鍥磋鎴戜滑@1point 3 acres
  151.                                 return false;
  152.                 }
  153.                
  154.                 return true;
  155.         }
  156.         .1point3acres缃
  157.        
  158.         public static void main(String[] args) {
  159.                 GridIllumination illumination = new GridIllumination();
  160.                

  161.                 // test case 1
  162.                 int N = 8;
  163.                 ArrayList<Integer[]> lamps = new ArrayList<Integer[]>();. 鍥磋鎴戜滑@1point 3 acres
  164.                 lamps.add(new Integer[]{1,6});
  165.                 lamps.add(new Integer[]{5,6});
  166.                 lamps.add(new Integer[]{7,3});. 1point 3acres 璁哄潧
  167.                 lamps.add(new Integer[]{3,2});
  168.        
  169.                 ArrayList<Integer[]> queries = new ArrayList<Integer[]>();
  170.                 queries.add(new Integer[]{4,4});
  171.                 queries.add(new Integer[]{6,6});
  172.                 queries.add(new Integer[]{8,1});
  173.                 queries.add(new Integer[]{3,2});
  174.                 queries.add(new Integer[]{2,3});
  175.                
  176.                
  177.                 ArrayList<String> answer = illumination.checkIllumination(N, lamps, queries);
  178.                
  179.                 for(int i = 0;i<answer.size();++i)
  180.                         System.out.println(answer.get(i));. 1point 3acres 璁哄潧
  181.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  182. . from: 1point3acres.com/bbs
  183. }
复制代码

评分

3

查看全部评分

gavin5566 发表于 2016-10-26 04:19:01 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
lz 內推 還 網申? 謝謝
回复 支持 反对

使用道具 举报

 楼主| theanois 发表于 2016-10-26 04:21:02 | 显示全部楼层
关注一亩三分地微博:
Warald
gavin5566 发表于 2016-10-26 04:19
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴lz 內推 還 網申? 謝謝
. 1point3acres.com/bbs
是找的同学帮忙内推的
回复 支持 反对

使用道具 举报

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. visit 1point3acres.com for more.
同学也是找的他的认识的人,关系有点远,不好意思。

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-27 12:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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