DropBox OA

马上要Dropbox的一面了，发个

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
还行吧。求各位给点大米。

1. import java.util.ArrayList;
   
2. import java.util.HashMap;
   
3. import java.util.HashSet;
   
4. 
   
5. public class GridIllumination {
   
6. 
   
7.         public GridIllumination()
   
8.         {
   
9.                
   
10.         }
    
11.        
    
12.         static class Point {
    
13.         public int x;
    
14.         public int y;
    
15.         
    
16.         public Point(int x, int y)
    
17.         {
    
18.             this.x = x;
    
19.             this.y = y;
    
20.         }
    
21.         
    
22.         public boolean equals(Object o)
    
23.         {
    
24.                 Point point = (Point)o;
    
25.                
    
26.                 if(this.x==point.x&&this.y==point.y)
    
27.                         return true;
    
28.                
    
29.                 return false;
    
30.         }
    
31.         
    
32.         public int hashCode()
    
33.         {
    
34.                 return this.x+this.y;
    
35.         }
    
36.         }
    
37.        
    
38. 
    
39.         public ArrayList<String> checkIllumination(int N, ArrayList<Integer[]>lamps, ArrayList<Integer[]> queries)
    
40.         {
    
41.                 HashMap<Long, Integer> rows = new HashMap<Long, Integer>();
    
42.                 HashMap<Long, Integer> cols = new HashMap<Long, Integer>();
    
43.                 HashMap<Long, Integer> diags = new HashMap<Long, Integer>();
    
44.                 HashMap<Long, Integer> otherDiags = new HashMap<Long, Integer>();
    
45.                 HashSet<Point> lampSet = new HashSet<Point>();
    
46.                
    
47.                 ArrayList<String> ans = new ArrayList<String>();
    
48.                
    
49.                 for(int i = 0;i<lamps.size();++i)
    
50.                 {
    
51.                         Integer[] lamp = lamps.get(i);
    
52.                         long row = lamp[0];
    
53.                         long column = lamp[1];
    
54.                        
    
55.                         Point point = new Point(lamp[0], lamp[1]);
    
56.                         lampSet.add(point);
    
57.                        
    
58.                         if(!rows.containsKey(row))
    
59.                         {
    
60.                                 rows.put(row, 1);
    
61.                         }
    
62.                         else {
    
63.                                 rows.put(row, rows.get(row)+1);
    
64.                         }
    
65.                        
    
66.                         if(!cols.containsKey(column))
    
67.                         {
    
68.                                 cols.put(column, 1);
    
69.                         }
    
70.                         else {
    
71.                                 cols.put(column, cols.get(column)+1);
    
72.                         }
    
73.                        
    
74.                         if(!diags.containsKey(row+column))
    
75.                         {
    
76.                                 diags.put(row+column, 1);
    
77.                         }
    
78.                         else {
    
79.                                 diags.put(row+column, diags.get(row+column)+1);
    
80.                         }
    
81.                        
    
82.                         if(!otherDiags.containsKey(row-column))
    
83.                         {
    
84.                                 otherDiags.put(row-column, 1);
    
85.                         }
    
86.                         else {
    
87.                                 otherDiags.put(row-column, otherDiags.get(row-column)+1);
    
88.                         }
    
89.                 }
    
90.                
    
91.                
    
92.                 for(int i = 0;i<queries.size();++i)
    
93.                 {
    
94.                         Integer[] query = queries.get(i);
    
95.                         int x = query[0];
    
96.                         int y = query[1];
    
97.                         // turn light off
    
98.                         for(long j = x-1;j<=x+1;++j)
    
99.                         {
    
100.                                 for(long k = y-1;k<=y+1;++k)
     
101.                                 {
     
102.                                         if(j>0&&j<=N&&k>0&&k<=N) // valid position
     
103.                                         {
     
104.                                                 if(lampSet.contains(new Point((int)j,(int)k)))
     
105.                                                 {
     
106.                                                         rows.put(j, rows.get(j)-1);
     
107.                                                         cols.put(k, cols.get(k)-1);
     
108.                                                         diags.put(j+k, diags.get(j+k)-1);
     
109.                                                         otherDiags.put(j-k, otherDiags.get(j-k)-1);
     
110.                                                 }
     
111.                                         }
     
112.                                 }
     
113.                         }
     
114.                        
     
115.                         boolean dark= this.isDark(x, rows)&&this.isDark(y, cols)&&this.isDark(x+y, diags)&&this.isDark(x-y, otherDiags);
     
116.                        
     
117.                         if(dark)
     
118.                                 ans.add("DARK");
     
119.                         else
     
120.                                 ans.add("LIGHT");
     
121.                        
     
122.                        
     
123.                         // turn light on
     
124.                         for(long j = x-1;j<=x+1;++j)
     
125.                         {
     
126.                                 for(long k = y-1;k<=y+1;++k)
     
127.                                 {
     
128.                                         if(j>0&&j<=N&&k>0&&k<=N) // valid position
     
129.                                         {
     
130.                                                 if(lampSet.contains(new Point((int)j,(int)k)))
     
131.                                                 {
     
132.                                                         rows.put(j, rows.get(j)+1);
     
133.                                                         cols.put(k, cols.get(k)+1);
     
134.                                                         diags.put(j+k, diags.get(j+k)+1);
     
135.                                                         otherDiags.put(j-k, otherDiags.get(j-k)+1);
     
136.                                                 }
     
137.                                         }
     
138.                                 }
     
139.                         }
     
140.                 }
     
141.                
     
142.                 return ans;
     
143.         }
     
144.        
     
145.        
     
146.         public boolean isDark(long key, HashMap<Long, Integer> map)
     
147.         {
     
148.                 // test if there is light on this row, column, diagnals
     
149.                 if(map.containsKey(key))
     
150.                 {
     
151.                         int value = map.get(key);
     
152.                         // test if the there is still some light on
     
153.                         if(value>0)
     
154.                                 return false;
     
155.                 }
     
156.                
     
157.                 return true;
     
158.         }
     
159.        
     
160.        
     
161.         public static void main(String[] args) {
     
162.                 GridIllumination illumination = new GridIllumination();
     
163.                
     
164. 
     
165.                 // test case 1
     
166.                 int N = 8;
     
167.                 ArrayList<Integer[]> lamps = new ArrayList<Integer[]>();
     
168.                 lamps.add(new Integer[]{1,6});
     
169.                 lamps.add(new Integer[]{5,6});
     
170.                 lamps.add(new Integer[]{7,3});
     
171.                 lamps.add(new Integer[]{3,2});
     
172.        
     
173.                 ArrayList<Integer[]> queries = new ArrayList<Integer[]>();
     
174.                 queries.add(new Integer[]{4,4});
     
175.                 queries.add(new Integer[]{6,6});
     
176.                 queries.add(new Integer[]{8,1});
     
177.                 queries.add(new Integer[]{3,2});
     
178.                 queries.add(new Integer[]{2,3});
     
179.                
     
180.                
     
181.                 ArrayList<String> answer = illumination.checkIllumination(N, lamps, queries);
     
182.                
     
183.                 for(int i = 0;i<answer.size();++i)
     
184.                         System.out.println(answer.get(i));
     
185.         }
     
186. 
     
187. }
     

复制代码

lz 內推 還 網申？ 謝謝

gavin5566 发表于 2016-10-26 04:19
lz 內推 還 網申？ 謝謝

是找的同学帮忙内推的

theanois 发表于 2016-10-26 04:21
是找的同学帮忙内推的

能幫忙內推嗎 感謝！

gavin5566 发表于 2016-10-26 05:33
能幫忙內推嗎 感謝！

同学也是找的他的认识的人，关系有点远，不好意思。

theanois 发表于 2016-10-26 05:37
同学也是找的他的认识的人，关系有点远，不好意思。

沒事的 謝謝lz