由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求教一道关于string的Google面试题~~
相关主题
面试题:根据输入字符串,返回正则表达式贡献一道电话面试题
careerup 150里面的一道题。。问个经典题目,感觉没错啊,可是过不了OJ,超时了,请大神帮着
onsite遇到的几个面试题G家电题
问一个facebook的电面面经+求助
做题做得很郁闷,求指点如何 serialization 和deserialization hash table ?
find first diff of 2 strings问一道算法题
F电面FB 面筋
求问一道算法题~贡献一道电面题
相关话题的讨论汇总
话题: string话题: str1话题: str2话题: str话题: google
进入JobHunting版参与讨论
1 (共1页)
g*******s
发帖数: 2963
1
要求写两个function, signature定义如下。把两个string 合并成一个,再把这个合成
的string还原成两个。string可以包含任意字母任意顺序,另外要求是不允许用额外空
间。比如合并的时候插入新字母或者返回额外变量记录长度什么的。
string serialize(string &str1, string &str2);
void deserialize(string &str, string &str1, string &str2);
b*****o
发帖数: 715
2
什么叫不允许用额外空间?
你返回的变量总要新申请内存吧?是说这个新申请的内存大小不能超过原来string之和
M********n
发帖数: 34
3
奇数位str1, 偶数位str2
d**********x
发帖数: 4083
4
不一样长

【在 M********n 的大作中提到】
: 奇数位str1, 偶数位str2
g*******s
发帖数: 2963
5
function signature已经定义好的不算额外。 比如楼上说的奇偶分布是符合条件的,
不过不能解决两个str长度不一样的情况。

【在 b*****o 的大作中提到】
: 什么叫不允许用额外空间?
: 你返回的变量总要新申请内存吧?是说这个新申请的内存大小不能超过原来string之和
: ?

r*******e
发帖数: 7583
6
那就简单了
在字符串之前写个长度tag就行

之和

【在 g*******s 的大作中提到】
: function signature已经定义好的不算额外。 比如楼上说的奇偶分布是符合条件的,
: 不过不能解决两个str长度不一样的情况。

d**********x
发帖数: 4083
7
我想了一会儿其他可能性,比如说什么异或,rotation之类的
感觉确实是没有多余的空间可以存东西。
所以要么是
1.字符的范围有限制,所以我们可以取一个bit,或者更少的空间做标记什么的
2.考虑到这是个c++函数,可以用很tricky的手段,即先设定字符串的capacity=str1.
length+str2.length,然后resize到str1.length,再把str1和str2的内容填进去。如
果有人想说G不会出这种恶心题目,请参考我的签名档……

【在 g*******s 的大作中提到】
: 要求写两个function, signature定义如下。把两个string 合并成一个,再把这个合成
: 的string还原成两个。string可以包含任意字母任意顺序,另外要求是不允许用额外空
: 间。比如合并的时候插入新字母或者返回额外变量记录长度什么的。
: string serialize(string &str1, string &str2);
: void deserialize(string &str, string &str1, string &str2);

g*******s
发帖数: 2963
8
这个我当时说了,他说不行。输入可以是任意字符,所以没法识别哪个是tag。

【在 r*******e 的大作中提到】
: 那就简单了
: 在字符串之前写个长度tag就行
:
: 之和

M********n
发帖数: 34
9
这样中不,
合并后的str, str[n] n>0 的是str1, str[n] n<0的是str2,
n从0直到end?
l********1
发帖数: 74
10
Tag+转义
相关主题
find first diff of 2 strings贡献一道电话面试题
F电面问个经典题目,感觉没错啊,可是过不了OJ,超时了,请大神帮着
求问一道算法题~G家电题
进入JobHunting版参与讨论
d**********x
发帖数: 4083
11
哦,如果意思是说可以加类似tag的东西就简单了
我以为原来的意思是说str的长度不能超过str1+str2的长度
tag可以是定长的。

【在 g*******s 的大作中提到】
: 这个我当时说了,他说不行。输入可以是任意字符,所以没法识别哪个是tag。
w**5
发帖数: 34
12
可以这样不?
string serialize(string &str1, string &str2)
{
string str = str1;
str.append(str2);
str[str1.length()] |= 0x80; // 把st2的第一个char变成负数
return
}
void deserialize(string &str, string &str1, string &str2)
{
for (int i=0; i {
if (str[i] < 0) {
str[i] &= 0x7f;
str1 = str.substr(0, i);
str2 = str.substr(i, str.length() - i);
}
}
}
u******g
发帖数: 89
13
char变为负数的implication是原来里面的char都是ASCII的(<127)。。。

【在 w**5 的大作中提到】
: 可以这样不?
: string serialize(string &str1, string &str2)
: {
: string str = str1;
: str.append(str2);
: str[str1.length()] |= 0x80; // 把st2的第一个char变成负数
: return
: }
: void deserialize(string &str, string &str1, string &str2)
: {

b******z
发帖数: 410
14
这方法好,
str 指到中间,左边str1,右边str2.

【在 M********n 的大作中提到】
: 这样中不,
: 合并后的str, str[n] n>0 的是str1, str[n] n<0的是str2,
: n从0直到end?

J**9
发帖数: 835
15
Then how do you know the start or end of str1?

【在 b******z 的大作中提到】
: 这方法好,
: str 指到中间,左边str1,右边str2.

l*******i
发帖数: 116
16
脑子有屎的人出的题讨论他做甚
b******z
发帖数: 410
17
str[0] points to str1 start, str[-1] points to str2. null terminator both
ends

Then how do you know the start or end of str1?

【在 J**9 的大作中提到】
: Then how do you know the start or end of str1?
1 (共1页)
进入JobHunting版参与讨论
相关主题
贡献一道电面题做题做得很郁闷,求指点
继续攒人品,发Apple面试题(iCloud)find first diff of 2 strings
Deserialize in-order array to a minimum height binary tree.F电面
求个java版本的binary tree serialization和deserialization求问一道算法题~
面试题:根据输入字符串,返回正则表达式贡献一道电话面试题
careerup 150里面的一道题。。问个经典题目,感觉没错啊,可是过不了OJ,超时了,请大神帮着
onsite遇到的几个面试题G家电题
问一个facebook的电面面经+求助
相关话题的讨论汇总
话题: string话题: str1话题: str2话题: str话题: google