一亩三分地论坛

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

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

[G家]新鲜面经

[复制链接] |试试Instant~ |关注本帖
D调的华丽 发表于 2016-1-16 09:03:05 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
刚面完Google, 就跑来地里写面经啦~
废话不多说,第一轮:美国小哥 略冷淡,都木有对我热情的微笑有所回应

设计一个map的block,使得二维map中,每两个ceil之间的只有一条路,并且每次run program, 得到的block分布不同。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
理解题意花的时间太长,最后只是把大致思路说了下, 代码没写完……
第二轮:印度姐姐,除了听不懂口音,其他都挺好的。真不好意思让人家重复了好多遍……
input: int n
function: 将n用2的指数表示,使得指数表达式的个数最少.鐣欏璁哄潧-涓浜-涓夊垎鍦
output : int num(指数的最少个数)
e.g: input = 28-google 1point3acres
28 = 2^4 + 2^3 + 2^2  => num = 3
28 = 2^5 - 2^2             => num = 2
所以 output = 2
第三轮:计算输入数据流中含有n个distinct character的最长substring
input: string stream, int n
output: the maximum length of the substring that has n disctinct characters
第四轮:求string s中含有string b order sequence 的最小长度
只想到了brutal force做法,小哥不满意,好桑西…… 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

感谢地里的面经,所以特地来回馈!
攒人品,求offer呀!!!

评分

4

查看全部评分

本帖被以下淘专辑推荐:

JohnsonMS 发表于 2016-1-17 04:06:04 | 显示全部楼层
楼主能否把第一题更形象精确地描述一下,对角线的两个cell 能否相邻
回复 支持 1 反对 0

使用道具 举报

Sense 发表于 2016-1-16 14:12:31 | 显示全部楼层
我写的第四题:

#include <string>
#include <vector>
#include <climits>
#include <iostream>. From 1point 3acres bbs
using namespace std;

int stringOrderSequence(string& s, string& b){
        int m = s.length(), n = b.length();
        if(m == 0 || n == 0 || m < n) return 0;
        vector<vector<int>> table(m, vector<int>(n, 0));
        for(int i = 0; i < m; i++) table[i][0] = (s[i] == b[0]) ? 1: 0;. 鍥磋鎴戜滑@1point 3 acres
        for(int j = 1; j < n; j++){
                for(int i = j; i < m; i++){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        if(s[i] == b[j]){
                                int temp = INT_MAX;
                                for(int k = j - 1; k < i; k++){
                                        if(table[k][j - 1] != 0) temp = min(temp, table[k][j - 1] + i - k);
                                }
                                if(temp != INT_MAX) table[i][j] = temp;
                        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
        }
        int res = INT_MAX;
        for(int i = n - 1; i < m; i++){
                if(table[i][n - 1]) res = min(res, table[i][n - 1]);
        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        return res;-google 1point3acres
}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

int main(){. visit 1point3acres.com for more.
        string s = "ADEFBDACBRFACGBC";
        string b = "ABC";
        cout << stringOrderSequence(s, b) << endl;
}

自己给的Test case是对的,不知道有没有理解错?
回复 支持 1 反对 0

使用道具 举报

chm34 发表于 2016-1-17 02:57:33 | 显示全部楼层
感觉第二题是greedy的思想,从最低位的bit开始,只要有连续的1的个数超过2个,就写成(2^M - 2^N)
回复 支持 1 反对 0

使用道具 举报

epochou 发表于 2016-1-16 10:14:46 | 显示全部楼层
LZ第二题怎么做的?目前能想到的就是看bit的规律。另外可否解释下第一题第四题?不知道什么意思
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-16 12:04:18 | 显示全部楼层
第一题咋搞
回复 支持 反对

使用道具 举报

Sense 发表于 2016-1-16 14:11:00 | 显示全部楼层
第一题没太看懂什么意思,是随机生成地图当中的房间和连通房间的走廊的吗?感觉要bug free会很花时间。
第二题要用recursion 和 backtrack吧,查验2的阶乘时可以用(1 << i) 的形式去求。
第三题的话应该是two pointers + hashmap吧?
第四题如果没理解错的话应该用dp可以做。
回复 支持 反对

使用道具 举报

umd2011 发表于 2016-1-16 23:58:48 | 显示全部楼层
感谢分享, 祝楼主早日收到offer!
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-17 00:08:31 | 显示全部楼层
第二题是不是就是check n的二进制0 1 的相对数量来决定
1 多的话可以用比这个是高一位的整数减去0位的数 注意合并 如那个例子一样。 0多的话就数1的个数。不知道是否对?
回复 支持 反对

使用道具 举报

JohnsonMS 发表于 2016-1-17 03:59:54 | 显示全部楼层
kinggarden2001 发表于 2016-1-17 00:08
第二题是不是就是check n的二进制0 1 的相对数量来决定
1 多的话可以用比这个是高一位的整数减去0位的数 注 ...

感到是只要连续1的个数大于2, 就可以变成用两1表示, 例如0b01111100  = 10000000 - 100. . From 1point 3acres bbs
如果一个数 0b11011,可以表示成为0b11100-1 => 0b100000 -0b100 - 0b1, 代码如下,请拍砖
int MinBinnaryRepresent(unsigned int num)
{
        int count = 0;
        int len = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        while (num != 0)
        {
                if ((num & 1) == 0)
                {
                        if (len >= 2)
                        {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                count += 1;
                                len = 1;
                        }
                        else
                        {
                                count += len;
                        }. more info on 1point3acres.com
                }. 1point3acres.com/bbs
                else
                {
                        len++;
                }
                num = num >> 1;
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

        if (len >= 2)
        {
                count += 2;
        }
        else
        {
                count += len; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        }
        return count;
}
回复 支持 反对

使用道具 举报

yjfox 发表于 2016-1-17 08:57:05 | 显示全部楼层
最后一题可能不需要DP吧,可以参考longest increase subsequence

第一题求lz细说。
回复 支持 反对

使用道具 举报

lfenjoy9 发表于 2016-1-18 01:48:02 | 显示全部楼层
感谢分享, 祝楼主早日收到offer!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-18 06:34:04 来自手机 | 显示全部楼层
请问楼主第一题是什么意思?第二题应该就是贪心吧,第四题可以给个例子吗?
回复 支持 反对

使用道具 举报

neverlandly 发表于 2016-1-18 07:19:10 | 显示全部楼层
yjfox 发表于 2016-1-17 08:57
最后一题可能不需要DP吧,可以参考longest increase subsequence

第一题求lz细说。

Longest increase subsequence怎么套到这道题来
回复 支持 反对

使用道具 举报

umd2011 发表于 2016-1-19 00:01:56 | 显示全部楼层
楼主,第一题我没看懂是什么意思, 能详细说下吗?
回复 支持 反对

使用道具 举报

echo33 发表于 2016-1-19 03:45:33 | 显示全部楼层
第四题是什么意思啊?.鐣欏璁哄潧-涓浜-涓夊垎鍦
s = 'bacdbcadabcd'. visit 1point3acres.com for more.
b = 'aabbcc'
.1point3acres缃返回‘abc’酱紫?
回复 支持 反对

使用道具 举报

echo33 发表于 2016-1-19 03:48:06 | 显示全部楼层
echo33 发表于 2016-1-19 03:45
第四题是什么意思啊?
s = 'bacdbcadabcd'
b = 'aabbcc'

哦 知道了....
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-27 08:36:45 | 显示全部楼层
请问第四题可以给个例子吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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