📣 VIP通行证夏日特惠 限时立减$68
回复: 18
跳转到指定楼层
上一主题 下一主题
收起左侧

10分钟前的G店面,面经

全局:

2016(7-9月) 码农类General 硕士 全职@google - 猎头 - 技术电面  | | Other | 在职跳槽

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

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

x
大龄男码农第一次面G, 印度大叔:, 但感觉没有要刁难的意思,迟到五分钟没寒暄直接做题。1. LC 303,
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
缩写错了。第二题timestamp整数

补充内容 (2016-8-5 22:09):
感谢三哥高抬贵手,又加了一个电面。G这么磨人对骑驴找马的人真是折磨

评分

参与人数 1大米 +10 收起 理由
mnmunknown + 10 感谢分享!

查看全部评分


上一篇:dropbox面经,vmware oa 题目
下一篇:Google new grad OA后的非技术面试怎么准备
推荐
yetangzhi 2016-8-4 18:46:58 | 只看该作者
全局:
第二题就是hash + binary serach, 用unordered_map<string,vector<pair<int,string>>> 来存,每次通过hash找历史记录,在历史记录上binary search lower_bound就行
回复

使用道具 举报

推荐
hxtang 2016-8-5 05:02:31 | 只看该作者
全局:
jason88628 发表于 2016-8-5 01:45
有道理。。。我两周前才系统的学了一下BIT,follow up被问到觉得运气真是好炸了,BIT代码简洁,写起来非 ...

其实segment tree可以借鉴BIT的表达,代码也可以很简洁的,用的空间也和BIT差不多(假定BIT还是需要另存一份data的话)。贴一个我刷leetcode的时候写的。
inline unsigned int next_power_of_two(unsigned int v) {
    --v;
    v |= (v >> 1);
    v |= (v >> 2);
    v |= (v >> 4);
    v |= (v >> 8);
    v |= (v >> 16);
    return v+1;
}

class NumArray {
public:
    NumArray(vector<int> &nums) : M(next_power_of_two(nums.size()+2)) {
        tree.resize(M<<1, 0);
        copy(nums.begin(), nums.end(), tree.begin()+M+1);
        for (int k = M-1; k>0; k--) tree[k] = tree[k<<1] + tree[k<<1|1];
    }

    void update(int i, int val) {
        i++; //number is 1 based
        int diff = val - tree[M+i];
        for (int key = M+i; key > 0; key >>= 1) tree[key] += diff;
    }

    int sumRange(int i, int j) {
        int sum = 0;
        for (i += M, j += M+2; i ^ j ^ 1; i >>= 1, j >>= 1) {
            if (!(i&1)) sum += tree[i^1];
            if (j&1) sum += tree[j^1];
        }
        return sum;
    }

private:
    vector<int> tree;  //tree stored in array, size is M*2
    int M; //smallest power of 2 greater or equal than nums.size()+2
};

回复

使用道具 举报

🔗
blackrose 2016-8-4 01:23:49 | 只看该作者
全局:
存个user + timestamp 的string?
回复

使用道具 举报

🔗
flex 2016-8-4 02:13:34 | 只看该作者
全局:
第二题是假设timestamp都是整数吗?如果是的话,用unordered_map<string, unordered_map<int, string>>来存储,第一个string是例子中的'a',后面一个int里是timestamp,最后的string是例子中'bad', 'good'。存储是O(1),查询a 的 timestamp n, 就要先从unordered_map里得到a对应的unordered_map<int,string>,然后把n一直递减到0,看unordered_map<int,string>有没有值,找到第一个值就返回,平均查询复杂度O(n)。我再想想能不能优化
回复

使用道具 举报

🔗
jy_121 2016-8-4 13:06:12 | 只看该作者
全局:
flex 发表于 2016-8-4 02:13
第二题是假设timestamp都是整数吗?如果是的话,用unordered_map来存储,第一个string是例子中的'a',后面 ...

可以用order map吗
回复

使用道具 举报

🔗
say543 2016-8-4 13:56:41 | 只看该作者
全局:
也是想到user + timestamp 的string . 楼主能说说吗?
回复

使用道具 举报

🔗
zhihaosun 2016-8-4 19:53:55 | 只看该作者
全局:
BIT挺难解释清楚的,相比之下segment tree虽然写得多,占内存也多,但好说啊
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
 楼主| jason88628 2016-8-5 01:41:49 | 只看该作者
全局:
say543 发表于 2016-8-4 13:56
也是想到user + timestamp 的string . 楼主能说说吗?

可能,题意没写清楚,这里面没有user, 你指的是例子里存a+1作为key么?
Po主当时脑残,说存个类似HashMap<key, Heap<Pair>>()。Pair是{timestamp, val}然后就接着写了,他又问了你如果Pair就存一个最普通的List呢,复杂度是怎样。(发现如果用heap, 反而更差。T_T)put的顺序不一定是按照1.2,3,4这样,有可能是先放4,在放1, put get也可以进行。Po主还提了一下如果timestampe range不大,用bucket最快。总之说了一些方法,三哥也表示这个好还是不好,就是问为什么,复杂度,有没有什么limit这样。
回复

使用道具 举报

🔗
 楼主| jason88628 2016-8-5 01:45:24 | 只看该作者
全局:
zhihaosun 发表于 2016-8-4 19:53
BIT挺难解释清楚的,相比之下segment tree虽然写得多,占内存也多,但好说啊

有道理。。。我两周前才系统的学了一下BIT,follow up被问到觉得运气真是好炸了,BIT代码简洁,写起来非常快,没想到会被要求解释。。。
回复

使用道具 举报

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

本版积分规则

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