一亩三分地论坛

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

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

Uber电面

[复制链接] |试试Instant~ |关注本帖
seekingJob320 发表于 2016-6-17 10:28:25 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Uber - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
若干sparse vector, 求dot product. sparse vector非常大, 不能读进ram,
1. find a data structure to store them.鐣欏璁哄潧-涓浜-涓夊垎鍦
2. find the dot product

评分

4

查看全部评分

wtcupup 发表于 2016-6-17 10:33:48 | 显示全部楼层
用hash map存吗?
回复 支持 反对

使用道具 举报

LearnerChao 发表于 2016-6-17 13:28:12 | 显示全部楼层
有空的话能给详细说说吗?忙的话就算了
回复 支持 反对

使用道具 举报

 楼主| seekingJob320 发表于 2016-6-17 14:57:52 | 显示全部楼层
LearnerChao 发表于 2016-6-17 13:28
有空的话能给详细说说吗?忙的话就算了

我也不知道我是否是对的 我已经po在leetcode讨论区了 你可以看看大家怎么说的
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-17 20:00:04 | 显示全部楼层
seekingJob320 发表于 2016-6-17 14:57. from: 1point3acres.com/bbs
我也不知道我是否是对的 我已经po在leetcode讨论区了 你可以看看大家怎么说的

是求每个vector的dot product还是连续的dot
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-17 20:06:02 | 显示全部楼层
X = [x1, x2, …] Y = [y1, y2, …], dot product = x1 * y1 + x2 * y2 + … .

hashmap 存(index,dot product in index) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2016-6-17 20:08):
读的时候就用stream把两个vector 当integer stream读
回复 支持 反对

使用道具 举报

LearnerChao 发表于 2016-6-17 20:27:32 | 显示全部楼层
seekingJob320 发表于 2016-6-17 14:57
我也不知道我是否是对的 我已经po在leetcode讨论区了 你可以看看大家怎么说的

链接?. 1point3acres.com/bbs
自数字数字书
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-6-18 02:31:49 | 显示全部楼层

ram更加不行了

补充内容 (2016-6-18 03:55):
我理解错了 用hashmap应该是对的
回复 支持 反对

使用道具 举报

1064no1carry 发表于 2016-6-18 02:51:53 | 显示全部楼层
感谢分享!想问一下lz的leetcode讨论贴链接?谢谢!
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-6-18 03:55:32 | 显示全部楼层
  1. /*. more info on 1point3acres.com
  2. * 若干sparse vector, 求dot product. sparse vector非常大, 不能读进ram,
  3. * 1. find a data structure to store them. more info on 1point3acres.com
  4. * 2. find the dot product-google 1point3acres
  5. * link :  http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=193428&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311. 鍥磋鎴戜滑@1point 3 acres
  6. *
  7. * 是在 太大的 value,那就external sorting,一条一条读
  8. */
  9. public class DotProduct {
  10.         HashMap<Integer, Double> vector1 = new HashMap<Integer, Double>();
  11.         HashMap<Integer, Double> vector2 = new HashMap<Integer, Double>();
  12.        
  13.         public double dotProduct(HashMap<Integer, Double> vector1, HashMap<Integer,Double> vector2) {
  14.                 double sum =0;
  15.                 if (vector1.size()>vector2.size()) {
  16.                         HashMap<Integer, Double> temp =  vector1;
  17.                         vector1 = vector2;
  18.                         vector2 = temp;
  19.                 }
  20.                
  21.                 for (int i:vector1.keySet()) {
  22.                         if (vector2.containsKey(i)) {
  23.                                 sum+=vector1.get(i)*vector2.get(i);
  24.                         }
  25.                 }
  26.                
  27.                 return sum;
  28.         }
  29.        
  30.         . from: 1point3acres.com/bbs
  31.         public static void main(String[] args) {
  32.                 DotProduct q = new DotProduct();
  33.                 HashMap<Integer, Double> vector1= new HashMap<Integer, Double>();
  34.                 HashMap<Integer, Double> vector2 = new HashMap<Integer,Double>();
  35.                 vector1.put(3, 0.5);
  36.                 vector1.put(9, 0.75);
  37.                 vector1.put(6, 0.11);
  38.                 vector2.put(3, 0.60);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  39.                 vector2.put(4, 0.90);
  40.                 System.out.println(q.dotProduct(vector1, vector2));
  41.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  42. }
复制代码
. 鍥磋鎴戜滑@1point 3 acres

不知道是不是这样
回复 支持 反对

使用道具 举报

jordandong 发表于 2016-6-18 04:07:14 | 显示全部楼层
我FB店面问了这个, 只care 非零元素,非零元素存成{index, value}, 然后index一样的话才做运算
回复 支持 反对

使用道具 举报

1064no1carry 发表于 2016-6-18 04:13:17 | 显示全部楼层
jordandong 发表于 2016-6-17 12:07.鐣欏璁哄潧-涓浜-涓夊垎鍦
我FB店面问了这个, 只care 非零元素,非零元素存成{index, value}, 然后index一样的话才做运算

想问一下,就是数据结构就是 index value是么? 按顺序读进来后相同index乘,否则小的向后走一位是吧?
回复 支持 反对

使用道具 举报

chs5003 发表于 2016-6-18 04:26:46 | 显示全部楼层
陈润鹏 发表于 2016-6-18 03:55
不知道是不是这样

I think it's correct according to @jordandong's reply.
回复 支持 反对

使用道具 举报

jordandong 发表于 2016-6-18 14:27:36 | 显示全部楼层
1064no1carry 发表于 2016-6-18 04:13
想问一下,就是数据结构就是 index value是么? 按顺序读进来后相同index乘,否则小的向后走一位是吧?

是的,一样就乘,不一样走最小的直到最后
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-6-19 03:13:11 | 显示全部楼层
楼主面的是什么职位?thanks
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-19 03:42:56 | 显示全部楼层
陈润鹏 发表于 2016-6-18 03:55
不知道是不是这样

dot Product 就剩一个sum?
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-6-20 02:33:01 | 显示全部楼层
blackrose 发表于 2016-6-19 03:42
dot Product 就剩一个sum?

dot product 不是剩下一个sum吗?https://en.wikipedia.org/wiki/Dot_product
回复 支持 反对

使用道具 举报

谎言之躯 发表于 2016-6-25 00:29:50 | 显示全部楼层
jordandong 发表于 2016-6-18 14:27
是的,一样就乘,不一样走最小的直到最后

那也可以不用hashmap吧?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
比如在c++中,用个pair<int,int>类,pair中第一个int代表index,第二个int代表对应的值,然后两个输入向量被转化成vector<pair<int,int>>(vector是动态数组,在C++里)。最后再用类似与merge sort的方法,“一样就乘,不一样走最小的直到最后”。你觉得对吗?
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-25 01:06:39 | 显示全部楼层
- - 存spare matrix 用hashmap<<row,col>, value> 不就好了

补充内容 (2016-6-25 01:08):
然后用 mapreduce 算dot product了
回复 支持 反对

使用道具 举报

jordandong 发表于 2016-6-25 04:17:28 | 显示全部楼层
谎言之躯 发表于 2016-6-25 00:29
那也可以不用hashmap吧?
比如在c++中,用个pair类,pair中第一个int代表index,第二个int代表对应的值 ...
. 鍥磋鎴戜滑@1point 3 acres
我当时就用的vector<pair<int, int>>, 面试官说可以
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 09:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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