一亩三分地论坛

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

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

1.25 Google 加面跪经

[复制链接] |试试Instant~ |关注本帖
dolphin_wby 发表于 2016-1-27 04:23:04 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
题目没有做出来,肯定是跪了,实在是智商捉急,说下题目攒人品吧:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

要生成一个magic string, magic string是什么呢,就是比如这个string是122112122122112112...它有下面的规律:


string: 122112122122112112...
count: 12  2 1 12 12  2 1 2...


stirng里包括1和2,如果两个连续的数字一样,那count就要append 2,否则就是append 1,生成的count必须和string是一样的,要先生成magic string,然后写个query(char c, int len) method, c是1或者2,len是magic string的长度,output是在len长的magic string中c出现的次数。lz一开始没有太理解magic string,以为是给出的,写完query后妹子说要生成magic string,magic string又理解了半天,中途尝试要hint无果,最后到时间没写出来。妹子很nice,一直耐心解释magic string,最后才告诉hint,反正是挂了,写出来给大家参考吧。另外这个题是有follow up的,lz太蠢没被问到orz. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴




补充内容 (2016-10-7 12:44):-google 1point3acres
如果大家觉得lz描述的不太清楚可以参考11垅的附件,当时面试官就给lz丢了这个pdf,题目一模一样~

评分

5

查看全部评分

本帖被以下淘专辑推荐:

stellari 发表于 2016-11-1 11:24:57 | 显示全部楼层
syjohnson 发表于 2016-11-1 03:29.鐣欏璁哄潧-涓浜-涓夊垎鍦
你这个方法前两位必须是12开头吧,但实际上11111和22222也是magic string

请看某楼附件中给出的原题,其中对magic string是这样定义的:The string is magical because because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string S itself.

换句话说,原string如果有X个连续的1或2,count string在相应位置上的值就必须是X。要想原stirng=count string,那么count string中也只能是1或2,换句话说原string中同一数字不可能连续出现超过2次。所以1111...和2222...都不可能是magic string。
回复 支持 1 反对 0

使用道具 举报

 楼主| dolphin_wby 发表于 2016-1-27 05:08:31 | 显示全部楼层
zatarratw 发表于 2016-1-27 04:42
之前在HackerRank有看到,沒想到竟然考出來了
你可以自己用手寫推一下sequence,他是有規律的

真是一模一样的!当时她就是把这个截图贴过来了,感谢分享~
回复 支持 0 反对 1

使用道具 举报

zatarratw 发表于 2016-1-27 04:42:46 | 显示全部楼层
之前在HackerRank有看到,沒想到竟然考出來了
你可以自己用手寫推一下sequence,他是有規律的

补充内容 (2016-1-27 04:52):
更正,不是有規律。你可以想像,那些1跟2,其實同時也是count,把他們從頭加到尾就是accumulation。接下來就是去找他一個循環有多長

magical-string-1-English.pdf

56.22 KB, 下载次数: 191, 下载积分: 大米 -1 升

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

acbh 发表于 2016-1-27 04:37:46 | 显示全部楼层
。。楼主求解释,没有太看懂题目的意思
回复 支持 反对

使用道具 举报

acbh 发表于 2016-1-27 04:40:22 | 显示全部楼层
其实让我想到leetcode上那道“count and say”。但我不太懂那个magic string是让你arbitrarily定的?还是一个input 。。?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-27 04:41:31 | 显示全部楼层
lz加油。
你hr有说,一般加面多久会出结果么。
我上周5面的3面,题都做出来了。由于之前amazon的经历,我怕是我google做出题也要挂了。都2个工作日了,还没有消息。
回复 支持 反对

使用道具 举报

 楼主| dolphin_wby 发表于 2016-1-27 05:09:02 | 显示全部楼层
acbh 发表于 2016-1-27 04:40
其实让我想到leetcode上那道“count and say”。但我不太懂那个magic string是让你arbitrarily定的?还是一 ...

具体可以看下地下室的资料,就是那个题
回复 支持 反对

使用道具 举报

 楼主| dolphin_wby 发表于 2016-1-27 05:09:48 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-27 04:41
lz加油。. 1point3acres.com/bbs
你hr有说,一般加面多久会出结果么。
我上周5面的3面,题都做出来了。由于之前amazon的经历,我 ...

没说,只说一有结果马上通知。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-27 05:12:54 | 显示全部楼层
dolphin_wby 发表于 2016-1-27 05:09
没说,只说一有结果马上通知。

谢谢,祝你好运。
回复 支持 反对

使用道具 举报

farm 发表于 2016-1-27 05:44:16 | 显示全部楼层
zatarratw 发表于 2016-1-27 04:42
之前在HackerRank有看到,沒想到竟然考出來了
你可以自己用手寫推一下sequence,他是有規律的
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
想问一下,你是怎么在HackerRank上看到这道题的啊?
HackerRank的题目可以搜么?还是只能是random的challenge?
回复 支持 反对

使用道具 举报

zatarratw 发表于 2016-1-27 06:09:57 | 显示全部楼层
farm 发表于 2016-1-27 05:44
想问一下,你是怎么在HackerRank上看到这道题的啊?
HackerRank的题目可以搜么?还是只能是random的chal ...

之前我朋友參加的challenge,找我支援的時候看到的。應該還是搜得到,剛剛試過,Google: "hackerrank magic string"就找得到了
回复 支持 反对

使用道具 举报

farm 发表于 2016-1-27 13:28:06 | 显示全部楼层
zatarratw 发表于 2016-1-27 06:09
之前我朋友參加的challenge,找我支援的時候看到的。應該還是搜得到,剛剛試過,Google: "hackerrank mag ...

赞赞赞~~~
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-1-27 14:40:25 | 显示全部楼层
这题好难,求hint
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-27 14:58:04 | 显示全部楼层
是不是可以从她给出的Magic string 开始结合count string继续生成? query 不就是遍历吗?难道有trick?
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-1-27 15:16:11 | 显示全部楼层
问题生成的速度比原串要慢,怎么能生成下去啊。。。。
回复 支持 反对

使用道具 举报

stellari 发表于 2016-1-27 19:58:59 | 显示全部楼层
生成倒是不难。如果已生成长为len的序列,query也不难。但是,如果follow up是问你在不生成magic序列的情况下,仅用O(1)时间(或者最起码是sublinear时间)完成query,有没有可能做出来呢?

-google 1point3acres补一个生成magic string的代码:

string getMagicString(int len) {
    string res(len, '1');
    if (len < 2) return res;
    res[1] = '2';
. 1point3acres.com/bbs
    int iCount = 1, iStr = 1; // Pointers in the 'count' and 'string' sequence
    char curChar = '2', nextChar = '1';
    while (iStr < len) {
. From 1point 3acres bbs        int count = res[iCount++] - '0'; // Get the current count;
        for (int i = 0; i < count; ++i) { // Append to the ‘string’ sequence
            res[iStr++] = curChar;
            if (iStr == len) break;
        }
        swap(curChar, nextChar);    // Flip the current character, e.g. '1'->'2'
    }
    return res;.鐣欏璁哄潧-涓浜-涓夊垎鍦
}
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-27 23:43:43 | 显示全部楼层
Good code 如果可以用extra memory的话 生成magic string 同时就建一个count array。但是我觉得Magic string 本身就是count 不知道怎么用这个特性。
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-1-28 02:19:33 | 显示全部楼层
stellari 发表于 2016-1-27 19:58. 1point 3acres 璁哄潧
生成倒是不难。如果已生成长为len的序列,query也不难。但是,如果follow up是问你在不生成magic序列的情况 ...

懂了,反过来generate。。。思维定势了。。。谢谢
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-2 16:45:57 | 显示全部楼层
stellari 发表于 2016-1-27 19:58
生成倒是不难。如果已生成长为len的序列,query也不难。但是,如果follow up是问你在不生成magic序列的情况 ...

leetcode discussion区的大神们居然都在混一亩三分地...
回复 支持 反对

使用道具 举报

zhan8803705 发表于 2016-10-5 22:59:34 | 显示全部楼层
stellari 发表于 2016-1-27 19:58-google 1point3acres
生成倒是不难。如果已生成长为len的序列,query也不难。但是,如果follow up是问你在不生成magic序列的情况 ...

你的code有bug,会生成 “12221.....” 而不是"1221....."

前三个字符应该要特别处理
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 22:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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