|
|---|
|
|
|
|
|
|
S**I
发帖数: 15689 | 1 ☆─────────────────────────────────────☆
recursive (递归) 于 (Mon Apr 11 10:56:49 2011, 美东) 提到:
大半夜收到HR的thank you note。不用管什么NDA了
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the output should be [2, 6]
binary search的变种
3，number of unique url accesses in huge log files
hashtable + bit vector
讨论hash的实现，bit vector如何快速统计有多少个entry
onsite：
4，老题，爬楼梯一次可以走一级或者两级，爬N级有多少种走法
5，文件读写
有个封装好的函数 int block_reader(char *buf)
内部有个静态文件指针，只能向文件末尾移动，不能rewind
每次只能读取4K的block到buf里，返回读取的字节数（除非到文件尾，否则总是4K）
要求实现 int anysize_reader(char *buf, int size)
从文件的当前位置读取任意大小的数据存入buf，并返回实际读到的数据字节数
白板写code
问题的关键在于anysize_reader会被多次调用，每次都可能不是4K对齐
所以需要自己维护一个4K的buffer
6，系统设计
讨论gmail的user authentication，描述详细的流程，性能瓶颈
如何做load balancing
7，写code实现int sqrt(int n)
用binary search，需要考虑比较多的细节
8，老题，实现分布的LRU cache，要求存取时间O(1)
9，Unix file path化简，写code
例如 /a/./b/../../c/ ，化简为 /c/
用stack或者d-queue，有些细节需要考虑，例如 /..//.. 还是输出 /
10，write code to find all the possible combinations of chars in a given
string
11，a set of intervals, how to tell if a given value is in any of the
intervals
讨论了overlapping的情况，interval tree，etc
还有一些类似难度的题，记不大清楚了。总之不是很难
俺基本功不扎实，倒在了胜利的前夕
希望后来的xdjm们都能传捷报～～～～
☆─────────────────────────────────────☆
boohockey (Pursuit of Dreams!) 于 (Mon Apr 11 11:06:40 2011, 美东) 提到:
楼主是怎么准备算法的？
☆─────────────────────────────────────☆
WWWXXX (WWWXXX) 于 (Mon Apr 11 11:24:35 2011, 美东) 提到:
拒信只有一句thank your note?
☆─────────────────────────────────────☆
recursive (递归) 于 (Mon Apr 11 11:53:28 2011, 美东) 提到:
标准模板
thanks for your interest
we are unable to find a matching position, etc etc
☆─────────────────────────────────────☆
fengzhongdi (fzd) 于 (Mon Apr 11 11:54:52 2011, 美东) 提到:
楼主辛苦了,会有更好的.
各位大牛能否把第五题的思路说明一下?
☆─────────────────────────────────────☆
Chevy (Chevy) 于 (Mon Apr 11 11:57:08 2011, 美东) 提到:
cmft
东家不亮西家亮
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Mon Apr 11 12:02:53 2011, 美东) 提到:
电面不简单啊。45分钟三道题还是挺紧张的。
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Mon Apr 11 12:04:21 2011, 美东) 提到:
gmail那个题怎么回答为好？最头疼这种问题。
☆─────────────────────────────────────☆
yangcheng (牛魔王) 于 (Mon Apr 11 13:11:16 2011, 美东) 提到:
和oauth差不多吧？
☆─────────────────────────────────────☆
fzzh24 (fzz) 于 (Mon Apr 11 13:42:16 2011, 美东) 提到:
感谢lz分享
bless offer即将到来～
☆─────────────────────────────────────☆
anonymous1 (无名氏) 于 (Mon Apr 11 14:35:25 2011, 美东) 提到:
怎么设计分布式LRU cache?
☆─────────────────────────────────────☆
marton (marton) 于 (Mon Apr 11 17:39:46 2011, 美东) 提到:
这里有Google的面试题和招聘信息：
http://jobguiding.com/it-jobs/it-company-google.html
☆─────────────────────────────────────☆
zwfreesky (自由天空) 于 (Mon Apr 11 20:20:57 2011, 美东) 提到:
谢谢楼主 加油 ！！
赞一个
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Mon Apr 11 22:13:24 2011, 美东) 提到:
My code for 9).
string extractUntilDelim(string s, int i, char delim) {
int n = s.length();
string ans;
for (int j = i; j < n; j++) {
if (s[j] == delim)
return ans;
else
ans += s[j];
}
return ans;
}
// constraint: path must begin with a '/'.
// "/var/www/html/../.././lc" -> "/var/lc/"
// "/../../ -> "/"
string simplifyUnixFilePath(string path) {
deque directories;
int n = path.length();
for (int i = 0; i < n; i++) {
char c = path[i];
if (c == '/') continue;
if (c == '.') {
if (i+1 < n && path[i+1] == '.') {
if (!directories.empty())
directories.pop_back();
continue;
} else if (i+1 >= n || path[i+1] == '/') {
continue;
}
}
string dir = extractUntilDelim(path, i, '/');
directories.push_back(dir);
i += dir.length();
}
string ans = "/";
while (!directories.empty()) {
ans += directories.front() + "/";
directories.pop_front();
}
return ans;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Mon Apr 11 22:18:12 2011, 美东) 提到:
Code for 2).
Idea is to use binary search to find the first occurence where A[i] == k.
Then apply binary search again to find both the lower and upper range.
int binarySearchLower(int A[], int n, int l, int h, int k) {
int lo = l;
int hi = h;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (A[mid] < k)
lo = mid+1;
else
hi = mid-1;
}
assert(lo >= 0 && lo <= n-1); assert(A[lo] == k); assert(lo == 0 || (lo >=
1 && A[lo-1] < k));
return lo;
}
int binarySearchUpper(int A[], int n, int l, int h, int k) {
int lo = l;
int hi = h;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (A[mid] > k)
hi = mid-1;
else
lo = mid+1;
}
assert(hi >= 0 && hi <= n-1); assert(A[hi] == k); assert(hi == n-1 || (hi
<= n-2 && A[hi+1] > k));
return hi;
}
//A={1,1,2,2,2,2,2,3,3,4,4,5,6,7}
//k = 2.
//returns {2,6}
void sortedArrayRepeated(int A[], int n, int k, int &beginIndex, int &
endIndex) {
beginIndex = endIndex = -1;
int lo = 0;
int hi = n-1;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (A[mid] < k) {
lo = mid+1;
} else if (A[mid] > k) {
hi = mid-1;
} else {
beginIndex = binarySearchLower(A, n, lo, mid, k);
endIndex = binarySearchUpper(A, n, mid, hi, k);
return;
}
}
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Mon Apr 11 23:38:42 2011, 美东) 提到:
Solution for 7):
// constraint: n is a positive integer.
// returns the integer part of the square root.
// uses a modification of the binary search.
int sqrt(int n) {
assert(n > 0);
int lo = 1;
int hi = n/2;
while (lo < hi) {
int mid = lo + (hi-lo+1)/2;
int k = mid*mid;
if (k <= n)
lo = mid;
else
hi = mid-1;
}
return lo;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
☆─────────────────────────────────────☆
fzblg (找工作) 于 (Tue Apr 12 01:34:17 2011, 美东) 提到:
mid*mid 溢出怎么办？
☆─────────────────────────────────────☆
CNY () 于 (Tue Apr 12 01:44:06 2011, 美东) 提到:
G家有黑名单这回事吗？收到拒信后换个职位再投行不？
☆─────────────────────────────────────☆
CNY () 于 (Tue Apr 12 01:44:38 2011, 美东) 提到:
同问
☆─────────────────────────────────────☆
recursive (递归) 于 (Tue Apr 12 01:48:43 2011, 美东) 提到:
兄弟跟我犯了同样的小错误
你测试这段code就会发现，n>=185360的时候结果就不对了
原因是 int k = mid*mid 这一行
第一次循环时 mid = 46341，k = 2147488281 > INT_MAX，溢出了 ;)
☆─────────────────────────────────────☆
CNY () 于 (Tue Apr 12 02:13:06 2011, 美东) 提到:
那就用python写;)
G家貌似也比较接受python的
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Apr 12 02:21:34 2011, 美东) 提到:
啊，真是！
那要小心初始化 hi 的值：
已知：
n < 2^32，
=> sqrt(n) < 2^16
这样应该能确保不会溢出：
int hi = min(n/2, (1<<16));
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Tue Apr 12 02:24:42 2011, 美东) 提到:
what is int sqrt(int n)?
☆─────────────────────────────────────☆
ckekebit (克克) 于 (Tue Apr 12 02:53:15 2011, 美东) 提到:
能不能麻烦牛兄展开说一下？
☆─────────────────────────────────────☆
hardtime123 (hard time) 于 (Tue Apr 12 03:14:13 2011, 美东) 提到:
写了一个第9题的,欢迎指正.
void g_SimplifyPath(string &input, string &output) {
int begin=0,end=1;
string tmp;
for ( end=1;end<=input.size();end++) {
if ( end==input.size() || input[end] == '/' ) {
tmp = input.substr(begin,end-begin);
if ( tmp == "/.." ) {
while ( output.size() > 0 && output[output.size()-1] != '/' ) {
output.pop_back();
}
if ( output.size() > 0 ) {
output.pop_back();
}
}
else if ( tmp != "/." ) {
output += tmp;
}
begin = end;
}
}
}
☆─────────────────────────────────────☆
recursive (递归) 于 (Tue Apr 12 10:06:23 2011, 美东) 提到:
你这个不能处理连续多个/的情况
例如 /a///../b，这种path是合法的，应该输出/b
☆─────────────────────────────────────☆
Hond (云卷云舒) 于 (Tue Apr 12 10:33:58 2011, 美东) 提到:
7
http://www.codeproject.com/KB/cpp/Sqrt_Prec_VS_Speed.aspx
☆─────────────────────────────────────☆
yangcheng (牛魔王) 于 (Tue Apr 12 18:47:08 2011, 美东) 提到:
http://hueniverse.com/2007/10/beginners-guide-to-oauth-part-ii-
workflow/
☆─────────────────────────────────────☆
fzhcary (独步天涯) 于 (Tue Apr 12 20:13:53 2011, 美东) 提到:
这些题不容易，尤其现场作，安慰一下。
☆─────────────────────────────────────☆
hardtime123 (hard time) 于 (Tue Apr 12 23:52:31 2011, 美东) 提到:
这个path也合法阿？
不是应该 /a/././../b吗？
不管如何，如果要考虑这个情况，那就改一行，如下，应该就可以了。
else if ( tmp != "/." && tmp != "/" ) {
☆─────────────────────────────────────☆
ckekebit (克克) 于 (Wed Apr 13 02:13:29 2011, 美东) 提到:
我有点儿不明白
user authentication，难道不是维护一个用户名和密码的数据库就可以了吗？怎么和
oAuth扯上关系了呢？
☆─────────────────────────────────────☆
CNY () 于 (Wed Apr 13 02:17:33 2011, 美东) 提到:
大概是指gmail的authentication是实现了OAuth协议的
☆─────────────────────────────────────☆
kiddfly (不老林) 于 (Wed Apr 13 03:36:04 2011, 美东) 提到:
cmft
☆─────────────────────────────────────☆
recursive (递归) 于 (Wed Apr 13 11:22:13 2011, 美东) 提到:
多个连续的/按一个/处理
到linux机器上试一下实际情况就知道了
☆─────────────────────────────────────☆
recursive (递归) 于 (Wed Apr 13 11:24:31 2011, 美东) 提到:
俺辛苦码了这么多字儿，连个mark都没有啊..
☆─────────────────────────────────────☆
speeddy (Wade) 于 (Wed Apr 13 11:46:06 2011, 美东) 提到:
It seems not many interview question relate with the skip list ?
Is it?
☆─────────────────────────────────────☆
gamf (G,A,M,F) 于 (Thu Apr 14 17:39:38 2011, 美东) 提到:
Search company could ask about it.
It is used in inverted list, a key data structure for indexing documents.
☆─────────────────────────────────────☆
falldew (falldew) 于 (Thu May 12 00:16:22 2011, 美东) 提到:
5，文件读写
有个封装好的函数 int block_reader(char *buf)
内部有个静态文件指针，只能向文件末尾移动，不能rewind
每次只能读取4K的block到buf里，返回读取的字节数（除非到文件尾，否则总是4K）
要求实现 int anysize_reader(char *buf, int size)
从文件的当前位置读取任意大小的数据存入buf，并返回实际读到的数据字节数
白板写code
问题的关键在于anysize_reader会被多次调用，每次都可能不是4K对齐
所以需要自己维护一个4K的buffer
请教一下 我没很明白为什么要维护一个4K的buffer?
☆─────────────────────────────────────☆
id425 (id425) 于 (Sun Jun 5 00:21:45 2011, 美东) 提到:
Mark! 感谢楼主辛苦奉献。Good luck!
☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Sun Jun 5 06:53:58 2011, 美东) 提到:
觉得不需要找first occurrence, 直接binary search左右边界，code更简单。
public int[] findRange(int[] a, int value) {
int low = findLeft(a, value, 0, a.length);
int high = findRight(a, value, 0, a.length);
return new int[]{low, high};
}
private int findLeft(int[] a, int value, int lower, int upper) {
int mid = (lower + upper) / 2;
if (mid == lower) return a[mid]==value? mid : mid+1;
return a[mid] >= value? findLeft(a, value, lower, mid) : findLeft(a, value, mid, upper);
}
private int findRight(int[] a, int value, int lower, int upper) {
int mid = (lower + upper) / 2;
if (mid == lower) return a[mid]==value? mid : mid-1;
return a[mid] > value)? findRight(a, value, lower, mid) : findRight(a, value, mid, upper);
}
☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Sun Jun 5 07:22:26 2011, 美东) 提到:
对Java来说，Integer.MAX_VALUE = 2^31-1，不能用2^16
code里加一个判断 if(t>n || t<0) then ...
☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Sun Jun 5 07:49:28 2011, 美东) 提到:
写了个9的Java ->
public class SimplifyPath {
public String simplify(String path) {
String[] segs = path.split("/");
Deque d = new ArrayDeque();
for (String seg : segs) {
if (".".equals(seg) || "".equals(seg)) {
continue;
}
else if ("..".equals(seg)) {
if (!d.isEmpty()) d.removeLast();
}
else {
d.addLast(seg);
}
}
StringBuilder builder = new StringBuilder();
while (!d.isEmpty()) {
builder.append("/" + d.pollFirst());
}
return builder.toString().length()==0? "/" : builder.toString();
}
}
☆─────────────────────────────────────☆
gunking (枪王) 于 (Sun Jun 5 10:42:59 2011, 美东) 提到:
ECE也作coding？
我要去面试hardware， power engineer
不知道google还作这种东西
☆─────────────────────────────────────☆
redgarment (红线裤) 于 (Thu Sep 22 16:19:57 2011, 美东) 提到:
这个明显很慢；用牛顿迭代。。
☆─────────────────────────────────────☆
returning (aaaaaaaaa) 于 (Thu Sep 29 14:45:53 2011, 美东) 提到:
请教
第三题不清楚bit vector在这里的作用，难道不是直接把url放hashtable就行了？bit
vector作用是？
第五题不清楚如果用每次只能读4K的函数实现读取任意字节。
第八题，分布式LRU如何实现?
10，write code to find all the possible combinations of chars in a given
string
这个题是不是要找出所有形成单词的combination？感觉需要像programming pearl一样
对字典做预处理，否则的话难道test每个combination？
谢谢了
☆─────────────────────────────────────☆
phantomlimb (幻肢) 于 (Tue Jan 3 00:43:33 2012, 美东) 提到:
9，Unix file path化简，写code
例如 /a/./b/../../c/ ，化简为 /c/
用stack或者d-queue，有些细节需要考虑，例如 /..//.. 还是输出 /
这题不需要额外的数据结构，从尾部向前反过来做。
我之前写的代码
/* The algorithm runs in O(n) time and O(n) space
* It works backwards so that no stack or other buffer is
* needed to skip the parents folder if a "../" is encountered.
* "//" is preserved as is, and "/./" is changed to "/
* I was able to do a inplace version, but string cut and cat are
* essentially array element revomal, which will make running time
* O(n^2).
*
* My solution is not perfect. I bookkeep the number of skips locally, so it
* only handles continous /../ on the way. It cannot handle mixed case
something like:
* " ../../././//.././/..//.././" in the middle of a path. I know I
* can bookkeep the number skips in the outmost loop, and check a single
* case and increment or decriment nskips accordingly. But I've spent a
couple
* of hours on it, and it's not fair to spend more time on it. That should
* be the right way to go, although my current solution handles all the test
cases
* listed.
*/
#include
#include
#include
#include
int path_normalize(char*);
void test_case(char*);
int main(){
char path0[] = "/abc/def/g/h//ijk";
char path1[] = "./abc/def/./g/h//ijk";
char path2[] = "./abc/def/./././g/h//ijk";
char path3[] = "../abc/def/../g/../h/../ijk";
char path4[] = "abc/def/g/h/../ijk";
char path5[] = "abc/def/g/h/../../ijk";
char path6[] = "/abc/def/g/h/../../ijk";
char path7[] = "abc/def/g/h/../../../ijk";
char path8[] = "abc/def/g/h/../../../../ijk";
char path9[] = "abc/def/g/h/../../../../../ijk";
char path10[] = "abc/def/g/h//../ijk";
test_case(path0);
test_case(path1);
test_case(path2);
test_case(path3);
test_case(path4);
test_case(path5);
test_case(path6);
test_case(path7);
test_case(path8);
test_case(path9);
test_case(path10);
return 0;
}
void test_case(char* path){
printf("Original:\t%s\n", path);
if (0 == path_normalize(path))
printf("Normalized:\t%s\n", path);
else
printf("Normalized:\tError. Mal-formed path\n");
printf("\n");
}
/* Scan input string backwards.
* Reserve "//",
* Fix "/./" to "/".
* Skip the parent path if "/../" encountered
*/
int path_normalize(char* in_str){
int len = strlen(in_str);
char* out_str = malloc(sizeof(char)*(len+1));
if(!out_str)
return -1;
char *src = in_str + len - 1;
char *dst = out_str + len - 1;
int nskips = 0;
*(dst + 1) = '\0';
// in_str indicates the start of the string
while( src >= in_str ){
// "./" pattern found
// Case of path starting with "./" is excluded
if( *src == '/' &&
src - 1 > in_str && *(src - 1) == '.' &&
src - 2 >= in_str && *(src - 2) == '/') {
// Skip ./ in the middle of a path
src -= 2;
continue;
}
// count number of continuous "../" patterns
nskips = 0;
while( *src == '/' &&
src - 1 > in_str && *(src - 1) == '.' &&
src - 2 > in_str && *(src - 2) == '.' &&
src - 3 > in_str && *(src - 3) == '/') {
nskips++;
src -= 3;
}
if(nskips > 0){
// Search for the previous '/'
while( nskips > 0 && (--src) >= in_str ){
if ( ( *src == '/' && ( src == in_str || *(src-1) != '/' ) /
*Skip "//" */)
|| src == in_str){
nskips--;
}
}
if ( src == in_str && *src != '/' && nskips == 0 ){
// Case where path not starting with /
src --;
continue;
} else if ( src > in_str && nskips == 0 )
continue;
else {
free( out_str );
return -1; // Failed to find previous '/', mal-formed path
}
}
*dst = *src;
src--;
dst--;
}
strcpy(in_str, dst+1);
free(out_str);
return 0;
}
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Tue Jan 3 01:03:22 2012, 美东) 提到:
太长。
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Tue Jan 3 01:03:40 2012, 美东) 提到:
这个帖子为何不mark？
☆─────────────────────────────────────☆
etlds (E.T.) 于 (Tue Jan 3 10:30:04 2012, 美东) 提到:
mark！
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Tue Jan 3 10:35:48 2012, 美东) 提到:
版主最近码了好几篇水文，这样的干货却视而不见。
☆─────────────────────────────────────☆
zkongcn (hanks) 于 (Tue Jan 3 14:33:53 2012, 美东) 提到:
No. 10 应该是 find all possible permutation，而不是 combination 吧
☆─────────────────────────────────────☆
geliang2008 (Nemo) 于 (Wed Jan 4 13:38:45 2012, 美东) 提到:
sqrt那道题，可以用
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#
编程很简单
float sqrt(const float m){
float i=0;
float x1,x2;
while( (i*i) <= m )
i+=0.1f;
x1=i;
for(int j=0;j<10;j++)
{
x2=m;
x2/=x1;
x2+=x1;
x2/=2;
x1=x2;
}
return x2;
}
当然这个是float,不过改成int，应该不难
☆─────────────────────────────────────☆
etlds (E.T.) 于 (Wed Jan 4 16:44:20 2012, 美东) 提到:
赞一个，学习了！
☆─────────────────────────────────────☆
Hbase (Hbase) 于 (Thu Jan 5 02:03:07 2012, 美东) 提到:
mark..
☆─────────────────────────────────────☆
Hbase (Hbase) 于 (Thu Jan 5 14:35:34 2012, 美东) 提到:
good one.
but add a minor condition when there doesn't exist such element?
this finds the first element that is >= value.
☆─────────────────────────────────────☆
etlds (E.T.) 于 (Mon Jan 9 10:28:04 2012, 美东) 提到:
请问一下牛顿迭代,怎么能知道收敛到第几次的int是正确的?
☆─────────────────────────────────────☆
etlds (E.T.) 于 (Mon Jan 9 10:38:14 2012, 美东) 提到:
对不起，我傻逼了
迭代到 if(result^2 <= n) 就是了。。。
☆─────────────────────────────────────☆
kirit (Jack) 于 (Mon Jan 9 12:49:22 2012, 美东) 提到:
我也试一个，in-placed的。先把要删掉的mark成'*'。第二次遍历时再删掉。
#include
// /a/b/./../../c/d => /c/d
void path (char *in) {
char *p, *q;
bool isSlash;
char inv='*';
if (!in || !*in) return;
int i=0;
// parse
p=in; isSlash=false;
while (*p) {
/* first slash */
if (*p=='/') {
if (!isSlash) {
isSlash=true;
} else {
*p=inv;
}
p++; continue;
}
isSlash=false;
// printf("\n%2d: %s ", i++, in);
// p is the starting point, looking for the stop
q=p+1;
while (*q && *q!='/') q++;
if ((q-p)==1 && *p=='.') { // ./
*p=inv;
while (p!=in && *p!='/') p--;
if (*q=='/' && *p=='/') *p=inv;
} else if ((q-p)==2 && *p=='.' && *(p+1)=='.') {
*p=*(p+1)=inv;
while (p!=in && *p!='/') {*p=inv; p--;}
if (p==in) {printf("error"); return;}
*p=inv;
while (p!=in && *p!='/') {*p=inv; p--;}
if (*q=='/' && *p=='/') *p=inv;
}
if (!*q) break;
p=q+1; isSlash=true;
}
// clean up
// printf("\ntoclean: %s", in);
char *x=in;
p=in-1;
bool isDirty=false;
while (*(++p)) {
if (*p==inv){ isDirty=true; continue;}
if (isDirty) {*x=*p;}
++x;
}
*x='\0';
printf("\nfinal: %s\n", in);
}
int main () {
char a[100]="///////a///////b/////.///..//./../c/.///./////..//d////////
//////";
printf("%s ", a);
path(a);
printf("=> %s", a);
}
☆─────────────────────────────────────☆
searchlyf (星仔) 于 (Mon Jan 9 16:13:20 2012, 美东) 提到:
Should have shorter version. Who can?
int MySqrt(int n){
if (n < 0)
return -1;
int low = 0;
int high = n;
while (low <= high){
int mid = low + (high - low) / 2;
if (n == mid * mid)
return mid;
else if (n < mid * mid)
high = mid - 1;
else
low = mid + 1;
}
return low - 1;
}
☆─────────────────────────────────────☆
searchlyf (星仔) 于 (Mon Jan 9 16:13:37 2012, 美东) 提到:
Should have shorter version. Who can?
int MySqrt(int n){
if (n < 0)
return -1;
int low = 0;
int high = n;
while (low <= high){
int mid = low + (high - low) / 2;
if (n == mid * mid)
return mid;
else if (n < mid * mid)
high = mid - 1;
else
low = mid + 1;
}
return low - 1;
}
☆─────────────────────────────────────☆
searchlyf (星仔) 于 (Mon Jan 9 17:19:35 2012, 美东) 提到:
// /a/./b/../../c/ -> /c/
// /aaa/./b/../../cccc/ -> /cccc/
// /a../ -> wrong
// /.../ -> wrong
// ./////////z////// -> z/
// /// -> /
// /..//.. -> /
// a/.. -> empty
// /../../../../a/ -> /a/
// ../../../../a/ -> ../../../../a/, no change, my god, tooo complex
☆─────────────────────────────────────☆
kirit (Jack) 于 (Mon Jan 9 19:34:04 2012, 美东) 提到:
I wonder whether we have to go down to this level of test case for interview
coding, in particular with the interview where multiple coding questions
are going to be asked. After all, we have only ~15 minutes for each coding
questions. Correct me if I'm wrong.
☆─────────────────────────────────────☆
etlds (E.T.) 于 (Tue Jan 10 10:43:16 2012, 美东) 提到:
我用C#写了个牛顿迭代的，收敛比binary search是快很多
public static int sqrt(int n)
{
int ret = 1;
do
ret = (ret + n/ret) / 2;
while(Math.Pow(ret, 2) > n); //Math.Pow()返回的是Double值，不用担心
overflow
return ret;
}
☆─────────────────────────────────────☆
Hbase (Hbase) 于 (Tue Jan 10 13:41:22 2012, 美东) 提到:
很喜欢火鸡这个两元素做为base cases. 很clean。如果一个元素作为base case总是容
易出错也不natural
我把所有的类似的问题的 实现都改成两元素作为base case了,呵呵
☆─────────────────────────────────────☆
searchlyf (星仔) 于 (Wed Jan 11 13:50:12 2012, 美东) 提到:
totally agree.
impossible for me to finish following during interview.
// /a/./b/../../c/ -> /c/
// /aaa/./b/../../cccc/ -> /cccc/
// /a../ -> wrong
// /.../ -> wrong
// ./////////z////// -> z/
// /// -> /
// /..//.. -> /
// a/.. -> empty
// /../../../../a/ -> /a/
// ../../../../a/ -> ../../../../a/, no change,
// ../../../../a/../b/ -> ../../../../b/
// blank space in the middle -> trancate
// my god, tooo complex
bool SimplePath(char *path){
if (!path)
return false;
char *pre = path;
char *p = path;
while (isspace(*p))
++p;
while(*p && !isspace(*p)){
if (*p == '.'){
if (pre > path && *(pre - 1) != '/'){
return false;
}
if (*(p + 1) == '/' || *(p + 1) == '\0'){
p += 1;
while (*p == '/')
++p;
}else if (*(p + 1) == '.' && (*(p + 2) == '/' || *(p + 2) == '\0
')){
if (pre > path){
if (pre > path + 1){
if (*(pre - 2) != '.'){
pre -= 2;
while (pre > path && *pre != '/'){
--pre;
}
if (*pre == '/'){
pre += 1;
}
}else{
*pre++ = '.'; *pre++ = '.'; *pre++ = '/';
}
}
}else{
*pre++ = '.'; *pre++ = '.'; *pre++ = '/';
}
p += 2;
while (*p == '/')
++p;
}else{
return false;
}
}else{
*pre++ = *p++;
if (*(p - 1) == '/'){
while (*p == '/')
++p;
}
}
}
*pre = '\0';
return true;
}
void TestSimplePath(){
char a[] = "/a/./b/../../c/";
char b[] = "/a/./b/../../c/"; // -> /c/
char c[] = "/aaa/./b/../../cccc/"; // -> /cccc/
char d[] = "/a../"; // -> wrong
char e[] = "/.../"; // -> wrong
char f[] = "./////////z//////"; // -> z/
char g[] = "///"; // -> /
char h[] = "/..//.."; // -> /
char i[] = "a/.."; // -> empty
char j[] = "/../../../../a/"; // -> /a/
char k[] = "../../../../a/"; // -> ../../../../a/, no change,
char l[] = "../../../../a/../b/"; // -> ../../../../b/
char m[] = "../../../../a/ ../b/"; //blank space in the middle ->
trancate
bool ba = SimplePath(a);
bool bb = SimplePath(b);
bool bc = SimplePath(c);
bool bd = SimplePath(d);
bool be = SimplePath(e);
bool bf = SimplePath(f);
bool bg = SimplePath(g);
bool bh = SimplePath(h);
bool bi = SimplePath(i);
bool bj = SimplePath(j);
bool bk = SimplePath(k);
bool bl = SimplePath(l);
bool bm = SimplePath(m);
}
interview
☆─────────────────────────────────────☆
searchlyf (星仔) 于 (Wed Jan 11 13:51:30 2012, 美东) 提到:
nice. just not easy to remember.
☆─────────────────────────────────────☆
mechanical (mechanical) 于 (Fri Jan 13 16:15:27 2012, 美东) 提到:
thanks for sharing
==================================
大半夜收到HR的thank you note。不用管什么NDA了
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the output should be [2, 6]
binary search的变种
3，number of unique url accesses in huge log files
hashtable + bit vector
讨论hash的实现，bit vector如何快速统计有多少个entry
onsite：
4，老题，爬楼梯一次可以走一级或者两级，爬N级有多少种走法
5，文件读写
有个封装好的函数 int block_reader(char *buf)
内部有个静态文件指针，只能向文件末尾移动，不能rewind
每次只能读取4K的block到buf里，返回读取的字节数（除非到文件尾，否则总是4K）
要求实现 int anysize_reader(char *buf, int size)
从文件的当前位置读取任意大小的数据存入buf，并返回实际读到的数据字节数
白板写code
问题的关键在于anysize_reader会被多次调用，每次都可能不是4K对齐
所以需要自己维护一个4K的buffer
6，系统设计
讨论gmail的user authentication，描述详细的流程，性能瓶颈
如何做load balancing
7，写code实现int sqrt(int n)
用binary search，需要考虑比较多的细节
8，老题，实现分布的LRU cache，要求存取时间O(1)
9，Unix file path化简，写code
例如 /a/./b/../../c/ ，化简为 /c/
用stack或者d-queue，有些细节需要考虑，例如 /..//.. 还是输出 /
10，write code to find all the possible combinations of chars in a given
string
11，a set of intervals, how to tell if a given value is in any of the
intervals
讨论了overlapping的情况，interval tree，etc
还有一些类似难度的题，记不大清楚了。总之不是很难
俺基本功不扎实，倒在了胜利的前夕
希望后来的xdjm们都能传捷报～～～～ | e*****a
发帖数: 79 | | g*******n
发帖数: 214 | 3 Mark
★ Sent from iPhone App: iReader Mitbbs Lite 7.38 |
|
|
|
|
|
|
|
