谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 3162|回复: 18
收起左侧

谷歌电面跪经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
linx0383 发表于 2016-11-30 03:07:38 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

x
第一次发帖,献给跪了的谷歌电面写一个Java Function. 一亩-三分-地,独家发布
输入: list of points in the plane, 比如[(0,0), (1,0), (0,1), (1,1), (2,0), (2,1)]
. 1point3acres
输出:The smallest rectangle formed by 4 of the points
坐标为整数,任意位置,有可能出现4个点不能组成rectangle的情况. 一亩-三分-地,独家发布
没做出来。。面试官小哥不到30分钟就结束了面试
有谁知道这题怎么做吗?求代码
好想去大公司啊,只能再多加练习了。。。。。

评分

参与人数 1大米 +30 收起 理由
candy_shmily + 30

查看全部评分


上一篇:找吃的实习2面
下一篇:空气床11.29店面

本帖被以下淘专辑推荐:

  • · Google|主题: 459, 订阅: 124
我的人缘0
chestnut9919 发表于 2016-11-30 03:39:38 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
之前onsite有人考过这题,如果只考虑跟xy轴平行的长方形的话,.本文原创自1point3acres论坛
1.把所有点存入hashset中
2. 从所有点中选取点 i 和点 j (for each i from 0 to n-1, find j from i to n-1),i 点和 j点分别表示长方形的左下角和右上角. 做如下循环:
  2.1 假设左下和右上角是(x1, y1),(x2, y2),可以推算出左上角为(x1, y2)右下角为(x2, y1).
  2.2 查找set中是否存在(x1, y2), (x2, y1). 若都存在,计算面积并更新最小面积
3. 输出最小面积。. From 1point 3acres bbs
O(N^2)
回复 支持 2 反对 0

使用道具 举报

我的人缘0
primbo 发表于 2016-11-30 05:51:45 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
  1. class Solution {
  2. public:. 一亩-三分-地,独家发布
  3.     int findSmallestRectangle(vector<pair<int,int>>& points) {
  4.         int res = INT_MAX;. From 1point 3acres bbs
  5.         set<pair<int, int>> s;. 一亩-三分-地,独家发布
  6.         for(int i = 0; i < points.size(); i++) {
  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})) {-google 1point3acres
  13.                     int area = abs(points[i].first - points[j].first)* abs(points[i].second - points[j].second);
  14.                     res = min(area, res);
  15.                 }
  16.             }
  17.         }
  18.         return res;
  19.     }
  20. };
复制代码
回复 支持 0 反对 1

使用道具 举报

我的人缘0
catinclay 发表于 2016-11-30 03:27:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
好像在地里看过这道题 但当时有说rectangle是平行或垂直于x跟y轴的

. more info on 1point3acres假如同样有这个条件, 那就把每个点都当作rectangle的左下角, 试着看看能不能跟另外三个点形成rectangle, 记得用Map<Integer, Map<Integer, Integer>>的嵌套map来存点的资讯这样可以n^2解
不知道有没有更好的方法
回复 支持 反对

使用道具 举报

我的人缘0
kunge12345 发表于 2016-11-30 04:42:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
chestnut9919 发表于 2016-11-30 03:39
之前onsite有人考过这题,如果只考虑跟xy轴平行的长方形的话,. from: 1point3acres
1.把所有点存入hashset中
2. 从所有点中选 ...

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

使用道具 举报

我的人缘0
primbo 发表于 2016-11-30 05:35:55 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
chestnut9919 发表于 2016-11-30 03:39. From 1point 3acres bbs
之前onsite有人考过这题,如果只考虑跟xy轴平行的长方形的话,
1.把所有点存入hashset中. from: 1point3acres
2. 从所有点中选 ...

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

使用道具 举报

我的人缘0
primbo 发表于 2016-11-30 06:01:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
kunge12345 发表于 2016-11-30 04:42
若不平行呢?是不是需要O(n^3)而且检查边垂直?

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

使用道具 举报

我的人缘0
kunge12345 发表于 2016-11-30 06:02:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
primbo 发表于 2016-11-30 06:01
若可以不平行,那么就再加一层for loop 找第三个可以和之前的两个点组成直角三角形的点(a2 + b2 =c2). ...

握手,跟我想法一样
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
chaosMonkey 发表于 2016-12-12 15:49:01 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

&&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的矩形  
回复 支持 反对

使用道具 举报

我的人缘0
ayzmkkk 发表于 2016-12-12 22:05:26 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
chaosMonkey 发表于 2016-12-12 15:49-google 1point3acres
&&s.count({points[j].second, points.first})  这里应该是s.count({points[j].first, points.second})吧 ...

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

使用道具 举报

我的人缘0
bigbearlake 发表于 2017-3-15 13:07:03 | 显示全部楼层
  此人我要顶:
 
100% (4) 【我投】
  此人我要踩:
 
0% (0) 【我投】

第二个应该是{points[j].first, points.second}
回复 支持 反对

使用道具 举报

我的人缘0
bigbearlake 发表于 2017-3-15 13:29:06 | 显示全部楼层
  此人我要顶:
 
100% (4) 【我投】
  此人我要踩:
 
0% (0) 【我投】
写了下code,必须得去重
  1. public class SmallestRectangle {

  2.     public static void main(String[] args) {
  3.         SmallestRectangle ss = new SmallestRectangle();. more info on 1point3acres
  4.         int[][] points = {{0,0}, {1,0}, {0,1}, {1,2}, {2,0}, {2,1}};
  5.         System.out.println(ss.findSmallestRectangle(points));
  6.     }

  7.     public int findSmallestRectangle(int[][] points) {. 牛人云集,一亩三分地
  8.         int res = Integer.MAX_VALUE;
  9.         if (points == null || points.length < 4) {
  10.             return res;
  11.         }

  12.         HashSet<String> set = new HashSet<>();
  13.         for (int[] p : points) {
  14.             set.add(p[0] + "#" + p[1]);
  15.         }

  16.         for (int i = 0; i < points.length; i++) {. 牛人云集,一亩三分地
  17.             for (int j = i + 1; j < points.length; j++) {. 1point 3acres 论坛
  18.                 String p1 = points[i][0] + "#" + points[i][1];. 牛人云集,一亩三分地
  19.                 String p2 = points[j][0] + "#" + points[j][1];
  20.                 String p3 = points[i][0] + "#" + points[j][1];
  21.                 String p4 = points[j][0] + "#" + points[i][1];.1point3acres网
  22.                 set.remove(p1);
  23.                 set.remove(p2);. Waral 博客有更多文章,
  24.                 if (set.contains(p3)
  25.                         && set.contains(p4)) {.1point3acres网
  26.                     int area = Math.abs(points[i][0] - points[j][0]) * Math.abs(points[i][1] - points[j][1]);. from: 1point3acres
  27.                     res  = Math.min(area, res);
  28.                 }
  29.                 set.add(p1);
  30.                 set.add(p2);
  31.             }
  32.         }

  33.         return res;
  34.     }. 围观我们@1point 3 acres
  35. }. 围观我们@1point 3 acres
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
YuanhuiYang 发表于 2017-3-15 17:22:03 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
扫描线算法
回复 支持 反对

使用道具 举报

我的人缘0
YuanhuiYang 发表于 2017-3-15 17:22:59 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
primbo 发表于 2016-11-30 05:35-google 1point3acres
可不可以用扫描线算法做呢?

可以的 很稳
回复 支持 反对

使用道具 举报

我的人缘0
zfzzwz 发表于 2017-3-21 11:31:11 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

请问这个如何用扫面线做?我想了下没有什么头绪,谢谢!
回复 支持 反对

使用道具 举报

我的人缘0
YuanhuiYang 发表于 2017-3-22 07:20:02 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zfzzwz 发表于 2017-3-21 11:31
请问这个如何用扫面线做?我想了下没有什么头绪,谢谢!

这类题 扫描线都是 必杀
回复 支持 反对

使用道具 举报

我的人缘0
YuanhuiYang 发表于 2017-3-22 07:20:24 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zfzzwz 发表于 2017-3-21 11:31
请问这个如何用扫面线做?我想了下没有什么头绪,谢谢!

我过几天 发给你哈
回复 支持 反对

使用道具 举报

我的人缘0
zfzzwz 发表于 2017-3-26 08:47:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
YuanhuiYang 发表于 2017-3-22 07:20.本文原创自1point3acres论坛
我过几天 发给你哈

谢谢!请问你说的扫描线是用来做会议室问题,天上几个飞机问题的那个扫面线吗?我还是没想出来。。。
回复 支持 反对

使用道具 举报

我的人缘0
exthrash 发表于 2018-3-5 11:15:21 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
https://www.quora.com/From-a-given-set-of-points-how-would-you-find-the-set-of-4-points-forming-a-rectangle
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-6-23 23:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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