一亩三分地论坛

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

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

g 最新7月电面

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

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

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

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

x
g 电面

把一个list的字符串  编码成 一个字符串

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

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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

msg7086 发表于 2014-7-30 07:23:13 | 显示全部楼层
字符串编码的话有现成的方案。. Waral 鍗氬鏈夋洿澶氭枃绔,
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;. Waral 鍗氬鏈夋洿澶氭枃绔,

  5. class bitTorrent {

  6. public:
  7.     vector<string> words;
  8.     string benCoding;

  9.     bitTorrent(vector<string> w) {. 1point3acres.com/bbs
  10.         words = w;. from: 1point3acres.com/bbs
  11.         benCoding = "";
  12.     }

  13.     void encoding() {. 鍥磋鎴戜滑@1point 3 acres
  14.         for(int i = 0; i < words.size(); i ++) {
  15.             benCoding += num2string(words[i].size()) + ":" + words[i];
  16.         }
  17.     }
  18. . Waral 鍗氬鏈夋洿澶氭枃绔,
  19.     vector<string> decoding() {
  20.         vector<string> rst;
  21.         int i = 0;
  22.         while( i < benCoding.size() ) {
  23.             int len = 0;
  24.             while(benCoding[i] >= '0' && benCoding[i] <= '9') { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25.                 len = 10 * len + ( benCoding[i] - '0' );
  26.                 i ++;
  27.             }
  28.             if(benCoding[i] == ':') {
  29.                 i ++;
  30.                 string oneWord = "";
  31.                 for(int l = i; l < len+i; l ++) {
  32.                     oneWord += benCoding[l];. 鍥磋鎴戜滑@1point 3 acres
  33.                 }. From 1point 3acres bbs
  34.                 i += len;
  35.                 rst.push_back(oneWord);
  36.             }else {
  37.                 cout << "Error" << endl;
  38.                 exit(0);
  39.             }
  40.         }
  41.         return rst;. 鍥磋鎴戜滑@1point 3 acres
  42.     }
  43.    
  44.     string num2string(int num) {
  45.         string rst = "";
  46.         int base = 1;
  47.         int tmp = num;
  48.         while(tmp != 0) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  49.             base *= 10;
  50.             tmp /= 10;
  51.         }
  52.         while(base != 1) {. more info on 1point3acres.com
  53.             rst += (num % base + '0');
  54.             base /= 10;
  55.         }
  56.         return rst;
  57.     }

  58. };


  59. int main() {

  60.     vector<string> t;
  61.     t.push_back("hello");
  62.     t.push_back("test");
  63.     t.push_back("10:10");
  64.     t.push_back(":");
  65.     t.push_back("10");


  66.     bitTorrent* test = new bitTorrent(t);
  67.     test->encoding();
  68. . From 1point 3acres bbs
  69.     cout << test->benCoding << endl;
  70.     . 1point 3acres 璁哄潧
  71.     vector<string> out = test->decoding();    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  72.     for(int i = 0 ; i < out.size(); i ++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  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){

}

List<String> decode(String s){. from: 1point3acres.com/bbs

}. 鍥磋鎴戜滑@1point 3 acres

加密解密的方法自己决定,但要保证对包含所有类型的字符的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. 1point 3acres 璁哄潧
用 c++ 写了一个, 不是特别简练, 希望指正

谢谢楼上的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
也就是说用"\"作为转义字符
-google 1point3acres
感觉这个办法是对的,连个,一个escape char,可以用比方说'\',一个separator,比方说'|'
回复 支持 反对

使用道具 举报

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

Hi 这位仁兄,
为什么你强调了逗号?
thanks!
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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