狗家实习电面面经，感觉差不多跪了，来攒人品……

下午面了两轮，来地里赞个人品
之前也各种看今年实习的电面面经，但是都没有考到，不过有类似题目的变形，我看到的电面面经也基本人人都不一样，感觉还是要靠平时基础，而且我leetcode就刷了300左右感觉还是不

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

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

>



补充内容 (2017-11-22 11:57):
第一题说错了，是最小的那个长方形面积，不过都差不多啦……

个人感觉第一题3 for loops就可以做了吧
先把所有点都放进set里，然后根据三个点可以算出能组成长方形的第四个点，查找第四个点是不是在set里
是的话，求global min就行

给一串数组代表坐标，求问这些坐标中能连成的长方形中，面积最大的那个是多大

假設長方行的邊皆與X軸或Y軸垂直或平行，不會有斜的長方形

1. import java.util.*;
   
2. public class RectangleMaxArea {
   
3.     public static void main(String[] args){
   
4.         Coordinate[] coordinates= new Coordinate[10];
   
5.         coordinates[0] = new Coordinate(-1,5);
   
6.         coordinates[1] = new Coordinate(-1,-3);
   
7.         coordinates[2] = new Coordinate(2,7);
   
8.         coordinates[3] = new Coordinate(2,3);
   
9.         coordinates[4] = new Coordinate(4,-1);
   
10.         coordinates[5] = new Coordinate(6,7);
    
11.         coordinates[6] = new Coordinate(6,3);
    
12.         coordinates[7] = new Coordinate(7,2);
    
13.         coordinates[8] = new Coordinate(2,-4);
    
14.         coordinates[9] = new Coordinate(6,-4);
    
15.         System.out.println(new RectangleMaxArea().getMaxArea(coordinates));
    
16.     }
    
17. 
    
18.     int getMaxArea(Coordinate[] coordinates){
    
19.         int maxArea = 0;
    
20.         Set<Coordinate> mySet = new HashSet<>();
    
21.         Collections.addAll(mySet,coordinates);
    
22.         if(mySet.size() < 4)
    
23.             return 0;
    
24.         int pointNum = coordinates.length;
    
25. 
    
26.         //we want to pick two diagonal points
    
27.         for(int i=0; i<pointNum; i++){
    
28.             for(int j=0; j<pointNum; j++){
    
29.                 // if we pick two points with
    
30.                 // 1. same coordinates or
    
31.                 // 2. they are on the same vertical line or
    
32.                 // 3. they are on the same horizontal line
    
33.                 // we skip them because we want to pick diagonal point of the rectangle
    
34.                 if(coordinates[i].equals(coordinates[j])
    
35.                         || coordinates[i].x == coordinates[j].x
    
36.                         || coordinates[i].y == coordinates[j].y)
    
37.                     continue;
    
38.                 int[] p1 = {coordinates[i].x, coordinates[i].y};
    
39.                 int[] p2 = {coordinates[j].x, coordinates[j].y};
    
40.                 int[] p3 = new int[2];
    
41.                 int[] p4 = new int[2];
    
42. 
    
43.                 if(mySet.contains(new Coordinate(p2[0],p1[1])) && mySet.contains(new Coordinate(p1[0],p2[1]))){
    
44.                     p3[0] = p2[0];
    
45.                     p3[1] = p1[1];
    
46.                     p4[0] = p1[0];
    
47.                     p4[1] = p2[1];
    
48.                     maxArea = Math.max(maxArea,getArea(p1,p3,p4));
    
49.                 }
    
50.             }
    
51.         }
    
52. 
    
53.         return maxArea;
    
54.     }
    
55. 
    
56.     int getArea(int[] p1, int[] p2, int[] p3){
    
57.         int edge1 = p1[0]-p2[0] + p1[1]-p2[1];
    
58.         int edge2 = p1[0]-p3[0] + p1[1]-p3[1];
    
59.         return edge1 * edge2;
    
60.     }
    
61. }
    
62. 
    
63. class Coordinate{
    
64.     int x;
    
65.     int y;
    
66.     Coordinate(int x, int y){
    
67.         this.x = x;
    
68.         this.y = y;
    
69.     }
    
70. 
    
71.     public boolean equals(Object p){
    
72.         Coordinate c = (Coordinate)p;
    
73.         return c.x == this.x && c.y == this.y;
    
74.     }
    
75. 
    
76.     public int hashCode(){
    
77.         final int prime = 997;
    
78.         return x + prime * y;
    
79.     }
    
80. }
    

复制代码

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

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

谢谢楼主分享。第一题能举个例子吗？

LZ能说下第二轮第二题不用extra space怎么做吗？
除了改变树的结构，其他方法想不到了。。。
给你加米啦~

570468837 发表于 2017-11-22 13:15
LZ能说下第二轮第二题不用extra space怎么做吗？
除了改变树的结构，其他方法想不到了。。。
给你加米啦~

感觉就是lc 160

szb23 发表于 2017-11-22 13:44
感觉就是lc 160

是的，基本就是这样

570468837 发表于 2017-11-22 13:15
LZ能说下第二轮第二题不用extra space怎么做吗？
除了改变树的结构，其他方法想不到了。。。
给你加米啦~

把它当成linkedlist一样来做，类似slow fast指针的感觉，上面也有人说了lc160。

edyyy 发表于 2017-11-22 13:00
谢谢楼主分享。第一题能举个例子吗？

比如给你点1点2点3点4点5点6的坐标，点1点2点3点4， 可以构成长方形，点3点4点5点6也可以构成长方形，选这两个里面最小的那个面积。

请问楼主第一问就是强算吗？楼主是怎么存储数据方便后面找长方形的呢？

求问楼主第一题怎么做？

同求问楼主第一题的思路/(ㄒoㄒ)/~~