Microsoft Word - evaeva.docx

Transcription

1 关于本面经与代码合集 原文为 evaeva 网友发表于 mitbbs, 原文一共有 7 个 doc 文档, 应该是对 mitbbs jobhutting 版截至 之前面经的大合集, 这里转化成 pdf, 主要是方便查询 还有一个部分是 mitbbs59 网友整理于 的大合集 本人的一些经验 : 1. <Computer Systems: A Programmer's Perspective> 是一本非常好的 computer science 入门的教科书, 网上可以找到第一版的 djvu 版本 2. 本人强烈否定推荐 <Introduction to Algorithms>, 网上可 以找到第二版的 chm 版本, 原因很简单, 对于面试准备, 不实用 这是一本非常好的 Algorithms 经典教程,mit ocw 也有大牛上课时的视频 3. & 简单明了的 tutorial 教程 ; labs.com/cm/cs/pearls/ 老一代的程序员基本都读过这本书, 网上只有第 一版的 djvu 版本. 4. Algorithm Design, 对于象 Google, Facebook 这样的公司, 会涉及很多这样的问题, 网上可以找到的教科书, 主要是 <Algorithm Design> Cornell University 2006 版本, <Introduction to the design and analysis of algorithms> Levitin 中文翻译第二版, <Algorithms> Berkeley 2006 版本, 这个有 free 的 copy OOD,Amazon 这样的公司非常喜欢问这类问题, 可能对面试准备有用的书是,<design pattern> <code complete> etc 6. 最后就是面经了,mitbbs jobhutting, <Programming Interview Exposed> <Careercup 150 问 > <ihas1337code.com> <geeksforgeeks.org> <sureinterview.com> < 编程之美 > < 程序员面试宝典 > < 何海涛面试题精选 > etc

2 Heap sort: #include "stdafx.h" #include <iostream> #include <fstream> #include <iomanip> using namespace std; void HeapSort(int num[],int size); void BuildHeap(int num[],int size); void PercolateDown(int num[], int index,int size); void PrintHeap(const char* strmsg,int array[],int nlength); void Swap(int num[], int v, int u); int main(int argc, char *argv[]) int data[13]=8,5,4,6,13,7,1,9,12,11,3,10,2; HeapSort(data,13); system("pause"); return 0; void HeapSort(int num[],int size) int i; int ilength=size; PrintHeap("Befor Sort:",num,iLength); BuildHeap(num,size);// 建立小顶堆 for (i = ilength - 1; i >= 1; i--) Swap(num, 0, i);// 交换 size--;// 每交换一次让规模减少一次 PercolateDown(num, 0,size);// 将新的首元素下滤操作 PrintHeap("Sort Heap:",num,iLength);

3 // 建堆方法, 只需线性时间建好 void BuildHeap(int num[],int size) int i; for (i = size / 2-1; i >= 0; i--) // 对前一半的节点 ( 解释为 从最后一个非叶子节点开始, 将每个父节点都调整为最小堆 更合理一些 ) PercolateDown(num, i,size);// 进行下滤操作 PrintHeap("Build heap:",num,size); // 对该数进行下滤操作, 直到该数比左右节点都小就停止下滤 void PercolateDown(int num[], int index,int size) int min;// 设置最小指向下标 while (index * 2 + 1<size) // 如果该数有左节点, 则假设左节点最小 min = index * 2 + 1;// 获取左节点的下标 if (index * 2 + 2<size) // 如果该数还有右节点 if (num[min] > num[index * 2 + 2]) // 就和左节点分出最小者 min = index * 2 + 2;// 此时右节点更小, 则更新 min 的指向下标 if (num[index] < num[min]) // 如果 index 最小, break;// 停止下滤操作 else Swap(num, index, min);// 交换两个数, 让大数往下沉 index = min;// 更新 index 的指向 // while

4 // 给定数组交换两个数的位置 void Swap(int num[], int v, int u) int temp = num[v]; num[v] = num[u]; num[u] = temp; void PrintHeap(const char* strmsg,int array[],int nlength) int i; printf("%s",strmsg); for(i=0;i<nlength;i++) printf("%d ",array[i]); printf("\n"); Quicksort: #include "stdafx.h" #include <iostream> #include <fstream> #include <iomanip> using namespace std; void Swap(int num[], int v, int u); void qsort(int num[],int left, int right); int main(int argc, char *argv[]) int data[13]=8,5,4,6,13,7,1,9,12,11,3,10,2; for(int i=0;i<13;i++) cout<<data[i]<<"---"; qsort(data,0,12); for(int i=0;i<13;i++) cout<<data[i]<<"---";

5 return 0; void qsort(int num[],int l, int r) int pivot=(l+r)/2; int left=l; int right=r; Swap(num,pivot,left); while( left<=right) while(num[left]<=num[l]) left++; while(num[right]>=num[l]) right--; if(left<right) Swap(num,left,right); left++;right--; Swap(num,--left,l); if(l<left-1) qsort(num,l,left-1); if(left+1<r) qsort(num,left+1,r); Bubble Sort #include "stdafx.h" #include <iostream> #include <fstream> #include <iomanip> using namespace std; void Swap(int num[], int v, int u); void qsort(int num[],int l); int main(int argc, char *argv[]) int data[13]=8,5,4,6,13,7,1,9,12,11,3,10,2; int l=sizeof(data)/sizeof(int); for(int i=0;i<13;i++) cout<<data[i]<<"---"; cout<<endl; qsort(data,l); for(int i=0;i<13;i++) cout<<data[i]<<"---"; return 0;

6 void qsort(int* num,int l) for (int i=0;i<l;i++) for( int j=i;j<l;j++) if (num[i]>num[j]) Swap(num,i,j); void Swap(int num[], int v, int u) int temp; temp=num[v];; num[v]=num[u]; num[u]=temp; BST: #include "stdafx.h" #include <iostream> #include <list> #include <algorithm> //#include <cstdlib> using namespace std; class BinarySearchTree private: struct tree_node tree_node* left; tree_node* right; int data; ; tree_node* root; public: BinarySearchTree() root = NULL; ; bool isempty() const return root==null; void print_inorder(); void inorder(tree_node*); void print_preorder(); void preorder(tree_node*); void print_postorder(); void postorder(tree_node*); void insert(int); void remove(int);

7 // Smaller elements go left // larger elements go right void BinarySearchTree::insert(int d) tree_node* t = new tree_node; tree_node* parent; t->data = d; t->left = NULL; t->right = NULL; parent = NULL; // is this a new tree? if(isempty()) root = t; else //Note: ALL insertions are as leaf nodes tree_node* curr; curr = root; // Find the Node's parent while(curr) parent = curr; if(t->data > curr->data) curr = curr->right; else curr = curr->left; if(t->data < parent->data) parent->left = t; else parent->right = t; void BinarySearchTree::remove(int d) //Locate the element bool found = false; if(isempty()) cout<<" This Tree is empty! "<<endl; return; tree_node* curr; tree_node* parent; curr = root; while(curr!= NULL) if(curr->data == d) found = true; break; else parent = curr; if(d>curr->data) curr = curr->right; else curr = curr->left;

8 if(!found) cout<<" Data not found! "<<endl; return; if((curr->left == NULL && curr->right!= NULL) (curr->left!= NULL && curr->right == NULL)) if(curr->left == NULL && curr->right!= NULL) if(parent->left == curr) parent->left = curr->right; delete curr; else parent->right = curr->right; delete curr; else // left child present, no right child if(parent->left == curr) parent->left = curr->left; delete curr; else parent->right = curr->left; delete curr; return; //We're looking at a leaf node if( curr->left == NULL && curr->right == NULL) if(parent->left == curr) parent->left = NULL; else parent->right = NULL; delete curr; return; //Node with 2 children // replace node with smallest value in right subtree if (curr->left!= NULL && curr->right!= NULL) tree_node* chkr; chkr = curr->right; if((chkr->left == NULL) && (chkr->right == NULL))

9 curr = chkr; delete chkr; curr->right = NULL; else // right child has children //if the node's right child has a left child // Move all the way down left to locate smallest element if((curr->right)->left!= NULL) tree_node* lcurr; tree_node* lcurrp; lcurrp = curr->right; lcurr = (curr->right)->left; while(lcurr->left!= NULL) lcurrp = lcurr; lcurr = lcurr->left; curr->data = lcurr->data; delete lcurr; lcurrp->left = NULL; else tree_node* tmp; tmp = curr->right; curr->data = tmp->data; curr->right = tmp->right; delete tmp; return; void BinarySearchTree::print_inorder() inorder(root); void BinarySearchTree::inorder(tree_node* p) if(p!= NULL) if(p->left) inorder(p->left); cout<<" "<<p->data<<" "; if(p->right) inorder(p->right); else return; void BinarySearchTree::print_preorder() preorder(root);

10 void BinarySearchTree::preorder(tree_node* p) if(p!= NULL) cout<<" "<<p->data<<" "; if(p->left) preorder(p->left); if(p->right) preorder(p->right); else return; void BinarySearchTree::print_postorder() postorder(root); void BinarySearchTree::postorder(tree_node* p) if(p!= NULL) if(p->left) postorder(p->left); if(p->right) postorder(p->right); cout<<" "<<p->data<<" "; else return; int main() BinarySearchTree b; int ch,tmp,tmp1; while(1) cout<<endl<<endl; cout<<" Binary Search Tree Operations "<<endl; cout<<" "<<endl; cout<<" 1. Insertion/Creation "<<endl; cout<<" 2. In-Order Traversal "<<endl; cout<<" 3. Pre-Order Traversal "<<endl; cout<<" 4. Post-Order Traversal "<<endl; cout<<" 5. Removal "<<endl; cout<<" 6. Exit "<<endl; cout<<" Enter your choice : "; cin>>ch; switch(ch) case 1 : cout<<" Enter Number to be inserted : "; cin>>tmp; b.insert(tmp); break; case 2 : cout<<endl; cout<<" In-Order Traversal "<<endl; cout<<" "<<endl; b.print_inorder(); break; case 3 : cout<<endl; cout<<" Pre-Order Traversal "<<endl; cout<<" "<<endl;

11 b.print_preorder(); break; case 4 : cout<<endl; cout<<" Post-Order Traversal "<<endl; cout<<" "<<endl; b.print_postorder(); break; case 5 : cout<<" Enter data to be deleted : "; cin>>tmp1; b.remove(tmp1); break; case 6 : return 0; Print all subsets: #include "stdafx.h" #include <vector> using namespace std; void PrintSubsetsInt(const vector<int> &set, int pos, int len, int start, vector<int> &output) if (len == 0) for (int i = 0; i < output.size(); ++i) printf("%d ", output[i]); printf("\r\n"); return; for (int i = start; i < set.size(); ++i) output[pos] = set[i]; PrintSubsetsInt(set, pos + 1, len - 1, i + 1, output); void PrintAllSubsets(const vector<int> &set) for (int i = 0; i < set.size(); ++i) vector<int> output(i); PrintSubsetsInt(set, 0, i, 0, output); int _tmain(int argc, _TCHAR* argv[]) vector<int> x(8);

12 for (int i = 0; i < x.size(); i++) x[i] = i; PrintAllSubsets(x); return 0; //////////////////////////////////////////////////////////////////////////////////////// #include "stdafx.h" #include <iostream> using namespace std; void Swap(char n[], int begin, int end) char temp; while( begin<end) temp=n[begin]; n[begin]=n[end]; n[end]=temp; begin++; end--; void Reverse(char s[]) int start=0; int end=0; int length=strlen(s); Swap(s,start,length-1); while(end<length) if (s[end]!=' ') start=end; while( end<length && s[end]!=' ') end++; Swap(s,start,--end); end++; void main() char s[]="c# strings are almost identical to Java strings"; Reverse(s); cout<<s<<endl; /////////////////////////////////////////////////// #include "stdafx.h"

13 #include <iostream> using namespace std; void atoi(char* s) int start=0; bool isneg=false; int n=0; if(s[start]=='-') isneg=true; start++; while(s[start]) int m=s[start++]-'0'; n=10*n+m; if(isneg) n=0-n; cout<<n<<endl; void main() char* s="-12345"; atoi(s); ///////////////////////////////////////////Binary seearch #include "stdafx.h" #include <string> #include <iostream> #include <vector> using namespace std; void bs(int* n,int s,int end, int i) if(s>=end) cout<<"not found"; return; int m=(s+end)/2; if(n[s+m]<i) bs(n,s+m+1,end,i); else if (n[s+m]>i) bs(n,s,s+m-1,i); else cout<<"find i:"; void main() int n[]=1,2,3,4,5,6,7,8; bs(n,0,sizeof(n)/sizeof(int),10); ////////////////////////////////////////////////String Permutation: #include "stdafx.h" #include <iostream> #include <string> using namespace std; void swap(char* first, char* second) char ch = *second;

14 *second = *first; *first = ch; int permute(char* set, int begin, int end) int i; int range = end - begin; if (range == 1) cout << set << endl; else for(i=0; i<range; i++) swap(&set[begin], &set[begin+i]); permute(set, begin+1, end); swap(&set[begin], &set[begin+i]); return 0; //initial swap //recursion //swap back //Example Implementation -- Up to you on how to use int main() char str[255]; //string cout << "Please enter a string: "; cin.getline(str, 255); //take string permute(str, 0, strlen(str)); //permutate the string return 0; /////////////////////////////////////////////////////////////////////Reverse Bit: unsigned char rev( unsigned char b ) unsigned char result = 0; while (b) result <<= 1; result = b % 2; b >>= 1; return result; void main() cout<< rev('g'); Another: int mirror_bits( int num) int tmp=0; int i=0; int int_size_in_bits=sizeof(int)*8; while(num>(1<<i)) if((1<<i)&num) tmp = 1<<(int_size_in_bits-1-i); i++;

15 return tmp; FAST: unsigned int reversebits(unsigned int x) x = (((x & 0xaaaaaaaa) >> 1) ((x & 0x ) << 1)); x = (((x & 0xcccccccc) >> 2) ((x & 0x ) << 2)); x = (((x & 0xf0f0f0f0) >> 4) ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) ((x & 0x00ff00ff) << 8)); return((x >> 16) (x << 16)); /////////////////////////////////////////////////Rotated Binary: #include "stdafx.h" #include <iostream> #include <string> using namespace std; int rotate(int* n, int s,int e) if(n[s]>=n[e]&&s<e) int m=(s+e)/2; cout<<m<<endl; if( n[m]<n[s]) return rotate(n,s,m); else return rotate(n,m+1,e); else return s; void main() int a[14]=4,5,6,7,8,9,10,11,12,13,14,1,2,3; cout<<rotate(a,0,13); ////////////////////////////// Hashtable setupdictionary(string[] book) Hashtable table = new Hashtable(); foreach (string word in book) if (!table.contains(word)) table.add(word, 0); table[word] = table[word] + 1; int getfrequency(hashtable table, string word) if (table == null or word == null) return 1; if (table.contains(word)) return table[word]; return 0; //////////////////////////////////// public static Character firstnonrepeated( String str ) Hashtable charhash = new Hashtable(); int i, length; Character c; Integer intgr; length = str.length(); // Scan str, building hash table for (i = 0; i < length; i++) c = new Character(str.charAt(i));

16 intgr = (Integer) charhash.get(c); if (intgr == null) charhash.put(c, new Integer(1)); else // Increment count corresponding to c charhash.put(c, new Integer(intgr.intValue() + 1)); // Search hashtable in order of str for (i = 0; i < length; i++) c = new Character(str.charAt(i)); if (((Integer)charHash.get(c)).intValue() == 1) return c; return null; string removechars( string str, string remove ) char[] s = str.tochararray(); char[] r = remove.tochararray(); bool[] flags = new bool[128]; // assumes ASCII! int len = s.length; int src, dst; // Set flags for characters to be removed for( src = 0; src < len; ++src ) flags[r[src]] = true; src = 0; dst = 0; // Now loop through all the characters, // copying only if they aren t flagged while( src < len ) if(!flags[ (int)s[src] ] ) s[dst++] = s[src]; ++src; return new string( s, 0, dst ); void permute( String str ) int length = str.length(); boolean[] used = new boolean[ length ]; StringBuffer out = new StringBuffer(); char[] in = str.tochararray(); dopermute( in, out, used, length, 0 ); void dopermute( char[] in, StringBuffer out, boolean[] used, int length, int level ) if( level == length ) System.out.println( out.tostring() ); return; for( int i = 0; i < length; ++i ) if( used[i] ) continue; out.append( in[i] ); used[i] = true; dopermute( in, out, used, length, level + 1 ); used[i] = false; out.setlength( out.length() - 1 ); void combine( string str ) int length = str.length; char[] instr = str.tochararray(); StringBuilder outstr = new StringBuilder(); docombine( instr, outstr, length, 0, 0 );

17 void docombine( char[] instr, StringBuilder outstr, int length, int level, int start ) for( int i = start; i < length; i++ ) outstr.append( instr[i] ); Console.WriteLine( outstr ); if( i < length - 1 ) docombine( instr, outstr, length, level + 1, i + 1 ); outstr.length = outstr.length - 1; static final int PHONE_NUMBER_LENGTH = 7; void printtelephonewords( int[] phonenum ) char[] result = new char[ PHONE_NUMBER_LENGTH ]; doprinttelephonewords( phonenum, 0, result ); void doprinttelephonewords( int[] phonenum, int curdigit, char[] result ) if( curdigit == PHONE_NUMBER_LENGTH ) System.out.println( new String( result ) ); return; for( int i = 1; i <= 3; i++ ) result[ curdigit ] = getcharkey( phonenum[curdigit], i ); doprinttelephonewords( phonenum, curdigit + 1, result ); if( phonenum[curdigit] == 0 phonenum[curdigit] == 1) return; static final int PHONE_NUMBER_LENGTH = 7; void printtelephonewords( int phonenum[] ) char[] result = new char[ PHONE_NUMBER_LENGTH ]; int i; /* Initialize the result (in our example, * put GWP1WAR in result). */ for( i = 0; i < PHONE_NUMBER_LENGTH; i++ ) result[i] = getcharkey( phonenum[i], 1 ); /* Main loop begins */ while( true ) for( i = 0; i < PHONE_NUMBER_LENGTH; ++i ) System.out.print( result[i] ); System.out.print( \n ); /* Start at the end and try to increment from right * to left. */ for( i = PHONE_NUMBER_LENGTH - 1; i >= -1; i-- ) /* You re done because you * tried to carry the leftmost digit. */ if( i == -1 ) return; /* Otherwise, we re not done and must continue. */ /* You want to start with this condition so that you can * deal with the special cases, 0 and 1 right away. */ if( getcharkey( phonenum[i], 3 ) == result[i] phonenum[i] == 0 phonenum[i] == 1 ) result[i] = getcharkey( phonenum[i], 1 ); /* No break, so loop continues to next digit */ else if ( getcharkey( phonenum[i], 1 ) == result[i] ) result[i] = getcharkey( phonenum[i], 2 ); break; else if ( getcharkey( phonenum[i], 2 ) == result[i] ) result[i] = getcharkey( phonenum[i], 3 );

18 break; boolean overlap( Rect a, Rect b) return( a.ul.x <= b.lr.x && a.ul.y >= b.lr.y && a.lr.x >= b.ul.x && a.lr.y <= b.ul.y ); To ensure that you didn t make a mistake, it s a good idea to verify that these conditions make sense. The preceding function determines that two rectangles overlap if A s left edge is to the left of B s right edge and A s upper edge is above B s bottom edge and A s right edge is to the right of B s left edge and A s bottom edge is below B s upper edge. bool endianness() int testnum; char *ptr; testnum = 1; ptr = (char *) &testnum; return (*ptr); /* Returns the byte at the lowest address */ bool endianness() union int theinteger; char singlebyte; endiantest; endiantest.theinteger = 1; return endiantest.singlebyte; int numonesinbinary( int number ) int numones = 0; while( number!= 0 ) if( ( number & 1 ) == 1 ) numones++; number = number >>> 1; return numones; int numonesinbinary( int number ) int numones = 0; while( number!= 0 ) number = number & (number 1); numones++; return numones; 情形一 : 如果栈不空并且当前将要入栈的柱子比栈顶的柱子低, 则有 : 1. 栈顶柱子的右边界完全确定, 其对应的局部最大矩形面积可求 ( 下面说明了左边界在它入栈时已确定 ) 更新全局最大矩形面积后, 栈顶柱子可以依次出栈, 直到当前的栈顶柱子比当前要入栈的柱子低或者栈变为空栈 2. 连续的出栈操作使得当前的栈顶柱子比当前要入栈的柱子低或者栈变为空栈, 这时候, 当前要入栈的柱子的左边界也确定, 可以入栈 情形二 : 如果栈为空或者当前要入栈的柱子比栈顶柱子高, 则无出栈操作, 且当前要入栈的柱子的左边界确定 总结 :

19 1. 每个入栈操作, 如果入栈柱子低于栈顶柱子, 则它确定了栈中比要入栈柱子高的那些柱子的右边界, 可以对它们执行出栈操作 出栈的过程伴随着矩形面积的计算 2. 每个入栈操作, 不论是否引起出栈操作, 我们都可以确定当前要入栈柱子的左边界 3. 每次入栈后, 栈内所剩柱子一定保持高度单调非递减的顺序 4. 可令最后一根柱子高度为 -1, 保证必有出栈操作 5. 除了高度为 -1 的哑元柱子, 所有的柱子都入栈一次, 出栈一次, 复杂度为 O(n) 6. 对高度相同的两根柱子, 我们可视后面的柱子比前面的柱子高 struct HistElem int index; // Index of the element, 0, 1, 2,... int height; // Height of the element int far_length_left; // How far can we extend to the left boundary ; // The last element of the histogram is set to the dummy value -1 // This can be used to indicate that we have reached the right boundary int HistogramMaxRect(int Hist[], int n) if (n < 1 Hist[n-1]!= -1) printf("incorrect input.\n"); return -1; int S = 0; struct HistElem Stack[MAX_SIZE]; int top = -1; for (int i = 0; i < n; i++) // Look backward for elements available for rectangle area calculation while (top!= -1 && Hist[i] < Stack[top].height) int area = Stack[top].height * (Stack[top].far_length_left + (i - Stack[top].index)); if (area > S) S = area; // We can pop up these elements now top--; // Find far_length_left for current element int far_length_left = i; if (top!= -1) far_length_left = i - Stack[top].index - 1; // Push current element into the stack top++; if (top == MAX_SIZE) printf("stack overflow.\n"); return -1;

20 Stack[top].index = i; Stack[top].height = Hist[i]; Stack[top].far_length_left = far_length_left; return S; int main() // May change to other test cases int Hist[] = 5, 13, 10, 0, 7, 7, 8, -1; int S = HistogramMaxRect(Hist, 8); printf("the largest size is %d\n", S); return 0; struct HistElem int index; int leftwidth; ; int MaxRect(int * H, int n) struct HistElem Stack[MAX_SIZE]; int top=-1; int area,maxarea=0; for(int pos=0;pos<n;pos++) while(top!=-1 && H[pos]<H[Stack[top].index] area=h[stack[top].index]*(stack[top].leftwidth+pos-stack[top].index); if(area>maxarea) maxarea=area; top--; int leftwidth=0; if(top!=-1 && H[pos]>=H[Stack[top].index]) leftwidth=pos-stack[top].index-1; top++; Stack[top].leftWidth=leftWidth; Stack[top].index=pos; while(top!=-1) area=h[stack[top].index]*(stack[top].leftwidth+n-stack[top].index); if(area>maxarea) maxarea=area; top--; return maxarea;

21 void itoa(int n, char s[]) int i, sign; if ((sign = n) < 0) /* record sign */ n = -n; /* make n positive */ i = 0; do /* generate digits in reverse order */ s[i++] = n % 10 + '0'; /* get next digit */ while ((n /= 10) > 0); /* delete it */ if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); /* trim: remove trailing blanks, tabs, newlines */ int trim(char s[]) int n; for (n = strlen(s)-1; n >= 0; n--) if (s[n]!= ' ' && s[n]!= '\t' && s[n]!= '\n') break; s[n+1] = '\0'; return n; /* strindex: return index of t in s, -1 if none */ int strindex(char s[], char t[]) int i, j, k; for (i = 0; s[i]!= '\0'; i++) for (j=i, k=0; t[k]!='\0' && s[j]==t[k]; j++, k++); if (k > 0 && t[k] == '\0') return i; return -1; #include <ctype.h> /* atof: convert string s to double */ double atof(char s[]) double val, power; int i, sign; for (i = 0; isspace(s[i]); i++) /* skip white space */ ; sign = (s[i] == '-')? -1 : 1; if (s[i] == '+' s[i] == '-') i++; for (val = 0.0; isdigit(s[i]); i++) val = 10.0 * val + (s[i] - '0'); if (s[i] == '.') i++; for (power = 1.0; isdigit(s[i]); i++) val = 10.0 * val + (s[i] - '0'); power *= 10; return sign * val / power; /* qsort: sort v[left]...v[right] into increasing order */

22 void qsort(int v[], int left, int right) int i, last; void swap(int v[], int i, int j); if (left >= right) /* do nothing if array contains */ return; /* fewer than two elements */ swap(v, left, (left + right)/2); /* move partition elem */ last = left; /* to v[0] */ for (i = left + 1; i <= right; i++) /* partition */ if (v[i] < v[left]) swap(v, ++last, i); swap(v, left, last); /* restore partition elem */ qsort(v, left, last-1); qsort(v, last+1, right); /* strcpy: copy t to s; pointer version 2 */ void strcpy(char *s, char *t) while ((*s++ = *t++)!= '\0') ; /* strcmp: return <0 if s<t, 0 if s==t, >0 if s>t */ int strcmp(char *s, char *t) for ( ; *s == *t; s++, t++) if (*s == '\0') return 0; return *s - *t; #include <stdio.h> /* cat: concatenate files, version 1 */ main(int argc, char *argv[]) FILE *fp; void filecopy(file *, FILE *) if (argc == 1) /* no args; copy standard input */ filecopy(stdin, stdout); else while(--argc > 0) if ((fp = fopen(*++argv, "r")) == NULL) printf("cat: can't open %s\n, *argv); return 1; else filecopy(fp, stdout); fclose(fp); return 0; /* filecopy: copy file ifp to file ofp */ void filecopy(file *ifp, FILE *ofp) int c; while ((c = getc(ifp))!= EOF) putc(c, ofp); /* fgets: get at most n chars from iop */

23 char *fgets(char *s, int n, FILE *iop) register int c; register char *cs; cs = s; while (--n > 0 && (c = getc(iop))!= EOF) if ((*cs++ = c) == '\n') break; *cs = '\0'; return (c == EOF && cs == s)? NULL : s; /* fputs: put string s on file iop */ int fputs(char *s, FILE *iop) int c; while (c = *s++) putc(c, iop); return ferror(iop)? EOF : 0; #include "syscalls.h" main() /* copy input to output */ char buf[bufsiz]; int n; while ((n = read(0, buf, BUFSIZ)) > 0) write(1, buf, n); return 0; #include <stdio.h> #include <fcntl.h> #include "syscalls.h" #define PERMS 0666 /* RW for owner, group, others */ void error(char *,...); /* cp: copy f1 to f2 */ main(int argc, char *argv[]) int f1, f2, n; char buf[bufsiz]; if (argc!= 3) error("usage: cp from to"); if ((f1 = open(argv[1], O_RDONLY, 0)) == -1) error("cp: can't open %s", argv[1]); if ((f2 = creat(argv[2], PERMS)) == -1) error("cp: can't create %s, mode %03o", argv[2], PERMS); while ((n = read(f1, buf, BUFSIZ)) > 0) if (write(f2, buf, n)!= n) error("cp: write error on file %s", argv[2]); return 0; #include "syscalls.h" /*get: read n bytes from position pos */ int get(int fd, long pos, char *buf, int n) if (lseek(fd, pos, 0) >= 0) /* get to pos */ return read(fd, buf, n); else

24 return -1; template<class T> class priqueue private: int n, maxsize; T *x; void swap(int i, int j) T t = x[i]; x[i] = x[j]; x[j] = t; public: priqueue(int m) maxsize = m; x = new T[maxsize+1]; n = 0; void insert(t t) int i, p; x[++n] = t; for (i = n; i > 1 && x[p=i/2] > x[i]; i = p) swap(p, i); T extractmin() int i, c; T t = x[1]; x[1] = x[n--]; for (i = 1; (c = 2*i) <= n; i = c) if (c+1 <= n && x[c+1] < x[c]) c++; if (x[i] <= x[c]) break; swap(c, i); return t;; Longest duplicate string: while (ch = getchar())!= EOF a[n] = &c[n] c[n++] = ch c[n] = 0 qsort(a, n, sizeof(char *), pstrcmp) for i = [0, n) if comlen(a[i], a[i+1]) > maxlen maxlen = comlen(a[i], a[i+1]) maxi = i printf("%.*s\n", maxlen, a[maxi]); Strategy Pattern: public abstract class Duck

25 FlyBehavior flybehavior; QuackBehavior quackbehavior; public Duck() public abstract void display(); public void performfly() flybehavior.fly(); public void performquack() quackbehavior.quack(); public void swim() System.out.println( All ducks float, even decoys! ); public interface FlyBehavior public void fly(); public class FlyWithWings implements FlyBehavior public void fly() System.out.println( I m flying!! ); public class FlyNoWay implements FlyBehavior public void fly() System.out.println( I can t fly ); public interface QuackBehavior public void quack(); public class Quack implements QuackBehavior public void quack() System.out.println( Quack ); public class MuteQuack implements QuackBehavior public void quack() System.out.println( << Silence >> ); public class Squeak implements QuackBehavior public void quack() System.out.println( Squeak ); Observer public interface Subject

26 public void registerobserver(observer o); public void removeobserver(observer o); public void notifyobservers(); public interface Observer public void update(float temp, float humidity, float pressure); public interface DisplayElement public void display(); public class WeatherData implements Subject private ArrayList observers; private float temperature; private float humidity; private float pressure; public WeatherData() observers = new ArrayList(); public void registerobserver(observer o) observers.add(o); public void removeobserver(observer o) int i = observers.indexof(o); if (i >= 0) observers.remove(i); public void notifyobservers() for (int i = 0; i < observers.size(); i++) Observer observer = (Observer)observers.get(i); observer.update(temperature, humidity, pressure); public void measurementschanged() notifyobservers(); public void setmeasurements(float temperature, float humidity, float pressure) this.temperature = temperature; this.humidity = humidity; this.pressure = pressure; measurementschanged(); // other WeatherData methods here public class WeatherStation public static void main(string[] args) WeatherData weatherdata = new WeatherData(); CurrentConditionsDisplay currentdisplay = new CurrentConditionsDisplay(weatherData);

27 StatisticsDisplay statisticsdisplay = new StatisticsDisplay(weatherData); ForecastDisplay forecastdisplay = new ForecastDisplay(weatherData); weatherdata.setmeasurements(80, 65, 30.4f); weatherdata.setmeasurements(82, 70, 29.2f); weatherdata.setmeasurements(78, 90, 29.2f); Factory: public interface PizzaIngredientFactory public Dough createdough(); public Sauce createsauce(); public Cheese createcheese(); public Veggies[] createveggies(); public Pepperoni createpepperoni(); public Clams createclam(); public class NYPizzaIngredientFactory implements PizzaIngredientFactory public Dough createdough() return new ThinCrustDough(); public Sauce createsauce() return new MarinaraSauce(); public Cheese createcheese() return new ReggianoCheese(); public Veggies[] createveggies() Veggies veggies[] = new Garlic(), new Onion(), new Mushroom(), new RedPepper() ; return veggies; public Pepperoni createpepperoni() return new SlicedPepperoni(); public Clams createclam() return new FreshClams(); public abstract class Pizza String name; Dough dough; Sauce sauce; Veggies veggies[]; Cheese cheese; Pepperoni pepperoni; Clams clam; abstract void prepare(); void bake()

28 System.out.println( Bake for 25 minutes at 350 ); void cut() System.out.println( Cutting the pizza into diagonal slices ); void box() System.out.println( Place pizza in official PizzaStore box ); void setname(string name) this.name = name; String getname() return name; public String tostring() // code to print pizza here public class ClamPizza extends Pizza PizzaIngredientFactory ingredientfactory; public ClamPizza(PizzaIngredientFactory ingredientfactory) this.ingredientfactory = ingredientfactory; void prepare() System.out.println( Preparing + name); dough = ingredientfactory.createdough(); sauce = ingredientfactory.createsauce(); cheese = ingredientfactory.createcheese(); clam = ingredientfactory.createclam(); public class NYPizzaStore extends PizzaStore protected Pizza createpizza(string item) Pizza pizza = null; PizzaIngredientFactory ingredientfactory = new NYPizzaIngredientFactory(); if (item.equals( cheese )) pizza = new CheesePizza(ingredientFactory); pizza.setname( New York Style Cheese Pizza ); else if (item.equals( veggie )) pizza = new VeggiePizza(ingredientFactory); pizza.setname( New York Style Veggie Pizza ); else if (item.equals( clam )) pizza = new ClamPizza(ingredientFactory); pizza.setname( New York Style Clam Pizza ); else if (item.equals( pepperoni )) pizza = new PepperoniPizza(ingredientFactory); pizza.setname( New York Style Pepperoni Pizza );

29 return pizza; ValidIpAddressRegex = "^(([0 9] [1 9][0 9] 1[0 9]2 2[0 4][0 9] 25[0 5])\.)3([0 9] [1 9][0 9] 1[0 9]2 2[0 4][0 9] 25[0 5])$"; ValidHostnameRegex = "^(([a za Z] [a za Z][a za Z0 9\ ]*[a za Z0 9])\.)*([A Za z] [A Za z][a Za z0 9\ ]*[A Za z0 9])$"; [A-Z0-9._%-]+@[A-Z0-9.-]+\.[A-Z]2,4 re = /^\w+([\.-]?\w+)*@\w+([\.- ]?\w+)*\.(\w2 (com net org edu int mil gov arpa biz aero name coop i nfo pro museum))$/ phonere = ^((\+\d1,3(- )?\(?\d\)?(- )?\d1,5) (\(?\d2,6\)?))(- )?(\d3,4)(- )?(\d4)(( x ext)\d1,5)0,1$ 矩阵乘法 for (i=1;i<=n1;i++) for ( j=1; j<=n2; ++j) Q[i][j]=0; for(k=1; k<=n1; ++k) Q[i][j]+=M[i][k]*N[k][j]; procedure STRASSEN(n,A,B,C); begin if n=2 then MATRIX-MULTIPLY(A,B,C) else begin 将矩阵 A 和 B 依 (1) 式分块 ; STRASSEN(n/2,A11,B12-B22,M1); STRASSEN(n/2,A11+A12,B22,M2); STRASSEN(n/2,A21+A22,B11,M3); STRASSEN(n/2,A22,B21-B11,M4); STRASSEN(n/2,A11+A22,B11+B22,M5); STRASSEN(n/2,A12-A22,B21+B22,M6); STRASSEN(n/2,A11-A21,B11+B12,M7); ; end; end; void STRASSEN(int n,float A[][N],float B[][N],float C[][N]) //STRASSEN 函数 ( 递归 )

30 float A11[N][N],A12[N][N],A21[N][N],A22[N][N]; float B11[N][N],B12[N][N],B21[N][N],B22[N][N]; float C11[N][N],C12[N][N],C21[N][N],C22[N][N]; float M1[N][N],M2[N][N],M3[N][N],M4[N][N],M5[N][N],M6[N][N],M7[N][N]; float AA[N][N],BB[N][N],MM1[N][N],MM2[N][N]; int i,j;//,x; if (n==2) MATRIX_MULTIPLY(A,B,C);// 按通常的矩阵乘法计算 C=AB 的子算法 ( 仅做 2 阶 ) else for(i=0;i<n/2;i++) ////////// for(j=0;j<n/2;j++) A11[i][j]=A[i][j]; A12[i][j]=A[i][j+n/2]; A21[i][j]=A[i+n/2][j]; A22[i][j]=A[i+n/2][j+n/2]; B11[i][j]=B[i][j]; B12[i][j]=B[i][j+n/2]; B21[i][j]=B[i+n/2][j]; B22[i][j]=B[i+n/2][j+n/2]; // 将矩阵 A 和 B 式分为四块 MATRIX_SUB(n/2,B12,B22,BB); ////////// STRASSEN(n/2,A11,BB,M1);//M1=A11(B12-B22) MATRIX_ADD(n/2,A11,A12,AA); STRASSEN(n/2,AA,B22,M2);//M2=(A11+A12)B22 MATRIX_ADD(n/2,A21,A22,AA); STRASSEN(n/2,AA,B11,M3);//M3=(A21+A22)B11 MATRIX_SUB(n/2,B21,B11,BB); STRASSEN(n/2,A22,BB,M4);//M4=A22(B21-B11) MATRIX_ADD(n/2,A11,A22,AA); MATRIX_ADD(n/2,B11,B22,BB); STRASSEN(n/2,AA,BB,M5);//M5=(A11+A22)(B11+B22) MATRIX_SUB(n/2,A12,A22,AA); MATRIX_SUB(n/2,B21,B22,BB); STRASSEN(n/2,AA,BB,M6);//M6=(A12-A22)(B21+B22) MATRIX_SUB(n/2,A11,A21,AA); MATRIX_SUB(n/2,B11,B12,BB); STRASSEN(n/2,AA,BB,M7);//M7=(A11-A21)(B11+B12) // 计算 M1,M2,M3,M4,M5,M6,M7( 递归部分 ) MATRIX_ADD(N/2,M5,M4,MM1); //////////// MATRIX_SUB(N/2,M2,M6,MM2); MATRIX_SUB(N/2,MM1,MM2,C11);//C11=M5+M4-M2+M6 MATRIX_ADD(N/2,M1,M2,C12);//C12=M1+M2 MATRIX_ADD(N/2,M3,M4,C21);//C21=M3+M4 MATRIX_ADD(N/2,M5,M1,MM1);

31 MATRIX_ADD(N/2,M3,M7,MM2); MATRIX_SUB(N/2,MM1,MM2,C22);//C22=M5+M1-M3-M7 for(i=0;i<n/2;i++) for(j=0;j<n/2;j++) C[i][j]=C11[i][j]; C[i][j+n/2]=C12[i][j]; C[i+n/2][j]=C21[i][j]; C[i+n/2][j+n/2]=C22[i][j]; // 计算结果送回 C[N][N] json_pretty 就是把一个一行的 json string 转换为容易被人阅读的格式 比如 : 输入 : id :"id-123","woe_id":[123,456,789],"attribute":"title":"a","desc ":"b" 输出 : id :"id-123", "woe_id":[123,456,789], "attribute": "title":"a", "desc":"b" public class JsonNode String nodename; Value nodevalue; public class StringValue extends Value String value; public class NodeValue extends Value JsonNode[] value; 然后分拆的代码 : private JsonNode parsenode(string jsonstring, int startindexinclusive, int endindexexclusive) assert (startindexinclusive >= 0); assert (endindexexclusive > startindexinclusive); assert (endindexinclusive <= jsonstring.length()); // find the first semicolon int sc = jsonstring.indexof(':', startindex); if (sc < 0 sc >= endindex) throw new InvalidFormatException(); String name = jsonstring.substring(startindex, sc); String value = jsonstring.substring(sc + 1, endindex);

32 Value nodevalue = value.startwith("")? new NodeValue(parse(value)) : new StringValue(value); return new JsonNode(name, nodevalue); public JsonNode[] parse(string jsonstring) List<JsonNode> buffer = new ArrayList<JsonNode>(); for (int i = 0; i < jsonstring.length(); i++) char ch = jsonstring.charat(i); boolean switch = (ch == ''); int j = switch? i + 1 : i; for (; j < jsonstring.length(); j++) if (switch && jsonstring.charat(j) == '') jsonstring.charat(j) == ',') break; JsonNode node = parsenode(jsonstring, i, j); buffer.add(node); for (i = j; jsonstring.charat(i)!= ','; i++) ; return buffer.toarray(new JsonNode[buffer.size()]); 打印的代码就好写多了 : public void print(printstream ps, JsonNode[] nodes, int indent) for (int i = 0; i < nodes.length; i++) JsonNode node = nodes[i]; printindent(indent); ps.print(node.getname()); ps.print(":"); if (node.getvalue() instanceof StringValue) ps.print(node.getvalue()); if (i < nodes.length - 1) ps.print(",\n"); else if (node.getvalue() instanceof NodeValue) JsonNode[] value = ((NodeValue)node.getValue()).getValue(); ps.print("\n"); print(ps, value, indent + 4); printindent(indent); ps.print("\n");

33 然后问我给定一个 FaceBook log file,100 billion 行, 每一行记录含 timestamp user_id visited_page, 找到 top 10 最长出现的三连串访问模式 比如 user 先后访问了页面 a,b,a, 那么就形成一个模式 a->b->a 但是记录没有按照 timestamp 排好序! 我的答案是,1)brute force: 对整个文件先对 timestamp 再对 user id 排序, 然后建 hash 表, 读入 log 文件, 对每一个模式计数 2)map-reduce: 将每一个 user id 对应的记录读到单独的机器上 --map, 接着对 timestamp 排序建 hash 表, 这样效率高些, 然后 -- reduce, 将 intermediate 结果对每个模式 key 累加, 计算最后结果 然后因为只需要 top 10, 可以用一个 10 个元素的 min heap 维护当前 top 10 给定 int read(char *buffer, int size) api, 写出 int readline(char * buffer, int size)code 举例说, 输入一个字符串 abcd\nefgh,read(buffer,3) 返回 3, buffer=abc, 同时指针指向字符 "d" read(buffer,7) 返回 7,buffer=abcd\nef, 同时指针指向字符 "g" 返回值是实际读取的字符数 要求 readline(buffer,3) 返回 3, buffer=abc, 同时指针指向字符 "d" readline(buffer,7) 返回 4,buffer=abcd, 同时指针指向字符 "e" 红绿灯 : while (true) setblue(direction1); setred(direction2); sleep(30 * 1000); setred(direction1); setblue(direction2); sleep(30 * 1000); Number of Sum void numberofsum(int sum, vector<int> v, int last) if(sum == 0) for (int i = 0; i < v.size(); i++) cout<<v[i]<<","; cout<<endl; return; for (int i = 1; i <= sum; i++) if(sum - i >= 0 && i >= last)

34 vector<int> temp = v; temp.push_back(i); numberofsum(sum-i,temp,i); void dijkstra(int start) priority_queue<pair<int,int> > queue; pair <int,int> nodotmp; int i, j; for (int i=1; i<=total; i++) distances[i] = MAXINT; father[i] = -1; visit[i] = false; distances[start] = 0; queue.push(pair <int,int> (distances[start], start)); while(!queue.empty()) nodotmp = queue.top(); queue.pop(); i = nodotmp.second; if (!visit[i]) visit[i] = true; for (j = 1; j<=total; j++) if (!visit[j] && graph[i][j] > 0 && distances[i] + graph[i][j] < distances[j]) distances[j] = distances[i] + graph[i][j]; father[j] = i; queue.push(pair <int,int>(-distances[j], j)); void getpath(int end) cout << end << " "; while (father[end]!= -1) cout << father[end] << " "; end = father[end]; cout << endl; int main() int a, b, c; int tedges; memset(graph, 0, sizeof(graph)); cin >> total >> tedges; for (int i=0; i<tedges; i++)

35 cin >> a >> b >> c; graph[a][b] = c; for(int i=1; i<=total; i++) for(int j=1; j<=total; j++) printf("%d ", graph[i][j]); printf("\n"); dijkstra(1); getpath(3); return 0; Moving-window maximum. Input: A long array A[], and a window width w Output: An array B[],B[i] is the maximum value of from A[i] to A[i+w-1] Requirement: find a good optimal to get B[i] I can think of two solutions First solution: if(a[i] =!B[i-1]) B[i] = B[i-1] else B[i] = maxa[i],...a[i+w-1] Second solution(this one is from one of my friend) Use minheap to store w number, each time when a new number A[i] enters, age out the oldest one, and use O(logW) time to get max value of A[i-w+1] to A[i]. O(n) algorithm: public Integer[] getmaxinslidewindow(integer[] A, Integer w) // invalid input if (A == null w <= 0 A.length - w + 1 <= 0) return null; Integer[] B = new Integer[A.length - w + 1]; // auxiliary queue that is sorted in descending order List<Integer> q = new LinkedList<Integer>(); for (int i = 0; i < A.length; i++) // enqueue. Remove those smaller values int data = A[i]; while (!q.isempty() && q.get(q.size() - 1) < data) q.remove(q.size() - 1); q.add(data); if (i < w - 1) continue; // dequeue. If the current number is the maximum. Also remove it // from the queue Integer max = q.get(0); B[i - w + 1] = max;

36 if (A[i - w + 1] == max) q.remove(0); return B; 1. 给定两个整数数组, 找出同时出现在两个数组中的整数 2. 如果不允许 O(n) 的空间, 怎么办? 3. 如果数组太大无法装入内存, 怎么办? 4. 如何测试? 5. 如果一个 web-based 系统中某个网页 crashed, 如何检测 what does class Derived : private Base mean? what does class Derived : protected Base mean? why initialize member variables in initializer list of constructor, rather than body of constructor? discuss different facets of polymorphism in C++ - dynamic, static. Define polymorphism clearly. what are the adapter, builder, command, singleton patterns in C++? what happens when you remove elements from a vector STL container, compare vector before vs after removal. what is the 1 thing you can have in a class declaration that you can never encounter in a union declaration? what are the 4 scenarios where the copy constructor comes into play? what are the 2 main categories of signals in UNIX? difference between re-entrant code vs. thread-safe code? How about async thread-safe? big endian byte order test inside the body of a function mutex vs. semaphore difference? fastest algorithms to find common elements of 2 distinct arrays? Give complexity in big O notation find the smallest K elements in a set of N > K elements, describe complexity of algorithm effect of database index in SQL databases on performance (i.e. insertion/lookups). Bulk loading considerations. describe a good thread pool implementation in C++ (hint: stay away from C idioms to do well on this question), look at Boost's bind class describe functors in C++ nterviewer 1: 写一个函数 validate XML tags ( 类似 parentheses matching). 我用了 stack. 然后测试这个函数 答完之后倒是聊了很多关于这个组的工作 interviewer 2: lunch interview. 我选择 take out, 所以在办公室里边吃边聊 把一个 BFS转成 doubly LL in BFS fashion. 我实现了 BFS traversal 但是发现 pointer relinking很难 结果面试官说他也不确定能否实现 于是我们就把 BFS 都放到一个 array里, 然后 relink pointers. 第二个问题, 有一个洗牌程序, 如何测试是不是真的随机 interviewer 3: Why microsoft? Why SDET? What programs I ve written? What is the most challenging? 说了一些 PhD research. 最后出题 : 设计一个 airplane control syst em. 如何测试

37 interviewr 4, Test Lead: Why microsoft? Why SDET? 让我介绍了一下我简历上的所有 experiences. 问题 : 一个单线程程序 looping over a million records, 一个双线程程序, 每个线程 looping over 500,000 records, respectively. Which one is faster? 在什么情况下那个双线程程序的效率会下降? 问题 : 有一环数字, 每隔一个数字, 划掉一个数字 如此循环, 直到所有数字都划掉 写程序实现, 随便什么数据结构都行 ( 我用了 doubly LL, 先写了程序 然后立刻 debug, 处理了 special cases, such as when there are two numbers left and there is only one number left). interview 5, Dev Lead: 如何测试一个程序? 看不看有关 Software engineer 的杂志 / 周刊? 问题 1: 估计一下一个 map system(such as goog le map) 需要多少存储 他需要实际数字, 所以每一步都要参考实际情况 比如说地球的半径 ( 6400KM), 而后计算表面积 然后, 假设最小单位是 20米乘 20米, 估算这个最小单位显示时为 100X100pixel, 每个 pixel(r/g/b) 占 3bytes, 所以这个最小单位占 30KB, 压缩后大约 1KB... 我算下来大约 1.2PB = 1200TB. 然后再考虑 zoom, 支持多少级 zoom. 不过 zoom out 之后, 空间小很多, 所以总和还是在 1.2PB左右 问题 2: 一个已排序但是有重复的 int array. rotated. 写一个函数, return 原来 index=0现在的位置 比如 4,4,5,6,6,1,1,2,3, 函数 returns 5. 如果数组是 2,2,2,2,2,2,2, 则 return 0. 对于没有重复的情况, 可以实现 logn, 但是现在只能实现 N. 这个 interviewer对 coding非常 picky, 不能有一点 pseudo code, 而且对程序要求很高 ( 那种为追求效率, 宁可牺牲可读性的程度 电面 1: 问了 Java的各种基本概念, Java 里面 int 多大, 怎么知道超过范围了, 链表检测 loop, Java 里面的 linkedlist检测 loop, 然后是一个 brain teaser, 和扔鸡蛋问题差不多 这个没回答上来 电面 2: 三道题目, 都很简单, 第一道是链表中倒数第 n个 node 是什么, 第二道题目是数组中只有一个数字出现了一次, 其他出现两次, 找出那个数字 第三道题目就是设计一个 chess 然后就给 on site了, on site 也不太难 所以感觉运气还不错, 没有网上看到的那些变态题目 具体的顺序忘了, 不过问过如下的题目 : 设计数据库的表储存网上购物时候的 order 给了 n 个线段, 然后知道他们的开始结束的坐标, 返回有多少条线段相交 关键就是写个代码判断两条线段有没有相交 设计 outlook的 calender( 这个由于没怎么用过 outlook, 回答的很烂, 完全不是对方期望的答案 ) 两种方法写斐波那契数列 两种方法写出给定一个字符集合的所有子集 知道 n 个雇员的住址坐标, 然后知道办公地点的坐标, 有一辆班车要接送所有的雇员, 停靠 5 站 优化公交车站点 判断二叉树是否平衡, 怎样维护 ( 这个就没让写代码了 ) 插入一个二叉树节点 worst case 是什么 一个二维数组, 从左到右, 从上到下都是增序, 找出这个二维数组是否包含某个数 吃午饭的时候还被问到有关动态维护前 100 个买的最多的商品的问题, 只不过商品信息不能全部载入内存中 然后每一次交易发生, 都会写一个 entry到 log file 中, 怎么维护 后来又改成有很多服务器储存商品的信息, 怎么维护 1. 两个文件里面存着行程安排, 开始时间以及结束时间, 设计算法找 conflicts 2. How would you find the first unique url among the millions of url available? 3. How to sort an array of only three possible values

38 4. 大数乘法 我是用 linked list 做的 是不是一般都用 array 做? 那位给个简洁的 code. BigInt BigInt::multiply(const BigInt &b) const BigInt answer; BigInt temp; int carry = 0; for (int i = 0; i < b.numdigits; i++) temp.numdigits = this->numdigits + 1; int down = b.digits[i]; for (int j = 0; j <= this->numdigits; j++) int up = (j < this->numdigits)? this->digits[j] : 0; int tempdigit = up * down + carry; temp.digits[j] = tempdigit % 10; carry = tempdigit / 10; temp.shiftdigits(i); temp.zerojustify(); answer = answer.add(temp); return answer; 1 load all schedule to a arraylist/vector, 所有行程按 start time sort ( 根据要求选 sort algrithm O(n)(radix/counting) or O(nlogn) ), 然后从头走一遍 ending time 跟后面的 start time 比较, 如果有 conflict 就做 mark 并且用老的 endtime 跟当前 endtime 比较做更新, 2 harsh 3 dutch national flag 4 这种题看着头晕, 需要细心和耐心 1. 谈一下不同数据结构的优缺点 2. 一个大文本文件里有电话号码 每行至多有一个号码 How do you process and return the total number of phone numbers. (in command line, use grep and wc) 3. A generic tree. how to print out nodes by level (one lever a line) 说了 pseudo code, 要求电面后 给他 4. A database application is slow. How do you investigate the problem and how to improve it. Second 电面 : 1. 写一个函数, 输出一个整数里 1- bit的数目 比如 CountOneBits(7) 应返回 3 2. 网页很慢 找出可能原因 ( 和一面的最后一个问题差不多 ) 3. 下面 statements的区别是什么? 接着问了关于 constructor 的问题 (copy), shallow vs. deep copy. Class A; A a = u; A a(u); A a(); A a;

39 4. What is virtual function and polymorphism? 5. What is reflection? 6. A large time- stamped log files, 怎么找一个时间范围内 logs? (grep) 7. What is the difference between hashing and encryption? Third 电面 ( 口音比较重的老印 不少地方听不明白, 只能不断叫他慢速重复 他人倒是不错, 很客气 ): 1. 谈了一下 phd research 2. 一个文件里一百万个数字 怎样找到最小的 100 个? (Use min-heap of size 100) Ask about complexity (nlogn) 3. 写函数输出 Fibonacci numbers in normal sequence (no loop allowed, use 递归, cannot compute Fibonacci number using F(X) = F(X-1) + F(X- 2)) 我用了两个 static variables. 程序写好念给他听 他运行了一下说 pass. 4. 写函数输出 Fibonacci num bers in reversed sequence, 和上题同样的限制 电话里没有想出来, 总觉得需要一个 stack的数据结构, 才能实现反序输出 他给我 30 分钟让我电话后写了程序 他 最后我还是用了一个辅助的数据结构 他 reply 我, 给了 idea. 实际上还是用两个 static variable. 在 recursion中计算, 在 foo(0) 里面输出 F(X), 然后在 recursion返回中在还原出 F(X-1), F(X- 2). 直到 F(1), F(0). Onsite ( because of NDA, 只能说的抽象一点 ): 组 A的 dev manager: 1. OO design该公司的一个 system, 设计的时候, 使用 patterns. 这个问题初听很难, 所以我就不断地问问题 最后把问题简化到一个可以操作的程度 这样设计起来方便不少 2. 如何在文件里找电话号 ( 他们的确喜欢 grep) Recruiter 组 A的 SDE: 1. 谈 research 2. 给一个 int array, 输出一个随机 permutation. ( 实际上就是 random shuffle) 用了 reservoir sampling. 然后演示了一下 1,2,3 的六种输入可能 3. difference between i++ and ++i 4. what is virtual function? why C++ makes non-virtual default? (speed tradeoff) 组 A的 SDET: 1. 写函数 : given an integer, 判断这个 integer, in binary format, 是不是一个回文结构 2. 一个 binary tree of integers. serialize and then desialize. 非面试组来的面试官 : 1. 谈 research 2. 公司网站上有一个错误的电话号码 怎么找出来 一开始回答得有些不得要领 后来说到要 web crawl一下公司的 domain, 他似乎有兴趣 于是就用 bfs traverse, 用 hash table来防止 infinite loop. 对于每个 page, 自然还是 grep 来找 组 B的 dev manager(lunch interview): 没问任何技术问题 基本在聊天 问我, 什么才是好的程序? 怎么样 comment 程序? 很多时候在说他们组的东西 该公司正在从 C++ 到 java转型 但面试我的人似乎都对 C++ 比较熟悉 至于用什么语言回答问题完全不重要 可能我说自己 C++ 比较熟, 所以他们没有问 java specific 的问题

40 第一次电面, 白人介绍自己的 research c++ questions: interface, abstract class, polymorphism find nth to last node in linked list design card game, extend to a specific game 第二次电面, 印度人, 有一点口音比较变态, 迟到十分钟, 说电话号码搞错了, 上来就说了一堆迟到的理由让我介绍 research 如果我是经理, 有一个大的项目, 怎么把这个大项目分成小项目分给手下人做, 要 high level, 扯软件设计的思想,user case? 我没听说过 Amazon 有一堆数据, 量很大, 要求设计一个系统, 搭建平台, 如何用 machine learning, data mining 建模 面到这儿我觉得被打了个措手不及, 觉得应该挂了,45 分钟到了, 他又出两道题, 一个小时结束题一 : 两个 array 找 common numbers 题二 : 亚麻有一个大的 array 里面是所有书的作者, 给定长度 N, 要求返回随机的 t 个作者, 要求概率相同 follow up, 要求每天返回随机 t 个作者, 而且前一天返回的作者不能出现在后一天的名单中 Phone 1: 1. 提出尽可能多的方法使一个 method 可以返回多个不同 type 的值 2.reverse string 比如 "I have a dream" -> "dream a have I" 3. 判断一个 binary tree 是不是对称的 Phone 2: 1. 给 a list of number, 返回前 top K 个 ( 内存足够怎么做, 内存不够怎么做 ) 2.OOD 电梯 3. 找两个链表的交集 Onsite 6 轮 1 轮 HR 1 轮午餐 4 轮技术 ( 亚马逊网络服务组 ) 签了保密协议, 希望不要被抓到 T_T 1. 设计个电话本可以用那些数据结构我说 suffix tree, 哈希表问了这两种方法的比较, 还考了 suffix tree 的插入, 2. 问 research, OOD 交通灯系统 3. 写函数算一个整数的阶层 n! 又问了 n 很大, 怎么办? 比如 99% 的 n 都在 之间, 怎么提高函数的执行速度 4. 给一个数组和一个数 n, 找出数组中的所有的对和等于 n 的 5. 给手机键盘, 给定某个按键序列比如 1489, 返回这个按键序列生成的所有的正确的单词

41 typedef struct range int begin; int end; Range; Range shortestsubstring(const char* str, int strlen, const char* characters, int charcount) int* needtofind=new int[256]; int* hasfound=new int[256]; for(int i=0;i<256;i++) needtofind[i]=0; hasfound[i]=0; for(int i=0;i<charcount;i++) int index=(int)characters[i]; needtofind[index]++; int count=0; // count is used to judge if the range satisfies the requirement // the criterion is count==charcount int begin=0; int end=-1; int index=0; Range minrange; minrange.begin=-1; minrange.end=-1; int minlength=strlen+1; int length=0; while(end+1<strlen) end++; index=(int)str[end]; if(needtofind[index]>0) hasfound[index]++; if(hasfound[index]<=needtofind[index])

42 count++; while(begin<end) index=(int)str[begin]; if(needtofind[index]==0) begin++; else if(hasfound[index]>needtofind[index]) begin++; hasfound[index]--; else break; // cout<<"begin:"<<begin<<", end:"<<end<<", count:"<<count<<endl; if(count==charcount) length=end-begin+1; if(length<minlength) minlength=length; minrange.begin=begin; minrange.end=end; return minrange; #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <errno.h> #include <string.h> #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <arpa/inet.h> #define MYPORT 1234 #define BACKLOG 5 // the port users will be connecting to // how many pending connections queue will hold

43 #define BUF_SIZE 200 int fd_a[backlog]; int conn_amount; // accepted connection fd // current connection amount void showclient() int i; printf("client amount: %d\n", conn_amount); for (i = 0; i < BACKLOG; i++) printf("[%d]:%d ", i, fd_a[i]); printf("\n\n"); int main(void) int sock_fd, new_fd; // listen on sock_fd, new connection on new_fd struct sockaddr_in server_addr; // server address information struct sockaddr_in client_addr; // connector's address information socklen_t sin_size; int yes = 1; char buf[buf_size]; int ret; int i; if ((sock_fd = socket(af_inet, SOCK_STREAM, 0)) == -1) perror("socket"); exit(1); if (setsockopt(sock_fd, SOL_SOCKET, SO_REUSEADDR, &yes, sizeof(int)) == - 1) perror("setsockopt"); exit(1); P server_addr.sin_family = AF_INET; // host byte order server_addr.sin_port = htons(myport); // short, network byte order server_addr.sin_addr.s_addr = INADDR_ANY; // automatically fill with my I memset(server_addr.sin_zero, '\0', sizeof(server_addr.sin_zero)); if (bind(sock_fd, (struct sockaddr *)&server_addr, sizeof(server_addr)) = = -1) perror("bind"); exit(1); if (listen(sock_fd, BACKLOG) == -1) perror("listen"); exit(1); printf("listen port %d\n", MYPORT); fd_set fdsr;

44 int maxsock; struct timeval tv; conn_amount = 0; sin_size = sizeof(client_addr); maxsock = sock_fd; while (1) // initialize file descriptor set FD_ZERO(&fdsr); FD_SET(sock_fd, &fdsr); // timeout setting tv.tv_sec = 30; tv.tv_usec = 0; // add active connection to fd set for (i = 0; i < BACKLOG; i++) if (fd_a[i]!= 0) FD_SET(fd_A[i], &fdsr); ret = select(maxsock + 1, &fdsr, NULL, NULL, &tv); if (ret < 0) perror("select"); break; else if (ret == 0) printf("timeout\n"); continue; // check every fd in the set for (i = 0; i < conn_amount; i++) if (FD_ISSET(fd_A[i], &fdsr)) ret = recv(fd_a[i], buf, sizeof(buf), 0); if (ret <= 0) // client close printf("client[%d] close\n", i); close(fd_a[i]); FD_CLR(fd_A[i], &fdsr); fd_a[i] = 0; else // receive data if (ret < BUF_SIZE) memset(&buf[ret], '\0', 1); printf("client[%d] send:%s\n", i, buf); ze); // check whether a new connection comes if (FD_ISSET(sock_fd, &fdsr)) new_fd = accept(sock_fd, (struct sockaddr *)&client_addr, &sin_si if (new_fd <= 0) perror("accept"); continue;

45 n_port)); // add to fd queue if (conn_amount < BACKLOG) fd_a[conn_amount++] = new_fd; printf("new connection client[%d] %s:%d\n", conn_amount, inet_ntoa(client_addr.sin_addr), ntohs(client_addr.si if (new_fd > maxsock) maxsock = new_fd; else printf("max connections arrive, exit\n"); send(new_fd, "bye", 4, 0); close(new_fd); break; showclient(); // close other connections for (i = 0; i < BACKLOG; i++) if (fd_a[i]!= 0) close(fd_a[i]); exit(0);

46 1. 二叉树中给定一个节点, 查找按照中序遍历顺序它的后继节点, 要求写代码, 并给出复杂度 ; 二叉树中查找中序遍历顺序中的第 k 个节点, 如果每个节点都添加了子树中节点个数这个变量, 如何在插入 删除和旋转时更新这个值 ( 旋转是为了保证 logn 的复杂度而要使二叉树保持平衡 ) 二 C++ 概念题, 包括虚函数 多继承 私有的构造 析构函数 重载的 new 运算符等 ; 以前的 project 问题 ; 开放性问题, 跟网络有关, 包括了分组交换 拥塞控制 流控制 多播等等知识点; 最后问了一个编程题, 跟 quad tree 有关, 不太常见, 但不是很难, 我觉得考查了函数的递归 三 一道编程题, 大意是给定一个类 read1, 它有一个函数 read4096, 每次调用它可以从文件中读取 4K个字节, 同时移动文件指针 4K个位置 ( 若文件中剩余数据不足 4K, 则读取剩下的所有数据 ), 这个函数返回实际读取的字节数, int 型 ; 要求实现另一个类 read2中的一个函数 read, 它有一个参数 int n_byte, 这个函数可以从文件中读取由 n_ byte指定的字节数, 同样返回实际读取的字节数 ; 然后又给出一个函数 reset, 它可以将文件指针重置到起始位置, 要求实现 re ad2中的另一个函数 seek, 有一个参数 int pos, 它可以将缓冲区的指针移动到第 pos 个字节的位置, 返回实际指针移动到的位置 可以在 read2 中添加任意变量来完成这两个函数 这道题也不难, 需要注意代码的一些细节, 比如循环的终止条件 特殊的输入等 第一轮, 问了一下自己觉得最有意思的项目 然后就是 3 个题 : 有一个很大的 Log 文件, 记录了每个用户点击网页的时间, 问怎么找到最常见的 3 连击 ; 有两个很大的文件, 文件里每行都是 string, 问怎么找到重复的 ; 找一个无序数组的第 k 大元素 第二轮, 很多基本的问题, 比如什么是 hash, 怎么处理冲突 ; 然后什么是 encapsulation, 什么是 inode 大多是基本概念 然后问了个程序题, 怎么验证一个数是不是素数 最后考了一个 OOD, 那个电梯的题目 第三轮, 两个进程之间有多少种方式可以互相通讯 ( 尽量说, 不要管效率 ) 然后问了问怎么处理 race condition 接着就是验证一个二叉树是不是 BST 然后问了一个设计题, 题目描述太复杂了 很难复述 然后俺就跟面试官聊啊聊, 后来才发现他想要一个多态的设计 1. 两个圆在什么条件下相交? 2. m*n 的矩阵 in place rotation? 看见阿三我心就凉了半截 年纪大了, 反应慢, 算算术吭哧吭哧, 第一题就捣持了半天 第二题就别提了, 吭哧到最后, 也就是讲了讲这题有什么 corner case, 难点在哪, 说如果换做 n*n 的就简单多了 三男非常满足的在一边幸灾乐祸的从头笑到尾, 把我写的任何一个字, 画的图, 说得任何一句话都恨不得要记下来 后来他让我写个不是 in place 的了事 回来我 google 半天, 也没有找到这道题在任何地方被提起和讨论过 我后来 discussion 的时候问他答案是什么, 他也不说, 就说这不是个 straightforward 的问题, 说我们主要是看你解决问题的思路, 我觉得 you are doing quite well, don't worry about this. 也许是看自己第一个面我, 折磨成那样, 良心发现了安慰一下 白男 : 1. n 个城市之间的距离要把都存下来, 怎么存最省空间? 2. 前序中序重建树 其实这个白男非常拽, 也有点岁数了, 估计 35 超上 但这个说的和写得都让他很满意, 应该是最没问题的一个 最后还剩 10 多分钟, 随便聊了聊 国女 :

47 0. 也许也有个什么 warmup, 我忘了 bit 的 integer, 怎么数里面 1 的个数? followup: 要是多次使用你怎么办? 你不觉得要用空间的太多了吗, 怎么办? 2. p*q 的 matrix, 从左下到右上路径数? followup: 你这个算的会有什么问题? 你怎么解决? followup: matrix 中有障碍呢? ( 其实我没有感觉到时间过的很快, 这个没有 code 完, 她让我说了说算法了事 ) 看到国女我喜极生悲, 简单的 coding 被她揪出来 bug, 不过我不知道她是不是非常 nice 的没有记下 要是她能看到这个帖子, 我很想说声大姐你很漂亮! 三女 : 1. m 长的 array, 长度为 k 的 sliding window, 求每次 slide 一下 window 里的最大值 然后问 test cases. 2. 你对网络了解吗?( 不了解 ) 好吧那多线程呢?( 还行吧 ) 于是问 mutex, semaphore 概念, 出了个多线程的题, 一点一点的深究设计 三女很认真, 虽然跟三男风格大不一样, 几乎不记笔记, 估计全记脑子里了, 但是她非常认真的在纸上画, 试图抓我 bug, 我面对三女当然谨慎了, 没有给她抓到 bug 多线程的设计具体确实不记得了, 最后问到一个地方, 我愣了 20 秒没答上来, 她心满意足的发表结束陈词 : 我们就是想让你能有点东西可以想的, 要是你所有问题都答上来了, 说明我们 interviewer 没有 do a good job. 我觉得她很有诚意, 应该也没有写太多坏话 1. 给一段 C 程序 ( 汗,C 我真没仔细学过 ) 看有什么问题, 具体的忘了, 好像是关于函数里的 char* 出了函数就有问题的事 2. 从 m 长的 array 中随机取里面的 n 个, 怎么做? 数学推导? 好像还有另外一个也是 sampling 啥的, 忘了 3. n-bit 的 integer, 打出所有有 k 个 bit 被 set 的数, 你这个复杂度多少? 怎么提高? 还是不够高, 怎么办? 4. 打印 power set 5. 多线程细节,hashtable 细节 6. 用 Java 写一个 iterator, 满足一些要求, 细节不记得了, 有一点 tricky 7. 给我讲 STL 里的 unique 函数是干什么的, 让实现, 怎么提高效率? 8. 读一个什么文件, 问看那些数据我想到些什么, 然后写程序求最大, 最小,average 之类的 for n = 0 to N - 2 for m = n + 1 to N - 1 swap A(n,m) with A(m,n for each length>1 cycle C of the permutation pick a starting address s in C let D = data at s let x = predecessor of s in the cycle while x s move data from x to successor of x let x = predecessor of x move data from D to successor of s

48 上来就一个问题, 设计一个网上预定飞机票的系统 讨论了 50 分钟左右, 弄的很细, 每个 class 里有啥 variable, 啥 method, 都要说. 比如 Controller class 谁去 call, 怎么用 Controller class. 还有内存怎么寸 ( 不用数据库, 全存 memory 里 ), 用什么数据结构,( 他提出 hashtable), 什么作为 key, 什么作为 value 一开始还好, 后来纠结在一个如何给用户一个指定日期的航班信息, 因为我没有存日期, 最后时间快到了, 他让我把想好的设计发邮件给他... 面完就忽然想出来了, 不过觉得面的一般, 老被烙到处印牵着问今天都周末了还没消息, 准备 move on.. 2. Boston 的一个大公司, 老板转给我的邮件, 发信给老板说招人马上给我安排了电面, 结果发现是 project manager 1 小时左右, 都是算法题一个问 apache 一个什么 log 里面如何找前 10 个频率最高的 ip 然后说如果前 k 个呢 第二题就那啥了, 说从 n 个数里取 m 个随即数, 前后不重复我说了 reject sampling, shuffle algorithm, 提到了 reservior sampling, 他说他没听说过 reservior sampling 然后就悲剧了, 他要我优化 shuffle 那个算法, 说现在是一个连续的整数空间, 要 keep track of the holes, 不要象 shuffle 那样 swap 来 maintain O(n) 的 space 我讲了一个 O(m^2) time 的, 用 LL 存 holes, 还要求被优化, 后来我犯晕了, 他说我想好后给他邮件... 我想了一个下午也没想出来怎么不用 linear data structure 去 maintain 那个 holes list, 发信给他说没想出来, 拜托告诉我 solution, 另外副了之前说的 3 个算法 他给我安排了 2nd 店面, 到现在也没告诉我算法, 还说那个 reservior sampling 不错, 时间 O(n) 小于 O(m^2), 靠, 不废话吗, 害我白想一下午! 八成自己回家发现自称的优化的结果不存在.. 和我专业 (machine learning) 相关的很多问题, 谈得比较细 记得的算法 : given one array, 找出两个数的和为给定的数给一个 string, 求所有的 permutation OOD 设计 graph 类 BST is valid 各种 sort 比较 linkedlist 和 hashmap 的相关细节 graph bfs 还有几个算法题我忘了, 都是经典的 除了个别的刚开始想复杂了, 其他的基本给的经典答案 第三面刚完, 大意了, 没从名字上判断出是老印, 交流是相当有问题 而且一上来态度就和我欠了他钱似的 跟他的面试记录等我休息会儿慢慢补上 就面了一道算法题 Given a stream of integer.given one integer K as the window size, compute the average of the numbers in the latest window. for example, with K=2 output 3.5 以前没见过, 不过还是很快给出啦算法, 计算 accumulated sums, maintain 一个 K+1 size 的

49 circular array to store the latest sums. 这样计算 latest average 的时候就是 constant time 的时间复杂度 老印态度立马好转 ( 之前听不懂他说话, 他就有点冲 ), 说他挺满意的 我以为 pass 了, 结果他让开始写 code, 交流完全不畅, 丫态度变得相当不好了 他只给了 3 分钟就说你写完了吧 解释一下 research 中用过的 machine learning 算法有一个项目中做了一个数据库, 把数据库结构画出来, 解释各个 entity 之间的关系 join 的种类, 区别 sql 用的是哪种 (mysql 之类 ) difference between struct and class features of object oriented design give examples;how did you used OOD in your research give the definition of the classes used in your research project virtual function; pure virtual function; abstract class for base/derived classes, destructor virtual or not virtual, why? constructor virtual or not virtual, why? int a; static int b; what is difference? where do they store? new 产生的对象存在哪里 what is semophore? multi thread 里面你用过哪种 (pthread) pthread 怎么定义 mutex( 写出命令 ) lock and unlock deadlock give the example of deadlock and how to avoid or deal with deadlock/circular wait (answer: 同时 lock 所有需要的资源 ) research 里面的哪个项目用了 multi thread 有没有遇到过 dead lock, 如何解决 multi-threading 定义 how to synchronize how to communication with each other between multi threads. pass by reference, pass by pointer, difference of them void foo (int* p) void foo (int& p) 哪个是 pointer, 哪个是 reference, 在这个 function 里的区别 tell me about all kinds of sort algorithms you know

50 列三个, 讲一下大概怎么实现 ( 写伪代码 ) 有几千个文件, 要按照文件名 sort, 应该用哪种 sort list all the data structure you know 大概讲一下定义 coding: two strings A and B 1.check if A is B's anagram( 忘了怎么拼了, 就是字母相同顺序不同的意思 ) 2. check if all the characters in A appear in B ( 不考虑重复的字母 ) 3. 如果考虑重复的字母, 比如 a 在 A 里面出现两次, 在 B 里也应该出现两次,2 的程序怎么改 hashtable 在 C++ 还是 JAVA 里是定义好的可以直接用? dynamic allocated memory, 最后要怎么处理 (delete) 怎么保证分配的空间一定被 delete 掉? 有什么工具可以检查 ( 老实说不知道 ) memory leak 是什么? 举例说明怎么处理 举出三种 design pattern 来给出代码你的 research project 中用过哪几种为什么用这几种 如果一个 class, 同一个功能在不同的地区有不同的 method, 并且参数类型也不一样怎么办用哪一种 design pattern design pattern 的定义为什么大家要用 design pattern TCP/UDP, 定义, 区别 sliding window IPv4/IPv6 的定义, 区别, 知不知道 IPV4 几个星期前用完了 让设计一个游戏, 楼主我不会玩这个游戏, 就算了改设计了个别的, 忘了... 又想起来一题, 补充一下 : process 和 thread 的定义, 区别 1. 8 瓶水, 一瓶有毒 老鼠喝了毒水第二天会死去 问用几只老鼠能尽快的找到毒水 2 二叉树给两 nodes 找最近公共祖先 3 给 n*m 的字符矩阵 然后给你一个字符串 问是否可以在矩阵中找到他的 track track 是指从其中一个符出发, 可以向四周走, 可以重复, 可以回头 1. Suppose we have a stream of web clicks. Now you need to provide at any time the count of web clicks during the past 1 minute. To be specific, you get informed whenever a web click happens. You need to provide a function " getcount()" such that once called, return the count of clicks during the past 1 minute. The solution will be both constant in time and space.

51 2 N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0 的那一行. 平均 O() 和 WORST CASE O() 是多少? 一个奥运会网页, 上面要显示每个国家拿了几块奖牌, 金牌银牌铜牌各多少块如果拿了新的奖牌, 要更新网页问怎么设计 class 要求写代码 2. 如何设计一个停车场? 停车场里有 n 个车位, 每个车位离入口有个距离, 当一辆新车进来以后, 给他安排最近的车位 3. 写一个程序, 计算给定字符串中单词的数目, 如何测试? 第二个人, 1. 最挑战的 project 2. 设计一个电话本, 如果内存不够, 你用 binary tree 还是 hashtable? ( 我答的 binary search tree, 不知道对否?) 如果想把电话本里面所有的 item 按字母顺序输出, 如何实现 (binary tree 和 hashtable 都要回答 )? 3. 如何寻找文件中所有的电话号码? 有一个 array, 每个元素是一个 string, 给定一个 string s, 查询 s 的 reverse string 是否出现在 array 当中 Phone 1 别的组的老美两个数组求交集 如果已经排好序了, 一个数组很大, 一个很小怎么办 如果数组都很大, 内存放不下, 怎么办 设计扑克牌 扑克牌 shuffle 算法 两个整数, 需要多少步才能把一个数的二进制表达转换到另一个数的二进制表达 ( XOR 后数 1) Phone 2 本组的印裔设计 LRU Cache, 然后讨论多线程访问 Cache 的问题 面完后实现 Cache 发代码给他 Onsite 见了 7 个人, 每个人 45 分钟, 连轴转 上午 10 点半进 building, 下午 4 点出来 Onsite 1 很 Nice 的老美讨论设计 web crawler, coding BFS, 讨论多线程处理 crawler 等 Onsite 2 印裔 OOD 机场 air traffic control system. Onsite 3 听口音像感觉英国人跟经理吃饭,common questions, 说一下你跟 coworker 有 disagreement, 怎么处理 问他问题 Onsite 4 亚裔凶 GG 一个网站, 如果有大量访问, 怎么设计结构 这个问题太开放了, 没有什么经验, 答的不好 给个矩阵, 每个格子是一个字母, 每次可走 8 个方向, 输出 valid word. 假如有个字典可以判断每个 word 是否 valid. 把矩阵看成图, 其实就是个简单的 DFS 当时被上一个问题搞的有点晕, 写了个 iterative 的算法, 比较 Messy 写 recursion 的效果可能好些 要是挂估计就挂在这个人身上了 Onsite 5 印裔还是上一个问题, 怎么进一步优化 ( 字典用 prefix tree 来表示, 一个 Prefix 要是到了叶子节点, 就没必要继续 DFS 下去了 ) coding search on the prefix tree Onsite 6 老美, 也比较 Nice 给电话号码, 打印可能的 words 跟 4 的第二问差不多, 写的 recursion, 意识到那个题如果写 recursion 简洁明了的多 讨论 distribute system 的设计, 考虑 durability 和 availability 的 balance 问题

52 Atoi OVERFLOW 目标 result*10+str[i]-'0'<=max_int 1) result<max_int/10 2) result=max_int/10 && str[i]-'0'<=max_int/10 接下来就说会问一个分析的问题和一个 coding 的题目, 然后问如何在一个无限长的 stream 里面找到前 1000 大的, 因为是非常常见的题目, 就和他说了一下用 min heap, 分析了一下复杂度, 很快就进入 coding 了 min: 问了一道我没有准备过的 coding 题目,simple regular expression match, 可以 match 的符号只有 3 种 : a-z : match a-z. : match any * : repeat 0 - arbitrary times 和没用过 regex 的同学解释一下例如 a*b 可以 match : b, ab, aab, aaaaaaaaaaab b.*b 可以 match : bb, bab, b12345b 我就说我知道 regex 的实现比较复杂, 我没研究过, 就只能用比较笨的方法, 复杂度应该比较高, 他说你先写了看看 函数的 prototype 是 : public static bool IsMatch(char[] str, char[] pattern) 返回是否 match BTW 我是用 C# 写的, 面试的时候觉得比 c++ 好写, 有 foreach 之类的,java 也是一样 ) ## 我用的是最笨的方法, 扫描 pattern, 然后递归的 match 剩下的 str 和剩下的 pattern 由于一开始紧张, 上来就写成了 wildcard 了,, 然后面试官说,, 你这个不对不是 regex, 我一看果然,, 太紧张了, 然后就改了一些 ( 改动不是很大 ), 写的时候那些 error case 都做了判断, 其他的也没有什么特别的, 写的也不是很好看, 后来 40 分钟快到了, 面试官就说一会要开会, 留 5 分钟问他问题, 这个时候我的那个基本写完了, 但是有点小问题 a* 还只能 match 1-n 个 a, 零个的情况没有考虑, 然后他说知道了, 没关系他知道我的算法了 char str[9]; str[8]= \0 ; printpar(4,4,4,str,0); It is very clear that we will have 4 open and 4 close parentheses. The only logic you have to apply is that right parentheses can appear in output string only when there are already more left parentheses present in the output string. The rest of the comments are in-line with the code. void printpar(int l, int r, char *str, int count) if (l < 0 r < l) return; // invalid state if (l == 0 && r == 0) printf( %s\n, str); // found one, so print it else if (l > 0) // try a left paren, if there are some available str[count] = ( ; printpar(l 1, r, str, count + 1); if (r > l) // try a right paren, if there s a matching left str[count] = ) ; printpar(l, r 1, str, count + 1);

53 struct ListOfLists ListOfLists() : next(null), data(null) ListOfLists* next; LLNode* data; ; struct LLNode LLNode(Node* t, LLNode* n) : next(n), tree(t) LLNode* next; Node* tree; ; ListOfLists* TreeLinkedLists(Node* root) ListOfLists * results = new ListOfLists(); traverse(root, results); return results; void traverse(node* root, ListOfLists* results) if (root == NULL) return; // nothing to do results >head = new LLNode(root, results >head); // prepend tree node if (results >next == NULL) // extend results if necessary results >next = new ListOfLists(); traverse(root >left, results >next); traverse(root >right, results >next); The main difference between OSPF and RIP is that RIP only keeps track of the closest router for each destination address, while OSPF keeps track of a complete topological database of all connections in the local network. The OSPF algorithm works as described below. Because of the increase in the population, there is a need of Ipv6 protocol which can provide solution for: 1. Increased address space 2. More efficient routing 3. Reduced management requirement 4. Improved methods to change ISP 5. Better mobility support 6. Multi-homing 7. Security 8. Scoped address: link-local, site-local and global-address space A mask is a bit pattern used to identify the network/subnet address. The IP address consists of two components: the network address and the host address. Chess Game: class PositionPotentialValue /* compares value of potential game position */ bool operator < (const PositionValue& pv); ; class ChessPieceBase virtual void estiationparameter0(); /* used by PositionEstimater in different circumstances */ virtual int estiationparameter1(); virtual bool canbechecked(); virtual bool issupportcastle(); // other rule base properties ; class King : public ChessPieceBase ; class Queen : public ChessPieceBase ; // other chess piece classes class Position // represents chess positions in compact form std::vector<chesspiece*> black; std::vector<chesspiece*> white; ; class PositionEstimater // calculate value of a position static PositionPotentialValue estimate(const Position& p);

54 ; class PositionBacktracker // get next postion for estimation. static Position getnext(position& p); ; class ChessPieceTurn... ; // represents move of a chess piece class PlayerBase virtual ChessPieceTurn getturn(position& p); ; class ComputerPlayer : public PlayerBase // actual implementation void setdifficulty(); PositionEstimater estimater; PositionBackTracker backtracter; ; class HumanPlayer : public PlayerBase...; // actual implementation class ChessFormat...; // include info about timing, etc. class GameManager // keeps track of time, end of the game, etc void processturn(playerbase * player); bool acceptturn(chesspieceturn * turn); Position currentpostion; ChessFormat formant; void setgamelog(char * filepath); ; Card Game: class Card public: enum Suit CLUBS=0x00, SPADES=0x10, HEARTS=0x20, DIAMONDS=0x30 ; Card(Suit s, int r) assert(1<=r && r<=13); card = int(s)+r; virtual ~Card() ; // just in case int rank() const return card & 0x0F; Suit suit() const return Suit(card & 0x30); private: short int card; ; Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen int[] pickmrandomly(int[] array, int m) int[] subset = new int[m]; for(int j = 0; j < m; ++j) index = random(j, array.size() 1); // random number in [j,n] subset[j] = array[index]; array[index] = array[j]; // array[j] is now dead /* potentially unnecessary, depending on how much we can * modify the array */ array[j] = subset[j]; return subset; int rand7() while (1) int num = 5*(rand5() 1) + rand5() 1; if (num < 21) return num % 7; /* Returns NULL, p, q, or the nearest common ancestor */ Tree * common_ancestor(tree * root, Tree * p, Tree * q) // assume p and q are in the tree // will return NULL, p, q, the nearest common ancestor if (root == null) return NULL;

55 if (root == p root == q) return root; left = common_ancestor(root >left, p, q); right = common_ancestor(root >right, p, q); /* p is on one side and q is on the other */ if ((left == p && right == q) (left == q && right == p)) return root; return left? left : right; void findsum(node* head, int sum, int[] buffer, int level) if (*head == NULL) return; int temp = sum; buffer[level] = head >data; /* Look up through the path we ve traversed to see if our path * equals sum */ for (int i = level; i >= 0; i ) temp = temp buffer[i]; if (temp == 0) /* We ve found sum by starting at the current node and * counting upwards until level i *. print(buffer, level, i); findsum(head >left, sum, buffer, left + 1); // traverse left findsum(head >right, sum, buffer, left + 1); // traverse right void print(int* buf, int start, int end) for(int i = start; i<=end; i++) printf(buffer[i]); FILE SYSTEM: #include <map> #include <vector> #include <string> struct DataBlock char data[data_block_size]; ; DataBlock datablocks[num_data_blocks]; struct INode std::vector<int> datablocks; ; struct MetaData int size; Data last_modifed; Data created; char extra_attributes; ; std::vector<bool> datablockused(num_data_blocks); std::map<string, INode *> mapfromname; sruct FSBase; struct File : public FSBase private: std::vector<inode> * nodes; MetaData metadata; ; struct Directory : pubic FSBase; std::vector<fsbase* > content; ; struct FileSystem init(); mount(filesystem*); unmount(filesystem*); File createfile(cosnt char * name) /* modifies MetaData */ Directory createdirectory (const char * name) /* modified MetaData */ void openfile(file * file, FileMode mode)

56 // mapfromname to find INode corresponding to file void closefile(file * file) void writetofile(file * file, void * data, int num) // Modifies all underlying structures. // Searches for next available datablock with datablockused // Modifies INode structure // Modifies MetaData // Accesses datablock using INode structure void readfromfile(file * file, void * res, int numbutes, int postion) // Accesses datablock using INode structure ; 1. 解释 Hash Table, 包括 可以用什么数据结构实现 hash table, what is a good hash function, 什么是 load factor 2 算法 : 删除一个给定数列中重复的元素 3 merge 两个有序数组 要求先给他解释算法, 再写代码 他当时给了我十分钟的时间, 让我写好以后发到他邮箱里 4 OOD: 设计一个汽车出租 (Car Rental Agency) 的系统 他先问我如果要实现 vehicle search, 需要哪些类 ; 然后又问要实现 rent a car, 又需要哪些类 ; 最后问如果快到了交车截至时间, 需要向用户发送提醒的邮件, 应该怎么做 第二轮电话面试 : 1 Favorite project 2 你最喜欢的排序算法, 它是怎么工作的, 有什么优点和缺点 我说的是选择排序, 他又问有什么排序算法比它的时间复杂度小, 并且同样要描述一下它们是怎么工作的 3 算法 写代码 : 给了两个数组, 要求找出他们之中相同的元素, 并且将相同的元素存储在一个新的数组里, 再输出 如果数组里有重复的元素, 比如 array1 中有四个 5,array2 中有两个 5, 那么新数组里只存储两个 5 要求我写代码, 再念给他听 4 OOD: 设计 restaurant reservation 系统 5 好像是一个开放性问题, 我没有完全理解 :log file 中存储了很多 order 的信息, 每个 order 都有一个 oid, 字符串格式 (xxx-xxxxxxx-xxxxxxx) 要求从 log file 中把所有的 oid 都提取出来, 问我怎么做 on-site: 一 给定一篇文章, 用户想要搜索一个单词, 要求给出搜索单词的建议 ( 就像一般的搜索引擎的那种功能 ) 要求描述算法 复杂度并写代码 二 先问了几个行为问题 然后问了两个简单的链表问题, 单链表中查找倒数第 n 个数和判断链表中是否有环 编程题问的是 boggle 游戏的问题 : 给定一个 4*4 的矩阵, 每个位置有一个字母, 可以从一个位置跳转到周围八个相邻位置中的任何一个, 但不能跳到已经访问过的位置, 要求找出所有的单词 ( 假设给定了一个词典 ) 三 午餐, 一个经理问了一些简历上的 projects 和实习的经历, 然后又介绍了一下他们组的工作 他说这次面试我的主要是 Kindle 组的 四 不是 Kindle 组的, 我估计是传说中的 bar raiser 第一个问题是给了一个很大的文件 ( 不能完全放入内存 ), 其中每一行存一个整数, 要求判断这个文件中的数有没有重复 然后是一个开放性问题 : 一台服务器每过三天就要挂一次, 需要重启才能再次使用, 每次重启需要一分钟的时间 ; 问有什么方法能解决这个问题

57 五 实现一个整数除法的函数, 不使用除号, 可以使用加号 减号和乘号, 函数只返回商 #include <vector> using namespace std; /* Finds longest strictly increasing subsequence. O(n log k) algorithm. */ void find_lis(vector<int> &a, vector<int> &b) vector<int> p(a.size()); int u, v; if (a.empty()) return; b.push_back(0); for (size_t i = 1; i < a.size(); i++) // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue if (a[b.back()] < a[i]) p[i] = b.back(); b.push_back(i); continue; // Binary search to find the smallest element referenced by b which is just bigger than a[i] // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity. for (u = 0, v = b.size()-1; u < v;) int c = (u + v) / 2; if (a[b[c]] < a[i]) u=c+1; else v=c; // Update b if new value is smaller then previously referenced value if (a[i] < a[b[u]]) if (u > 0) p[i] = b[u-1]; b[u] = i; for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v; /* Example of usage: */ #include <cstdio>

58 int main() int a[] = 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 ; vector<int> seq(a, a+sizeof(a)/sizeof(a[0])); // seq : Input Vector vector<int> lis; // lis : Vector containing indexes of longest subsequence find_lis(seq, lis); //Printing actual output for (size_t i = 0; i < lis.size(); i++) printf("%d ", seq[lis[i]]); printf("\n"); return 0; System Design (CHAPTER-1 bool findminwindow(const char *str, const char *pattern, int &minwindowbegin, int &minwindowend) int N = strlen(str); int M = strlen(pattern); int minwindowlen = INT_MAX; // hash table init all to 0s // used to check how many letters left in T to be filled char needtofill[256] = 0; for (int i = 0; i < M; i++) needtofill[pattern[i]]++; // set the rest to -1 so we know that letter is not in T for (int i = 0; i < 256; i++) if (needtofill[i] == 0) needtofill[i] = -1; // array of queues, each corresponds to a unique char in T queue<int> q[256]; // maintains a sorted map (maps indices to char), // the first and last element tells us the // starting and ending position of the window map<int,char> m; for (int i = 0; i < N; i++) // skips characters not in T if (needtofill[str[i]] == -1) continue; // push character to queue if (q[str[i]].size() < needtofill[str[i]]) q[str[i]].push(i); m[i] = str[i]; // replace the character in the queue // and updates the corresponding element in the map else int idxtoerase = q[str[i]].front(); map<int,char>::iterator it = m.find(idxtoerase); m.erase(it); m[i] = str[i]; q[str[i]].pop(); q[str[i]].push(i);

59 // found a window, check for minimum if (m.size() == M) int end = m.rbegin()->first; int begin = m.begin()->first; int windowlen = end - begin + 1; if (windowlen < minwindowlen) minwindowlen = windowlen; minwindowbegin = begin; minwindowend = end; // end if // end for return (m.size() == M)? true : false; ///////////////////////////////////////////////////////////////////////// bool minwindow(const char* S, const char *T, int &minwindowbegin, int &minwindowend) int slen = strlen(s); int tlen = strlen(t); int needtofind[256] = 0; for (int i = 0; i < tlen; i++) needtofind[t[i]]++; int hasfound[256] = 0; int minwindowlen = INT_MAX; int count = 0; for (int begin = 0, end = 0; end < slen; end++) // skip characters not in T if (needtofind[s[end]] == 0) continue; hasfound[s[end]]++; if (hasfound[s[end]] <= needtofind[s[end]]) count++; // if window constraint is satisfied if (count == tlen) // advance begin index as far right as possible, // stop when advancing breaks window constraint. while (needtofind[s[begin]] == 0 hasfound[s[begin]] > needtofind[s[begin]]) if (hasfound[s[begin]] > needtofind[s[begin]]) hasfound[s[begin]]--; begin++; // update minwindow if a minimum length is met int windowlen = end - begin + 1; if (windowlen < minwindowlen) minwindowbegin = begin; minwindowend = end; minwindowlen = windowlen; // end if // end if // end for return (count == tlen)? true : false; int findkthsmallest(int A[], int m, int B[], int n, int k) assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);

60 int i = (int)((double)m / (m+n) * (k-1)); int j = (k-1) - i; assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n); // invariant: i + j = k-1 // Note: A[-1] = -INF and A[m] = +INF to maintain invariant int Ai_1 = ((i == 0)? INT_MIN : A[i-1]); int Bj_1 = ((j == 0)? INT_MIN : B[j-1]); int Ai = ((i == m)? INT_MAX : A[i]); int Bj = ((j == n)? INT_MAX : B[j]); if (Bj_1 < Ai && Ai < Bj) return Ai; else if (Ai_1 < Bj && Bj < Ai) return Bj; assert((ai > Bj && Ai_1 > Bj) (Ai < Bj && Ai < Bj_1)); // if none of the cases above, then it is either: if (Ai < Bj) // exclude Ai and below portion // exclude Bj and above portion return findkthsmallest(a+i+1, m-i-1, B, j, k-i-1); else /* Bj < Ai */ // exclude Ai and above portion // exclude Bj and below portion return findkthsmallest(a, i, B+j+1, n-j-1, k-j-1); 整个算法有点像 minimum spanning tree, z=a(x)+b(y) 是个二维函数 我们从原点开始 有把确定的结果涂黑 第一个涂黑的是 (1,1) 下一个涂黑的只能是 (1,2) 或者 (2,1), 我们只要比较这两个就可以了 假设是 ( 1,2) 比较大, 那就是 (1,2) 涂黑 那下一个 candidate 只可能在 (1,3),(2, 1) 或者 (2,2), candidate 有什么特点呢 就是涂黑的那些点的横坐标或者总坐标加 1 而且可以通过一些前提条件排出一些 candidates, 比如 (2,2) 不是 candidates, 因为 (2,1) 肯定要比 (2,2) 大, 那 candidate 其实最多只有 min(m,n) 个, 一行最多只能有一个 candidate 所以那些 candidates 组成一个堆, 每次在堆里面删除最大值, 也就是把一个点确定涂黑以后, 就把它的横坐标或者纵坐标 +1 的点放入堆 堆的节点数目最多是 min(m,n), 做 k 次删除最大值的操作所以复杂度是 k log(min(m,n)) 写一个 loop, 从一个文件读数据读到另外一个文件, 假定文件都 valid, 已经 open 我写了一个 byte by byte 的, 然后被问了一大堆问题 : 比如怎么提高效率, buffer size 怎么选, 如果 line by line 的话,line 太长了会有什么问题,etc 对于这一题, 最大的 bottleneck 是 disk random seek IO 若是能极大的提高 disk sequential seek, 那么就可以把 random seek 的损耗减小到最少 用 byte by byte 拷贝最好了, 反正 buffer size 提高点, 越高越好, 把整个可用的内存都吃掉就没问题 ( 比如 win7 操作系统, 若是同盘拷贝几百 M 的文件, 内存大于文件体积的话, 几乎几秒不到就可以搞定, 其实是系统把文件吃到内存里面先, 然后在朝目标写的 ) 若是有 2 颗磁盘, 那么就用双线程了 : 一个线程从一颗磁盘里读 bytes, 一个线程朝另外一个磁盘写 bytes,

61 这样可以把效率开到最大 : 读写操作都是 sequential seek 若是 line by line 的拷贝的话, 若是 line 太长了 buffer 吃不下, 就很麻烦了阿 最好的办法, 是把 stream read/write 这一层抽象出来, 做成 BufferedStream 文件拷贝的那一层逻辑就 2 行代码 : while ((line = bufferedstreamin.readline())!= null) bufferedstreamout.writeline(line); bufferedstreamout.flush(); 然后, 在 bufferedstreamout 里面做实现 给固定的 buffersize, 每当 buffer 满的时候, 就写入磁盘 void writeline(string line) foreach char in line: if buffer is full write buffer into disk clear buffer end if append char into buffer end for boolean haspath(point a, Point b) if (a == null isblocked(a)) return false; if (a.equals(b)) return true; if (visitedpoints.contains(a)) return visistedpoints.get(a); boolean cango = haspath(godown(a), b) haspath(goright(a), b) haspath(goup(a), b) haspath(goleft(a), b); visitedpoints.put(a, cango); return cango; 动态规划, 位运算, 递归, 图最短路径, 堆, 杨氏矩阵

62 Give an algorithm to compress a memory. To be more clear if you are given a memory of some stored data here and there and some empty and null memory in between, how will you fragment and compress your memory? Design Parking Lot How do you implement a linked list without using dynamic memory allocation? So basically you need to use an array as a linked list. Generating and testing Sodoku problem Given a MxN matrix, in how many ways can you go from top-left to bottom-right? how can we find the longest palindrome in the given sentence??? Suffix tree Given two sorted positive integer arrays A(n) and B(n), we define a set S = (a,b) a \in A and b \in B. Obviously there are n2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. NlogN Given a singly linked list sorted in ascending order, convert it to a height balanced BST from this. Design the data structure to provide the mathematical operations +, -,/, * etc for the very very large numbers also implement the + function for two such very very large numbers...say numbers with 1 Million digits. a There is a string S ans another string s1, Design the algorithm to check if s1 is contained inside S and return the location as well. Hint: Interviewer told me that this is a standard problem from book, b test cases to check this. en.wikipedia.org/wiki/rabin Karp_string_search_algorithm en.wikipedia.org/wiki/knuth%e2%80%93morris%e2%80%93pratt_algorithm en.wikipedia.org/wiki/boyer%e2%80%93moore_string_search_algorithm Test cases: null, null -> exception null, not null -> exception not null, null -> exception empty, empty -> 0 not empty, empty -> -1 empty, not empty -> -1 S smaller than s1 -> -1 S larger than s1 with no occurrences of s1 -> -1 S larger than s1 with 1 occurrence of s1 -> index of s1 S larger, with multiple occurrences of s1 -> first index of s1 if the search is case sensitive, other tests can be imagined. Implement the function bool isregex(char *reg, char *string); This function is passed two strings : a regular expression, consisting of the [a-z] and the * and? characters. We had to

63 check if the string matched the supplied regular expression. For example, if reg is a*b, and string is acbcb, we should return true. And if reg is a?b and string is accb, we return false... Find closest ancestor of two nodes in a binary tree. Print a matrix spirally Reverse an integer array bitwise algorithm? code? Test cases? You are given an array containing only 0,1 and 2. Sort this array in one pass.you can't use anything like counting the no. of 0s and 1s. Given a BST (Binary search Tree) how will you find median in that? Constraints: -No extra memory. -Function should be reentrant (No static, global variables allowed.) -Median for even no of nodes will be the average of 2 middle elements and for odd no of terms will be middle element only. -Algorithm should be efficient in terms of complexity. Write a solid secure code for it. In usual Intel computers: Between processes, a context switch needs to change the OS-specific data and VM pointers to data, stack and code segments. But between threads, a context switch would only involves a change to stack segment. The process of swapping and/or signalling switches is handled by the same code (timer interrupt) in the OS. Write a function to generate all possible n pairs of balanced parentheses. void generate(string p,int o,int c,int n) if( o==n && c==n ) PRINT(p); return ; if(c>o)return; if( o >=c && o<n ) generate(p+'',o+1,c,n ); if( c<o ) generate( p+ '',o,c+1,n ); Connect the leafs in a binary tree and return a reference to the first of the linked leafs. This would allow clients of this API to subsequently traverse the leafs. The API has a flr flag indicating if the leafs should be connected from left-right (flr = true) or from right-left (flr = false). Please implement the following API: public Node ConnectLeafs(Node root, bool flr) Given a set of points, find the line that intersects the most number of points

64 write a program to shuffle an pack of cards in the most efficient way. Write code to check if a string contains a substring. KMP, Suffix Tree given a string, print each character and its number of occurence in sequence. use BST and no recursion, no extra memory is allowed. e.g, char* str="bcdaceffbe", you should print a 1 b 2 c 2 d 1 e2 f 2. QMutex mutex; void ReaderThread::run()... mutex.lock(); read_file(); mutex.unlock();... void WriterThread::run()... mutex.lock(); write_file(); mutex.unlock();... const int MaxReaders = 32; QSemaphore semaphore(maxreaders); void ReaderThread::run()... semaphore++; read_file(); semaphore--;... void WriterThread::run()... semaphore += MaxReaders; write_file(); semaphore -= MaxReaders; > 5 < >11<-----> 13 <--

65 In the BST you have the leaf nodes connected to form a doubly LL. Given a node, identify its height In our indexes, we have millions of URLs each of which has a link to some page contents, that is, URL->contents. Now, suppose a user types a query with wild cards *, which represent 0 or multiple occurrences of any characters, how do you build the indexes such that such a type of query can be executed efficiently by finding all corresponding URLs->contents efficiently. For example, given a query You need to find iloveyou.com, itveabcu.com, etc given two binary search trees, merge them in O(n) time with O(1) space Given char* func1(char* target, char* substring,char* replacement) write a c++ code to find the substring in the target and replace the whole substring with the replacement. (hint: replacement can be larger or smaller than the substring.)consider all possible test cases and check. merge two sorted list; 3. rotate an array by K; 4. Given an XML string, check if it's valid or not; 5. binary tree: each node has an additional field node which is initialized to be NULL at first. Asked to, for each node, point its next pointer to the next node in level-by-level traversal order. NO QUEUE should be used HERE! Given two arrays of numbers, find if each of the two arrays have the same set of integers? Suggest an algo which can run faster than NlogN without extra space? The requirement is to get the size of the datatype, without declaring a variable or a pointer variable of that type,and, of course without using sizeof operator! To find LCA for nodes A and B: O((logn)^2): 1. Find in A in left subtree, B in right subtree 2. If both not found, find in A in right subtree, B in left subtree 3. If both found, current node is the common LCA 4. If one found and not the other, make a recursive to call to that branch of the tree and start from 1. O(nlogn) with O(n) space: 1. Traverse the tree until node A is found, store the path in an array a1. 2. Traverse the tree until node B is found, store the path in an array a2. 3. Compare a1 and a2, the last common element is the LCA. But there are better, more complicated ways of doing this in constant time using RMQ. st%20common%20ancestor%20%28lca%29 find the longest palindrome in a string? Given a character string, find out all the English words contained in the string. Optimize the solution. Given a M*N matrix A in which all the elements in a row and all the elements in a column are strictly increasing. Find a path from the smallest element (ie A[0][0]) to the largest element (ie A[M-1][N-1]) such that the sum of the elements in the path is maximum. Time Complexity O(m+n). Use efficient space. Topological sort.

66 Peterson's algorithm is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single-use resource without conflict, using only shared memory for communication. It can be extended to more than two processes. Using Peterson's algorithm to implement mutual exclusive access to stack: while(1) // thread i (0 <= i < n) for (j=1 ; j<n ; j++) flag[i]=j; last[j]=i; for (k=0 ; k<n ; k++) if (k==i) continue; while (flag[k]>=flag[i] && last[j]==i) sleep(random()); // critical section... // end of critical section flag[i]=0; // not critical section... // end of not critical section min/max heap Maximum subarray sum problem Kadane's 2D algorithm O(N 3 ) #include <iostream> #include <algorithm> using namespace std; int main( void ) int N; int t = 0; int a[100][100]; int pr[100]; int S = 1<<31, s = 0, k, l, x1 = 0,x2 = 0,y1 = 0,y2 = 0,j; cin >> N; for( int i = 0; i < N; i++) for( j = 0; j < N; j++) cin >> a[i][j]; for( int z = 0; z < N; z++) for(int i = 0; i < N; i++) pr[i] = 0;

67 for(int x = z; x < N; x++) t = 0; s = 1<<31; j = 0; k = 0; l = 0; for(int i = 0; i < N; i++) pr[i] = pr[i] + a[x][i]; t = t + pr[i]; if( t > s) s = t; k = i; l = j; if( t < 0 ) t = 0; j = i + 1; if( s > S) S = s; x1 = x; y1 = k; x2 = z; y2 = l; cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl; cout << S; return 0; Given an array, find the longest subarray which the sum of the subarray less or equal then the given MaxSum int[] FindMaxSumArray(int[] array, int maxsum) Given a string of 10 characters and a number, insert multiplies and additions to make the characters equal the number ie , 995 -> 123*2+35*7+8*58 Given an array of N elements, one element is repeated N/2 times. Find the element if such an element exists.

68 You have a stack that is accessed by multiple threads simultaneously and you wish to synchronize access. You do not want to use locking to implement synchronization. Implement a thread-safe version of the stack. Serialize: #include<vector> #include<string> #include<iostream> using namespace std; int serialize(const vector<string> & stringvector1) FILE *fptr = fopen("c:\\serializedstring.txt","w"); if(!fptr) return 0; vector<string>::const_iterator i = stringvector1.begin(), end = stringvector1.end(); for(; i<end;i++ ) ::fputs((*i).c_str(),fptr); ::fputs("\n",fptr); fclose(fptr); return 0; int Deserialize(vector<string> & stringvector2) FILE *fptr = fopen("c:\\serializedstring.txt","r"); if(!fptr) return 0; char arr[1024],*ptr=null; while(!feof(fptr)) ptr = fgets(arr,1024,fptr); if(ptr == arr) stringvector2.push_back(string(arr)); fclose(fptr); return 0;

69 int main() vector<string> stringvector1,stringvector2; stringvector1.push_back("cracking"); stringvector1.push_back("programming"); stringvector1.push_back("interview"); stringvector1.push_back("with"); stringvector1.push_back("arif"); stringvector1.push_back("and"); stringvector1.push_back("krishna"); serialize(stringvector1); Deserialize(stringVector2); vector<string>::iterator i = stringvector2.begin(), end = stringvector2.end(); for(; i<end;i++ ) cout<<*i; getchar(); return 0; implement your own malloc and free for application x, which should control the heap memory usage of the application x. Given an input array of integers of size n, and a query array of integers of size k, find the smallest window of input array that contains all the elements of query array and also in the same order. Create methods for Set implementation. (Getting unique values from user to create a Set, and methods to implement Intersection, Union... of 2 sets you are given 2 arrays sorted in decreasing order of size m and n respectively. Input: a number k <= n*n and >= 1 Output: the kth largest sum(a+b) possible. where a (any element from array 1) b (any element from array 2) Given preorder and inorder traversal of tree, write the code to form binary tree from given traversal. Tree* Createnode(int *inorder, int *preorder, int index, int high, int low, int length) int element = preorder[index]; int pos = search(element, inorder, low, high); if(pos >= 0) Tree *temp = new Tree(); temp->data = element;

70 temp->left = Createnode(inorder, preorder, index+1, pos-1, low, length); temp->right = Createnode(inorder, preorder, index+1, high, pos+1, length); return temp; else if(index < length && low <= high) return Createnode(inorder, preorder, index+1, high, low, length); else return NULL; int _tmain(int argc, _TCHAR* argv[]) int inorder[] = 11,3,6,13,9,15,8,14; int preorder[] = 6,3,11,8,9,13,15,14; Tree *root = NULL; root = Createnode(inorder, preorder, 0, 7, 0, 8); return 0; Interval trees Write a function to validate a SuDoKu board. Write a function void DrawRectangle(char *Screen, int x1, int y1, int x2, int y2). Height and width of the monitor is known. To set a pixel, you need to set that particular bit of the screen. void DrawRectangle(char *Screen, int x1, int y1, int x2, int y2) if (x1>=width x2>=width x1>x2 y1>=height y2>=height y1>y2) return; for (int i=y1; i<=y2; i++) if (i==y1 i==y2) for (int j=x1; j<=x2; j++) setpixel(j,i); else setpixel(x1,i); setpixel(x2,i); void setpixel(char *Screen, int x, int y) int n = (y>0)? y*width : 0; n+=x; int a = n/8; int b = n%8; Screen[a]+= 256>>b; An array of integers of size n-1, all the elements are form [1,n]. Find the missing number. You can read only one bit in one operation, ie, to read A[i], you need to perform log(a[i]) operations.

71 Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's say they are decreasingly sorted), we define a set S = (a,b) a \in A and b \in B. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. Auto pointers have ownership. If you assing an auto pointer to another, the assigned auto_ptr loses ownership. Point to note is that RHS is modified. Shared pointers are reference counted. Assignment or copying increases the count and out of scope or delete reduces the count. When the count goes to 0, actual object is destroyed. All you go to do in a simple case is to maintain a counter which is incremented in constructors and decremented in destructors. If count goes to 0, delete the actual object. If a robust solution is needed Boost::shared_ptr is available. Given an 32-bit integer X, swap the i-th and j-th bit. swap(int n,int i,int j) if( (n & 1<<i)>>i ^ (n & (i<<j))>>j) ) // if bits i and j are different n^= 1<<i; n^= 1<<j; return n; Describe and algorithm and implement UNIX tail command void tail(file *fp, int num_lines) char **buffer = calloc(num_lines, sizeof(char *)); int index = 0; int i; for (;;) char *line = NULL; int len = 0; if (getline(&line, &len, fp) < 0) break; if (buffer[index]) free(buffer[index]); buffer[index] = line; index++; index %= num_lines; for (i = 0; i < num_lines; i++) puts(buffer[(index + i) % num_lines]); give an array, remove all the 'a's and add one 'd' after each 'b', do it in O(n)... int i=0, pos = 0, nb = 0, ; for(int i=0; i<n; i++) if(a[i] == 'b')

72 nb++; if(a[i]!= 'a') a[pos] = a[i]; pos++; if(nb==0) return; i = pos; pos = pos+nb; for(; i>=0; pos--,i--) if(a[i]=='b') a[pos] = 'd'; pos--; a[pos] = 'b'; else a[pos] = a[i]; In an ordinary sorted list, insert, remove, and find operations require sequential traversal of the list. This results in performance per operation. Skip Lists allow intermediate nodes in the list to be ``skipped'' during a traversal - resulting in an expected performance of per operation p_lists/skip_lists.html There is a stream of numbers, design an effective datastructre to store the numbers and to return the median at any point of time. Maintain 2 heaps : min and max Each time when a number is to be inserted. Insert it in max first. Now get the number at the top and insert it in min heap. The number at the root in the min heap will give you the median. [or] half of the top elements of max and min heap, if n is even. [Note: Each time keep equal no. of element in min and max heap. Also adjust if the max element in max heap is larger than the min element in min heap. Exchange the two numbers and rebuild the min heap] Adding each number will take O(log n) time Write an algorithm to check the winning condition in a tic-tac toe game for a NXN grid? (Hint. can be done in O(1) need int ROW[N]; int COL[N]; int diagonal; int anti-diagonal ) #define SIZE 3 #define MSIZE -3

73 int row[size]; int col[size]; int init () int i, j; for (i=0; i<size; ++i) row[i] = 0; for (j=0; j<size; ++j) row[j] = 0; // 0: no win // 1: 1st player win // 2: 2nd player win int check (int x, int y, int p) // O(1) if (p == 1) row[y]++; col[x]++; else col[x]--; row[y]--; if (row[y] == SIZE row[y] == MSIZE col[x] == SIZE col[x] == MSIZE) return p; // return 0; Given an array of 'n' random integers. Given an integer k<=n. Find the k numbers such that the minimum difference of all the possible pairs of k numbers is maximum (maximum among other minimum differences for various possible selections of k numbers ). How to increase web browsing speed. You are allowed to do anything at client/server At the server: Enable gzip. Ensure caching of static file fetch is enabled. If your users are spread across the globe, try having servers located in diff GeoLocs to save the n/w latency. Content Management System might also can take adv of it. router/firewall can also do some caching. see, if you can take advantage of that. On the client: Limit roundtrips to minimal. Keep javascript outside of the page, into one(or more) js files, so that they can be used in multiple pages, with taking advantage of caching. club css files into a single(or as minimum nos as possble) file. use image-crunching for tiny/small images used in the web pages make use of ajax, to avoid full-page round-trips. how to implement a queue using one integer. this should store value 0 to 9. example suppose queue has first value 2 then insert 4 then 6 so it should look like 246. first value should be popped as 2. then it should be 46. program should support 0 in all the levels also. example queue should handle like also, 0 as first value in queue. remember 0 just to use integer, nothing else as data storage.

74 Given an array of integers(both positive and negative) divide the array into two parts(subarrays) such that the difference between the sum of elements in each array is minimum???? n an array of n elements, find if there is a subset of 3 elements sum up to value T with time complexity O(nlgn). Design an LRU cache with all the operations including getting the least recently used item to be O(1). Use a Hashmap along with doubly linked list. Insertion: When an element is inserted into the hashmap create a new node at the front of the doubly linked list. The hashmap entry will have the reference to this node in the douly linked list. Also the node in the liked list will have a reference to the entry in the hashmap. So Insertion : O(1) Deletion: Delete the entry from the hashmap and also following the reference to the doubly linked list, delete the node too. So O(1) Access: Get the element in the hashmap, follow the reference to the doubly linked list and just move this node in the doubly linked list to the front of the list. Recently used: Get the first element from the linked list. So Access: O(1) Largest rectangle in histogram problem #include <iostream> #include <sstream> #include <stack> using namespace std; int DEBUG = 0; void getmax(int hist[], stack<int> * s, int newheight, int right, int & max, int & start) int height, left = 0, area; while (s->size() > 0 && hist[s->top()] > newheight) height = hist[s->top()]; s->pop(); left = (s->size() > 0)? s->top() : start; while (s->size() > 0 && hist[s->top()] == height) s->pop(); left = (s->size() > 0)? s->top() : start; area = height * (right - left); if (DEBUG) printf("area: %d * (%d - %d) = %d\n", height, right, left, area);

75 if (area > max) max = area; // // Note that when hist[i] == top_v, we push i. // In the acm judge site, it says skip i if equal. // But I feel somehow it can't keep track of the left value // when multiple columns have the same height. // int dohist(int hist[], int len) stack<int> * s = new stack<int>; int i, max, top_v; int start = -1; // the position before the last 0, used by left. max = 0; for (i = 0; i < len; i ++) if (s->size() == 0) s->push(i); continue; top_v = hist[s->top()]; if (hist[i] >= top_v) s->push(i); else if (hist[i] < top_v) getmax(hist, s, hist[i], i - 1, max, start); s->push(i); if (hist[i] == 0) start = i - 1; getmax(hist, s, 0, i - 1, max, start); cout << "max = " << max << endl; return max; int main() int hist[] = 3, 5, 4, 7, 6, 5, 2; // answer: 20 dohist(hist, sizeof(hist) / sizeof(int)); return 0; How would you find the first unique url among the millions of url available? BFS, DFS, Detecting Cycles,

76 Convert a doubly linked list to a binary search tree in place. Given a 2D plane, suppose that there are around 6000 points on it. Find a line which passes the most number of points. unclockwise BST: void PrintLeafNode(Tree *root) if(root!= NULL) if(root->left == NULL && root->right == NULL) printf("\n %d", root->data); PrintLeafNode(root->left); PrintLeafNode(root->right); void PrintLEdges(Tree *root) if(root!= NULL) printf("\n %d", root->data); PrintLEdges(root->left); PrintLeafNode(root->right); void PrintREdges(Tree *root) if(root!= NULL) PrintLeafNode(root->left); PrintREdges(root->right); printf("\n %d", root->data); int _tmain(int argc, _TCHAR* argv[]) int arr[] = 50,40,70,30,45,60,90,42,47,55,65,80; Tree *root = NULL; for(int i=0; i<11; i++) root = CreateTree(root, arr[i]); printf("\n %d",root->data);

77 PrintLEdges(root->left); PrintREdges(root->right); return 0; clockwise: void FlipOrder(Node* root) if (root == null) return; if( root->left) Print(Node->left->data); FlipOrder(Node->left; if( root->right) FlipOrder(Node->right->data); Print(Node->right->data); Print(Node->data); int MyAtoi(char *inputparam) if(*inputparam == 0) throw new FormatException(); int result = 0; bool isnegative = false; if(*inputparam == '-') inputparam++; isnegative = true; if(*inputparam == 0) throw new FormatException(); while(*inputparam) if(*inputparam >= 0x32 && *inputparam < 0x3C) int tempresult = (result + (*inputparam - 0x32) ) * ((*(inputparam + 1) == 0)? 1 : 10); if(tempresult < result) throw new OverflowException(); result = tempresult; else throw new FormatException(); return result * (isnegative? -1:1); Reverse a singly linked list

78 // // iterative version // Node* ReverseList( Node ** List ) Node *temp1 = *List; Node * temp2 = NULL; Node * temp3 = NULL; while ( temp1 ) *List = temp1; //set the head to last node temp2= temp1->pnext; // save the next ptr in temp2 temp1->pnext = temp3; // change next to privous temp3 = temp1; temp1 = temp2; return *List; /********************************************************************** -> This C++ Program is to convert a given infix expression (either parenthesized or unparenthesized) to postfix form -> Ex. of infix expression is ::(a+b^c^d)*(c+d) -> Data Structers used Stack:array -> This program works in microsoft vc environment. ************************************************************************ / #include<iostream.h> #include<string.h> #include<stdlib.h> #include<ctype.h> class expression private: char infix[100]; char stack[200]; int top; int r; char postfix[100]; public: void convert(); int input_p(char); int stack_p(char);

79 int rank(char); ; int expression::input_p(char c) if(c== + c== -') return 1; else if(c== * c== /') return 3; else if(c== ^') return 6; else if(isalpha(c)!=0) return 7; else if(c== ( ) return 9; else if(c== )') return 0; else cout<< Invalid expression ::input error\n ; exit(0); int expression::stack_p(char c) if(c== + c== -') return 2; else if(c== * c== /') return 4; else if(c== ^') return 5; else if(isalpha(c)!=0) return 8; else if(c== ( ) return 0; else cout<< Invalid expression ::stack error\n ; exit(0); int expression::rank(char c) if(c== + c== -') return -1; else if(c== * c== /')

80 return -1; else if(c== ^') return -1; else if(isalpha(c)!=0) return 1; else cout<< Invalid expression ::in rank\n ; exit(0); void expression::convert() cout<< \n*************************************************\n << This program converts the given infix expression\n << in to postfix form << \n*************************************************\n ; cout<< Enter an infix expression ::\n ; cin>>infix; int l=strlen(infix); infix[l]= )'; infix[l+1]= ; //Convertion starts top=1; stack[top]= ( ; r=0; int x=-1; int i=0; char next=infix[i]; while(next!= ) //Pop all the elements to outputin stack which have higher precedence while( input_p(next) < stack_p(stack[top]) ) if(top<1) cout<< invalid expression ::stack error\n ; exit(0); postfix[++x]=stack[top]; top ; r=r+rank(postfix[x]); if(r<1)

81 cout<< Invalid expression ::r<1\n ; exit(0); if(input_p( next )!= stack_p( stack[top])) stack[++top]=next; else top ; i++; next=infix[i]; postfix[++x]= ; if(r!=1 top!=0) cout<< Invalid expression ::error in rank or stack\n ; exit(0); cout<< \n\nthe corresponding postfix expression is ::\n ; cout<<postfix<<endl; int main() expression obj; obj.convert(); return 0; /*********************************************************************** * SAMPLE OUTPUT:: ************************************************* This program converts the given infix expression in to postfix form ************************************************* Enter an infix expression :: (a+b^c^d)*(c+d) The corresponding postfix expression is :: abcd^^+cd+* Press any key to continue ************************************************************************ **/

82 Microsoft Interview 1 (phone interview) 1. What's your most challenging problem in your projects? (I try to use the STAR principle: situation, task, action, result.) 2. If you can go back in time, what would you do better? 3. What's your preference for the positions in MS? (testing or developer) 4. What's your experience in testing? 5. What's a binary search tree? 6. Suppose you are going to explain this concept to a 5 year old girl, how are you going to explain it? 7. How to test a calculator (mouse/chair/glasses/whatever)? 8. How to get an applicant's telephone number if you know: First name, last name, school, address? (Pressure question, he will push you for more answers. Prepare for at least 10 solutions) 9. What's the use of binary search tree? Onsite Interview (SDET in live team) Summary of questions: 1. Sort 0,1 bit array. Use partition and count. 2. let me give test cases for one of her GUI applications. 3. Given a movie star relation (co-star in one movie) database, given a most popular star (say A), then find the distance of other star to A. BFS. 4. How to convert an integer array to byte array? How to test elevator? byte MyBytes[4]; //set values to this also. int Int32 = 0; Int32 = (Int32 << 8) + MyBytes[3]; Int32 = (Int32 << 8) + MyBytes[2]; Int32 = (Int32 << 8) + MyBytes[1]; Int32 = (Int32 << 8) + MyBytes[0]; uint32 GetInt32( uint8 *pbytes ) return (uint32)(*(pbytes + 3) << 24 *(pbytes + 2) << 16 *(pbytes + 1) << 8 *pbytes); void Int32ToUInt8Arr( int32 val, uint8 *pbytes ) pbytes[0] = (uint8)val; pbytes[1] = (uint8)(val >> 8); pbytes[2] = (uint8)(val >> 16); pbytes[3] = (uint8)(val >> 24); 5. How do you feel about today s interview, how much things do you learn. Google Interview 1 1. Implement a code to do wildcast string matching. int main()

83 char* text = "scr*w?d"; char* sig = "screeeewywxd"; int i = 0; int j = 0; for(i = j = 0; text[i] && sig[j]; ++i ) if( text[i] == '*') while( sig[j] && (sig[j]!= text[i+1]) ) j++; else if( sig[j] == text[i] text[i] == '?' ) j++; else printf("match failed\n"); break; e.g. source: readme.txt, query: *.txt, should return true. 2. check whether a Sudoku is valid. 9*9 matrix, and each row, column and 3*3 cell only contain unique integers (in range [1,9]) or empty. bool isvalid(int grid[] [9]) int i, j; bool status; status = true; for (int column = 0; column < 9; column++) if (column!= j && grid[i] [column] == grid[i] [j]) status = false; cout << "1st test: " << status << endl; for (int row = 0; row < 9; row++) if (row!= i && grid[row] [j] == grid[i] [j]) status = false; cout << "2nd test: " << status << endl; for (int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++) for (int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++) if (row!= i && col!= j && grid[row] [col] == grid[i] [j]) status = false; cout << "3rd test: " << status << endl; for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (grid[i][j]!= 0) status = false;

84 cout << "4th test: " << status << endl; for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if ((grid[i][j] < 0) (grid[i][j] > 9)) status = false; cout << "5th test: " << status << endl; return status; 3. Find intersection of two sorted array A, B. vector<int> findintersection(vector<int> A, vector<int> B) vector<int> intersection; int n1 = A.size(); int n2 = B.size(); int i = 0, j = 0; while (i < n1 && j < n2) if (A[i] > B[j]) j++; else if (B[j] > A[i]) i++; else intersection.push_back(a[i]); i++; j++; return intersection; i) What if elements of array B is stored on disk, and the memory is limited such that you cannot load all elements into the memory at once? ii) How will the complexity change in this case? Are there any factors you need to consider? iii) How do you change your solution to adapt to this situation? All above questions need to write detailed codes, check input, and handle special cases. Need to provide time/space complexity. Interview 2 1. Lots of compiler stuff which I know nothing. 2. Check whether a binary tree is a binary search tree. #include <stdio.h> #include <stdlib.h> #include <limits.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node int data; struct node* left; struct node* right;

85 ; int isbstutil(struct node* node, int min, int max); /* Returns true if the given tree is a binary search tree (efficient version). */ int isbst(struct node* node) return(isbstutil(node, INT_MIN, INT_MAX)); /* Returns true if the given tree is a BST and its values are >= min and <= max. */ int isbstutil(struct node* node, int min, int max) /* an empty tree is BST */ if (node==null) return 1; /* false if this node violates the min/max constraint */ if (node->data < min node->data > max) return 0; /* otherwise check the subtrees recursively, tightening the min or max constraint */ return isbstutil(node->left, min, node->data) && isbstutil(node->right, node->data+1, max); /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newnode(int data) struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); /* Driver program to test above functions*/ int main() struct node *root = newnode(4); root->left = newnode(2); root->right = newnode(5); root->left->left = newnode(1); root->left->right = newnode(3); if(isbst(root)) printf("is BST"); else printf("not a BST");

86 getchar(); return 0; Need to write detailed codes, time/space complexity, any improvements? 3. Sampling of incoming integers, then return one sample with equal probability. Time/space complexity, how to prove you are right? Interview 3 (Host bidding 1) 1. Ask general description of my related projects. 2. Give a general description of his potential project. 3. discuss about some implementation details. Interview 4 (Host bidding 2) He has really exciting project and match my background perfectly, many technical questions though, unexpected. The lesson here is that expecting technical questions even in host bidding interviews. 1. Describe in detail of your previous related project. (Android, Google API, PhD research) 2. The major advantages and disadvantages of following languages: C++, Python, Java. (He asked for at least 3 disadvantages for each language, if you can only give two, he will continue to let you think). 3. What s the difference between C# and Java, why you choose C# in one of your project? Feature C# C++ Java Inheritance Single class inheritance, multiple interface implementation Multiple class inheritance Single class inheritance, multiple interface implementation The notion of interface Through the "interface" keyword Through abstract class Through the "interface" keyword Memory management Managed, using a garbage collector Manual Managed, using a garbage collector Pointers Yes, but only in the rarelyused unsafe mode. References are used, instead. Yes, a very commonly used feature. Not at all. References are used, instead. Form of Compiled Source Code.NET intermediate language (IL) Executables. Byte code. One common base class Yes No Yes

87 4. Consider you are constructing a system for data synchronization, what problem will you face, and how you solve it? (I did not do well on this question, since for my understanding, the data synchronization is normally among process, or among different users, like the one in source code version control (Git/repo). I finally understand after 15 mins, he wants to know about multi-threads synchronization. :< ) 5. What is mutex, semaphore, deadlock? Give examples of them. (That s when I finally realize what he wants to know about synchronization, just the classic stuff.) Interview 5 (Host bidding 3) The interview runs very smoothly. He basically just talked about which experiences I have. Facebook: First phone screen. 1. Tell me about your self, your PhD research, what do you want to do in facebook. 2. What s your applications/projects in Garmin? 3. Do you use facebook a lot? What do you normally do in using it. 4. Binary search, complexity. 5. Bubble sort, best case complexity. 6. Guess a number in a given range, say (still Binary search). 7. When will java destruct object. (automatic garbage collection for unused object that no reference points to it, finalize() method) 8. Java stuff: how to avoid other programmer from changing the function. (Final keyword) 9. What is the transient keyword. Second Phone Interview. 1. Describe your background, and what you are seeking for. Then he tell me I am not a good fit for his team, and want to recommend me to the other team. He even didn t want to continue the interview. :< 2. How to use stacks to simulate queue. (do not use online tool, just write and tell him. Use two stacks). 3. How to find the lowest common ancestor of a binary tree, node do NOT have parent pointers. (Recursion, additional check for the case when nodes are not in the tree, or only one node is in the tree.) Use collabedit.com, really awesome tool. Third Phone Interview. 1. The project they are working on. 2. The projects I was working in research and internship, all resume stuff. 3. Given a linked list, say A->B->C, print it in reversed order. Time & space analysis. What if I want the original list not changed? How about multithreads call this functions simultaneously? 第一个人 1. 返回给定字符串的第一个不符合字母顺序的 index 比如 abcdaf 就需要返回第二个 a 的 index, 比如 aze 就返回 e 的 index 反正题目不难, 就是需要考虑的东西多一点

88 2. 检查 sudoku 的输入是 valid, 允许 solution 是不完全的题目一样还是简单, 还是要考虑一些细节比如你的 matrix 用什么表示,int** 的话就没法表示空白的格子 第二个人 1. 就是那道带 random pointer 的 linklist 的 copy 我当时给的 solution 当然是用 hashmap 之类的东西做, 她也没反对, 好像是接受了 不过刚才看了其他的解, 觉得最好的还是那个在原有序列里面插入再拆分的解, 看着比较完美 2. 不是程序问题了, 稍微有点设计的意思 给了 3 个函数, 分别是注册一个电话号码 ; 是否被注册 ; 返回一个未被使用的号码 然后问我数据结构以及方法怎么实现 我首先问这些号码是存储在内存还是数据库里面的 其实这个题目挺二的, 哪有程序会把号码存内存里面的, 不过我猜她想考察这个东西, 所以故意这么问的 这个题目答的不是太好, 首先是需求没有搞清楚, 就是电话号码是否全在里面了 是否允许创建一个新号码 她自己也没弄明白, 说你可以随意产生一个号码 这样一来就把题目弄的很麻烦 其实本意显然是所有号码都在里面了 然后就是数据结构了, 当时有点紧张, 想到的当然是 hash, 后来因为发现如果用一个 hash 的话, 返回一个没使用过的号码很费时间 ( 假如号码库很大 ), 于是就又拆成了两个存储, 一个是使用中的, 一个是没有被使用的 也不知道有没有更好的数据结构了

89 1. 开放式问题, 有些网站每天只允许有限次访问, 怎么抓取网页使得索引尽量全面和新鲜?? 2. 在 C++ 文件中只 declare class A, 但不以任何方式 define class A, 是做什么用 3. Estimate the time cost of transfering 1M of data from one memory stick to another. - when the data in memory is sequentially stored; - when the data in memory is stored in blocks; - does the bus width matter here? 4.How to transform a unbalanced tree into balanced tree? 第 2个题我想的是保留 A 的名字, 以后再定义第四个题我想的是先算每个节点的 blance factor 然后再调整, 具体怎么调整就不知道了 第四个题还想到一个办法是转成双链表, 然后再转 balanced tree, 保证了 inplace Phone: ///////////////////////////////////////////////////////////////////////////////////////////////////////////// SSL, for example a -> b (A refer B) d -> c (D refer C) c -> a (C refer A) find a data structure to save these information and print the following result: d->c->a->b The data structure I pick is Array Hash Table. Typedef struct NODE unsigned char keyval; unsigned char *prefer; // point to the char referred. Node; Node key[26]; Insertion operation: space O(26), time O(1) int insertpair(unsigned char refer, unsigned char *referred) key[refer-'a'].prefer = referred; Print function: space O(26), time O(n) we need a auxiliary list to sort the linked list. Onsite: 1. design public interfaces for cache (like cache for string) 2. design public interfaces for router 3. merge two binary search tree 终极方案 : O(logn + logm) 的复杂度, O(1) 的空间, 把 BST a和 b 互相挂 public BST merge(bst a, BST b) if (b == null) return a; if (a == null) return b; if (a.root < b.root) return merge(b, a); // now, a.root >= b.root

90 BST bleft = b.left; BST bright = b; bright.left = null; // we know every node in bleft is less than a.root if (a.left == null) a.left = b; else a.left = merge(b, a.left); a.right = merge(a.right, bright); return a; 4. 爬楼梯, 每次可以一个 step, 或者两个 step, 问有多少种走法? 5. 如何实现一个 queue? 怎么分别通过 stack,linked list, heap 实现? 6. preorder binary search tree. 判断两个 binary search tree的 preorder 序列相同不相同可否把空间节省点? 到 O(1) 写 2个 iterator public boolean hassamepreorder(bst a, BST b) Iterator ait = a.iterator(); Iterator bit = b.iterator(); while (ait.hasnext() && bit.hasnext()) if (ait.next()!= bit.next()) return false; return ait.hasnext() && bit.hasnext(); 问题就转化成了使用空间 O(1), 实现 iterator 7. 判断两个树相等不相等 DFS 遍历, 判断是否相等咯 public boolean equals(bst a, BST b) if (a == null) return b == null; if (b == null) return a == null; return a.value = b.value && equals(a.left, b.left) && equals(b.left, b.right); 8. 判断两个 DAG( 有向无环图 ) 相等不相等 DFS 遍历, 判断是否相等咯 public boolean equals(dag a, DAG b) if (a == null) return b == null; if (b == null) return a == null; if (a.value!= b.value)

91 return false; DAG[] anext = a.child(); DAG[] bnext = b.child(); if (anext.length!= bnext.length) return false; for (int i = 0; i < anext.length; i++) if (!equals(anext[i], bnext[i])) return false; return true; 1. 算时针和分针的夹角 整个钟面是 360 度, 算算时针的位置和分针的位置, 然后求差的绝对值即可 double foo(int hour, int minute) assert (minute < 60 && minute >= 0); assert (hour < 24 && hour >= 0); if (hour >= 12) hour -= 12; double minuteangle = 360. * minute / 60 double hourangle = 360. * (hour / 12) + minute / 60. * (360 / 12); return Math.abs(hourAngle - minuteangle); 判断 List 有没有环, 分析时间复杂度 用 2个指针, 一个快的, 一个慢的 若是 2 个指针重叠了, 那么就是有环 public boolean hasloop(node head) assert (head!= null); Node p1 = head; Node p2 = head; while (true) if ((p1 = p1.next) == null) return false; if ((p1 = p1.next) == null) return false; if ((p2 = p2.next) == p1)

92 return true; return false; 时间复杂度是 O(n). 1 compare binary search tree & hashtable 2 design a hashtable to print words between 'B' and 'C' 3 design a general hash function for words(like words in dictionary) 4 why multh-threading? implementation in C/C++ 5 mutually exclusive, disadvantage of mutual exclusion? 6 describe your best project 早上 10 点半开始 面第一位阿三哥, 开始侃项目, 谈跟专业相关的东西, 追问的很深, 最后还有 15分钟的时候要求写代码, 要求 inplace 对一个数据结构内的元素重新排序, 昏倒啊 在白板上画了简单的结构, 讨论后获得首肯, 然后开始写代码 我把笔记本电脑带了过去, 所以在键盘上敲 大概一会就写出来了 ( 若是在白板上写, 怎么死的都不知道阿 ) 然后三哥问, are you done? 我说跑几个测试案例试试看 然后在纸上写了 5个案例, 一行一行的检查 立马发现 2个 bug, 更正之 三哥看到快没时间了, 说你跑这个案例试试 遂发现一个新的 bug, 更正之 最后代码写出来完整 三哥满意的走了 第二位是个白人 一上来就做题 开始我理解以为是一个 DP, 后来沟通之后发觉可以有很简单的解法 直接奔向 O(n) 的解法 跟面官沟通完想法, 最后获得同意后在笔记本上敲键盘 很快写了出来 面官随后问测试案例 我直接在笔记本电脑里面写测试代码, 写了 10多个 面官随后表示满意 我表示可以 compile跑跑看 解决了 compile的 error, 有一个测试案例不通过 解决 bug, 最后所有测试案例通过 下午, 第三位是个黑人 这场面试最凄惨了, 希望我的经验教训能帮助大家 开始一个很简单的题目, 2叉树遍历的, 5 分钟不到搞定, 写了代码 然后黑人老兄把问题延伸, 问了一个复杂的情况, 我没有跟面官沟通, 就直接写代码 有错误 被指正出来, 再修改代码, 面官说还是有错误, 在修改代码, 面官说还有错误 最后我说, 我们得沟通沟通, 遂又回白板开始讨论算法 最后一刻把问题解决出来, 但是没时间写代码了 我看了下黑人老兄的笔记本电脑, 昏倒, 他把我的每一个版本的代码全部写了下来! 包括第一个版本有错误的, 然后第二个版本, 第三个版本 遂后悔不已, 应该先在白板前沟通好再写代码的 当时黑人老兄在我说完算法之后面无表情, 我应该询问是否有无 bug 不过最后黑人老兄说, 虽然你没有时间写正确的代码了, 但是能走到这步能把问题解出来的人不多 第四位一个白人, 一进来沉着脸, 一副别人欠你钱的表情 开始一个简单的问题, Programming Pearl 上第一章的案例题, 大家都知道了吧 之后遂把数据规模提高到 10^10 我给了 2个解法 之后把数据规模提高到 10^15, 输入已经无法存在一台电脑上, 说咱们有 1000 个电脑, 每个电脑上存一部分输入, 你怎么解决 这个磨蹭了好久, 最开始我有个 brute force 的想法, 当时没有说出来, 觉得不够好, 后来跟面官折腾了半天, 才发觉最开始的想法就是他想要的 最后白人老兄终于脸开笑容, 握手拜拜 第五位一位三哥, 讨论 open end question 但是问的很深, 涉及到数据库的实现, 多线程, cache的实现, Javascript, 等等等等, 这些都是我简历上写做过的东西, 我把所有可能的情况全部都列了出来, 说的嗓子都哑了 三哥面无表情, 但是自我感觉还说的挺多挺全的 Write the clone method of a linked list whose one node point to some random node. You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say "foo", output all the products which have names having 50% or more similarity with the given keyword ie "foo" Write the most efficient algorithm for the same.

93 You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.) Given an array of n elements and an integer k where k<n. Elements a[0]...a[k] and a[k+1]...a[n] are already sorted. Give an algorithm to sort in O(n) time and O(1) space. en n number of points in space and a point P, find 3 nearest point to p 大整数乘法一面大概 1 小时用 google doc写 java code 1. 最 challenging的 project 问的很细关注 challeing 在哪怎么解决的 2. abstract class和 interface 的区别什么时候用哪个 3. 实现 List<PhoneNumber> deduplicate(list<phonenumber> phonenumbers) 我先写把 list加到一个 set里面然后把 set包装成 list 出来他就笑了说不给这么搞用别的 data structure 然后我就写了个用 HashMap 的. 然后问复杂度然后问 hashcode 怎么写其实后来想想用 HashMap 的话和原来是一样的都靠的是 HashMap 的 keyset是一个 set 4. reservoir sampling. 实现 List<Node> getrandomsample(iterator<node> itr, int samplesize) 返回 samplesize 个随机的元素因为只给了 Iterator 拿不到 collection的 size我就说入过给的是 collection, 那么有 size, 有 samplesize 可以算下 possibility看 iterate的时候当前元素要不要加到 result list 里面去只想到了这么多后来搜了下贴个解 二面是老印一听到心里就一凉唉都有心理阴影了 1. 问了几个 inner class 的情形, static和 non static 的区别各什么时候用,anonymous 什么时候用 2.interface和 abstract class 的区别 3.garbage collection 原理是怎样的然后就写 code 了全是 bst, insert, count nodes, count nodes non-recursive, isbst 最后 isbst 我还是写错了 他一说我就知道挂了唉 move on 吧开始 coding, 很简单, 关于字符串的, 不过没听清楚他在问什么, 接着他讲了个例子才明白 然后, simple solution, O(n^2), 接着 binary search 优化 O(nlgn), 接着 bit map 优化 O(n), 1. 写程序判断一棵二叉树是不是对称的 2. 写程序求一个词到另一个词的最短变换路径 ( 二词长度相等 ) 3.Design auction ads bid的 data holder class 4.Design Amazon 主页服务器的 auto recovery, load balancing, 应该 min imize 的指标, 针对指标估计标准值 ; 对含有 user ID信息的 request如何 load balancing 5. 提出一个对 Amazon有用的 feature, design 6. 假如你是一个 start up公司的 tech management 最高层, 公司的网站最近有些慢, 如何分析解决 ( 假设面试官是 CEO) 7. 写程序分层打印一个矩阵, 如下例 : 打印输出的顺序是 : Machine learning的一些概念, bias, variance, boosting,svm&decisiontree& NeuralNetwork 比较 9.design 算法, 抽取不同 product record 中对应同一属性的不同值, 比如 Nike Shoes, Black, Size 7, ID: WSLT Nike Shoes, White, Size 9, ID: WSLT Black White, Size 7, 9 都是属性 10. 一个巨大的 File (billions of rows), 每行包含两个 field: ID, description

94 设计算法, 找出所有对应 duplicated description的 ID 11. 介绍以往的 project, 个人的 working style,etc. 第一个是老美, 先问了一些简单问题, 比如怎么判断一个 32 bit是 big endian 还是 small endian等等 最后出了一道算法题, 也很容易, 给定 K个 sorted array, 要求输出一个大的 sorted array 简单的 merge sort就解决了 不过 merge sort 要求每次 K 个 array中, 最小的 element 简单的当然是 scan 这 K个 array 我提出可以把 K个 array 的当前 element放入 Heap structure, 这样每次搜索就从 O(K) 降低到 O(logK) 最后写了个程序 第二个是老中 也是先问了一些简单问题, 然后让我设计一个分布式文件系统, 给定 path name, 可以读写文件 具体的 system design 这里就不提了 其中一个细节是, 给定 path name, 怎么知道哪个 node拥有这个文件 我提出需要实现一个 lookup function, 它可以是一个 hash function, 也可以是一个 look up table 如果是 lookup table, 为了让所有 client sync, 可以考虑额外做一个 lookup cluster 然后 Interviewer 很纠结, 既然可以用 hash function, 为什么还搞得那么复杂 我就告诉他 hash function 的缺点 假定一开始有 N个 node, hash function把 M个文件 uniformly distribute到 N 个 node上 某天发现 capacity不够, 加了一个 node 首先, 要通知所有的 client machine,configur ation 改变了 如果不想重启 client machine的 process, 这不是一个 trivial job 其次, 文件到 node的 mapping也变了 比如, 本来按照 hash function, 一个文件是放在 node 1 加了一个 node 后, 它可能就 map到 node 2了 平均来说, N/(N +1) 的文件需要 move到新的 node 这个 data migration 还是很大的 然后我就提出一些 hash function的 design, 可以减少 data migration 最后他提了一个问题, 说要实现一个 function, 要统计 distributed file system 所有目录的大小 前提是, 一个目录下的文件可能放在不同的 node 上 我说这个不就是在每个 node上统计, 然后发到一个 merge吗 他说对, 但是又问用什么 data structure 来表示 我说这就是 hash table, key就是 directory name, value 就是大小 因为 directory本身是树结构, 这个 hash table的 key可以用 tree 来组织 最后让我实现一个 function, 把我说得这个 data structure serialize成 byte array 因为这个 byte array就是网络传输的 data 我用了 depth first traverse 不过等我程序写完, 才发现, 用 breath first traverse会更方便, code 也会很简洁 第三个也是老中 他可能没有很好的准备, 问题一开始有点含混不清 花了一点时间, 基本明确, 他是要我用 pthread实现 thread pool, 以及 thread job management 先是 define class interface, 然后用 pthread的 mutex和 semaphore实现了 consumer/ producer queue 这个 queue允许 users( producers) 加入 thread jobs, thread managers(consumers) 拿出 thread jobs, 并执行 当场 design class interface, 并做到面面俱到有点难, 好在我山寨了 Java的 thread class 有了 interface, implementation 还是比较容易的 他顺便也问了一些 multiple thre ad的问题, 比如怎么做 singleton 等等 第四个是老印 他问了一道算法题, 假定有个 graph, 怎么找出不带 circle的最长 path 我纠结了很久, 最后用 dynamic programming 解决的 好在他主要 focus在 idea 上面, 没让我把 code写完 等我想清楚算法, 一半时间已经过去了 要写完 code, 我还真做不到 电话面试 : 1 个小时 4 个面试官, 主要问工作经验, 多线程, socket, 程序优化相关然后第一次 onsite: 3 个小时 2个 VP, 4个 AVP 项目相关的问得很多, 基本上差不多整个项目实现的细节都问了, 包括多线程模型, memory pool 实现, socket 模型 ( select和 async socket 实现 ), 异步文件读写, 内部使用的数据结构, 和 IPC 实现, 跨平台的实现方法 (thread, socket, timer, TLS, fast mutex 实现 ) coding : 比较简单, 就是 c 的字符串操作

95 第二次 onsite: 1 个小时 1个 VP, 1个 AVP C++/template, JAVA, C#, 估算某个 building 每个月的电费 这个很晕 2个 coding: C 字符串操作 Sorting o Bubble/select/insertion/counting/qsort/heap/merge/bst o Time/space complexity analysis Caching design o Replacement policy (LRU, LFU, NRU, etc ) o Efficiency/complexity/performance o Distributed cache o Hashing Multi-thread o Locking/mutex/semaphore/critical section o Coding pattern producer/consumer (aka writer/reader) ref-counting Tree o Heap o BST/black-red (BR/AVL is a stretch) o B+ o Suffice/prefix trees (trie) o Expression tree DP (dynamic programming) Search o Basic backtrack o Backtrack trimming o Breadth first vs depth first search o A* o Bidirectional search Graph o Shortest distance (djstra, floydwarshall) o Cycle detection o Flow network algorithms List o Stack/queue/priority queue o List manipulation Pattern matching o Strict string matching o Wildcard matching Bit operations Compression algorithm.

96 o Huffman o RLE (run-length encoding) o LZW Design o Design pattern: singleton, factory, provider, witness, command, etc o OOP designs Interface vs abstract class Virtual behaviors o Design a feature like: Twitter Facebook/linkedin friend recommendation C#/Java o GC algorithm Tech o Hadoop o Mapreduce o TSQL/SQL o Memcached o Membase o Cassendra Reason to use/not to use STL/ATL Exception versus error code. Memory allocator/heap manager ==================== Actual coding/interview questions encountered lately = =================== 主要面试的对象集中在 high scale/high perf/highly available/distributed service infra areas. 所以题目有点偏.. 仅供参考, 并不准备一道一道解释回答 Sorry. ============================================== 1. Say a compare function f F(x, y) returns 1, if x is better than y F(x, y) returns 0, if x is not better than y (but doesn t say x is worse than y, it s simply saying x isn t better than y) F is communitive: F(x, y) -> 1 then F(y, x) -> 0 But F isn t transitive: F(x, y) -> 1 && F(y, z) -> 1, doesn t mean F(x, z) -> 1 So based on the rules above, write an efficient algorithm to find an element in a list that is the best. If x is the best, it means for any y (that y!= x) in the list, F(x, y) -> 1. The function can return NULL to indicate there isn t such an element exist. ============================================== 2. Two strings (ASCII, value range is 0 255), test, and alpha. Write a function to return true if every character in test appears in alpha, and

97 return false otherwise. ============================================== 3. Say we have a simple file system on disk is like the following: There are many consecutive sectors on disk, the sector 0 is the file index table. Each of the following sector would either belong a file, or empty. Each sector has a head structure, which contains info 1) whether this is an empty sector or not and 2) if this is not an empty sector, so it belongs to a file, then what s the next sector in the file. If this field is null, then this sector is the last sector for this particular file. The file index table contains a list of entries, each has a file name, and its first sector number. Now somehow the sector 0 (file index table) is completely corrupted, write an efficient algorithm to rebuild the file index table. Filenames can be generated randomly as long as they re unique. ============================================== 4. Say have a N computer, each computer gets assigned with a random integer value. We need to write a single program, that the same program will be run on all the N computers at the same time. At the end, every program on each computer needs to print out the sum of all the integers associated w / all computers. To achieve this, there are two synchronous blocking APIs to use. Send(k, n): if a program calls this API, it means it wants to send an arbitrary integer n to computer k (0 <= k < N). Receive(k): if a program on computer j calls this API, it means it wants to receive the integer from computer k where the program sends that integer to computer j. Both API are sync/blocking. That means if there is sender, but on the receiving end, there is no receiver, then the sender will be blocked and wait until corresponding receiving API is called on the target computer. Vice versa. Two metrics for achieving this goal. 1) # of msgs (send -> receive counts as 1 msg) and 2) assume each msg takes time t to complete, the total T. Try to write the program to 1) achieve the goal and 2) try to optimize T so T being the smallest ============================================== 5. Say you have an array of bytes (value is [0-255]), write an (LRE) compression algorithm to offer fast, efficient, on the flight compression and decompression. ============================================== 6. Given an integer array, calculate total number of pairs (x, y) in the

98 array, such as x > y. For example, given an array of 5, 6, 2, 1 All the pairs that have descending order are: 5, 2 5, 1 6, 2 6, 1 2, 1 So result = 5. ============================================== 7. Minesweeper a. Design data structure for the board and its mines b. Given n (board width), m (board height), and k (number of mines), efficiently and randomly generate k mines and place them in the board. ============================================== 8. itoa ============================================== 9. given an array of integers, find the smallest number; find two smallest numbers; find k smallest numbers; ============================================== 10. F(a, b) -> true or false means that person a knows person b. But it s not commutative, because person a can know person b, but b may not know a. Say, you throw a party, you knows a number of people, invite them, then each of them knows a bunch of people (those sets of people can intersect), so on and so forth. Now there is a celebrity comes in, everyone in the party knows him, but he knows no one. Write an algorithm effectively find out who the celebrity is. ============================================== 11. Say you re Walter Disney and you have so many copyrighted videos, and you want to write an algorithm (high level description is good enough) to detect any video clips on YouTube.com are violating copyrights. ============================================== 12. Given two identical length strings, say abcdefg, bcdefgx, first define the distance (or think in search term, relevance) between these two strings, and then write an algorithm. ============================================== 13. Master mind guess. Say a random 6-digit number is generated and hidden secretly. Then there is a function: int Tell(int n); where the n is any 6-digit number, and the function Tell returns how many of the digits are correct and in the right position.

99 For example, if the secret is , and Tell( ) -> 3 Now write an algorithm such that you can call Tell to figure out what is the secret number efficiently. ============================================== 14. a stream of integer coming in (in single link list fashion), you don t know how many, but you can use current->next == NULL to know if the stream ends. Now given a K (assume K < count of total number of element in the stream, even though you don t know the total number until you fully scan the stream) Output randomly sampled K integers from this stream. (reservoir-sampling) This is very similar to #7, the random generate minesweeper problem. ============================================== 15. say two linked list may or may not merge at certain node. If they merge, then it will be like a Y shape structure. Write a function, taking two linked list and 1) return true/false whether these two linked lists merge or not and 2) return the node where the merge occurs. ============================================== 16. swap every pair two adjacent nodes in a linked list. ============================================== 17. Write a function to find the nth last element from a Linked List. ============================================== 18. Given a linked list, findout wether it is a palindrome or not, Idea: find mid point, then compare. ============================================== 19. struct node int value; node *next; node *random_ref; How to write a function to take a link list in such structure and dup it into a new link list with both next and random_ref both honored for each

100 node in the new list? ============================================== 20. given two link lists, determine whether they re reverse of each other. ============================================== 21. 1) merge sort on array 2) merge short on linked list. ============================================== 22. LCS (longest common subsequence), given two string a, b, and calculate their LCS value. ============================================== 23. edit distance. LCS is in fact a sub set of the edit distance problem (aka Levenshtein distance) Edit distance: Two strings, a, b, use minimum number of following operations to make them identical Insert/delete/sub While LCS, the set of operations allowed is insert/delete And hamming distance, the set of operations allowed is only sub (thus two strings must have the same length) Dynamic programming. ============================================== 24. write a function to find mid point of a linked list. two methods 1) two scans, and 2) use fast/slow pointers. ============================================== 25. find the longest palindrome in a string. Solution1: Brute force Solution2: string A, reverse it becomes A, so the problem changes to find the longest common substring. Note, it s different than #22 below, that one is about longest common subsequence. But the idea is the same using DP. ============================================== 26. Do you know about the recommendation engine built/used by Amazon.com? How would you build one? Now use what you know to build a relevancy engine for Bing Search. Backend module: Storage: for transactional data; logging; system health Caching: Mid tier modules: User module: retrieving user info, user history, user social info

101 (friends, etc). Product/action relevancy: if user click kindle, we should find related products such as kindle cover, skins. Popularity module: for each item, what s the popularity Campaign: amazon can have an active campaign promoting kindle, no matter what user is doing Feedback/improvement: once recommendations served, what are the user follow-up actions, click through rate, etc, to retrain those numbers in those components. ============================================== 27. Design a logging system for an application server? see to it that Logging system you define does not include a large overhead in case of large loads to server? Lossless or eventual consistency or best effort? In memory ring buffer for speed (flight blackbox) Async persistent write Central collection mechanism such can be throttled and retried easily ============================================== 28. How do you design cache server for a simple web application. How do you make sure of the data consistancy. How do update your data/cache. ============================================== 29. Design a Hotel reservation system which will support the following functions. a) User will get a list of all different types of rooms. b) User selects a room type & check the room availabilty between the specified dates. c) User Makes Reservation. [Discussed about "locking" the room availbilty or not in case if user wants to proceed with reservation] ============================================== 30. If you were integrating a feed of end of day stock price information (open, high, low, and closing price) for 5,000 companies, how would you do it? You are responsible for the development, rollout and ongoing monitoring and maintenance of the feed. Describe the different methods you considered and why you would recommend your approach. The feed would be delivered once per trading day in a comma-separated format via an FTP site. The feed will be used by 1000 daily users in a web application ============================================== 31. Imagine that there are 7 servers running in parallel. What happens when you need to expand to 20 live? What are issues? What could you do to fix this issue in the future ==============================================

102 32. How to implement a LRU cache. Fast item retrieve, fast to kick LRU item out, fast to add items in. Combination of doubly linked list (dll) + hash. Dll is a sorted list ordering from least to most recently used items. Hash store <key, ref> to those items. Operations need to be supported: Get-item Kickout-item Update-item (means it s been used, this can actually be folded into the get -item) Insert-item Delete-item Most these operations first go into hash map to find the key, and locate the item in the linked list, then do certain operations such as remove, move to head, move to tail, insert, etc. More about caching strategies: ============================================== 33. say char a-z maps to 1 26, A-Z maps to Give you a numeric string sequence, such as "123", there would be multiple possible mappings: "abc", "lc", "aw". But for "101", there is only one possible mapping: "ja". And for "00", no possible mappings. Write a function, given a numeric sequence in string, return the total number of possible mappings. ============================================== 34. string/pattern matching. pattern can contain a-z and special chars like "." and "*" "." means matching any single char "*" means matching zero or more chars of any kind. string can contain a-z and "." "*". Note "." and "*" in string are just regular chars, no special meanings. 题 1: UITableView+ NSArray, 白板写代码题 2: NSDictionary, 直接在电脑上写代码题 3: 动态规划智力题题 4: Objective- C与 C++ 的比较, 优劣 先让我写 N! 我写了递归, 然后又让用非递归写了一次 继续问递归的确定 接着问求 fib 数怎么写代码, 这些代码早练过了, 所以不是问题 本来想给他 show下我 logn 的算法, 后来他没要求就不写了 还问了些 stack 里面存了哪些东西, 以及顺序, 顺序是和编译器有关 其他问题我也忘记了,

103 反正这个哥们是物理的 PHD, 问到问题和数学有点关系 然后就是 2个以后的同事来面我, 问的题目还有点水平 先是 OOP 的设计, 关于公司的船运货物到不同港口, 怎么设计这个系统 具体是怎么样的, 我也忘记了 接下来就是关于这个 OOP 的算法设计, 问如何计算一个港口哪段时间船最多, 给你每搜船进出港口的时间 这个题和 facebook 的一个 puzzle 如出一辙 接下来是写了一段代码让我找错, 这个很简单, 常见错误 还问了我些设计模式的题目, 问我用过哪些, 怎么用的 第二天是周五, 晚上猎头就说 feedback好, 问我要求多少钱 周六周日他家 VP 就跟我商量 offer 了, 其实我根本不想这么早就商量, microstrategy onsite 在下周呢 不过他们特别着急, 所以没办法, 就接了 offer是 85k 2000 股票无 bonus 周 3又去面了 microstrategy 电面是一个中国人面的, 本来 hr说面题都是 brain teaser, 结果问题完全是围绕我简历, 问的非常细致, 具体忘记了, 最后一个简单的 brain teaser onsite 一共 4 个人先做题 1小时, 本来是 1个半小时的题, 为啥就让我做 1 小时 题目不难, 除了一个题很傻, 条件不全让无知群众受害 给你 level order 的序列, 让你重建 BST. 还有一个 LCS 然后就是进来 2 个小兵, 看着就不是那种很聪明的人, 果然问的问题都很简单, 害的我还故意给他不好的方法, 然后给他点让我改进的机会 比如大小是 100的数组, 数的范围是 1-99, 有一个重复, 怎么找出重复的 我给的方案很多, 基本版面有的都给了 然后联系到排序问了我 2 个排序复杂度 接下去就是 brain tease, 设计模式的问题, 都不难 最后还有 8 分钟就把题目问完了, 只能让我问他们问题 我就发挥了下, 问了他们很多 接着是个 manager, 问了个比较新的问题, 但是办法很老 关于树的题目, 就用递归搞定 还问了我一个 OOP 的设计问题, 主要考我数据结构 反正我给他的方案他满意 到吃饭时间了, 于是一个美国人带我吃饭 天下没有免费的午餐, 果然是啊 路上先问我做过的 project, 又到我发挥了 说过 n 次的了, 当然不是问题 不过他还挺懂的, 我说的信号处理的东西他也能明白一些 接着该他发彪了, 智力问题是开胃菜, 然后就是线程同步问题, 如何解决死锁 还有一个 OOP设计问题, 设计一个高速收费站, 里面有 bar, 投币机器, 地下还有一个秤, 判断是不是卡车 我给的方案里面用到观察模式 老美的智力题也太老了, 问来问去就那些 最后我说我喜欢当面试官, 可以出题, 多好 吃完饭, 我以为还有几轮, 结果就是最后一轮了, 进来一个老印, 给我个名片 我居然没看... 我知道他有点来头, 表情就没其他人那么和蔼 问我为啥 EE的找 CS 工作, 我说我擅长写软件, 而且算法, 数据结构是强项 以前读 EE 完全是因为对图像处理有兴趣, 然后被忽悠到匹大 结果来了发现没有老师有项目 接着给我出题, 就是一个查黄页的题, 问我 300万个名字, 一页有 1000

104 个名字的黄页, 要找到一个人的电话, 需要查几次 太简单了, binary search, log1500 然后问大概是多少 问完问我有什么问题, 我说他们的开始的 test 里面条件不全, 希望他们能改了 还有如果有 offer 什么时候通知, 我着急 他说 1周, 我说我有 offer 等, 他说尽快 他好像有事, 着急就走了 GLM. 这个包括了整个过程, 从一开始的 data cleaning and transformation, outlier detection, missing value related..., etc. 到 mulitcollinearity detection, variable/model selection, model fitting 直至最后的 model validation & model diagnostics... 像 multicollinearity, model selection, cross-valid ation 这些问题, 一定会问, 屡试不爽 2. data mining 需要指出的是, 由于 regulation的限制, GLM是 credit risk modeling的主流方法, fancy的 model 一般来说没啥用武之地 ( 实际上也有论文指出, SVM和 boosting之类的方法, 对于 credit scoring data 来说表现并不比 Logistic Rregression 更好 ) 但也有银行要求有 data mining的技术, 一般用于 marketing和 behaviral modeling 一般来说, 需要的 data mining methods会在 job requirement 里说清楚 这个没啥好说的, 太多细节了, 自己掌握吧 3. SAS. 主要是 data step, proc sql, macro. 以及上面说的 1和 2相对应的 proc 4. 简历相关的一切技术问题 像我在招工上篇说的, 这个答不好是诚信问题 要把简历上的东西和衍生的所有细节都倒背如流 5. 统计的基本概念, 以及如何 communicate with non-technical audiences. 比如说, 要如何不用任何统计术语来解释 p- value, confidence interval, model inferences 等等 6. 其他一些零散的统计和数学知识, 比如说 experimental design, six sigma, econometrics, optimization.. 1. 回答要有层次 举个例子, how to do model selection? 比较一下这三个答案 A: I use forward/backward/stepwise... blah blah... B: I know three methods, subset selections(forward/backward/stepwise), PCA, shrinkage method (ridge/lasso). I prefer PCA...blah blah... C: Many people used to prefer forward/backward/stepwise because of its easy computation and straightforward interpretation. However it has some severe problems, e.g. unstable estimations and unable to deal with multicollinearity. Harrell's 2001 paper has detailed discussion. I personally prefer PCA, if there is a good interpretation for those principle components. If it's not the case, shrinkage method may be a better choice. Ridge regression offers a biased but less-variance prediction, however it is not really about "selection" since its shrinking process is continuous. Instead, LASSO truncates some coefficients at 0 and thus discards those correspondent variables, blah...blah...i usually implement those methods in Proc glmselect, blah... blah... However, the most important are the stories behind the data. Instead of using some fancy statistical stuff, some experts knowledge and business context are more necessary for selecting the right model. blah, blah... 喜欢那个版本的答案应该很清楚了, 组织一个既有深度和广度, 又有条理的答案会有 interviewer 很大加分 当然这个只是一个例子, 我的水平还不够写出足够有深度的答案, 希望大牛们可以就这个问题发表自己看法

105 2. 一定要准备好问 interviewer 的问题 可以反问一些技术问题, 比如说, 你们在实际中是怎么搞 model selection 的 ( 有个 HM 有点尴尬地说他们就在用 stepwise, 在我说了 stepwise 的一堆缺点之后 ), 你们怎么 evaluate models, etc... 在这里需要严重指出的是, 咱们中国人比老美或者阿三强的就是技术, 所以在面试里要最大程度地表现出自己的技术优势 但是, 不是每个 interviewer 都有备而来, 他们可能只准备了一些很简单的 TQ, 让你的技术优势无从体现 这时候可以反问一些他们没有问的技术问题, 然后在相互讨论中将准备好的答案说出来, 这样就可以让 interviwers知道你其实也懂这方面的知识 另一类问题是跟职位相关的, 比如说这个职位的面临的最大挑战是啥, 这个部门在整个公司起到的作用等等 问这类问题, 是为了表现 1. 你有备而来 ; 2. 你对这个职位很感兴趣 还有一些问题需要即席发挥, 就 interviewer的 introduction的内容发问 这个没法准备, 不过有个小窍门可以分享 -- 很多时候, 几个 interviewer会有内容雷同的 introduction 如果你反应不够快不能及时发掘出有意义的问题, 可以留到下一个 interviewer 再问 总的来说, 问问题的重要性不比答问题的低 而且还有一个窍门在里面 -- 你问的问题多了, interviewer 问你的时间自然就少了, then we can take the control and hide our language weakness... 当然要谨记的是, NO STUPID QUESTIONS!! 3. 抓住一切可以主动表现自己的机会, 比如说 self introduction和 presentation self intro 就不细说了, 任何一本面试的书都会介绍应该怎么组织 我觉得 presentation需要两点, 一要有趣味性, 二是要全面 我当时 onsite做的 ppt 尽量减少文字, 多用图表, 还准备了一个切题的暖场小笑话 至于内容, 我一开始先介绍了我现在做的 project 的理论背景 和 literature review, 尽量简短, 没有任何数学推导, 只给出结论和 reference 然后讨论了 simulation和 data analysis, 还详细说了一下我在 sas中是怎么实现这个比较新的算法的 最后我还说了一下这个算法在 credit risk modeling 的应用和它的局限性 老板和同事们反应非常热烈, 屡屡中途打断我问技术问题, 原定半个小时超了半小时 2. Just had interview with Goldman Sachs, : "Trading Analystics". I think I failed, but I share : with you their questions. : : Stochastic Calculus : 1) Is it obvious that Brownian Motion B(t) is a martingale? : and B(t) square? B(t) is, B(t) square is not. The expection of B(t)^2 is t, so B(t)^2 -t is a martingale. : 2) Can you integrate B(t) square? Or which formula do you : use? Use ITO formula.

106 : : : Probability : Two people wants to flip a coin to decide who will use : black : in a "go" game. They suddenly found that this is not a : fair coin, : what should they do? Now head-tail and tail-head become equal probability events. : : Algorithm : 1) I have a file with unknown length, with characters in it. : You can : only read the file sequentially. How do you pick a : character, so that : the chance of picking it, is equal to pick any other one :? The idea is, at any step, you save one character from the previous character set. : 2) Give me an example of n*log(n) sorting algorithm. See any C Book. : : Programming : 1) What is Virtual Funtion in C++? See any C++ Book. : 2) What is "Associate Arrary" in Perl? See any Perl Book. : 3) How do you choose all variable in a table using SQL? create table A as select * from table B : : Computer Basics : 1) What is the Unix command which give you number of lines : in a file? nl 3. : 2) What is the Unix command which shows file names in a : directory? inheritance vs composition 2. what is clonable 3. what is shallow copy & deep copy. how to do deep copy without immplement

107 clonable 4. what is transient 5. say something about java collection framework. what are the common method of class Collection. 6. how to immplement a hashmap. how does hashmap immplemented in java 7. public static final Map m = new HashMap(); can you do m.put("k", "v")? 8. how does factory pattern work. 9. some of my previous project person # 2: 1. how does java permanate generation & young generation work? ( 我一下就死菜了 ) 2. what's the difference of synchronized method and synchronized block what is read/write lock. how does reentrance lock work. 3. how does ExecutorService work. How does executor recieve/handle the status/feedback of each thread. 4. how does Future work 5. how does Semaphore & Latch work 3-5 need to write sample code person # 3: 1. how to find intersections of two collections. how to improve the performance. what if there are dulicated elements in those collections. 2. what is trie map, how to build it 3. some of my previous project Another group: test: 1. find fibonacci f(n) using efficient algorithm. I used the matrix multiplication method but didn't write the correct code. lol 2. three register, A,B,R, three operations A->R, B->R, (A-R)->R, how to do B ->A 3. a very long java code to test your understanding about java argument passing person # 1: 1. SQL query. left/right inner join 2. how do you handle stress 3. how do you handle mistakes during work 4. lots of other behavior questions 5. some school project person # 2: 1. asked a lot about matrix multiplication for the fibonacci algorithm. however I didn't write it correctly so I had a hard time. 2. java reflection. write a method to return a thread by taking a string of class name which immplements runnable interface. what you need to take caution when do java reflection. what execptions does java reflection throws ( I said I don't remember... lol) 3. Thread.start() Runnable.run() what's the difference person #3: 1. explain string literal. will gc recycle a string while it has a reference in string literal? 2. compound SQL queries

108 3. HashSet problem ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// SAS Programer Position 1. What kind of AE tables are there? 2. What difference between proc means and freq? 3. What does run statement mean? 4. What is ITT? What assessment in ITT definition is? 5. Which procedure can produce standard deviation of a variable? 6. What do put and input functions do? 7. How to validate your program? 8. How to identify TEAE? Namely, what variables can tell us if a patient is TEAE? 9. What differences between scan and substr? 11. What is MedDRA? 12. What does the statement break do? 13. How to code options for estimate and contrast? Are there any differences between them? 14. What PROCs do you use for drawing a graph? How to code for X direct and Y direct when coding for graphs? 15. How to remove format? 16. Is there any difference between macro BBB (a, b) and BBB (a=, b=)? 17. What Macro functions have you used? 18. In proc report, what difference between group and order? 19. How to validate data? 20. What procedures can perform linear regression analysis? 21. What procedures can conduct statistical analysis for categorical data? 22. What difference between Chi-square test and Fisher s exact test? 23. Which dataset is on the left hand side in the merging the two datasets A and B? 24. What do we need to pay a special attention to a matching merge? 25. Have you used ODS? How to organize SAS output (e.g. p-value, odds ratio, 95% confidence interval) into a table using ODS? 26. What is %eval for? 27. How to create a macro? 28. How to create a macro variable? 29. How to pass a macro variable? 30. What difference between global and local macro variable? 31. What lab tables did you worked on? 32. Have you accomplished a shift table? 33. How to avoid changing the raw dataset when you work on proc sort? 34. Except proc report what else do you use to produce a table? 35. What is ID statement in Proc transpose? 36. In proc format, what are value and picture? 37. What is difference between having and where in proc sql? 38. What are the two types of parameters that is available in macro? Any difference between them? 39. What kinds of lab datasets are there? 40. Are there any other datasets have we encountered? 41. What is macro routine? 42. When do you use ARRAY, MACRO and SQL? 43. What macro functions have you used? 44. How to do validation? 45. How to implement LOCF?

109 46. Why use SAS arrays? 47.What kind of p-value have you encountered? 48. What difference between data step functions and macro functions are? 49. What difference between macro (A=,b=) and macro (A,B)? 50. Macro debug options 51. How to code LOCF? 52. Explain why NOTE: MERGE statement has more than one data set with repeats of BY values. appears in log file when we merge datasets. 53. Tell us about your self and your current work. 54. What is your strength as a SAS programmer? 55. What is your weak point as a SAS programmer? 56. How to tell if a program is good or not? 57. What part of SAS do you like most? 58. Which part of SAS is more difficult for you? 59. What is the difference between where and if? 60. What proc have you used most often? 61. Data both; merge demog (keep=sex race ) vitals; run; what do you think about this program? 62. If I have a very long string, how can you get only last character? 63. What is the most difficult problem when you program and how you solved it? 64. What is difference between sum(a, b) and c=a+b? 65. What components does the Macro Language contain? 66. Any difference between %let and call symput? 67. What advantages does Macro have? 68. What options do SAS have? What are differences between statements and options of drop, keep, rename? A SAS technical interview typically starts with a few of the key concepts that are essential in SAS programming. These questions are intended to separate those who have actual substantive experience with SAS from those who have used in only a very limited or superficial way. If you have spent more than a hundred hours reading and writing SAS programs, it is safe to assume that you are familiar with topics such as these: SORT procedure Data step logic KEEP=, DROP= dataset options Missing values Reset to missing, or the RETAIN statement Log Data types FORMAT procedure for creating value formats IN= dataset option Tricky Stuff After the interviewer is satisfied that you have used SAS to do a variety of things, you are likely to get some more substantial questions about SAS processing. These questions typically focus on some of the trickier aspects of the way SAS works, not because the interviewer is trying to trick you, but to give you a chance to demonstrate your knowledge of the details of SAS processing. At the same time, you can show how you approach technical questions and issues, and that is ultimately more important than your knowledge of any specific feature in SAS. STOP statement The processing of the STOP statement itself is ludicrously simple. However,

110 when you explain the how and why of a STOP statement, you show that you understand: How a SAS program is divided into steps, and the difference between a data step and a proc step The automatic loop in the data step Conditions that cause the automatic loop to terminate, or to fail to terminate RUN statement placement The output of a program may be different based on whether a RUN statement comes before or after a global statement such as an OPTIONS or TITLE statement. If you are aware of this issue, it shows that you have written SAS programs that have more than the simplest of objectives. At the same time, your comments on this subject can also show that you know: The distinction between data step statements, proc step statements, and global statements How SAS finds step boundaries The importance of programming style SUM or + Adding numbers with the SUM function provides the same result that you get with the + numeric operator. For example, SUM(8, 4, 3) provides the same result as Sometimes, though, you prefer to use the SUM function, and at other times, the + operator. As you explain this distinction, you can show that you understand: Missing values Propagation of missing values Treatment of missing values in statistical calculations in SAS Why it matters to handle missing values correctly in analytic processing The use of 0 as an argument in the SUM function to ensure that the result is not a missing value The performance differences between functions and operators Essential ideas of data cleaning Statistics: functions vs. proc steps Computing a statistic with a function, such as the MEAN function, is not exactly the same as computing the same statistic with a procedure, such as the UNIVARIATE procedure. As you explain this distinction, you show that you understand: The difference between summarizing across variables and summarizing across observations The statistical concept of degrees of freedom as it relates to the difference between sample statistics and population statistics, and the way this is implemented in some SAS procedures with the VARDEF= option REPLACE= option Many SAS programmers never have occasion to use the REPLACE= dataset option or system option, but if you are familiar with it, then you have to be aware of: The distinction between the input dataset and the output dataset in a step that makes changes in a set of data The general concept of name conflicts in programming theory Issues of programming style related to name conflicts How the system option compares to the corresponding dataset option A question on this topic may also give you the opportunity to mention syntax check mode and issues of debugging SAS programs. WHERE vs. IF Sometimes, it makes no difference whether you use a WHERE statement or a

111 subsetting IF statement. Sometimes it makes a big difference. In explaining this distinction, you have the opportunity to discuss: The distinction between data steps and proc steps The difference between declaration (declarative) statements and executable (action) statements The significance of the sequence of executable statements in a data step Some of the finer points of merging SAS datasets A few points of efficiency theory (although tests do not seem to bear the theory out in this case) The origin of the WHERE clause in SQL (of course, bring this up only if you re good at SQL) WHERE operators that are not available in the IF statement or other data step statements Compression Compressing a SAS dataset is easy to to, so questions about it have more to do with determining when it is a good idea. You can weigh efficient use of storage space against efficient use of processing power, for example. Explain how you use representative data and performance measurements from SAS to test efficiency techniques, and you establish yourself as a SAS programmer who is ready to deal with large volumes of data. If you can explain why compression is effective in SAS datasets and observations larger than a certain minimum size and why binary compression works better than character compression for some kinds of data, then it shows you take software engineering seriously. Macro processing Almost the only reason interviewers ask about macros is to determine whether you appreciate the distinction between preprocessing and processing. Most SAS programmers are somewhat fuzzy about this, so if you have it perfectly clear in your mind, that makes you a cut about the rest and if not, at least you should know that this is a topic you have to be careful about. There are endless technical issues with SAS macros, such as the system options that determine how much shows up in the log; your experience with this is especially important if the job involves maintaining SAS code written with macros. SAS macro language is somewhat controversial, so be careful what you say of your opinion of it. To some managers, macro use is what distinguishes real SAS programmers from the pretenders, but to others, relying on macros all the time is a sure sign of a lazy, fuzzy-headed programmer. If you are pressed on this, it is probably safe to say that you are happy to work with macros or without them, depending on what the situation calls for. Procedure vs. macro The question, "What is the difference between a procedure and a macro?" can catch you off guard if it has never occurred to you to think of them as having anything in common. It can mystify you in a completely different way if you have thought of procedures and macros as interchangeable parts. You might mention: The difference between generating SAS code, as a macro usually does, and taking action directly on SAS data, as a procedure usually does What it means, in terms of efficiency, for a procedure to be a compiled program The drastic differences in syntax between a proc step and a macro call The IMPORT and EXPORT procedures, which with some options generate SAS statements much like a macro The %SYSFUNC macro function and %SYSCALL macro statement that

112 allow a macro to take action directly on SAS data, much like a procedure Scope of macro variables If the interviewer asks a question about the scope of macro variables or the significance of the difference between local and global macro variables, the programming concept of scope is being used to see how you handle the new ways of thinking that programming requires. The possibility that the same name could be used for different things at different times is one of the more basic philosophical conundrums in computer programming. If you can appreciate the difference between a name and the object that the name refers to, then you can probably handle all the other philosophical challenges of programming. Run groups Run-group procedures are not a big part of base SAS, so a question about run -group processing and the difference between the RUN and QUIT statements probably has more to do with: What a procedure is What a step is All the work SAS has to go through as it alternately acquires a part of the SAS program from the execution queue, then executes that part of the program Connecting the program and the log messages SAS date values Questions about SAS date values have less to do with whether you have memorized the reference point of January 1, 1960, than with whether you understand the implications of time data treated as numeric values, such as: Using a date format to display the date variable in a meaningful way Computing a length of time by subtracting SAS date values Efficiency techniques With today's bigger, faster computers, efficiency is a major concern only for the very largest SAS projects. If you get a series of technical questions about efficiency, it could mean one of the following: The employer is undertaking a project with an especially large volume of data The designated computer is not one of today's bigger, faster computers The project is weighed down with horrendously inefficient code, and they are hoping you will be able to clean it all up On the other hand, the interviewer may just be trying to gauge how well you understand the way SAS statements correspond to the actions the computer takes or how seriously you take the testing process for a program you write. Debugger Most SAS programmers never use the data step debugger, so questions about it are probably intended to determine how you feel about debugging does the debugging process bug you, or is debugging one of the most essential things you do as a programmer? Informats vs. formats If you appreciate the distinction between informats and formats, it shows that: You can focus on details It doesn't confuse you that two routines have the same name You have some idea of what is going on when a SAS program runs TRANSPOSE procedure The TRANSPOSE procedure has a few important uses, but questions about it usually don't have that much to do with the procedure itself. The intriguing characteristic of the TRANSPOSE procedure is that input data values

113 determine the names of output variables. The implication of this is that if the data values are incorrect, the program could end up with the wrong output variables. In what other ways does a program depend on having valid or correct data values as a starting point? What does it take to write a program that will run no matter what input data values are supplied? _N_ Questions about the automatic variable _N_ (this might be pronounced underscore N underscore or just N ) are meant to get at your understanding of the automatic actions of the data step, especially the automatic data step loop, also known as the observation loop. A possible follow-up question asks how you can store the value of _N_ in the output SAS dataset. If you can answer this, it may show that you know the properties of automatic variables and know how to create a variable in the data step. PUT function A question about the PUT function might seem to be a trick question, but it is not meant to be. Beyond showing that you aren't confused by two things as different as a statement and a function having the same name, your discussion of the PUT function can show: An understanding of what formats are Your experience in creating variables in data step statements Important SAS trivia Some SAS trivia may be important to know in a technical interview, even though it may never come up in your actual SAS programming work. MERGE is a data step statement only. There is no MERGE procedure. PROC MERGE is a mythical construction created years ago by Rhena Seidman, and if you are asked about it in a job interview, it is meant as a trick question. It is possible to use the MERGE statement without a BY statement, but this usually occurs by mistake. SAS does not provide an easy way to create a procedure in a SAS program. However, it is easy to define informats and formats and use them in the same program. Beginning with SAS 9.2, the same is true of functions. The MEANS and SUMMARY procedures are identical except for the defaults for the PRINT option and VAR statement. Much of the syntax of the TABULATE procedure is essentially the same of that of the SUMMARY procedure. CARDS is another name for DATALINES (or vice versa). DATA _NULL_ is commonly used as a code word to refer to data step programming that creates print output or text data files. The program data vector (PDV) is a logical block of data that contains the variables used in a data step or proc step. Variables are added to the program data vector in order of appearance, and this is what determines their position (or variable number) attribute.

114 1. 我们知道, 从一个数组里找一段 ( 连续的 ) 子数组求最大和, 是一道经典的面试题, 方法很简单, 只要 O(n) 的时间 把这个问题变一下, 假设是一个循环数组呢? 找一个 size<=n 的子数组 with 最大和 分析, 很容易想到第一步, 找个地方把循环数组切断, 回到了原来的问题, 然后在考虑一下额外的情况 额外的情况就是 : 有可能最大和的子数组是跨越了切断点的? 这种情况的最大和怎么求呢? 一个 naive 的方法能做到 O(n), 但是需要 O(n) 的空间 巧妙的解法就是, 注意到所有数的和是固定的, 考虑切断后的非循环数组, 找一段从首开始 + 一段从尾开始的两个子数组 with 最大和, 等价于找一段子数组 with min sum. 总结, 要擅长利用等价性转换问题, 从而将新的问题转变为一个已知有好 solution 的旧问题 利用已知的经典问题来解决新问题, 可以说是面试题目中相当重要的一个技巧 2. largest rectangular problem: 问题是这样的, 一个 N M 的棋盘, 上面的数字要么是 1, 要么是 0, 那么要 :a) 最大的一个正方形全是 1 填充,b) 最大的全是 1 的矩形 a) 是用动态规划做, 虽然方法也很好, 但是这里就不提了 b) 问题感觉上要比 a 难很多, 为什么呢, 因为 rectangular 比 square 有更大的自由度 不好用 DP 来做, 分冶也不合适 这题的奥妙就在于, 利用经典问题 什么经典问题呢? 其实是另外一道面试题, 其本身也是有一定难度的题, 题目是 : 给你一个统计直方图, 假设每根柱子都是单位宽度, 从图的最左边一个紧挨一个排到图的最右边, 求在这个图里找到一个最大矩形, 它不跟任何直方柱相交 ( 边缘接触是允许的 ) 为什么提起这个题呢, 故事是这样的, 我之前没有做出 O(N*M) 解法的 largest rect 题, 后来有一天遇到了这个直方图的题目, 找到了很漂亮的 O(N) 解法, 猛然回顾起那道 largest rect 的题, 这次就很轻松的搞定了 3( 鸣谢 mittbbs jobhunting 版上的一位面试官贡献自己出的题 ) 有 n 个房间, 小偷每天偷一间, 偷的规律简单说就是随机行走, 如果今天偷了第 i 间屋子, 明天有一半的几率偷 i-1, 一半的几率偷 i+1, 注意如果刚好偷到了边界上, 那么第二天只有唯一的选择 如果你是警察, 你只能每天选择一个房间蹲守, 并且贼的手段相当高明, 偷了一个房间后, 没有任何人能发觉该房间是否曾经被偷过 提示 : 奇偶性 总结 : 注意观察题目中隐含的性质 4. wild card 匹配 + 搜索 : 假设你有一个 dictionary( 原题中是 URL 集合 ), 你要搜到到所有与 *a*bc*d 这样的输入所匹配的 words 这里,* 是通配符, 可以当成是任意个任意字符 ( 包括空 ), 怎么预处理 + 搜索? 如果输入是???a???b??cde 这类呢?? 代表单个任意字符 如果输入是? * 的混合呢? 有道题目最近频繁出现, 特地总结一下常规解法以及它的变体 有个经典变体我还没看到一个很经典的答案, 希望有人补上, 呵呵 1. The largest rectangle under a histogram Given: An integer array represents a histogram Goal: Find the largest rectangle under the histogram.

115 Key observation: 输入为一个整数数组 如果某元素比它两边的邻居都小 ( 比如 Ai), 那么高度大于 Ai 的矩阵要么在该元素左边, 要么在该元素右边, 不可能穿过 Ai 利用这个性质, 想办法遍历所有的矩形 Complexity O(N) where N is the size of the given array. 2. Maximum subarray with all 1 s. (Generalization of problem 1) Given A two-dimensional array b (M rows, N columns) of Boolean values ("0" a nd "1") Goal: Find the largest (most elements) rectangular subarray containing all o nes. Key observation: 从一边 ( 假设右边 ) 开始逐列扫描, 构造直方图 每次构造出直方图来, 用上面的解法求最大矩阵 每次构造直方图只需要 O(M), 解需要 O(M), 做 N 次 Complexity O(MN). 3. Given a binary matrix, find out the maximum size square sub-matrix with a ll 1s. (Specialization of problem 2) Key observation: 假设输入二位矩阵为 M, 构造辅助矩阵 S If M[i][j] is 1 then S[i][j] = min(s[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 Else /*If M[i][j] is 0*/ S[i][j] = 0 Complexity: O(MN) 4. Imagine you have a square matrix, where each cell is filled with either b lack or white. Design an algorithm to find the maximum subsquare such that a ll four borders are filled with black pixels. (variation of problem 3) 1. write a iterative function to calculate fibonacci sequence 2. what is the difference of Delete table and truncat table.(about sql & database) 3. what is ACID.(about sql or database) 4. write a find() for BST, How to decide the element could not be found.(( less than && No left child) (large than && no right child)) 5. how to reverse a link list using one point (should I use recursive calling)

116 6. find the sizeof(int) without using sizeof(). ( 大家可以讨论一下, 我用 (~ 0x0) 右移位做的, 但是不对方希望的答案 ) 7. main() folk(); folk(); folk(); printf("abc\n"); How many abc will be printed? 8. what is the difference between. kill proces_id kill -9 process_id 另外一家类似职位的电面, 全部是 stl 的问题, 很简单 1. new a vector, what is the size(), 2. how to prevent relocation when push elements into a vector. (reserve()) 3. why vector use relocation instead of chunks of memory.(keep compatible with C array) 4. how is deque implemented?(uses chunks of memory) 5. the different of set & map? what is the return value of find()? (an iterator of element ) 6. what is the member function needed to use set.find() or map.find().(less( )) 7. what if the element class doesn't have less() operator? (pass a functor to constructor as comparing function) 8. for loop to find a element in a vector, what is the method the class need to support? (equal operator) 9. For smart pointer, How it implement the reference counter(a pointer to a int or unsigned int) 1. count the number of 1s in binary representation 我用的 4 位 4 位 hash 的方法但是没有考虑负数情况, 在面试官提示下, 意识到对负数向右 shift, 发生的是 sign extension, 所以这题要先对输入进行检查 2. remove duplicates from linked list, suppose you can use stl list. 我用的 hash_set, 这题很顺利 3. 很长很长的 string/file, 要我找出中间重复次数最多的 character, character set 可能是任何 char set, unicode... 我说 mapreduce, 后来面试官说如果是一台机器,8 个 core, 1 个 process, 怎么办 我说似乎 mapreduce 需要在 distributed system 环境下 ( 但其实我不肯定, 如果一台机器多进程 / 多线程 ) 是不是就也可以 mapreduce). 面试官又给了提示, 我才说 multi-process, 后改成 multi-threading, 后来他问我那几个 thread 怎么写协调, 我说可以公用 data segment in the process space, 但是要注意锁的问题 最后他问我说 mapreduce 和 multi-thread 的 tradeoff, 我说 communication overhead, 似乎他对我的答案满意 我和面试官说 honestly 第一题我见过了 ( 我不知道这是不是画蛇添足了!!!!!) 哎总之虽然觉得自己答得还可以但是很担心!! 第二个人先问了一些暑期实习的项目问题 1. 设计一个 counte class, 写一个函数算某机器最后一分钟处理任务的个数 我说用 circular array, 他说 right way to go, 但是在细节上澄清了一会 不知道是不是我的表达不够好 2. vector of vector of ints, 请 implement bool hasnext() 和 int next() 我说要用

117 一个变量 track 在 nested vector 中的位置, 他提示用 2 个, 然后我开始 code, hasnext code 完了然后也解释给他, 似乎没有问题 next() 由于时间不够, 但我把逻辑解释完了, 把关键的那 4,5 行 code 出来 因为赶着年底毕业, 九月底才开始投简历 这个 offer 来的太快, 小 startup 就是动作快, 从十月初联系我, 到 offer, 就两周 那几个大公司的 on-campus interview 还都没开始 也算是 hot startup, 但这里肯定没人知道的, 移民版知道这个公司的更多些 就不透露公司的名字和考题了, 见谅 HR 联系之后, 先是组里的头直接电面, 问了一个他们实践中的问题, 我没想出答案, 但还是扯了扯 后来就在谈公司做什么, 我有准备, 问了很多问题 刚放下电话,HR 问我什么时候作 coding test, 可以马上把题发给我, 就是 fill Java class, 实现某些功能, 一般给 2-3 个小时 我想这么大工作量, 不能拖, 否则牵扯时间和精力, 就说马上作, 决定不准备了, 冒一定风险 结果一个小时做完发给他们, 小 impress 了一下 然后另一个 team lead 马上打电话二面, 顺便考察一下是不是真是我自己写的程序 这就是一天三面, 两电一编程, 然后就给 onsite 了 面了组里的 4 个 lead,hr 和 Founder 前两个基本都在问我的 research 和 big picture, 没有考我, 第三个问了两个经典算法, 属于偏简单的, 版上都有, 出现过很多次的 有一个我当时不知道, 提示着才做出来 感觉面试的时候脑子不是很转的开, 没有准备的话, 很多题都不可能马上想出来 反过来, 有准备的, 就当不知到结果, 从头把思路说一遍 吃午饭的时候, 拍了拍马屁, 开了开玩笑, 到下午果然放水 第一个人就问我 PhD 为什么不考虑 academic job, 这个之前 HR 也问过, 基本是 PhD 必问的 behavioral question, 一定要准备 我就说整天 synthetic data, abstract problem 不如实际的问题 motivating. 然后就是我在问他做什么东西, 追的很 detail, 就没他问我的机会了 第五个还是那个联系我的 HR, 人很精干, 办事效率高, 问了很多 behavior 的 你最想作又没机会做的, 我就说 leadership 还有什么你总做不好, 例子是 time management, work life balance, 我说了一些 research 的艰辛 还有你跟人关系处的不好的例子, 怎么解决的等等 最后是大老板,Founder, 向我夸赞他们的产品, 策略和公司影响, 还有公司的光明前景, 我们组的重要性, 还有股票来者有分, 听得我直流口水 Onsite 后第二天晚上就给口头 offer 了 要了 reference,background check, 第四天正式 offer, 但只给我一周答复实践 觉得工资低了点, 就大胆照着 Google 的 negotiate 了一下, 涨了一些, 达到了 Google PhD 的下限, 觉得知足了 我这样的, 去面 Google, 估计不到一成的胜率 再说其他面试经历, 年初有一个猎头从 linkedin 上找到我要给我介绍什么 DE Shaw, Two Sigma. 我说年底要毕业,thesis 还八字没一撇, 到时候再联系吧 到了九月底, 联系那猎头, 很热情的要了我的简历, 还帮我改了改, 说很好, 我马上给你投 DE Shaw, Two Sigma. 没两天就受到裸拒, 深受打击 后来一看, 也不冤 这是两个名 hedge fund 要不牛校 (MIT, Stanford, Berkley, Ivy 级别的 ), 要不拿过竞赛奖的, 否则基本不会考虑你 恍然大悟, 原来这个该死的猎头本着中六合彩的心态拿我撞运气 从此发现了可以走 quant dev/strategist 这条路 从九月底, 先投了两个 wall street 的 第一个是作 CDO 相关的 quant strategist, 过了 coding test, 和两轮 phone interview, 然后问我什么时候来纽约, 好安排 onsite. 我说你得出钱呀, 被告知他们一般只招 local, 早说呀 费这么半天劲, 就当练手了 另一个是 hedge fund 的 data specialist, 通过另一个猎头找的 面试我的是中国人 team lead 由于被 DE Shaw, Two Sigma 拒的神经错乱, 整天想着牛校, 在结束之前竟然问人家是什么学校出身, 被不愉快的谢绝回答 以为就完蛋了, 猎头打来电话说不错, 继续 二面又是一个中国同胞, 感觉比一面还好些, 最后又问人家是什么学校出身, 不长记性, 又被不愉快的谢绝回答 至此就没消息了 肯定是觉得我人品有大问题 如果二位在版上混, 请不要见怪 这两个公司, 除了经典算法题如 longest increasing subsequence, linear time selection, verify if S1 is substring of S2, 还都问了很多 C++, Java 概念题,

118 如虚函数, 如何用 destructor 实现 exception safe code, 顺便提及为什么 Java 不需要 destructor? 因为 Java 有 garbage collection, 但是 Java 如何 safely release external resource in case of exception? 答案是用 try/finally. 用 finalize 也可以, 但不是同步的 (asynchronous) 还问了 smart pointer, reference counting, Java garbage collection, 这些都是相关的 也投了一些其他的金融类, 都默拒了 看来还是找猎头好, 至少不会默拒 上周和这周 on campus 面了 Microsoft, Epic, Amazon, Facebook Microsoft: 从 numeric array 里找两个数之和最大 刚开始还以为是经典的找和为固定值的两个数, 其实这个更简单 找最大的两个数就行 Simple O(n) algorithm. 都没有让优化到 N+lgN-2 个 comparison. Instead, 让考虑意外情况, 比如数字太大, 加起来 overflow 怎么办. EPIC: 竟然没有 technical question!( 干什么来的?), 跟我套了套近乎, 说他 N 年以前选过一门 database 的课, 跟我写在简历上 TA 的是同一门课, 同一个 professor. 我说现在教的很不一样了, 顺便吹了吹 继续说到他们在用一个很老很奇怪的 database 叫什么 CHRONICLE 之类的,70 年代他们 CEO 自己写的, 现在还在用 还属于 postrelational database, 我后来在 Wiki 上也没找到这个什么 Chronicle. 又说他们还在用 VB, 小惊讶了一下 后来在 Glassdoor 上看了一下 EPIC 的员工 review, 很多人在抱怨 working on legacy code, old technology 尽管 EPIC 在 healthcare 里占有很大份额, 但得不到什么技术上的提高, 作码工还是那种最累的, 从 H1B visa 纪录看,pay 的也不是很好的样子 劝大家能不去就不去 一家之言 Amazon: 这回是经典的从 array 里找两个数, 和为一个特定输入的值 一种是用 hash, expected O(N) time, 一种是 sort 之后从两头往中间 scan, O(NlgN) 第二题是 verify that a binary tree is a binary search tree. 就是 recursive in-order traversal, 然后看是不是都是单调递增 如果不用多余空间, 只要再用到一个全局变量记录上一个访问节点的数值就行了 当时脑子短路, 提示了一会儿才想出来 这两个都要再纸上写 code, 他们存档讨论 Facebook: 把一个 binary tree 变成 double linked list 也是写一个 recursive inorder traversal, update pointer 的时候稍微有点 tricky. 第二题是经典的计算 x/y 不用 division operator. 我说用 log 和 exp, 他说可以 又问这些也不能用怎么办 提示了一下 x, y 都是正整数的话, 从 x 减去 y 一直减到 0, 看要减多少次, 很 obvious 是 bisection 了 面完之后说我肯定第二轮 on campus 了, 如果过了就是 onsite 后来 recruiter 打来电话说根据我问的问题, 他们决定让某个比较 match 的组约电话 interview 时间, 马上会联系我, 而不是继续下一轮 on campus 等了一天还没消息, 不知到是不是传说中婉拒的最高境界 这些大公司都只过了一轮, 题也比较简单, 见笑了 手头 offer 催的紧, 觉得不算太差,base pay 的和 google 也差不了太多,potential bonus 比例还高些, 但要看公司业绩, 所以很可能是望梅止渴 Stock 给的也没 google 值钱, 不过 YY 起来还够用 还要赶着写论文, 就决定从了 另外说一下 Facebook 现在给的 stock 确实很诱人, 我委婉问 interviewer 他有多少股 (2 年员工 ), 是不是很有钱了 感觉他有上 10 万股, 但很 frustrated 的样子说, 不 IPO 就跟废纸一样 也许是怕我嫉妒他 听说二手市场买卖 facebook 的 share 有一定的成交量, 但不知到是不是有限制, 所以伦不上小喽啰门 最遗憾的是没有试试 Google 找好了递简历的同学, 但是一直觉得没准备好 想放到最后 估计现在去了也白给 手头只有一个 offer 就从了, 但从各方面分析, 也只能这样了 现在只剩一个月写 thesis 了, 八字才刚有一撇 :( Yahoo 电面印度人 1. 电话键盘上 1- abc 2->cde... 现在来一堆数, 未知长度, 比如 请输出序列可能对应的所有字符串比如 123 输出 acf, acg, ach, bcf...

119 2. 检测链表是否有环 3.sql 语句 employee(id(primary key),name) employee_bonus(id(primary key), bonus) ( 现在觉得这题似乎有点问题, 因为他和我说 id 可以对应多个 bonus, 那这还算是 primary key 吗 ) 请写 sql 输出 name 和这个人 bonus 总和 MS on campus interview - first round 1. 简历问题 2. 给一个字符串检测是否是 valid ip address, 这题他似乎是想看看我的思路, 我说 regular express, 他说要 code, 我就写了一些, 解释了一下 总之, 这题真要追究起来, 细节颇多, 但因为我们每个人都只有 30 分钟, 所以他没有要求完美的答案 我知道的其他 ms 校园面试题 1. bst 删除一个节点 2. 矩阵, 每行从左到右递增, 每列从上到下递增, 找一个数 Amazon 所有轮的题目 1. 数一个字符串中的单词数 2. 经典的一堆数只有一个出现 2 次其他数出现一次怎么找出那个重复的数 请给出 4 种以上解法 包括 brute force longest palindrome. 4. design restaurant reservation system. 5. atoi, 只能用一个 loop. 要考虑 -213, 2-13, a 各种情况 这题看似简单, 但是要小心, 容易出错 6. design a phonebook, 要求输入人名的时候电话随之更新 比如 a 给出一个电话, abc 给一个,abcd 再更新给出一个电话 trie 的 implementation, 假设每个节点存一个数据和 26 个指针 7. c++ 中 static 和 virtual keyword, 请解释用法 amazon 给我的感觉就是算法不一定很难, 但喜欢考 oo design. 1. 一个 rotated 的排序整数数组, 比如 A=[6,8,1,2,4,5], 写 code 找一个给定元素, 并分析复杂度 其实就是 binary search 的变体, 但是需要考虑两种 A[m] 中值的情况加以判断 2. 他谈到 facebook 的 log, 如果每个 log 文件有 10 billion 行, 每行包括 timestamp, user_id, visited page 三个 field 如果高效的统计一个月内用户访问量最多的十个网页 假设文件已经按照 timestamp 排好序了 不用写 code, 谈想法就成 我的解法是, 如果内存足够, 建立一个 < 网页, 访问数 > 的 hash 表, 每读入一条记录, 该网页 key 对应的项加一 但是加入内存不够大, 可能需要 map reduce 方法 面试官马上说, 内存根本不是问题, 用个 4G 或者 8G 内存来算这个月访问量很值得, 不要省内存 然后我说, 那 hash 表就好了 面试官表示赞许, 接着提出引申问题 : 3. 假设我们已经算了一个月的, 如果这个滑动窗口要往前移动一个 delta 量, 就是说, 已经算好 timestamp=[t_1..t_x] 区间的访问量, 要计算 timestamp=[t_2..t_x+1] 的访问量, 提出高效算法 当然, 最 brute force 的方法就是针对 [t_2..t_x+1] 再建一个 hash 表, 显然这不是面试官想要的 我提出来, 可以建个 multi-level hash 表, 外层为网页, 内层为 timestamp, 但是仔细想想也不算好 面试官也没说他们的解法是啥 1 external sort 2 一道正态随机的题目 我到现在还不太明白 3 print BST in level order 4 实现 linkend 里查找两个人之间 connection 的功能 ( 如果每人有 100 个熟人, 假设任

120 何两个人之间只隔 6 个人, 需要 space 100^6, 内存放不下 所以改用同时从两边 bfs, 需要 space 2*100^3) 5 合并两个直方图, 新图是原来两图的和 ( 直方图用点的 array 储存, 比如一个直方图有两个矩形 :x 2-3, y 4; x 3-5, y 3. 表示成 (2,4), (3,3), (5,0). 计算的新图点对就类似成 combine two sorted array 了 ) apple 网投, 一个月后 phone 1 c++ 的多态有哪些实现方法 ( 继承,template specification, 好像还有一个, 忘了 ) 2 为啥用 mutex(to avoid unstable states) ebay 网上投简历,1 轮 phone interview+onsite. onsite 从 9 点面到 6 点, 一个小时一个人, 累死了 签了保密协议, 具体题目就不说了 ( 能记住的只有下面这些了 ) 1 design patten. factory method, factory, visitor, bridge, class design. 2 反转 link list 3 external sort 4 实现查找两点间最短路径 5 1 堆数, 找出所有和为定值的三个数 #include <stdio.h> void permutation(char * p_str, char * p_begin) if(!p_str!p_begin) return; /* * If p_begin points to the end of string, * this round of permutation is finished, * print the permuted string. */ if('\0' == *p_begin) printf("%s\n", p_str); /* Otherwise, permute string. */ else char * p_ch; for(p_ch = p_begin; *p_ch!= '\0'; ++p_ch) char temp; /* Swap p_ch and p_begin. */ temp = *p_ch; *p_ch = *p_begin; *p_begin = temp; permutation(p_str, p_begin + 1); /* Restore p_ch and p_begin. */ temp = *p_ch;

121 *p_ch = *p_begin; *p_begin = temp; int main(int argc, char * argv[]) char strr[4]="123"; char strd[4]; permutation(strr, strr); return 0; UTF8 解码器线段 overlap 死锁机制 fair streaming sample 最不好的是, 忘记可以用 bitmap 记录 sparse data, 选择了 hashtable. 最近开始准备 OO design questions, 这两天学习了一下 design pattern, 用 Amazon 了 经典的 Hotel Reservation OO Design 的问题练习了一下 希望能和版上各位高手交流一下 (1) 问题 1: 这个 system 应该就那些类在 version 1 设计, 我定义了如下类 Room, SingleRoom, DoubleRoom, SuitRoom, Hotel, Customer, Reservation, Date 因为感觉这个 design, 主要就是如何设计 check different types of rooms' availability 和 make reservation (2) 问题 2: 这些类的关系应该如何 其实就是 "has-a" and "is-a" 的设计, 也就是用 inheritance 或是 composition 根据直觉定了了如下的 UML 图 以上两步估计大部分人都能得道, 不过如何才能打动 interviewer 呢? 怎么才能提高这个设计呢? 我想可以从两各方面入手 :(1)program with interface ( 不过这个好像是 java programmer 的 rule) (2) 多用 design pattern, 因为 design pattern 能 decouple code, 这样就能提高 code 的

122 resuability. 在什么情况下, 如何使用 design pattern 就是门学问了, 需要经验阿! 不过对于这个问题, 我想了些改进方法 (3) 问题 3: 如何 create object 用 factory method pattern 来建造不同的 Room object, 虽然目前的 design 只有三个 Room-based classes, 不过随着以后系统复杂度的增加, 可能回有 n 个 Room-based classes 我猜想 design 的时候考虑日后扩展的 flexibility, 应该也是 interviewer 喜欢看到的把 (4) 问题 4: 如何 hold 多个 Room-based objects 是用一个 list 来 hold 所有的 SingleRoom, DoubleRoom, SuitRoom 的 object, 还是用三个 list 来 hold 各自的 object? 这个没有想好, 目前就用了一个 list, 因为估计总 room 的数目不会太大, 对单个 list 进行 iterate 的效率不会太差 (5) 问题 5: 如何有效的 check availability. 假设有一个 customer 要查询每种 room 从某天到某天的 availability, 那么需要对所有的 Room subclasses 都定义一个查询函数 checkavailabity() 这样的话不是很好的 design 因为日后要加其他的查询 : 如 Room 的朝向 ( 如, 有没有 view 之类的 :-)), 那又再改 interface, 然后对所有的 classes 添加函数 麻烦! 所以, 我考虑用 strategy pattern 可以日后 extend 各种查询 (6) 问题 6: 找到 availability, 如何设计 reservation 回想一下,make a reservation 其实需要多个步骤的, 需要填用户信息, 需要填信用卡 ( 如果是 pre-pay 的话 ), 需要计算 tax, 还可以用 discount code 的, 最后得到 total amount 这些步骤都是 sequential 的, 有一定的次序 所以我们可以用 builder pattern 来 generate 所有这些步骤

123 写个 code( 看下面 link), 欢迎各位排砖 -- 修改 : langqinren 於 Nov 13 10:29: 修改本文 [FROM: ] 来源 : WWW 未名空间站海外 : mitbbs.com 中国 : mitbbs.cn [FROM: ] 此主题相关图片如下 : HotelReservation.gif (5967 字节 ) [ 删除 ]