求问一道面试题

http://www.mitbbs.com/article_t/JobHunting/32959699.html

发信人: guokecc (guokecc), 信区: JobHunting
标  题: 求问一道面试题
发信站: BBS 未名空间站 (Mon May  4 00:08:12 2015, 美东)

求问一道pocket gems的面试题 ：
写一个mutable string。 里面有三个methods, charAt(int i), substring(int
beginIndex, int endIndex), setcharAt(int i, char c); 只能是O（1） space
毫无头绪。。。这些不是c++ stl 自带的函数么。。。跪求指导。。。最好用c++
谢谢！


是malloc一个内存，然后用指针吗？这个string class里的变量是
指针和一个内存。因为要求O(1)的space，第一个method charat可以指针在O(1) time
and O(1) space 返回对应的char即可。

第二个method substring 怎么达到O(1) space的呢？返回reference？可是新建一个
class的instance来放这个substring还是要内存啊。

第三个method setcharAt(int i, char c) 就完全不知道了。连字符都改了，又要求O(
1)的space，这个新字符放到哪呢？我想原string是不能改的，因为会有别的instance
指向这个string。那这个新的char又怎么和原string组合成新string呢？
网上搜了一下有人提了一句用tree，我没明白。

还请高人指点！谢谢！