一亩三分地论坛

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

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

F 店面

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

2016(4-6月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Pass在职跳槽

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

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

x
周二电面F。吃水不忘挖井人,回馈地里。. 鍥磋鎴戜滑@1point 3 acres
电面两道题:
1. Moving Average of An Input Stream. The size of a window is n
For example:
input = [1, 1, 2, 3, 3, 4, 4, 4, 5.....], n = 3;
moving average = [1, 1, 1.33, 2, 2.67, 3.33, 3.67, 4, 4.33...]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

public void movingAverage(Stream input, int windowSize) .1point3acres缃

.鏈枃鍘熷垱鑷1point3acres璁哄潧
2. Decode Ways.

评分

2

查看全部评分

rjr130 发表于 2016-6-12 06:44:10 | 显示全部楼层
请问楼主是如何拿到电面的呀?之前有工作经历么还是背景非常牛。。

补充内容 (2016-6-12 06:44):
Sorry是想问之前有多久工作经历...
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2016-6-12 06:47:50 | 显示全部楼层
rjr130 发表于 2016-6-12 06:44-google 1point3acres
请问楼主是如何拿到电面的呀?之前有工作经历么还是背景非常牛。。

补充内容 (2016-6-12 06:44):

领英上系统推荐一个F的HR,加了她,然后她就主动问我加她是为了新机会吗,我说是的……接下来的一切就自然而然的发生了……
不牛,菜B一个……
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-6-12 08:46:08 | 显示全部楼层
请问你第一题是怎么答的,用队列吗? 然后这题有没有follow up呢
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-12 08:54:49 | 显示全部楼层
yueliu2366 发表于 2016-6-12 08:46
请问你第一题是怎么答的,用队列吗? 然后这题有没有follow up呢

双指针即可。
  1. #include <vector>
  2. #include <iostream>
  3. using namespace std;
  4. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  5. vector<double> movingAverage(vector<int>& nums, int n) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.   vector<double> res;
  7.   int j = 0;
  8.   int sum = 0;
  9.   for(int i = 0; i < nums.size(); ++i) { // for test. 鍥磋鎴戜滑@1point 3 acres
  10.     sum = sum + nums[i];
  11.     if(i - j < n-1) {
  12.       res.push_back(nums[i]);. visit 1point3acres.com for more.
  13.     } else {
  14.       double tmp = double(sum) / n;
  15.       res.push_back(tmp);
  16.       sum = sum - nums[j];
  17.       j++;
  18.     }
  19.   }
  20.   return res;
  21. }.1point3acres缃

  22. int main(void) {
  23.   vector<int> nums{1, 1, 2, 3, 3, 4, 4, 4, 5};
  24.   vector<double> res = movingAverage(nums, 3);
  25.   for(int i = 0; i < res.size(); ++i) {
  26.     cout << res[i] << endl;
  27.   }
  28. }
复制代码
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-6-12 10:04:02 | 显示全部楼层
. 1point 3acres 璁哄潧
你好,如果给的是一个array,那么用j指针可以指向要删除的那个元素,你这个解法可以行,空间复杂度是O(1)。但是楼主的题目好像给的是一个Stream input, 我理解是不是应该有个input.getNext()的方法可以得到下一个进来的元素?如果是这样的话,我只能想到队列,双指针的方法好像不可行的,因为你无法知道这次要删除哪个元素?
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-12 10:05:45 | 显示全部楼层
yueliu2366 发表于 2016-6-12 10:04
你好,如果给的是一个array,那么用j指针可以指向要删除的那个元素,你这个解法可以行,空间复杂度是O(1 ...

删除什么? j 指针 和 i 指针保持 n-1的距离就可以了。即使stringstream,也没关系阿,保持i递增不就行了。
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-6-12 10:18:13 | 显示全部楼层
可能是我理解错了,我的理解是input不是一个数组,每次你只能获得一个新的元素,如果这样的话,你的代码第16行sum = sum - nums[j],如何知道要删除哪个元素?
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-12 10:21:16 | 显示全部楼层
yueliu2366 发表于 2016-6-12 10:18
可能是我理解错了,我的理解是input不是一个数组,每次你只能获得一个新的元素,如果这样的话,你的代码第1 ...

那就搞一个K size大的deque。。。。
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2016-6-12 10:51:07 | 显示全部楼层
yueliu2366 发表于 2016-6-12 08:46
请问你第一题是怎么答的,用队列吗? 然后这题有没有follow up呢

我用的queue,没有follow up,写完了,过一个test case,就move on到下一题了
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2016-6-12 10:52:48 | 显示全部楼层
blackrose 发表于 2016-6-12 10:21. 1point 3acres 璁哄潧
那就搞一个K size大的deque。。。。

多谢兄台的大米~
回复 支持 反对

使用道具 举报

zhangyichi12 发表于 2016-6-17 01:19:54 | 显示全部楼层
我也觉得貌似两个变量就可以了。多谢。.鐣欏璁哄潧-涓浜-涓夊垎鍦
  1. vector<float> movingAvg(vector<int> &input, int cap) {
  2.     vector<float> res;
  3.     if(input.empty()) {
  4.         return res;
  5.     }
  6.     . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7.     float dqSum = 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8.     int dqSize = 0;;
  9.     for(int i = 0; i < input.size(); i++) {
  10.         if(dqSize < cap) {
  11.             dqSum += input[i];
  12.             dqSize += 1;
  13.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  14.         else {
  15.             dqSum -= input[i - cap];
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  16.             dqSum += input[i];
  17.         }
  18.         
  19.         res.push_back(dqSum / dqSize);
  20.     }
  21.    
  22.     return res;
  23. }
复制代码
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

 楼主| tianyangche 发表于 2016-6-17 01:44:39 | 显示全部楼层
zhangyichi12 发表于 2016-6-17 01:19
我也觉得貌似两个变量就可以了。多谢。.1point3acres缃
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次, ...

No, it is not possible. Input is a stream. You can't access to a give position easily.
回复 支持 反对

使用道具 举报

zhangyichi12 发表于 2016-6-18 01:32:05 | 显示全部楼层
tianyangche 发表于 2016-6-17 01:44
No, it is not possible. Input is a stream. You can't access to a give position easily.
-google 1point3acres
哦哦!多谢!那貌似是得用真queue了~
回复 支持 反对

使用道具 举报

cicean 发表于 2016-9-8 06:06:13 | 显示全部楼层
346. Moving Average from Data Stream
这题?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 04:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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