一亩三分地论坛

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

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

谷歌电面跪经

[复制链接] |试试Instant~ |关注本帖
linx0383 发表于 2016-11-30 03:07:38 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Fail在职跳槽

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

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

x
第一次发帖,献给跪了的谷歌电面写一个Java Function
输入: list of points in the plane, 比如[(0,0), (1,0), (0,1), (1,1), (2,0), (2,1)]

输出:The smallest rectangle formed by 4 of the points
坐标为整数,任意位置,有可能出现4个点不能组成rectangle的情况
没做出来。。面试官小哥不到30分钟就结束了面试
有谁知道这题怎么做吗?求代码
好想去大公司啊,只能再多加练习了。。。。。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

catinclay 发表于 2016-11-30 03:27:19 | 显示全部楼层
好像在地里看过这道题 但当时有说rectangle是平行或垂直于x跟y轴的
. Waral 鍗氬鏈夋洿澶氭枃绔,
假如同样有这个条件, 那就把每个点都当作rectangle的左下角, 试着看看能不能跟另外三个点形成rectangle, 记得用Map<Integer, Map<Integer, Integer>>的嵌套map来存点的资讯这样可以n^2解
不知道有没有更好的方法
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-11-30 03:39:38 | 显示全部楼层
之前onsite有人考过这题,如果只考虑跟xy轴平行的长方形的话,
1.把所有点存入hashset中
2. 从所有点中选取点 i 和点 j (for each i from 0 to n-1, find j from i to n-1),i 点和 j点分别表示长方形的左下角和右上角. 做如下循环:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2.1 假设左下和右上角是(x1, y1),(x2, y2),可以推算出左上角为(x1, y2)右下角为(x2, y1).
  2.2 查找set中是否存在(x1, y2), (x2, y1). 若都存在,计算面积并更新最小面积
-google 1point3acres3. 输出最小面积。
O(N^2)
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

kunge12345 发表于 2016-11-30 04:42:19 | 显示全部楼层
chestnut9919 发表于 2016-11-30 03:39
之前onsite有人考过这题,如果只考虑跟xy轴平行的长方形的话,
1.把所有点存入hashset中
2. 从所有点中选 ...

若不平行呢?是不是需要O(n^3)而且检查边垂直?
回复 支持 反对

使用道具 举报

primbo 发表于 2016-11-30 05:35:55 | 显示全部楼层
chestnut9919 发表于 2016-11-30 03:39
之前onsite有人考过这题,如果只考虑跟xy轴平行的长方形的话,
1.把所有点存入hashset中
2. 从所有点中选 ...

可不可以用扫描线算法做呢?
回复 支持 反对

使用道具 举报

primbo 发表于 2016-11-30 05:51:45 | 显示全部楼层
  1. class Solution {
  2. public:
  3.     int findSmallestRectangle(vector<pair<int,int>>& points) {
  4.         int res = INT_MAX;
  5.         set<pair<int, int>> s;
  6.         for(int i = 0; i < points.size(); i++) {. from: 1point3acres.com/bbs
  7.             s.insert(points[i]);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8.         }
  9.         for(int i = 0; i < points.size() - 1; i++) {
  10.             for(int j = i + 1; j < points.size(); j++) {
  11.                 if(s.count({points[i].first, points[j].second})
  12.                    &&s.count({points[j].second, points[i].first})) {
  13.                     int area = abs(points[i].first - points[j].first)* abs(points[i].second - points[j].second);. visit 1point3acres.com for more.
  14.                     res = min(area, res);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15.                 }
  16.             }. from: 1point3acres.com/bbs
  17.         }
  18.         return res;
  19.     }
  20. };
复制代码
回复 支持 反对

使用道具 举报

primbo 发表于 2016-11-30 06:01:19 | 显示全部楼层
kunge12345 发表于 2016-11-30 04:42
若不平行呢?是不是需要O(n^3)而且检查边垂直?

若可以不平行,那么就再加一层for loop 找第三个可以和之前的两个点组成直角三角形的点(a2 + b2 =c2).第三个点确定后对角线的点的坐标可以确定。然后check 是不是在set里面,如果在的话更新res。
回复 支持 反对

使用道具 举报

kunge12345 发表于 2016-11-30 06:02:36 | 显示全部楼层
primbo 发表于 2016-11-30 06:01
若可以不平行,那么就再加一层for loop 找第三个可以和之前的两个点组成直角三角形的点(a2 + b2 =c2). ...

握手,跟我想法一样
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-12-12 15:49:01 | 显示全部楼层

&&s.count({points[j].second, points.first})  这里应该是s.count({points[j].first, points.second})吧,而且是不是应该加上一个判断point.first != point[j].first && point.second != point[j].second 否则的话,可能会出现面积为0的矩形  
回复 支持 反对

使用道具 举报

ayzmkkk 发表于 2016-12-12 22:05:26 | 显示全部楼层
chaosMonkey 发表于 2016-12-12 15:49
&&s.count({points[j].second, points.first})  这里应该是s.count({points[j].first, points.second})吧 ...

同意,我觉得是要去重的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-23 14:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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