传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2931|回复: 19
收起左侧

Uber电面

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

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

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

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

x
若干sparse vector, 求dot product. sparse vector非常大, 不能读进ram,
1. find a data structure to store them. from: 1point3acres.com/bbs
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
我也不知道我是否是对的 我已经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)
. from: 1point3acres.com/bbs
. 1point 3acres 璁哄潧
补充内容 (2016-6-17 20:08):
读的时候就用stream把两个vector 当integer stream读
回复 支持 反对

使用道具 举报

LearnerChao 发表于 2016-6-17 20:27:32 | 显示全部楼层
seekingJob320 发表于 2016-6-17 14:57
我也不知道我是否是对的 我已经po在leetcode讨论区了 你可以看看大家怎么说的
. Waral 鍗氬鏈夋洿澶氭枃绔,
链接?
自数字数字书
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-6-18 02:31:49 | 显示全部楼层
wtcupup 发表于 2016-6-17 10:33 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
用hash map存吗?

ram更加不行了

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

使用道具 举报

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

使用道具 举报

陈润鹏 发表于 2016-6-18 03:55:32 | 显示全部楼层
  1. /*
  2. * 若干sparse vector, 求dot product. sparse vector非常大, 不能读进ram,. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3. * 1. find a data structure to store them
  4. * 2. find the dot product
  5. * link :  http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=193428&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
  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.         . more info on 1point3acres.com
  30.        
  31.         public static void main(String[] args) {
  32.                 DotProduct q = new DotProduct();. Waral 鍗氬鏈夋洿澶氭枃绔,
  33.                 HashMap<Integer, Double> vector1= new HashMap<Integer, Double>();. from: 1point3acres.com/bbs
  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);. visit 1point3acres.com for more.
  40.                 System.out.println(q.dotProduct(vector1, vector2));. From 1point 3acres bbs
  41.         }.1point3acres缃
  42. }
复制代码
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

使用道具 举报

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
. From 1point 3acres bbs不知道是不是这样

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> 不就好了
. visit 1point3acres.com for more.
补充内容 (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代表对应的值 ...

我当时就用的vector<pair<int, int>>, 面试官说可以
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-25 14:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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