一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 1953|回复: 5
收起左侧

DropBox OA

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

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

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

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

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 {. 鍥磋鎴戜滑@1point 3 acres
  5. .1point3acres缃
  6.         public GridIllumination()
  7.         {
  8.                
  9.         }
  10.        
  11.         static class Point {
  12.         public int x;
  13.         public int y;
  14.         
  15.         public Point(int x, int y)
  16.         {
  17.             this.x = x;
  18.             this.y = y;
  19.         }
  20.         
  21.         public boolean equals(Object o). visit 1point3acres.com for more.
  22.         {
  23.                 Point point = (Point)o;
  24.                 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25.                 if(this.x==point.x&&this.y==point.y)
  26.                         return true;
  27.                
  28.                 return false;
  29.         }
  30.         
  31.         public int hashCode(). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  32.         {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  33.                 return this.x+this.y;
  34.         }
  35.         }
  36.        

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

  184. }
复制代码

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · 面经|主题: 22, 订阅: 0
gavin5566 发表于 2016-10-26 04:19:01 | 显示全部楼层
lz 內推 還 網申? 謝謝
回复 支持 反对

使用道具 举报

 楼主| theanois 发表于 2016-10-26 04:21:02 | 显示全部楼层
gavin5566 发表于 2016-10-26 04:19
lz 內推 還 網申? 謝謝
. visit 1point3acres.com for more.
是找的同学帮忙内推的
回复 支持 反对

使用道具 举报

gavin5566 发表于 2016-10-26 05:33:22 | 显示全部楼层
theanois 发表于 2016-10-26 04:21.鏈枃鍘熷垱鑷1point3acres璁哄潧
是找的同学帮忙内推的
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
能幫忙內推嗎 感謝!
回复 支持 反对

使用道具 举报

 楼主| 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
同学也是找的他的认识的人,关系有点远,不好意思。
. 1point 3acres 璁哄潧
沒事的 謝謝lz
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-1-21 23:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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