📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 11
跳转到指定楼层
上一主题 下一主题
收起左侧

Google电面4/17

全局:

2017(4-6月) 码农类General 硕士 全职@google - 猎头 - 技术电面  | | Pass | 在职跳槽

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
(刚刚发了贴可是我被审核了?所以没发出去?但是我又迫不及待想发出来贡献啊。。)
白人小姐姐就是nice啊。。我答的非常一般居然给我过了!
但是没有headcount了。。。。所以现在是等着hr联系其他的team然后等有机会可以直接去onsite
题目是地里的
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
所以就大概讲了一下然后小姐姐说她要去开会实在是不好意思就挂电话了,全程45分钟一分不多一分不少。。
没有进小黑屋太开心啦!两年前被印度大哥黑的进了黑屋现在还心有余悸。。

上一篇:Amazon OA 社招面经4/22/2017
下一篇:坞博电面

本帖被以下淘专辑推荐:

  • · Google|主题: 458, 订阅: 133
推荐
yanshuining 2017-6-10 01:47:18 | 只看该作者
全局:
liuhuan2002767 发表于 2017-6-9 17:38
这题就是用线段树啊,成段更新

我面试也碰到过这题,一开始我用线段树解,但是面试官不满意,说,调用update的次数很少,所以我最后用了interval。
回复

使用道具 举报

推荐
codemonk 2017-8-26 11:24:49 | 只看该作者
全局:
写了 fenwick tree 和 segment tree with lazy propagation 两个解法。通过这题我学会了lazy propagation
  1. class FenwickTree{
  2. public:
  3.     // idea:
  4.     // 1. toggle [i,j] is equivalent to toggle [1,i] then toggle[1,j]
  5.     // 2. let tree[i] stores the **total number of toggles** in the corresponding binary range
  6.     // 3. for a bulb x,
  7.     //    (i) sum of toggles in [1,x] is odd, if x belongs to [i,j] and x being toggled odd times, i.e. [1,j] will covers x odd times, while [1,i] covers x even times (or 0 time).
  8.     //   (ii) sum of toggles in [1,x] is even, if x is out of[i,j] or x is in [i,j] && x being toggled even times.
  9.     FenwickTree(int n_) {
  10.         n = n_;
  11.         tree.resize(n+1, 0);
  12.     }
  13.     vector<int> tree;
  14.     int n;
  15.     void update(int i, int add) {
  16.         for(; i > 0; i -= i&(-i))
  17.             tree[i] += add;
  18.     }
  19.    
  20.     int query(int i) {
  21.         int ans = 0;
  22.         for(; i <= n; i += i&(-i))
  23.             ans += tree[i];
  24.         return ans;
  25.     }
  26.    
  27.     bool isOn(int i) {
  28.         return query(i) & 1;
  29.     }
  30.    
  31.     void toggle(int start, int end) {
  32.         update(start-1, 1);
  33.         update(end, 1);
  34.     }
  35.    
  36.     void run() {
  37.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  38.         cout << endl;
  39.         toggle(2,5);
  40.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  41.         cout << endl;
  42.         toggle(3,8);
  43.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  44.         cout << endl;
  45.         toggle(4,6);
  46.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  47.         cout << endl;
  48.     }
  49. };

  50. class SegmentTree{ // muse use lazy propagation to guarantee log(n) complexity for update() on a range of indices.
  51.     // worst case space complexity O(4*N) with lazy propagation.
  52.     // to learn lazy propagation: http://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/
  53. public:  
  54.     struct TreeNode{
  55.         int lb, ub, count;
  56.         TreeNode *left, *right;
  57.         TreeNode(int lb_, int ub_) {
  58.             lb = lb_;
  59.             ub = ub_;
  60.             count = 0;
  61.             left = right = nullptr;
  62.         }
  63.     };
  64.     TreeNode* root;
  65.     int n;
  66.     unordered_map<TreeNode*, int> lazy;
  67.    
  68.     SegmentTree(int n_) {
  69.         n = n_;
  70.     }
  71.    
  72.     TreeNode* build(int lb, int ub){
  73.         if(lb > ub) return nullptr;
  74.         TreeNode* node = new TreeNode(lb, ub);
  75.         if(lb == ub) return node;
  76.         int mid = lb + (ub - lb) / 2;
  77.         node->left = build(lb, mid);
  78.         node->right = build(mid+1, ub);
  79.         return node;
  80.     }
  81.    
  82.     void update(TreeNode* node, int lo, int hi, int add) {
  83.         if(lazy[node] != 0) {
  84.             node->count += (node->ub - node->lb + 1) * lazy[node];
  85.             if(node->left) lazy[node->left] += lazy[node];
  86.             if(node->right) lazy[node->right] += lazy[node];
  87.             lazy[node] = 0;
  88.         }
  89.         if(!node || node->ub < lo || node->lb > hi) return;
  90.         if(lo <= node->lb && node->ub <= hi) {
  91.             node->count += (node->ub - node->lb + 1) * add;
  92.             if(node->left) lazy[node->left] += add;
  93.             if(node->right) lazy[node->right] += add;
  94.             return;
  95.         }
  96.         update(node->left, lo, hi, add);
  97.         update(node->right, lo, hi, add);
  98.         node->count = (node->left ? node->left->count : 0) + (node->right ? node->right->count : 0);
  99.     }
  100.    
  101.     int query(TreeNode* node, int start, int end){
  102.         if(lazy[node] != 0) {
  103.             node->count += (node->ub - node->lb + 1) * lazy[node];
  104.             if(node->left) lazy[node->left] += lazy[node];
  105.             if(node->right) lazy[node->right] += lazy[node];
  106.             lazy[node] = 0;
  107.         }
  108.         if(!node || start > node->ub || end < node->lb) return 0;
  109.         if(start <= node->lb && node->ub <= end) return node->count;
  110.         return query(node->left, start, end) + query(node->right, start, end);
  111.     }
  112.    
  113.     void toggle(int start, int end) {
  114.         update(root, start, end, 1);
  115.     }

  116.     bool isOn(int i) {
  117.         return query(root, i, i) & 1;
  118.     }

  119.     void run() {
  120.         root = build(1, n);
  121.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  122.         cout << endl;
  123.         toggle(2,5);
  124.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  125.         cout << endl;
  126.         toggle(3,8);
  127.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  128.         cout << endl;
  129.         toggle(4,6);
  130.         for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
  131.         cout << endl;
  132.     }
  133. };

  134. int main() {
  135.     FenwickTree ft(10); // 10 bulbs
  136.     ft.run();
  137.     cout << "----------" << endl;
  138.     SegmentTree st(10);
  139.     st.run();
  140. }
复制代码
回复

使用道具 举报

全局:
感谢楼主分享!楼主加油!
楼主可以说说如何用线段树来解的么?
我目前的想法:每次toggle的时候不update每一个灯泡,只update这个interval,有重合的部分就消掉,这样剩下的所有interval就是涵盖了当前被打开的灯;调用isOn得时候二分查找这个灯泡是否在已有的interval中。这样做减少了toggle的时间复杂度,但是增大了isOn的时间复杂度。不知道这样做对否?
回复

使用道具 举报

🔗
SamSam88 2017-4-30 15:16:07 | 只看该作者
全局:
ding ding ding
回复

使用道具 举报

🔗
 楼主| waye_tt 2017-5-1 06:40:26 | 只看该作者
全局:
lianjishuati 发表于 2017-5-1 01:10
感谢楼主分享!楼主加油!
楼主可以说说如何用线段树来解的么?
我目前的想法:每次toggle的时候不update每 ...

我理解跟你说的差不多的,我理解就是在toggle的时候update区间,isOn也会增加因为做二分查找
回复

使用道具 举报

🔗
yanshuining 2017-5-2 01:50:21 | 只看该作者
全局:
线段树的话空间复杂度比较高,用interval来表示区间灯泡的ON/OFF比较好
回复

使用道具 举报

🔗
edyyy 2017-5-2 08:48:48 | 只看该作者
全局:
现在还找new grad吗??
回复

使用道具 举报

🔗
Michael2013 2017-5-16 11:33:13 | 只看该作者
全局:
是不是可以用BIT,update(i, j) 转换为在i的位置+1, 在j+1的位置-1,isOn(i) 就是sum(0,i)为奇数
update(i, j): log(n)
isOn(i): log(n)
回复

使用道具 举报

🔗
dsxz 2017-5-17 04:15:02 | 只看该作者
全局:
谢谢楼主,总算弄明白小灯泡的题了。这是把几个灯泡设一个总开关吗?
回复

使用道具 举报

🔗
 楼主| waye_tt 2017-5-17 08:16:29 | 只看该作者
全局:
dsxz 发表于 2017-5-17 04:15
谢谢楼主,总算弄明白小灯泡的题了。这是把几个灯泡设一个总开关吗?

我的理解是这样子的
回复

使用道具 举报

全局:
这题就是用线段树啊,成段更新
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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