Fall 18 我的 HCI 申请复盘与策略总结

一亩三分地论坛

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

最近看过此主题的会员

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

Uber电面-4sum

[复制链接] |试试Instant~ |关注本帖
我的人缘0
jaly50 发表于 2015-8-28 13:08:39 | 显示全部楼层 |阅读模式
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】

2015(7-9月) 码农类General 硕士 全职@Uber - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
今天uber电面
问了三年规划5年目标...(`_′)ゞ

幸运地考到4sum...leetcode原题
不幸运地,我之前的解法都是n^3.但今天要我写出n^2的代码。
没来得及把bug调完 ....sad

贴一记后来反省写完的代码....
  1. class Solution {. Waral 博客有更多文章,
  2.         // store index of pair
  3.         static class Pair {
  4.                 Integer[] eles;
  5. . 1point 3acres 论坛
  6.                 public Pair(int a, int b, int c, int d) {. more info on 1point3acres
  7.                         eles = new Integer[] { a, b, c, d };
  8.                         Arrays.sort(eles);
  9.                 }

  10.                 static boolean valid(int a, int b, int c, int d) {
  11.                         if (a == c || b == d || b == c). 一亩-三分-地,独家发布
  12.                                 return false;. From 1point 3acres bbs
  13.                         return true;
  14.                 }
  15. .本文原创自1point3acres论坛
  16.                 public int hashCode() {
  17.                         Integer ans = 2;
  18.                         for (int i : eles) {
  19.                                 ans += ans * i;
  20.                         }
  21.                         return ans;
  22.                 }

  23.                 public boolean equals(Object that) {
  24.                         if (!(that instanceof Pair))
  25.                                 return false;
  26.                         if (that == this). From 1point 3acres bbs
  27.                                 return true;
  28.                         for (int i = 0; i < 4; i++) {
  29.                                 if (this.eles[i] != ((Pair) that).eles[i]). 1point 3acres 论坛
  30.                                         return false;-google 1point3acres
  31.                         }

  32.                         return true;. 留学申请论坛-一亩三分地
  33.                 }

  34.         }
    .本文原创自1point3acres论坛

  35.         public static List<List<Integer>> sum4(List<Integer> list, int target) {
  36.                 Collections.sort(list); 来源一亩.三分地论坛.
  37.                 List<List<Integer>> ans = new ArrayList<List<Integer>>();

  38.                 // Map <2sum, list of pairs>
  39.                 Map<Integer, List<List<Integer>>> map = new HashMap<Integer, List<List<Integer>>>();

  40.                 for (int i = 0; i < list.size(); i++) {. 牛人云集,一亩三分地
  41.                         for (int j = i + 1; j < list.size(); j++) {
  42.                                 int sum2 = list.get(i) + list.get(j);
  43.                                 List<Integer> pair = new ArrayList<Integer>();
  44.                                 pair.add(i);
  45.                                 pair.add(j);
  46.                                 if (map.containsKey(sum2)) {
  47.                                         map.get(sum2).add(pair);
  48.                                 } else {
  49.                                         List<List<Integer>> listofPair = new ArrayList<List<Integer>>();
  50.                                         listofPair.add(pair);
  51.                                         map.put(sum2, listofPair);
  52.                                 }
  53.                         }
  54.                 }
    . 一亩-三分-地,独家发布

  55.                 Set<Pair> set = new HashSet<Pair>();
  56.                 for (int key : map.keySet()) {
  57.                         int anotherkey = target - key;
  58.                         if (anotherkey < key)
  59.                                 continue;
  60.                         if (map.containsKey(anotherkey)) {
  61.                                 for (List<Integer> firstValues : map.get(key)) {
  62.                                         int a = firstValues.get(0);
  63.                                         int b = firstValues.get(1);-google 1point3acres
  64.                                         for (List<Integer> secondValues : map.get(anotherkey)) {
  65.                                                 int c = secondValues.get(0);
  66.                                                 int d = secondValues.get(1);. 1point3acres
  67.                                                 if (Pair.valid(a, b, c, d)) {
  68.                                                         Pair pair = new Pair(a, b, c, d);
  69.                                                         set.add(pair);

  70.                                                 }

  71.                                         }. 一亩-三分-地,独家发布

  72.                                 }
  73. . 1point3acres
  74.                         }
  75.                 }
  76. . Waral 博客有更多文章,
  77.                 for (Pair p : set) {
  78.                         List<Integer> path = new ArrayList<Integer>();. 牛人云集,一亩三分地
  79.                         for (Integer ele : p.eles) {. 牛人云集,一亩三分地
  80.                                 path.add(list.get(ele));
  81.                         }
  82.                         ans.add(path);
  83.                 }
  84.                 return ans;. from: 1point3acres
  85.         }

  86.         public static void main(String[] args) {. from: 1point3acres
  87.                 ArrayList<String> strings = new ArrayList<String>();
  88.                 Integer[] numbers = new Integer[] { 4, 2, 6, 1, 5, 3 };
  89.                 List<Integer> list = Arrays.asList(numbers);
  90.                 System.out.println(sum4(list, 16));. 留学申请论坛-一亩三分地

  91.         }
  92. }
复制代码

评分

参与人数 4大米 +68 收起 理由
ymqytw + 3 感谢分享!
会编程的猪先生 + 5 谢谢你的介绍!
martin31hao + 10 感谢分享!
whdawn + 50

查看全部评分


上一篇:请教Uber一道经典面经题,Excel设计,主要请教follow up的内容
下一篇:10钟前google电面

本帖被以下淘专辑推荐:

我的人缘0
likenisha 发表于 2015-11-29 06:02:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我怎么觉得这个代码不是很对。。。。比如{1,2,3}, pair会是{1,2}{2,3}{1,3},但很明显这个array是没结果的,可是pair可能target等于7的时候有一个输出,似乎不太对
回复 支持 1 反对 0

使用道具 举报

我的人缘0
 楼主| jaly50 发表于 2015-8-29 11:28:16 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
bluezebra 发表于 2015-8-29 11:09
这么良心的帖子没人顶?感谢楼主!

应该加分 XD


拿到onsite了 :)
回复 支持 0 反对 1

使用道具 举报

我的人缘0
 楼主| jaly50 发表于 2015-8-28 13:22:02 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
Give a array of integers, find all unique 4 number combination (a, b, c, d) that satisfy:
1. a, b, c and d is in the array and each element in the array can be used only once.
2. a + b + c + d = target
3. a <= b <= c <= d
  
    参数要求: public  List<List<Integer>> sum4(List<Integer> list, int target) {}
回复 支持 反对

使用道具 举报

我的人缘0
bluezebra 发表于 2015-8-29 11:09:05 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这么良心的帖子没人顶?感谢楼主!
回复 支持 反对

使用道具 举报

我的人缘0
jy_121 发表于 2015-8-29 11:45:34 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
恭喜楼主,好像之前跟CS61B的时候见过你的帖子。从O(n3)到O(n2)就是将一层的遍历换成hashmap吗
回复 支持 反对

使用道具 举报

我的人缘0
wenqiang88 发表于 2015-8-29 11:52:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
如果array里面有重复元素的话,那么worst case 不止O(n^2)吧,因为map里的list会很长
回复 支持 反对

使用道具 举报

我的人缘1
whdawn 发表于 2015-8-29 11:59:12 | 显示全部楼层
  此人我要顶:
 
75% (3) 【我投】
  此人我要踩:
 
25% (1) 【我投】
学长还在匹村等TOC吗~
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| jaly50 发表于 2015-8-29 13:10:00 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
wenqiang88 发表于 2015-8-29 11:52. more info on 1point3acres
如果array里面有重复元素的话,那么worst case 不止O(n^2)吧,因为map里的list会很长

嗯...worst case可能要n^4了...
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| jaly50 发表于 2015-8-29 13:10:36 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
whdawn 发表于 2015-8-29 11:59
学长还在匹村等TOC吗~

不是学长
不等TOC
骑驴找马
回复 支持 反对

使用道具 举报

我的人缘1
whdawn 发表于 2015-8-29 13:22:56 | 显示全部楼层
  此人我要顶:
 
75% (3) 【我投】
  此人我要踩:
 
25% (1) 【我投】
jaly50 发表于 2015-8-29 13:10
不是学长
不等TOC
骑驴找马

那就是学姐了。。。我错了
回复 支持 反对

使用道具 举报

我的人缘0
larry_cn 发表于 2015-8-29 13:36:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

然而 楼主 没有说明 n^2 在哪里
也没有 看出来 代码 是 n^2
回复 支持 反对

使用道具 举报

我的人缘0
larry_cn 发表于 2015-8-29 13:41:39 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
jaly50 发表于 2015-8-29 13:10
嗯...worst case可能要n^4了...

worst case 也不应该 是 n^4.... 吧
应该 是 n^3
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| jaly50 发表于 2015-8-30 06:41:40 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
larry_cn 发表于 2015-8-29 13:41
worst case 也不应该 是 n^4.... 吧
. 一亩-三分-地,独家发布应该 是 n^3

假设n个数都是1, target是4.
这样子 map里就只有 key=2; Value中list.size=n*(n+1)/2
. 一亩-三分-地,独家发布
. more info on 1point3acres
所以下面的循环中  . 1point 3acres 论坛
(key:map.keySet()) //o(1)
for (firstValues:map.get(key))  // o(n^2)
for (secondValues: map.get(anotherkey) )// o(n^2)

这不是n^4么
回复 支持 反对

使用道具 举报

我的人缘0
larry_cn 发表于 2015-8-30 09:55:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
jaly50 发表于 2015-8-30 06:41
假设n个数都是1, target是4.
这样子 map里就只有 key=2; Value中list.size=n*(n+1)/2
. 1point3acres
嗯  是n^4 这个 地方 额 没考虑对

(不过楼主 那个 size 和 little-O 用错了)
回复 支持 反对

使用道具 举报

我的人缘0
hulahu 发表于 2015-8-30 11:07:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主, 下次打给答案, 照抄。 好难哦。。
回复 支持 反对

使用道具 举报

我的人缘0
会编程的猪先生 发表于 2015-9-4 06:24:18 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
所以worst case是O(n^4) 根据楼主面试情况 这是面试官想要的答案吗?
回复 支持 反对

使用道具 举报

我的人缘0
mary小丸子 发表于 2015-9-4 06:55:42 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主你好。我是CMU 14 FaLL ECE的。顶楼主。也要电面了。
回复 支持 反对

使用道具 举报

我的人缘0
aplusplus 发表于 2015-9-13 06:24:03 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这题不可能< O(n^3)的ba
回复 支持 反对

使用道具 举报

我的人缘0
f1371342385 发表于 2015-9-18 07:25:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
LZ,你的这个方法就是存下标啊 然后找出来以后得到4 sum的解啊
回复 支持 反对

使用道具 举报

我的人缘0
jypdw 发表于 2015-10-19 07:03:06 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
LZ, 算法有点问题吧?
test case :
1. {5,5,5,5} 20
2. { 4, 2, 6, 1, 5, 3, 0,4,0 } 16
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-20 21:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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