几家

发信人: jakemajia (jakemajia), 信区: JobHunting
标  题: 报Amazon Offer，附bloomberg等几家面经，发100个包子
发信站: BBS 未名空间站 (Sun Aug 17 18:39:54 2014, 美东)

感谢版上的人报各种面经，小弟也尽量回忆说说自己的面试经历， 希望有所帮助。强
烈推荐大家加入群名称是zalgorithm算法面试QQ群 （229623621）。 喜欢讨论问题的
可以讨论，喜欢潜水的可以看人家讨论激励自己多做题。

我的背景是 new graduate PHD, 由于老板的原因，在一家公司有3-4年的intern经验。
申请的都是编程的工作。

第一个面试过的是新泽西的audible 亚马逊的公司，整体难度不大， 题目在leetcode
里面属于中等偏下。总共2 轮电面，5轮 on-site. OOD 设计题是 design flight
ticket system有一轮没有做题，纯粹说自己做的东西还有behavior questions （
interviewer 是经理，应该是bar risers）。  面试完后一个星期给offer，但是感觉
offer不好，据了。

后面面bloomberg，可能运气好题目也不难。一轮 电话面试包括 best time to sell
stock, 还有一个string排序的问题 （具体不记得）。 On-site的问题包括 2 Sum,
build Stack using Two Queues,  一个数组里重复最多的元素， reverse linked
list,  多个数组找到到在每个数组里面都重复的元素 (比如 [1,2,2,3,4,4],  [1,2,2
,3,3], 第一个数组里面 2和4重复，第二个里面2，3重复， return [2]).    经理面
试没问编程题目，就问了问做的东西，哪里有瓶颈，哪里怎么实现的。 最后拿到了
Offer。

后面面F家 new york 的位置。电话面试题是 检测palindrome string, 找出最长
palindrome string (跟leetcode不一样，方法差不多)。 On site 题目有Merge
Intervals,  Binary Tree Maximum Path Sum。 设计题： 已知有facebook.com, m.
facebook.com (移动端),  o.facebook.com（为贫困山区建的，省数据流量，没有图片
）， 服务器端有各种数据不用你操心，设计一个客户端和服务器端的API。  大概一个
月收到据信。

后面 亚马逊纽约招人，所以又点了下申请。然后Recruiter联系，没有面试给了纽约的
offer。 最后决定接受这个offer。

现在小弟也终于可以内推人了 ^_^.  有需要内推amazon可以联系我




发信人: yaqifighting (yaqi), 信区: JobHunting
标  题: EE 转ＣＳ面经
发信站: BBS 未名空间站 (Wed Apr  9 15:33:18 2014, 美东)

小女ＥＥ小硕一枚，　从刷题到面试整整半年，总算有着落了，在版上学了很多，现在
把自己的面经总结下，希望能帮到别人。
1, Microsoft
on-campus
*Card Shuffle
*设计一个报警器

2, Yelp
phone:
*chain iterator
*给一个特定的message，根据keyword 输出，比如输出所有含yelp food 的message

3, blackrock
1, 设计file system
2, Java refactor 的用法
3， OOP 的基本概念

4， A 家
1， URL group， 输出最常用的URL
2， 黑白格路径问题
3， reverse a linked list ，两种方法
4， Design bus schedule system


还有一些记不太清楚，总体来讲觉得对EE 的同学来说从cracking the coding 开始是
个不错的选择，然后再做一些leetcode, 对语言的基本概念要清楚。祝大家都能找到理
想的工作。



发信人: Zhuimeng1314 (  追梦一生), 信区: JobHunting
标  题: Facebook面经
发信站: BBS 未名空间站 (Sat Aug 16 12:34:34 2014, 美东)

都不难，非常注重代码的速度跟简洁性。不过俺已挂。大家加油。
电面
Clone graph
onsite
1. 一个manager 先聊behavior， 然后做了一个小题
    isOneEditDistance 判断两个string是不是只差一个编辑距离。
2. 3Sum 变体，每个数字可以重复用。
3. System design设计手机上读取photo feeds的app。
    功能： 读取好友的最近图片
               阅览好友的相册
    要求： 满足功能的同时减少对手机的能耗。
4. (1) 一维度向量相乘。每个向量很长，billion个数字。
    (2) 多线程 reader 跟 writer 的经典问题。
加面
1. 求 LCA 两种情况，有parent结点跟没有parent的结点的情况都要回答。
2. search in rotated sorted array LC原题。
    decode ways LC原题。

--------------------------------------------

g 最新2014.7月电面


把一个list的字符串  编码成 一个字符串

再把这个编码过的字符串 转回原来的list
String encode(List<String> strings){

}

List<String> decode(String s){

}



Ans:
用"\"作为转义字符:

我找了一下，看到一个不错的答案。就是先将每个单词里面的反斜杠'\'加倍变成连续2个'\'，然后将每个每个单词里面的逗号','前面加上一个反斜杠'\'。最后在每个单词中间加上一个逗号','。得到输出的字符串。
反序列化的时候遇到第一个反斜杠就先跳过，然后加上后面的字符。这样就可以解码了。说起来不太描述，大家可以看一下这个链接里的第一个答案，然后在纸上比划比划。

http://stackoverflow.com/questions/853475/whats-the-simplest-way-to-encoding-liststring-into-plain-string-and-decode-it

Ans2:
字符串编码的话有现成的方案。
BitTorrent规范里用到的BEncoding就是，字符串长度+冒号+字符串。
直接照着BEncoding的规范做List<String>序列化和反序列化就行了。
---------------------

Given a string s, remove duplicate adjacent characters from s recursively.(注意这里的recursively 不是指必须写recursive函数)

For example:
Input: "abbac"
Output: "c", first remove adjacent duplicated 'b's, then remove adjacent
duplicated 'a'.

Input: "acbbcad"
Output" "d", first remove 'b', then remove 'c', then remove 'a'.

Input: "acbbcda"
Output: "ada"

other example:
string str1 = "geeksforgeeg";
Output: gksfor

string str2 = "azxxxzy";
Output: ay （3个x相邻，全删掉，然后删除z）

string str3 = "caaabbbaac";
Output: empty string

Do it with one pass over the string.

发信人: rtscts (syslink), 信区: JobHunting
标  题: Re: 请教一道题：Remove adjacent duplicate char recursively fro
发信站: BBS 未名空间站 (Tue Jun  3 20:52:35 2014, 美东)

push into stack and popup if next char is the same.

  public static String removeDup(String str)
        {
            if(str == null || str.length() <= 1)
                return str;
            Stack <Character> stack = new Stack<Character>();
            Character last = ' ';
            for(int i = 0; i < str.length(); i++)
            {
                char ch = str.charAt(i);
              
                if(ch!=last && (stack.isEmpty() || ch != stack.peek()))
                {
                    stack.push(ch);
                }
                else if(!stack.isEmpty() && ch == stack.peek())
                {
                        stack.pop();
                }
                else if (ch == last);
              
                last=ch;
            }

            return stack.toString();
        }




Expand a random range from 1–5 to 1–7



Adam Rosenfield's solution:

关于思路也可参考：
http://ariya.blogspot.com/2007/11/random-number-15-to-17.html
   

There is no (exactly correct) solution which will run in a constant amount of time, since 1/7 is an infinite decimal in base 5. One simple solution would be to use rejection sampling, e.g.:


int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;  // result is now uniformly random between 1 and 7

This has an expected runtime of 25/21 = 1.19 iterations of the loop, but there is an infinitesimally small probability of looping forever.





This is equivalent to Adam Rosenfield's solution, but may be a bit more clear for some readers. It assumes rand5() is a function that returns a statistically random integer in the range 1 through 5 inclusive.

int rand7()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}

How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it's a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That's what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don't get a good result, we keep throwing darts.

Like Adam said, this can run forever in the worst case, but statistically the worst case never happens. :)




2

design a Data structure that satisfies: insert, remove, contains, get random element, all at O(1)



Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.

    insert(value): append the value to array and let i be it's index in A. Set H[value]=i.
    remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.
    contains(value): return H.contains(value)
    getRandomElement(): let r=random(current size of A). return A[r].

since the array needs to auto-increase in size, it's going to be amortize O(1) to add an element, but I guess that's OK.





3.

A zero-indexed array A consisting of N integers is given. A magnitude pole of this array is an integer Q such that:
0 ≤ Q < N;
A[P] ≤ A[Q] for 0 ≤ P < Q;
A[Q] ≤ A[R] for Q < R < N.
For example, consider array A consisting of ten elements such that:
  A[0] = 4 
  A[1] = 2 
  A[2] = 2
  A[3] = 3 
  A[4] = 1 
  A[5] = 4
  A[6] = 7 
  A[7] = 8 
  A[8] = 6
  A[9] = 9
Number 5 is a magnitude pole of this array, because all elements to the left of A[5] have values smaller than or equal to A[5] (4, 2, 2, 3 and 1 are smaller than or equal to 4) and all elements to the right of A[5] have values greater than or equal to A[5] (7, 8, 6 and 9 are greater than or equal to 4). Number 9 is also a magnitude pole of this array.
Write a function:
class Solution { public int solution(int[] A); }
that, given a zero-indexed array A consisting of N integers, returns any of its magnitude poles. The function should return ?1 if array A does not have a magnitude pole.
For example, given array A consisting of ten elements such that:
  A[0] = 4 
  A[1] = 2 
  A[2] = 2
  A[3] = 3 
  A[4] = 1 
  A[5] = 4
  A[6] = 7 
  A[7] = 8 
  A[8] = 6
  A[9] = 9
the function may return 5 or 9, as explained above.
Assume that:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [?2147483648..2147483647].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.















Answer:

use two array. one array records the max value till now. the other records the min value in the range [cur_pos, end].




5.Given a file, find the ten most frequently occuring words as efficiently as possible


Answer:


I think the trie data structure is a choice.

In the trie, you can record word count in each node representing frequency of word consisting of characters on the path from root to current node.

The time complexity to setup the trie is O(Ln) ~ O(n) (where L is number of characters in the longest word, which we can treat as a constant). To find the top 10 words, we can traversal the trie, which also costs O(n). So it takes O(n) to solve this problem.


Also: trie+minheap    http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

related:
ebay interview:

    a. how to get top 10 frequent words in a small file?
    b. how to get top 10 frequent words in a large file (cannot fit into memory)?
    c. how to get top n frequent words in a large file (cannot fit into memory, n could be dynamically changed, this function would be called for several times)?
    d. how to get top n frequent words in a word stream?




find longest increasing sub sequence in 2d array.
(bit more expl..)
ex: finding length of the snake in snake game
---------
the sequence must not be diagonally.
but it can be any like top-bootm,bottom-left-top ........
increasing means one step
ex: 10,11,12,13 (correct)
12,14,15,20(wrong)
Ex: input: consider 4x4 grid
 2 3  4  5
 4 5 10 11
20 6  9 12
 6 7  8 40

output : 4 5 6 7 8 9 10 11 12



Answer:(此题应该用dp的memoization, as it is said in CLRS, if some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required.)



we can do it by dynamic programming. here are the steps:
1. create a new 2d array (let say named temp[][]) of same dimension as original. the element temp[i][j] contains the length of the LIS starting at this point.
2. first fill this temp array with 0's.
3. now, start filling this temp array. let say given array's dimension is MxN.

int arr[M][N]; // given array.
int temp[M][N];

for (i=0;i<M;i++){
for(j=0;j<N;j++){
if(temp[i][j] == 0){
fill(temp,i,j);
}
}
}

here is fill() function.
int fill(int temp[][], int i, int j){
if(i<0 || j< 0 || i>=M || j>=N)
return 0;

if(temp[i][j] != 0)
return temp[i][j];

int left=0,right=0,up=0,down=0;
if(arr[i-1][j] = arr[i][j] +1)
up = fill(temp,i-1,j);
if(arr[i+1][j] = arr[i][j] +1)
down = fill(temp,i+1,j);
if(arr[i][j-1] = arr[i][j-1] +1)
left = fill(temp,i,j-1);
if(arr[i][j+1] = arr[i][j+1] +1)
right = fill(temp,i,j+1);

temp[i][j] = max(up,down,left,right) + 1;
return temp[i][j];
}

thus it will calculate each element of temp array only once.

4. now, find the maximum element in the array. it's value will be the length of LIS.
max_x=0,max_y=0;
for(i=0;i<M;i++){
for(j=0;j<N;j++){
if(temp[i][j] > temp[max_x][max_y]){
max_x = i;
max_y = j;
}
}
}

5. Above will give the length of LIS. now, to find the LIS, we will check it's neighbours whose LIS value difference is 1.

i=max_x, j= max_y ;
printf("%d ",temp[i][j]);
while(temp[i][j] != 1){
if(temp[i-1][j] == temp[i][j] -1){
i = i-1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i+1][j] == temp[i][j] -1){
i = i+1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j-1] == temp[i][j] -1){
j = j-1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j+1] == temp[i][j] -1){
j = j+1;
printf("%d ",temp[i][j]);
continue;
}

}


time complexity is: O(M.N)


相关题目：Longest Increasing Sequence 2D matrix（除了上下左右，对角线也要考虑）


int original[m][n] = {...};
int longest[m][n] = {0};

int find() {
    int max = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int current = findfor(i, j);
            if (current > max) { max = current; }
        }
    }
    return max;
}

int findfor(int i, int j) {
    if (longest[i][j] == 0) {
        int max = 0;
        for (int k = -1; k <= 1; k++) {
            for (int l = -1; l <= 1; l++) {
                if (!(k == 0 && l == 0) &&
                    i + k >= 0 && i + k < m &&
                    j + l >= 0 && j + l < n &&
                    original[i + k][j + l] > original[i][j]
                   )
                    int current = findfor(i + k, j + l);
                    if (current > max) { max = current; }
            }
        }
       
        longest[i][j] = max + 1;
    }
    return longest[i][j];
}