k***t
发帖数: 276 | 1 谁写了？或有没有好一些的online的参考答案？
用于对照检查自己写的是否全面。谢谢。
发信人: xicheng17 (super), 信区: JobHunting
标 题: fb面试题【转】
发信站: BBS 未名空间站 (Wed Nov 9 20:42:44 2011, 美东)
不知道发过没，在其他地方看到的。
Implement a function
char* readLine();
which returns single lines from a buffer. To read the buffer, you can makes
use of a function
int read(char* buf, int len)
which fills buf with upto len chars and returns the actual number of chars
filled in. Function readLine can be called as many times as desired. If
there is no valid data or newline terminated string available, it must block
. In order to block, it can use read function which in turn will block when
it doesn't have anything to fill the buf.
Implement a function string balanceParanthesis(string s); which given a
string s consisting of some parenthesis returns a string s1 in which
parenthesis are balanced and differences between s and s1 are minimum.
Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2"
")))(((" -> ""
How will you design TinyUrl?
How will you design facebook newsfeed. Focus was on a design which could
handle the huge number of status updates and display them on each of the
user's friend's wall. | f*******t
发帖数: 7549 | 2 平衡括号的题可以用贪心法做吧
#include
#include
#include
#include
#define INVALIDCHAR -1
using namespace std;
char *balance(char *str)
{
int len = strlen(str);
if(len < 1)
return NULL;
char *buff = (char*)calloc(len + 1, 1);
stack left;
for(int i = 0; i < len; i++) {
if(str[i] == '(')
left.push(i);
else if(str[i] == ')') {
if(left.empty()) {
buff[i] = INVALIDCHAR;
continue;
}
else
left.pop();
}
buff[i] = str[i];
}
while(!left.empty()) {
int p = left.top();
buff[p] = INVALIDCHAR;
left.pop();
}
char *ans = (char*)calloc(len + 1, 1);
int idx = 0;
for(int i = 0; i < len; i++) {
if(buff[i] != INVALIDCHAR)
ans[idx++] = buff[i];
}
free(buff);
return ans;
}
int main()
{
char str[] = "(ab(xy)u)2)";
char str2[] = ")))(((";
char *result1 = balance(str);
printf("\"%s\" -> \"%s\"\n", str, result1 ? result1 : "");
char *result2 = balance(str2);
printf("%\"%s\" -> \"%s\"\n", str2, result2 ? result2 : "");
if(result1)
free(result1);
if(result2)
free(result2);
return 0;
} | k***t
发帖数: 276 | 3 看到一个 Space O(1)的，写了一下。
不过"(ab(xy)u)2)" -> "(ab(xyu)2)"而不是(ab(xy)u)2)" -> "(ab(xy)u)2"。
#define INVD -1
void balance (char *a) {
if (!a || !*a) return;
int l=0, u=(int)strlen(a)-1;
while (1) {
while (l<=u && a[l]!='(') {
if (a[l]==')') a[l]=INVD;
l++;
}
if (l>u) break;
while (u>=l && a[u]!=')') {
if (a[u]=='(') a[u]=INVD;
u--;
}
if (l>u) break;
l++; u--;
}
char *p=a;
bool dirty=false;
while (*a) {
if (*a==INVD) {
dirty=true;
a++;
continue;
}
if (dirty) {
*p=*a;
}
a++; p++;
}
*p='\0';
}
int main()
{
char str[] = "(ab(xy)u)2)";
char str2[] = ")))(((";
printf(""%s" -> ", str);
balance(str);
printf(""%s"\n", str);
printf(""%s" -> ", str2);
balance(str2);
printf(""%s"\n", str2);
return 0;
}
发信人: etlds (E.T.), 信区: JobHunting
标 题: Re: one facebook software problem
发信站: BBS 未名空间站 (Thu Nov 3 14:40:42 2011, 美东)
Left从左往右找左括号, Right从右往左找右括号。
left找到一个，right应该找到一个，找不到了把当前left的左括号删除。
left找不到了，right继续找，找到一个删一个。还要记录第一个左括号的index与最后
一个右括号的index(从右往左就是第一个了），删除第一个左括号的index之前的右括
号，删除最后一个右括号的index之后的左括号
Time O(n), Space O(1)
【在 f*******t 的大作中提到】
: 平衡括号的题可以用贪心法做吧
: #include
: #include
: #include
: #include
: #define INVALIDCHAR -1
: using namespace std;
: char *balance(char *str)
: {
: int len = strlen(str);
| k***t
发帖数: 276 | 4 自己顶一下，大拿们都不屑于写这个readLine()吗？
这道readLine()的题到底想考什么？
StackOverflow上的一个comment说要考security和memleak。
Implement a function
char* readLine();
which returns single lines from a buffer. To read the buffer, you can makes
use of a function
int read(char* buf, int len)
which fills buf with upto len chars and returns the actual number of chars
filled in. Function readLine can be called as many times as desired. If
there is no valid data or newline terminated string available, it must block
. In order to block, it can use read function which in turn will block when
it doesn't have anything to fill the buf.
附stackoverflow 上的一个comment:
==============================
Allocate an appropriately sized buffers.
If you don't have characters in your read buffer, read in a new chunk.
If the next character from the read buffer is a newline, return the result
buffer.
If the result buffer is full, bug out and whine about lines being too long.
Otherwise, add the next character from the read buffer into the result
buffer.
NOTE: The answer to the question as asked is a security issue waiting to
happen, and also a potential memory leak.
makes
【在 k***t 的大作中提到】
: 谁写了？或有没有好一些的online的参考答案？
: 用于对照检查自己写的是否全面。谢谢。
: 发信人: xicheng17 (super), 信区: JobHunting
: 标 题: fb面试题【转】
: 发信站: BBS 未名空间站 (Wed Nov 9 20:42:44 2011, 美东)
: 不知道发过没，在其他地方看到的。
: Implement a function
: char* readLine();
: which returns single lines from a buffer. To read the buffer, you can makes
: use of a function
|
|
