攒人品之facebook电面面经 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 攒人品之facebook电面面经

相关主题
● 1道brianbench 的题 c++
● C++ 面试题
● 贡献两道google面试题
● 一个基本的string问题
● 请教c++的string vector问题，谢谢！
● 请教一个C++问题
● 贴一个OJ 的 longest valid parenthesis
● 这道题咋做？
● 问个Zenefits电面题目，他家好难。。。
● GOOG intern interview 题目

相关话题的讨论汇总
话题: str话题: cowstring话题: string话题: len话题: char

进入JobHunting版参与讨论

(共1页)

r*****k
发帖数: 1281

implement copy on write string class in c++

s******n
发帖数: 3946

就是写两个overload吧？
COWString& operator=(const char*)
COWString& operator=(const COWString&)

q********c
发帖数: 1774

什么叫copy on write? 不懂这个，那一电面不歇菜了? 不是说F止考算法和数据结构吗
?

r*****b
发帖数: 310

I think that it is more complex that this. We need to consider both updating
the whole string, and updating one character in the string.
Here is what I thought about the implementation:
http://basicalgos.blogspot.com/2012/03/16-implement-copy-on-wri

【在 s******n 的大作中提到】

: 就是写两个overload吧？
: COWString& operator=(const char*)
: COWString& operator=(const COWString&)

S********y
发帖数: 565

p*****2
发帖数: 21240

不懂呀。

s******n
发帖数: 3946

觉得那个不太好，用share pointer：
class COWString {
share_ptr data;
public:
COWString(const char* input)
{
data = share_ptr(new CString(input));
}
COWString(const COWString& str)
{
data = str.data;
}
COWString& operator=(const COWString& str)
{
data = str.data;
return *this;
}
COWString& SetAt(int index, char c)
{
CString* newStr = new CString(data->c_str());
newStr->SetAt(index, c);
data = share_ptr(newStr);
return *this;
}
char GetAt(int index) const
{
return data->GetAt(index);
}
}

updating

【在 r*****b 的大作中提到】

: I think that it is more complex that this. We need to consider both updating
: the whole string, and updating one character in the string.
: Here is what I thought about the implementation:
: http://basicalgos.blogspot.com/2012/03/16-implement-copy-on-wri

h*****g
发帖数: 312

写了一个，有错误请指正~~
//copy on write
class String
{
private:
char *str;
int len;
public:
String():str(0),len(0)
{

}
String(char *p)
{
len=strlen(p);
char *tm=new char(len+2);
memset(tm,0,len+2);
str=tm+1;
strncpy(str,p,len+1);
}
String(const String &ms)
{
len=ms.len;
str=ms.str;
++(str[-1]);
}
String & operator =(const String &ms)
{
ms.str[-1]++;
descUse();
str=ms.str;
len=ms.len;
return *this;
}
void descUse()
{
str[-1]--;
if(str[-1]==-1)
{
delete str;
str=NULL;
len=0;
}
}
char & opeator[](int idx)
{
if(idx<0||idx>len)
{
return NULL;
}
if(str[-1]>0)
{
char *tmp=new char(len+2);
memset(tmp,0,len+2);
strncpy(tmp+1,str,len+1);
str[-1]--;
str=tmp+1;
}
return str[idx];
}
~String()
{
descUse();
}
};

【在 r*****k 的大作中提到】

: implement copy on write string class in c++

s******n
发帖数: 3946

你这等于实现了一个share_ptr

【在 h*****g 的大作中提到】

: 写了一个，有错误请指正~~
: //copy on write
: class String
: {
: private:
: char *str;
: int len;
: public:
: String():str(0),len(0)
: {

r*****k
发帖数: 1281

阿三面的
implement copy on write string class in c++

相关主题
● 一个基本的string问题
● 请教c++的string vector问题，谢谢！
● 请教一个C++问题
● 贴一个OJ 的 longest valid parenthesis
进入JobHunting版参与讨论

s******n
发帖数: 3946

就是写两个overload吧？
COWString& operator=(const char*)
COWString& operator=(const COWString&)

q********c
发帖数: 1774

什么叫copy on write? 不懂这个，那一电面不歇菜了? 不是说F止考算法和数据结构吗
?

r*****b
发帖数: 310

: 就是写两个overload吧？
: COWString& operator=(const char*)
: COWString& operator=(const COWString&)

S********y
发帖数: 565

p*****2
发帖数: 21240

不懂呀。

s******n
发帖数: 3946

h*****g
发帖数: 312

: 阿三面的
: implement copy on write string class in c++

s******n
发帖数: 3946

你这等于实现了一个share_ptr

【在 h*****g 的大作中提到】

: 写了一个，有错误请指正~~
: //copy on write
: class String
: {
: private:
: char *str;
: int len;
: public:
: String():str(0),len(0)
: {

l*********y
发帖数: 142

#include
#include
#include
#include
#include
#include
#include
using namespace std;
class Counter {
public :
Counter() {
counter = 0;
}
void increment() {
counter++;
}
void decrement() {
counter --;
}
int getValue() {
return counter;
}
private:
int counter;
};
class COWString {
public:
COWString() {
pointer = NULL;
rc = new Counter();
}
COWString(string& s) {
pointer = new string(s);
rc = new Counter();
rc->increment();
}
COWString(const COWString& cows) {
pointer = cows.pointer;
rc = cows.rc;
rc->increment();
}
COWString(COWString* const & cows) {
pointer = cows->pointer;
rc = cows->rc;
rc->increment();
}
COWString& operator= (const COWString& rhs) {
if (this == & rhs) {
return *this;
}
pointer = rhs.pointer;
rc = rhs.rc;
rc->increment();
return *this;
}
~COWString() {
rc->decrement();
if (rc->getValue() == 0) {
delete pointer;
delete rc;
}
}
char charAt(int index) {
return pointer->at(index);
}
void set(int index, char c) {
string* newpointer = new string(*pointer);
Counter* newrc = new Counter();
rc->decrement();
if (rc->getValue() == 0) {
delete pointer;
delete rc;
}
newpointer->at(index) = c; //问题//
newrc->increment();
pointer = newpointer;
rc = newrc;
}
string getData() {
return *pointer;
}
Counter* getCounter() {
return rc;
}
private:
string* pointer;
Counter* rc;
};
int main() {
string input = "hello world!";
COWString* s = new COWString(input);
COWString* copy = new COWString(const_cast (s));
cout << s->getData() << endl;
cout << s->getCounter()->getValue() << endl;
cout << copy->getData() << endl;
cout << copy->getCounter()->getValue() << endl;
copy->set(0, 'H');
cout << s->getData() << endl;
cout << s->getCounter()->getValue() << endl;
cout << copy->getData() << endl;
cout << copy->getCounter()->getValue() << endl;
return 0;
}
我也写了一个。顺便问一个问题，在程序中为什么
newpointer->at(index) = c;
改成
newpointer[index] = c之后，结果就不对了。谢谢！

C***U
发帖数: 2406

溢出？
[] 不检查range at会检查

【在 l*********y 的大作中提到】

: #include
: #include
: #include
: #include
: #include
: #include
: #include
: using namespace std;
: class Counter {
: public :

w****x
发帖数: 2483

明显的刁难嘛(除非楼主简历上写了会这个), 大家就别讨论了

(共1页)

进入JobHunting版参与讨论

相关主题
● GOOG intern interview 题目
● 为什么我这段简单的程序segment fault
● 【一个BB公司问的字母排序的问题】
● A simple google interview question
● LRU Cache class：有没有面试可用的精简一些的Sample Code
● 问求array中3个数和最接近k的解法
● 今天G家电面的一道题
● 请问一个面试题
● 以前能过的leetcode 3sum，现在fail了，求助（时间超出了）
● 也说两个面试题

相关话题的讨论汇总
话题: str话题: cowstring话题: string话题: len话题: char

boards