一亩三分地论坛

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

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

g 最新7月电面

[复制链接] |试试Instant~ |关注本帖
zhaogongzuo 发表于 2014-7-19 07:22:43 | 显示全部楼层 |阅读模式

2014(7-9月) 码农类 本科 全职@Google - 网上海投 - 在线笔试 |Other

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

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

x
g 电面
. 1point 3acres 璁哄潧
把一个list的字符串  编码成 一个字符串 . 鍥磋鎴戜滑@1point 3 acres

再把这个编码过的字符串 转回原来的list

面试官态度生硬,在它提示下做出来了,但时间不够下一题。额

评分

2

查看全部评分

本帖被以下淘专辑推荐:

jfwwlong 发表于 2014-7-20 10:55:04 | 显示全部楼层
我找了一下,看到一个不错的答案。就是先将每个单词里面的反斜杠'\'加倍变成连续2个'\',然后将每个每个单词里面的逗号','前面加上一个反斜杠'\'。最后在每个单词中间加上一个逗号','。得到输出的字符串。
反序列化的时候遇到第一个反斜杠就先跳过,然后加上后面的字符。这样就可以解码了。说起来不太描述,大家可以看一下这个链接里的第一个答案,然后在纸上比划比划。
http://stackoverflow.com/questions/853475/whats-the-simplest-way-to-encoding-liststring-into-plain-string-and-decode-it

回复 支持 1 反对 0

使用道具 举报

msg7086 发表于 2014-7-30 07:23:13 | 显示全部楼层
字符串编码的话有现成的方案。
BitTorrent规范里用到的BEncoding就是,字符串长度+冒号+字符串。
直接照着BEncoding的规范做List<String>序列化和反序列化就行了。
回复 支持 1 反对 0

使用道具 举报

Interviwer 发表于 2014-9-17 00:26:35 | 显示全部楼层
用 c++ 写了一个, 不是特别简练, 希望指正
  1. #include<iostream>
  2. #include<string>
  3. #include<vector>
  4. using namespace std;

  5. class bitTorrent {

  6. public:
  7.     vector<string> words;
  8.     string benCoding;
  9. . From 1point 3acres bbs
  10.     bitTorrent(vector<string> w) {
  11.         words = w;
  12.         benCoding = "";
  13.     }
  14. . Waral 鍗氬鏈夋洿澶氭枃绔,
  15.     void encoding() {
  16.         for(int i = 0; i < words.size(); i ++) {
  17.             benCoding += num2string(words[i].size()) + ":" + words[i];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.         }
  19.     }

  20.     vector<string> decoding() {
  21.         vector<string> rst;
  22.         int i = 0;
  23.         while( i < benCoding.size() ) {
  24.             int len = 0;
  25.             while(benCoding[i] >= '0' && benCoding[i] <= '9') {
  26.                 len = 10 * len + ( benCoding[i] - '0' );
  27.                 i ++;
  28.             }
  29.             if(benCoding[i] == ':') {
  30.                 i ++;
  31.                 string oneWord = "";
  32.                 for(int l = i; l < len+i; l ++) {
  33.                     oneWord += benCoding[l];
  34.                 }
  35.                 i += len;
  36.                 rst.push_back(oneWord);
  37.             }else {
  38.                 cout << "Error" << endl;. 1point3acres.com/bbs
  39.                 exit(0);
  40.             }
  41.         }
  42.         return rst;. 1point 3acres 璁哄潧
  43.     }
  44.    
    . 1point 3acres 璁哄潧
  45.     string num2string(int num) {
  46.         string rst = "";
  47.         int base = 1;
  48.         int tmp = num;
  49.         while(tmp != 0) {
  50.             base *= 10;
  51.             tmp /= 10;
  52.         }
  53.         while(base != 1) {
  54.             rst += (num % base + '0'); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  55.             base /= 10;
  56.         }
  57.         return rst;.1point3acres缃
  58.     }. visit 1point3acres.com for more.

  59. };


  60. int main() {

  61.     vector<string> t;. 鍥磋鎴戜滑@1point 3 acres
  62.     t.push_back("hello");
  63.     t.push_back("test");
  64.     t.push_back("10:10");
  65.     t.push_back(":");
  66.     t.push_back("10");


  67.     bitTorrent* test = new bitTorrent(t);
  68.     test->encoding();

  69.     cout << test->benCoding << endl;
  70.    
  71.     vector<string> out = test->decoding();   
  72.     for(int i = 0 ; i < out.size(); i ++) {
  73.         cout << out[i] << endl;
  74.     }

  75. }
复制代码
回复 支持 1 反对 0

使用道具 举报

花农 发表于 2014-7-19 08:52:32 | 显示全部楼层
跟我遇到的题目完全一样,我三月份面的,听口音是白人小哥。当时我自己做出来,但也是花了很多时间,也是没时间做第二题。
回复 支持 反对

使用道具 举报

notbad 发表于 2014-7-19 09:51:38 | 显示全部楼层
可以chunk编码吗? |size1|string1|size2|string2|....
回复 支持 反对

使用道具 举报

nathanwong 发表于 2014-7-20 02:54:56 | 显示全部楼层
LZ 请问list的是怎么样的呀 那个list的串是啥格式呢? 能否给个详细点的描述。想做一下这个题目
回复 支持 反对

使用道具 举报

花农 发表于 2014-7-20 04:27:17 | 显示全部楼层
nathanwong 发表于 2014-7-20 02:54
LZ 请问list的是怎么样的呀 那个list的串是啥格式呢? 能否给个详细点的描述。想做一下这个题目

String encode(List<String> strings){
. more info on 1point3acres.com
}
. 1point 3acres 璁哄潧. From 1point 3acres bbs
List<String> decode(String s){

}.1point3acres缃

加密解密的方法自己决定,但要保证对包含所有类型的字符的String都能成功加密解密。
回复 支持 反对

使用道具 举报

lvluolan 发表于 2014-7-20 14:38:44 | 显示全部楼层
jfwwlong 发表于 2014-7-20 10:55
我找了一下,看到一个不错的答案。就是先将每个单词里面的反斜杠'\'加倍变成连续2个'\',然后将每个每个单 ...

这个方法确实不错,暂时还没找出bug,谢谢^_^
回复 支持 反对

使用道具 举报

joy9088 发表于 2014-7-26 04:22:42 | 显示全部楼层
也就是说用"\"作为转义字符
回复 支持 反对

使用道具 举报

 楼主| zhaogongzuo 发表于 2014-7-30 05:57:16 | 显示全部楼层
花农 发表于 2014-7-19 08:52
跟我遇到的题目完全一样,我三月份面的,听口音是白人小哥。当时我自己做出来,但也是花了很多时间,也是没 ...

g让我再phone screen一次
回复 支持 反对

使用道具 举报

arthur1026 发表于 2014-8-2 13:41:46 | 显示全部楼层
不错,和leetcode上的题风格不同
回复 支持 反对

使用道具 举报

blesscol 发表于 2014-8-2 14:30:04 | 显示全部楼层
Google从啥时候开始电面变成这种风格了
回复 支持 反对

使用道具 举报

loveinCA 发表于 2014-8-4 21:59:35 | 显示全部楼层
感觉难度还可以
回复 支持 反对

使用道具 举报

头像被屏蔽
hungryhuang 发表于 2014-8-5 00:39:19 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

IamForrest 发表于 2014-11-15 00:17:59 | 显示全部楼层
Interviwer 发表于 2014-9-17 00:26
用 c++ 写了一个, 不是特别简练, 希望指正
. From 1point 3acres bbs
谢谢楼上的c++代码,有几个建议,没必要numtostring,直接用c++11里的to_string就可以了。此外decoding时候每次都push_back(word),这样有大量没必要的copy,建议灵活使用move来消除没必要的损耗,push_back(std::move(word))
回复 支持 反对

使用道具 举报

GTea 发表于 2014-11-15 18:20:30 | 显示全部楼层
joy9088 发表于 2014-7-26 04:22
也就是说用"\"作为转义字符

感觉这个办法是对的,连个,一个escape char,可以用比方说'\',一个separator,比方说'|'
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-28 13:34:33 | 显示全部楼层
jfwwlong 发表于 2014-7-20 10:55.鐣欏璁哄潧-涓浜-涓夊垎鍦
我找了一下,看到一个不错的答案。就是先将每个单词里面的反斜杠'\'加倍变成连续2个'\',然后将每个每个单 ...

Hi 这位仁兄,.鏈枃鍘熷垱鑷1point3acres璁哄潧
为什么你强调了逗号?
thanks!
回复 支持 反对

使用道具 举报

joseph5wu 发表于 2015-7-28 18:10:08 | 显示全部楼层
jiebour 发表于 2015-7-28 13:34
Hi 这位仁兄,
为什么你强调了逗号?
thanks!

因为使用逗号来隔开list里面不同的string,这样用来区分这些string里面自带的逗号
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-18 03:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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