r*******e
发帖数: 7583 | 1 大半夜收到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们都能传捷报～～～～ |
b*******y
发帖数: 1240 | 2 楼主是怎么准备算法的？
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
W****X
发帖数: 84 | |
r*******e
发帖数: 7583 | 4 标准模板
thanks for your interest
we are unable to find a matching position, etc etc
【在 W****X 的大作中提到】
: 拒信只有一句thank your note?
|
f*********i
发帖数: 197 | 5 楼主辛苦了,会有更好的.
各位大牛能否把第五题的思路说明一下? |
C***y
发帖数: 2546 | 6 cmft
东家不亮西家亮
【在 r*******e 的大作中提到】
: 标准模板
: thanks for your interest
: we are unable to find a matching position, etc etc
|
g*********s
发帖数: 1782 | 7 电面不简单啊。45分钟三道题还是挺紧张的。
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
g*********s
发帖数: 1782 | 8 gmail那个题怎么回答为好？最头疼这种问题。
【在 g*********s 的大作中提到】
: 电面不简单啊。45分钟三道题还是挺紧张的。
|
y*******g
发帖数: 6599 | 9 和oauth差不多吧？
【在 g*********s 的大作中提到】
: gmail那个题怎么回答为好？最头疼这种问题。
|
f****4
发帖数: 1359 | 10 感谢lz分享
bless offer即将到来～ |
|
|
a********1
发帖数: 750 | |
m****n
发帖数: 11 | 12 这里有Google的面试题和招聘信息：
http://jobguiding.com/it-jobs/it-company-google.html
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
z*******y
发帖数: 578 | |
i**********e
发帖数: 1145 | 14 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 |
i**********e
发帖数: 1145 | 15 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 |
i**********e
发帖数: 1145 | 16 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 |
f***g
发帖数: 214 | 17 mid*mid 溢出怎么办？
【在 i**********e 的大作中提到】
: 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;
|
C*Y
发帖数: 736 | 18 G家有黑名单这回事吗？收到拒信后换个职位再投行不？ |
C*Y
发帖数: 736 | 19 同问
【在 g*********s 的大作中提到】
: gmail那个题怎么回答为好？最头疼这种问题。
|
r*******e
发帖数: 7583 | 20 兄弟跟我犯了同样的小错误
你测试这段code就会发现，n>=185360的时候结果就不对了
原因是 int k = mid*mid 这一行
第一次循环时 mid = 46341，k = 2147488281 > INT_MAX，溢出了 ;)
【在 i**********e 的大作中提到】
: 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;
|
|
|
C*Y
发帖数: 736 | 21 那就用python写;)
G家貌似也比较接受python的
【在 r*******e 的大作中提到】
: 兄弟跟我犯了同样的小错误
: 你测试这段code就会发现，n>=185360的时候结果就不对了
: 原因是 int k = mid*mid 这一行
: 第一次循环时 mid = 46341，k = 2147488281 > INT_MAX，溢出了 ;)
|
i**********e
发帖数: 1145 | 22 啊，真是！
那要小心初始化 hi 的值：
已知：
n < 2^32，
=> sqrt(n) < 2^16
这样应该能确保不会溢出：
int hi = min(n/2, (1<<16));
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 r*******e 的大作中提到】
: 兄弟跟我犯了同样的小错误
: 你测试这段code就会发现，n>=185360的时候结果就不对了
: 原因是 int k = mid*mid 这一行
: 第一次循环时 mid = 46341，k = 2147488281 > INT_MAX，溢出了 ;)
|
g*********s
发帖数: 1782 | 23 what is int sqrt(int n)?
【在 r*******e 的大作中提到】
: 兄弟跟我犯了同样的小错误
: 你测试这段code就会发现，n>=185360的时候结果就不对了
: 原因是 int k = mid*mid 这一行
: 第一次循环时 mid = 46341，k = 2147488281 > INT_MAX，溢出了 ;)
|
c******t
发帖数: 1500 | 24 能不能麻烦牛兄展开说一下？
【在 y*******g 的大作中提到】
: 和oauth差不多吧？
|
h*********3
发帖数: 111 | 25 写了一个第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;
}
}
}
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
r*******e
发帖数: 7583 | 26 你这个不能处理连续多个/的情况
例如 /a///../b，这种path是合法的，应该输出/b
【在 h*********3 的大作中提到】
: 写了一个第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();
|
H**d
发帖数: 152 | |
y*******g
发帖数: 6599 | |
f*****y
发帖数: 444 | 29 这些题不容易，尤其现场作，安慰一下。
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
h*********3
发帖数: 111 | 30 这个path也合法阿？
不是应该 /a/././../b吗？
不管如何，如果要考虑这个情况，那就改一行，如下，应该就可以了。
else if ( tmp != "/." && tmp != "/" ) {
【在 r*******e 的大作中提到】
: 你这个不能处理连续多个/的情况
: 例如 /a///../b，这种path是合法的，应该输出/b
|
|
|
c******t
发帖数: 1500 | 31 我有点儿不明白
user authentication，难道不是维护一个用户名和密码的数据库就可以了吗？怎么和
oAuth扯上关系了呢？
【在 y*******g 的大作中提到】
: http://hueniverse.com/2007/10/beginners-guide-to-oauth-part-ii-
: workflow/
|
C*Y
发帖数: 736 | 32 大概是指gmail的authentication是实现了OAuth协议的
【在 c******t 的大作中提到】
: 我有点儿不明白
: user authentication，难道不是维护一个用户名和密码的数据库就可以了吗？怎么和
: oAuth扯上关系了呢？
|
k*****y
发帖数: 131 | 33 cmft
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
r*******e
发帖数: 7583 | 34 多个连续的/按一个/处理
到linux机器上试一下实际情况就知道了
【在 h*********3 的大作中提到】
: 这个path也合法阿？
: 不是应该 /a/././../b吗？
: 不管如何，如果要考虑这个情况，那就改一行，如下，应该就可以了。
: else if ( tmp != "/." && tmp != "/" ) {
|
r*******e
发帖数: 7583 | 35 俺辛苦码了这么多字儿，连个mark都没有啊..
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
s*****y
发帖数: 897 | 36 It seems not many interview question relate with the skip list ?
Is it?
【在 r*******e 的大作中提到】
: 多个连续的/按一个/处理
: 到linux机器上试一下实际情况就知道了
|
g**f
发帖数: 414 | 37 Search company could ask about it.
It is used in inverted list, a key data structure for indexing documents.
【在 s*****y 的大作中提到】
: It seems not many interview question relate with the skip list ?
: Is it?
|
f*****w
发帖数: 2602 | 38
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?
【在 r*******e 的大作中提到】
: 俺辛苦码了这么多字儿，连个mark都没有啊..
|
i***5
发帖数: 121 | 39 Mark! 感谢楼主辛苦奉献。Good luck!
【在 r*******e 的大作中提到】
: 俺辛苦码了这么多字儿，连个mark都没有啊..
|
g**********y
发帖数: 14569 | 40 觉得不需要找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? lower : lower+1;
if (a[mid] >= value) {
return findLeft(a, value, lower, mid);
}
else {
return 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;
if (a[mid] > value) {
return findRight(a, value, lower, mid);
}
else {
return findRight(a, value, mid, upper);
}
}
【在 i**********e 的大作中提到】
: 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;
|
|
|
g**********y
发帖数: 14569 | 41 对Java来说，Integer.MAX_VALUE = 2^31-1，不能用2^16
code里加一个判断 if(t>n || t<0) then ...
【在 i**********e 的大作中提到】
: 啊，真是！
: 那要小心初始化 hi 的值：
: 已知：
: n < 2^32，
: => sqrt(n) < 2^16
: 这样应该能确保不会溢出：
: int hi = min(n/2, (1<<16));
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
g**********y
发帖数: 14569 | 42 写了个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();
}
} |
g*****g
发帖数: 3623 | 43 ECE也作coding？
我要去面试hardware， power engineer
不知道google还作这种东西 |
r********t
发帖数: 395 | 44 这个明显很慢；用牛顿迭代。。
【在 i**********e 的大作中提到】
: 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;
|
r*******g
发帖数: 1335 | 45 请教
第三题不清楚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？
谢谢了 |
r*******e
发帖数: 7583 | 46 大半夜收到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们都能传捷报～～～～ |
b*******y
发帖数: 1240 | 47 楼主是怎么准备算法的？
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
W****X
发帖数: 84 | |
r*******e
发帖数: 7583 | 49 标准模板
thanks for your interest
we are unable to find a matching position, etc etc
【在 W****X 的大作中提到】
: 拒信只有一句thank your note?
|
f*********i
发帖数: 197 | 50 楼主辛苦了,会有更好的.
各位大牛能否把第五题的思路说明一下? |
|
|
C***y
发帖数: 2546 | 51 cmft
东家不亮西家亮
【在 r*******e 的大作中提到】
: 标准模板
: thanks for your interest
: we are unable to find a matching position, etc etc
|
g*********s
发帖数: 1782 | 52 电面不简单啊。45分钟三道题还是挺紧张的。
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
g*********s
发帖数: 1782 | 53 gmail那个题怎么回答为好？最头疼这种问题。
【在 g*********s 的大作中提到】
: 电面不简单啊。45分钟三道题还是挺紧张的。
|
y*******g
发帖数: 6599 | 54 和oauth差不多吧？
【在 g*********s 的大作中提到】
: gmail那个题怎么回答为好？最头疼这种问题。
|
f****4
发帖数: 1359 | 55 感谢lz分享
bless offer即将到来～ |
a********1
发帖数: 750 | |
m****n
发帖数: 11 | 57 这里有Google的面试题和招聘信息：
http://jobguiding.com/it-jobs/it-company-google.html
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
z*******y
发帖数: 578 | |
i**********e
发帖数: 1145 | 59 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 |
i**********e
发帖数: 1145 | 60 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 |
|
|
i**********e
发帖数: 1145 | 61 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 |
f***g
发帖数: 214 | 62 mid*mid 溢出怎么办？
【在 i**********e 的大作中提到】
: 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;
|
C*Y
发帖数: 736 | 63 G家有黑名单这回事吗？收到拒信后换个职位再投行不？ |
C*Y
发帖数: 736 | 64 同问
【在 g*********s 的大作中提到】
: gmail那个题怎么回答为好？最头疼这种问题。
|
r*******e
发帖数: 7583 | 65 兄弟跟我犯了同样的小错误
你测试这段code就会发现，n>=185360的时候结果就不对了
原因是 int k = mid*mid 这一行
第一次循环时 mid = 46341，k = 2147488281 > INT_MAX，溢出了 ;)
【在 i**********e 的大作中提到】
: 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;
|
C*Y
发帖数: 736 | 66 那就用python写;)
G家貌似也比较接受python的
【在 r*******e 的大作中提到】
: 兄弟跟我犯了同样的小错误
: 你测试这段code就会发现，n>=185360的时候结果就不对了
: 原因是 int k = mid*mid 这一行
: 第一次循环时 mid = 46341，k = 2147488281 > INT_MAX，溢出了 ;)
|
i**********e
发帖数: 1145 | 67 啊，真是！
那要小心初始化 hi 的值：
已知：
n < 2^32，
=> sqrt(n) < 2^16
这样应该能确保不会溢出：
int hi = min(n/2, (1<<16));
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 r*******e 的大作中提到】
: 兄弟跟我犯了同样的小错误
: 你测试这段code就会发现，n>=185360的时候结果就不对了
: 原因是 int k = mid*mid 这一行
: 第一次循环时 mid = 46341，k = 2147488281 > INT_MAX，溢出了 ;)
|
g*********s
发帖数: 1782 | 68 what is int sqrt(int n)?
【在 r*******e 的大作中提到】
: 兄弟跟我犯了同样的小错误
: 你测试这段code就会发现，n>=185360的时候结果就不对了
: 原因是 int k = mid*mid 这一行
: 第一次循环时 mid = 46341，k = 2147488281 > INT_MAX，溢出了 ;)
|
c******t
发帖数: 1500 | 69 能不能麻烦牛兄展开说一下？
【在 y*******g 的大作中提到】
: 和oauth差不多吧？
|
h*********3
发帖数: 111 | 70 写了一个第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;
}
}
}
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
|
|
r*******e
发帖数: 7583 | 71 你这个不能处理连续多个/的情况
例如 /a///../b，这种path是合法的，应该输出/b
【在 h*********3 的大作中提到】
: 写了一个第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();
|
H**d
发帖数: 152 | |
y*******g
发帖数: 6599 | |
f*****y
发帖数: 444 | 74 这些题不容易，尤其现场作，安慰一下。
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
h*********3
发帖数: 111 | 75 这个path也合法阿？
不是应该 /a/././../b吗？
不管如何，如果要考虑这个情况，那就改一行，如下，应该就可以了。
else if ( tmp != "/." && tmp != "/" ) {
【在 r*******e 的大作中提到】
: 你这个不能处理连续多个/的情况
: 例如 /a///../b，这种path是合法的，应该输出/b
|
c******t
发帖数: 1500 | 76 我有点儿不明白
user authentication，难道不是维护一个用户名和密码的数据库就可以了吗？怎么和
oAuth扯上关系了呢？
【在 y*******g 的大作中提到】
: http://hueniverse.com/2007/10/beginners-guide-to-oauth-part-ii-
: workflow/
|
C*Y
发帖数: 736 | 77 大概是指gmail的authentication是实现了OAuth协议的
【在 c******t 的大作中提到】
: 我有点儿不明白
: user authentication，难道不是维护一个用户名和密码的数据库就可以了吗？怎么和
: oAuth扯上关系了呢？
|
k*****y
发帖数: 131 | 78 cmft
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
r*******e
发帖数: 7583 | 79 多个连续的/按一个/处理
到linux机器上试一下实际情况就知道了
【在 h*********3 的大作中提到】
: 这个path也合法阿？
: 不是应该 /a/././../b吗？
: 不管如何，如果要考虑这个情况，那就改一行，如下，应该就可以了。
: else if ( tmp != "/." && tmp != "/" ) {
|
r*******e
发帖数: 7583 | 80 俺辛苦码了这么多字儿，连个mark都没有啊..
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
|
|
s*****y
发帖数: 897 | 81 It seems not many interview question relate with the skip list ?
Is it?
【在 r*******e 的大作中提到】
: 多个连续的/按一个/处理
: 到linux机器上试一下实际情况就知道了
|
g**f
发帖数: 414 | 82 Search company could ask about it.
It is used in inverted list, a key data structure for indexing documents.
【在 s*****y 的大作中提到】
: It seems not many interview question relate with the skip list ?
: Is it?
|
f*****w
发帖数: 2602 | 83
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?
【在 r*******e 的大作中提到】
: 俺辛苦码了这么多字儿，连个mark都没有啊..
|
i***5
发帖数: 121 | 84 Mark! 感谢楼主辛苦奉献。Good luck!
【在 r*******e 的大作中提到】
: 俺辛苦码了这么多字儿，连个mark都没有啊..
|
g**********y
发帖数: 14569 | 85 觉得不需要找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);
}
【在 i**********e 的大作中提到】
: 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;
|
g**********y
发帖数: 14569 | 86 对Java来说，Integer.MAX_VALUE = 2^31-1，不能用2^16
code里加一个判断 if(t>n || t<0) then ...
【在 i**********e 的大作中提到】
: 啊，真是！
: 那要小心初始化 hi 的值：
: 已知：
: n < 2^32，
: => sqrt(n) < 2^16
: 这样应该能确保不会溢出：
: int hi = min(n/2, (1<<16));
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
g**********y
发帖数: 14569 | 87 写了个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();
}
} |
g*****g
发帖数: 3623 | 88 ECE也作coding？
我要去面试hardware， power engineer
不知道google还作这种东西 |
r********t
发帖数: 395 | 89 这个明显很慢；用牛顿迭代。。
【在 i**********e 的大作中提到】
: 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;
|
r*******g
发帖数: 1335 | 90 请教
第三题不清楚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？
谢谢了 |
|
|
p*********b
发帖数: 47 | 91 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;
} |
q****x
发帖数: 7404 | 92 太长。
【在 p*********b 的大作中提到】
: 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
|
q****x
发帖数: 7404 | 93 这个帖子为何不mark？
【在 r*******e 的大作中提到】
: 大半夜收到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***s
发帖数: 799 | |
q****x
发帖数: 7404 | 95 版主最近码了好几篇水文，这样的干货却视而不见。
【在 e***s 的大作中提到】
: mark！
|
z*****n
发帖数: 447 | 96 No. 10 应该是 find all possible permutation，而不是 combination 吧
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
g*********8
发帖数: 64 | 97 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，应该不难 |
e***s
发帖数: 799 | 98 赞一个，学习了！
【在 g**********y 的大作中提到】
: 觉得不需要找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;
|
H***e
发帖数: 476 | 99 mark..
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
H***e
发帖数: 476 | 100 good one.
but add a minor condition when there doesn't exist such element?
this finds the first element that is >= value.
【在 g**********y 的大作中提到】
: 觉得不需要找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;
|
|
|
e***s
发帖数: 799 | 101 请问一下牛顿迭代,怎么能知道收敛到第几次的int是正确的?
【在 r********t 的大作中提到】
: 这个明显很慢；用牛顿迭代。。
|
e***s
发帖数: 799 | 102 对不起，我傻逼了
迭代到 if(result^2 <= n) 就是了。。。
【在 e***s 的大作中提到】
: 请问一下牛顿迭代,怎么能知道收敛到第几次的int是正确的?
|
k***t
发帖数: 276 | 103 我也试一个，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);
}
【在 q****x 的大作中提到】
: 太长。
|
s*******f
发帖数: 1114 | 104 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;
}
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
s*******f
发帖数: 1114 | 105 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;
}
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
s*******f
发帖数: 1114 | 106 // /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
【在 r*******e 的大作中提到】
: 大半夜收到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.
|
k***t
发帖数: 276 | 107 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.
【在 s*******f 的大作中提到】
: // /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
|
e***s
发帖数: 799 | 108 我用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;
}
【在 s*******f 的大作中提到】
: 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;
|
H***e
发帖数: 476 | 109 很喜欢火鸡这个两元素做为base cases. 很clean。如果一个元素作为base case总是容
易出错也不natural
我把所有的类似的问题的 实现都改成两元素作为base case了,呵呵
【在 g**********y 的大作中提到】
: 觉得不需要找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;
|
