一亩三分地论坛

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

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

发个Houzz的跪经吧

[复制链接] |试试Instant~ |关注本帖
stevez 发表于 2016-6-4 05:51:49 | 显示全部楼层 |阅读模式

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

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

x
感觉地里他们家面经不多,也是属于初创的Unicorn公司,看里面的人都很牛的样子。
LZ是3月底海投的,岗位是Unity Engineer,一直没有消息。半个月后直到他们recruiter给我打电话,原来是把我邮箱搞错了=_=.1point3acres缃
然后约了第一轮电面,上来一阵寒暄,然后开始做题. From 1point 3acres bbs
1. two sum, 只要返回任意一个组合就行,还是排好序无重复的那种,瞬秒。
2. three sum,我说先挑一个数字然后再用2sum,他说不错,还能不能更快,要我写个nlogn的写法, lz当时也是懵逼了。他提示说我能不能用binary search的思路去找后面两个sum,我想了下好像也没法logn啊。。墨迹半天没搞出来,然后他说那跳过吧。。。
然后问了个UI设计题:说要在Unity里做一个有一百万条的菜单,还有filter能选择相应的菜系,问怎么设计。
最后问了下你觉得5-10年以后的家装app应该是什么样,然后lz一顿扯。。他说不错我们就是打算做这个.... 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
因为一个题没做出来,lz面完以后还是很懵逼,去wiki了下好像3sum nlogn解法是要用FFT的,明显和他想说的不太一样。。。-google 1point3acres

然后两个小时以后发来邮件约第二轮电面。
面试那天lz状态不是很好,上来第一题是判断两个矩形是否相交。lz很2的在想如何靠矩形对角两个点的关系判断,还漏了两种情况,代码也很丑。。后来一看好像lc里面有个easy题和这个类似的。。lz还做过。。
然后面了个Unity的代码题,问怎么样写一个bouncing ball,写完以后被提示了两次才改完所有的bug。。此时已经1小时10分钟了。面试官还是很给面子的,无奈当时水平实在太烂了。。。
然后第二天邮件通知,不出所料的跪了

大米,然后希望有Unity相关经验的同学可以试着投投哈,感觉他们还是很想招人的。

评分

2

查看全部评分

 楼主| stevez 发表于 2016-6-4 05:54:43 | 显示全部楼层
好像发错版了。。。这个能移动到面经版么。。
回复 支持 反对

使用道具 举报

jerryyu3000 发表于 2016-6-27 13:27:46 | 显示全部楼层
樓主好人 好人一生平安
回复 支持 反对

使用道具 举报

liu.haonan 发表于 2016-10-17 08:35:31 | 显示全部楼层
这个我好像以前写过,就是用binary search在查找的时候稍微优化一下。
  1. public class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         List<List<Integer>> res = new LinkedList<>();
  4.         Arrays.sort(nums);
  5.         if (nums == null || nums.length < 3) return res;
  6.         int curi = Integer.MAX_VALUE;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7.         for (int i = 0; i < nums.length - 2; i++){
  8.             if (curi == nums[i]) continue;
  9.             curi = nums[i];
  10.             int target = 0 - nums[i];
  11.             int h = i+1, t = nums.length - 1;
  12.             if (nums[i+1] + nums[i+2] > target) break;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.             if (nums[nums.length - 2] + nums[nums.length - 1] < target ) continue;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.             int curh = Integer.MAX_VALUE;
  15.             int curt = Integer.MIN_VALUE;
  16.             while (h < t){
  17.                 if (h == -1 || t == -1) break;
  18.                 //System.out.println("i = "+ i + ", curh: "+ curh + ", " + nums[i]+ "+" + nums[h] + "+" + nums[t] + "=" + (nums[h] + nums[t]) + ", target = " + target);. from: 1point3acres.com/bbs
  19.                 curh = nums[h];
  20.                 curt = nums[t];
  21.                 if (nums[h] + nums[t] == target){
  22.                     List<Integer> cbn = new LinkedList<>();
  23.                     cbn.add(nums[i]);
  24.                     cbn.add(nums[h]);
  25.                     cbn.add(nums[t]);
  26.                     res.add(cbn);

  27.                     while (h < t && (nums[h] == curh && curt == nums[t])){. Waral 鍗氬鏈夋洿澶氭枃绔,
  28.                       h++;
  29.                     }
  30.                     while (h < t &&  curt == nums[t]){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  31.                        t--;
  32.                     }
  33.                 } else if ( nums[h] + nums[t] > target){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  34.                     t = helper2(nums, h+1, t, target - curh);
  35.                 } else {
  36.                     h = helper1(nums, h, t-1, target - curt);
  37.                 }. 1point 3acres 璁哄潧
  38.             }
  39.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  40.         return res;
  41.     }
  42.    
  43.     public int helper1(int[] nums, int start, int end, int target){
  44.         int h = start;. visit 1point3acres.com for more.
  45.         int t = end;
  46.         while (h + 1 < t){
  47.             int mid = h + (t - h)/2;. Waral 鍗氬鏈夋洿澶氭枃绔,
  48.             if (nums[mid] >= target){
  49.                 t = mid;. 鍥磋鎴戜滑@1point 3 acres
  50.             } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  51.             else if (nums[mid] < target) h = mid;

  52.         }
  53.         if (nums[h] >= target){
  54.             return h;
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  55.         }
  56.         if (nums[t] >= target){
  57.             return t;
  58.         }. visit 1point3acres.com for more.
  59.         return -1;
  60.     }
  61.     public int helper2(int[] nums, int start, int end, int target){.1point3acres缃
  62.         int h = start;
  63.         int t = end;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  64.         while (h + 1 < t){. more info on 1point3acres.com
  65.             int mid = h + (t - h)/2;
  66.             if (nums[mid] <= target){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  67.                 h = mid;
  68.             }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  69.             else if (nums[mid] > target) t = mid;
  70.         }
  71.         if (nums[t] <= target){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  72.             return t;
  73.         }
  74.         if (nums[h] <= target){
  75.             return h;
  76.         }
  77.         return -1;-google 1point3acres
  78.     }
  79. }
复制代码

补充内容 (2016-10-17 08:36):. 1point3acres.com/bbs
代码巨丑 = =。。

补充内容 (2016-10-17 08:36):. 1point3acres.com/bbs
各位凑合看一下
回复 支持 反对

使用道具 举报

 楼主| stevez 发表于 2016-10-17 14:07:50 | 显示全部楼层
liu.haonan 发表于 2016-10-17 08:35
这个我好像以前写过,就是用binary search在查找的时候稍微优化一下。

思路不错,但是本质上还是n方的,在2sum部分,你把本来t+1, h-1的constant time的操作变成了一个logn的操作,得到了一个lower/upper bound。一来一去是一样的。
其实k-sum问题的最低复杂度很早有人证明过,不可能低于n^ceil(k/2)。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 09:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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