google interview summary

1. balance speed and accuracy
(think twice before start, think if there is a better data structure)

2. do not be overwhelmed by stl
especially those i am not familiar with.

3. make ur program as simple as possible. if for loop is too complicated, use while. if need temp variable, then use it, if need to start with a big complexity, then do it. improve it little by little. (simplicity avoid corner case)

4. it is more important to keep clear logic rather than rushing fast.

some classical problems

1. divide and conquer

see:  http://www.cse.ust.hk/faculty/scheng/comp3711h/notes/array.pdf

can also use our method of BST.

both nlogn

2. closest pair

divide and conquer

3. minimum spanning tree:

prim's algorithm

kruskal algorithm

Dijkstra’s algorithm and prim's algorithm

skyline problem: divide and conquer == search + bst

Teris problem

http://www.careercup.com/question?id=14099679


#include<iostream>
#include<map>
#include<algorithm>

using namespace std;

typedef map<int,int> Map;

Map FindOverNth(int arr[],int size,int n)
{
Map ret_map;
typedef Map::value_type Elem;
int total=0;
for_each(arr,arr+size,[&,n](int val)
{
auto ret_pair=ret_map.insert(Elem(val,0)); //no duplicates!
++(*ret_pair.first).second;++total;
if(ret_map.size()==n)
{
for(auto iter=ret_map.begin();iter!=ret_map.end();)
{
--(*iter).second;
--total;
if((*iter).second==0)
ret_map.erase(iter++);
else
iter++;
}
}
});
for_each(ret_map.begin(),ret_map.end(),[](Elem &elem){elem.second=0;});
for_each(arr,arr+size,[&ret_map](int val){if(ret_map.find(val)!=ret_map.end())ret_map[val]++;});
for(auto iter=ret_map.begin();iter!=ret_map.end();)
{
if((*iter).second<=size/n)
ret_map.erase(iter++);
else
iter++;
}
return ret_map;

}

random access of stl

set<int>::iterator iter=test.end();

iter=iter-1; //not allowed!!

iter--; //allowed

deque...

iter=iter-1;//allowed

list...

iter=iter-1;//not allowed!
iter--;//allowed

string matching

void preMap(char *x,int m,int mpNext[])
{
int i,j;
i=0;
j=mpNext[0]=-1;
while(i<m)
{
while(j>-1 && x[i]!=x[j])
j=mpNext[j];
mpNext[++i]=++j;
}
}

void MP(char *x,int m,char* y,int n)
{
int i,j,mpNext[256];
preMap(x,m,mpNext);
i=j=0;
while(j<n)
{
while(i>-1 && x[i]!=y[j])
i=mpNext[i];
i++;
j++;
if(i>=m)
{
cout<<x<<endl;
i=mpNext[i];
}
}
}

C++ revisited

1. const and reference members may only be initialized, never assigned.

2. list members in an initialization list in order in which they are declared.
- static data members are initialized only once.
- base class data members are initialized before derived class data members.
-virtual destructor must be defined

3. ps1->Shape::draw();   //explicitly call base function

4. a summary of public/private inheritance and friend:

- public and private inheritance can access public and protected members of base class;
- public and private inheritance cant access private members of base class;
- an instance of derived class
           --public inheritance can access public members of base class
           --private inheritance cannot access public members of base class

class B
{
friend class A;
friend B operator+(B b1, B b2);
}

A can access private members of B;
+ can access private members of B;

a very interesting problem

if you see O(n). dont hesitate just do linear traversal

http://www.careercup.com/question?id=14912744


void PrintReverse(int i,int j)
{
for(int k=j;k>=i;k--)
cout<<k<<endl;
}

void WritePermu(string signature)
{
int N=signature.length();
int lasti=1;
for(int i=0;i<N;i++)
{
if(signature[i]=='I')
{
PrintReverse(lasti,i+1);
lasti=i+2;
}
}
PrintReverse(lasti,N+1);
}

it can also be solved using topological sort

tree bfs

void FindNode(Node* root)
{
deque<Node*> queue1,queue2;
queue1.push_back(root);
int level=0;
Node* last_node=root;
while(!queue1.empty() || !queue2.empty())
{
if(!queue1.empty())
{
Node* cur_node=queue1.front();
last_node=cur_node;
if(cur_node->L)
queue2.push_back(cur_node->L);
else if(cur_node->R)
queue2.push_back(cur_node->R);
queue1.pop_front();
}
if(!queue2.empty())
{
Node* cur_node=queue2.front();
last_node=cur_node;
if(cur_node->L)
queue1.push_back(cur_node->L);
else if(cur_node->R)
queue1.push_back(cur_node->R);
queue2.pop_front();
}
level++;
}
cout<<last_node->val<<endl;
}

backtracking using stack/deque

void GetSentence(string text,vector<string> dictionary)
{
deque<pair<string,int>> my_deque;
hash_set<string> my_hash;
int N=dictionary.size();
vector<int> temp(text.length());
fill(temp.begin(),temp.end(),-1);
for(int i=0;i<N;i++)
my_hash.insert(dictionary[i]);
my_deque.push_back(pair<string,int>::pair("",-1));
while(!my_deque.empty())
{
pair<string,int> top_string=my_deque.back();
int cur_pos=top_string.second;
if(cur_pos==text.length()-1)
break;
bool flag=false;
for(int i=cur_pos+1;i<text.length();i++)
{
string sub_string=text.substr(cur_pos+1,i-cur_pos);
hash_set<string>::iterator iter=my_hash.find(sub_string);
if(iter!=my_hash.end() && i>temp[cur_pos+1])
{
my_deque.push_back(pair<string,int>::pair(sub_string,i));
temp[cur_pos+1]=i;
flag=true;
break;
}
}
if(!flag)
my_deque.pop_back();
}
if(!my_deque.empty())
my_deque.pop_front();
while(!my_deque.empty())
{
pair<string,int> cur_pair=my_deque.front();
my_deque.pop_front();
cout<<cur_pair.first<<" ";
}
cout<<endl;
}

tree post order traversal using stack

int GetDiameter2(int& height)
{
if(!root)return 0;
stack<Node*> s;
s.push(root);
Node* prev=NULL;
int res=0;
while(!s.empty())
{
Node* cur=s.top();
if(!prev || prev->L==cur || prev->R==cur)
{
if(cur->L)
s.push(cur->L);
else if(cur->R)
s.push(cur->R);
else
{
s.pop();
cur->tmp=1;
res=max(res,1);

}
}
else if(cur->L==prev)
{
if(cur->R)
s.push(cur->R);
else
{
s.pop();
cur->tmp=cur->L->tmp+1;
res=max(res,cur->L->tmp+1);
}
}
else if(cur->R==prev)
{
s.pop();
if(cur->L)
{
cur->tmp=max(cur->L->tmp,cur->R->tmp)+1;
res=max(res,cur->L->tmp+cur->R->tmp+1);
}
else
{
cur->tmp=cur->R->tmp+1;
res=max(res,cur->R->tmp+1);
}

}
prev=cur;
}
return res;
}

check overlapping

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool MyCompare(pair<int,int> p1,pair<int,int> p2){return p1.first<p2.first;}
bool MyCompare2(int p1,pair<int,int> p2){return p1<p2.first;}

int NumOfIntersection(vector<int> A)
{
int N=A.size();
vector<pair<int,int>> P;
for(int i=0;i<N;i++)
{
int start_pt=i-A[i],end_pt=i+A[i];
P.push_back(pair<int,int>::pair(start_pt,end_pt));
}
sort(P.begin(),P.end(),MyCompare);
int res=0;
for(int i=0;i<N;i++)
{
vector<pair<int,int>>::iterator iter=upper_bound(P.begin()+i,P.end(),P[i].second,MyCompare2);
iter--;
int id=iter-P.begin();
res+=(id-i);
}
return res;
}

sum range (a lot of stl!!)

find the range that sum up to a closest value to a given value


#include<set>
#include<vector>
#include<algorithm>
#include<iostream>
#include<iterator>
using namespace std;

struct ltstr
{
bool operator()(pair<int,int> p1, pair<int,int> p2) const
{
return p1.first<p2.first;
}
};

void FindRange(vector<int> X,int val,int& startId, int& endId)
{
int size=X.size();

//preprocessing sum
set<pair<int,int>,ltstr> sum;
vector<pair<int,int>> my_vec;
int cur_sum=0;
for(int i=0;i<=size;i++)
{
sum.insert(pair<int,int>::pair(cur_sum,i));
my_vec.push_back(pair<int,int>::pair(cur_sum,i));
if(i<size)cur_sum+=X[i];
}

int closest=INT_MAX;
for(vector<pair<int,int>>::iterator iter=my_vec.begin();iter!=(my_vec.end()-1);iter++)
{
//remove already searched range so the output range is valid
pair<int,int> to_erase=*iter;
sum.erase(*iter);

int to_search=(*iter).first+val;
//search for closest value with lower bound and upper bound
set<pair<int,int>,ltstr>::iterator lower_bound=sum.lower_bound(pair<int,int>::pair(to_search,0));
set<pair<int,int>,ltstr>::iterator upper_bound=lower_bound;
if(lower_bound!=sum.begin())
upper_bound--;
if(lower_bound==sum.end())
lower_bound--;
int cur_min=min(abs((*lower_bound).first-to_search),abs((*upper_bound).first-to_search));
if(cur_min<closest)
{
closest=cur_min;
startId=iter-my_vec.begin();
endId=abs((*lower_bound).first-to_search)<abs((*upper_bound).first-to_search)?(*lower_bound).second-1:(*upper_bound).second-1;
}

}
}

longest increasing subsequence

#include<iostream>
#include<vector>
#include<set>
using namespace std;

void LongestSubSequence(vector<int> X)
{
int n=X.size();
vector<int> M(n+1);
int L=0;
for(int i=0;i<n;i++)
{
int j;
if(L==0)j=0;
else
{
for(j=1;j<=L;j++)
{
if(X[M[j]]>X[i])
break;
}
j--;
}
if(j==L || X[i]<X[M[j+1]])
{
M[j+1]=i;
L=max(L,j+1);
}
}
cout<<L<<endl;
}

linked list revisited

#include<list>
#include<iterator>
#include<iostream>
using namespace std;
void TestList()
{
list<int> L;
L.push_back(0);
L.push_front(1);
L.insert(++L.begin(),2);
copy(L.begin(),L.end(),ostream_iterator<int>(cout," "));
}

knapsack problem revisited

#include<iostream>
#include<vector>

using namespace std;

void Knapsack(vector<int> v,vector<int> w,int W)
{
//unbounded
vector<int> m(W);
m[0]=0;
for(int i=1;i<=W;i++)
{
int maximum=0;
for(int j=0;j<w.size();j++)
{
if(i>=w[j])
maximum=max(maximum,v[j]+m[i-w[j]]);
}
m[i]=maximum;
}
//bounded
vector<vector<int>> m2;
m2.resize(v.size());
for(int i=0;i<v.size();i++)
{
m2[i].resize(W);
fill(m2[i].begin(),m2[i].end(),0);
}
for(int i=1;i<v.size();i++)
{
for(int j=0;j<W;j++)
{
m2[i][j]=m2[i-1][j];
if(j>w[i])
m2[i][j]=max(m2[i][j],m2[i-1][j-w[i]]+v[i]);
}
}

}


matrix multiplication chain can also be solved by dp

set operation

void ThreeCoke()
{
int a[4]={1,2,3,4},b[4]={4,5,6,7};
set<int> A(a,a+4),B(b,b+4);

cout<<"set A: ";
copy(A.begin(),A.end(),ostream_iterator<int>(cout," "));
cout<<endl;
cout<<"set B: ";
copy(B.begin(),B.end(),ostream_iterator<int>(cout," "));
cout<<endl;
set<int> C;
cout<<"Union:";
set_union(A.begin(),A.end(),B.begin(),B.end(),ostream_iterator<int>(cout," "));
cout<<endl;
cout<<"Intersection:";
set_intersection(A.begin(),A.end(),B.begin(),B.end(),inserter(C,C.begin()));
cout<<endl;
copy(C.begin(),C.end(),ostream_iterator<int>(cout," "));

}

check sum

find two numbers that sum up to a certain number

1.  if it is a sort array.

if(A[1st_index] + A[2nd_index] < x)
    2nd_index--;
else if (A[1st_index] + A[2nd_index] > x)
    1st_index++;
else
     print 1st_index,2nd_index;
do this until 2nd_index > 1st_index

2. if it is a tree (bst)


#include<iostream>
#include<vector>
#include<stack>

using namespace std;
struct Node
{
Node* L;
Node* R;
int val;
};

void FindTwo(Node* root,int val)
{
stack<Node*> stack1,stack2;
Node* cur_node=root;
while(cur_node)
{
stack1.push(cur_node);
cur_node=cur_node->L;
}
cur_node=root;
while(cur_node)
{
stack2.push(cur_node);
cur_node=cur_node->R;
}
while(true)
{
Node *node1=stack1.top(),*node2=stack2.top();
if(!node1 || !node2)
break;
int val1=node1->val,val2=node2->val;
if(val1+val2==val)
{
cout<<val1<<" "<<val2<<endl;
break;
}
else if(val1+val2<val)
{
stack1.pop();
Node* cur_node=node1->R;
while(cur_node)
{
stack1.push(cur_node);
cur_node=cur_node->L;
}
}
else if(val1+val2>=val)
{
stack2.pop();
Node* cur_node=node2->L;
while(cur_node)
{
stack2.push(cur_node);
cur_node=cur_node->R;
}
}
}
}

some small typos of program writings

1.

char a[10][256]={
"..",
"..",
...
".."
};  //dont miss the semicolon

2.

Node* node1,node2;  //wrong!!

Node *node1,*node2;

3.

int a[5]={1,2,3,4,5};
vector<int> b(a,a+5);  NOT b(a,a+4)

4.

pay attention to return type
and if it returns int, dont write return; write return -1 instead.

5.

if

else if   //not elseif

map english words to byte

char map_english_words(string word)
{
char xorsum=0;
for(int i=0;i<word.length();i++)
{
xorsum^=word[i];
}
return xorsum;
}


char map=map_english_words("k");
char buffer[256];
itoa((int)map,buffer,2);
cout<<buffer<<endl;
system("pause");

(bitwise output)

____________________________________


huffman coding

dynamic programming

the max coin problem

#include<iostream>
#include<vector>

using namespace std;
int max_coin(vector<int> pots)
{
vector<vector<int>> dp_table;
int pot_num=pots.size();
dp_table.resize(pot_num);
for(int i=0;i<pot_num;i++)
{
dp_table[i].resize(pot_num);
for(int j=0;j<i;j++)
dp_table[i][j]=0;
}
for(int k=0;k<pot_num;k++)
{
for(int i=0;i<pot_num;i++)
{
int j=i+k;
if(j>=pot_num)
continue;
double pots1,pots2;
if(i+2<pots.size() && j-1>=0)
pots1=pots[i]+min(dp_table[i+2][j],dp_table[i+1][j-1]);
else
pots1=pots[i];
if(i+1<pots.size() && j-2>=0)
pots2=pots[j]+min(dp_table[i+1][j-1],dp_table[i][j-2]);
else
pots2=pots[j];
dp_table[i][j]=max(pots1,pots2);
}
}
return dp_table[0][pot_num-1];
}

design a web browser like Chrome

Chrome stores everything in separate process, which implies that the parent process would keep a hashmap of all the processes. The key would be the index and the value would be the process. The process would provide the details with regard to tab-content. Movement of tabs is just swapping of hash-keys.

Each tab is a process and have URL-handler. The handler would call a factory of protocol, such as httpFactory, ftpFactory etc. Each protocol handler has a retrieving-engine and rendering-engine. The browser would retrieve and render using factory.

I cant state definitively how Chrome handles the rendering threads - but I would assume that each tab has its own rendering thread. I wouldnt see the point of going through all the effort of process isolating the tabs, only to tie them all together on a common rendering thread. They would all have the opportunity to interfere with each other.

Don't confuse threads and processes. Each process will have it's own ui thread, but likely also it's own message pump.

Interestingly, using multiple processes means Google Chrome can have its own Task Manager (shown below), which you can get to by right clicking on the browser's title bar.  This Task Manager lets you track resource usage for each web app and plug-in, rather than for the entire browser.  It also lets you kill any web apps or plug-ins that have stopped responding, without having to restart the entire browser.

some old, but useful tree algorithms

1. in-order traversal to test if a binary search tree


#include<iostream>
#include<stack>

using namespace std;

struct TreeNode
{
int value;
TreeNode* left;
TreeNode* right;
};

bool IsBST(TreeNode* root)
{
stack<TreeNode*> my_stack;
TreeNode* prev=nullptr;
TreeNode* cur_node=root;
while(cur_node || !my_stack.empty())
{
if(cur_node)
{
my_stack.push(cur_node);
cur_node=cur_node->left;
}
else
{
TreeNode* top_node=my_stack.top();
if(prev && top_node->value<=prev->value)
return false;
prev=top_node;
cur_node=prev->right;
my_stack.pop();
}

}
return true;
}

2. a recursive algorithm to test if 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;

};

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-1) &&  // Allow only distinct values

    isBSTUtil(node->right, node->data+1, max);  // Allow only distinct values

}


bool IsBST(Node* root,int& mymin,int& mymax)
{
if(!root)
{
mymin=INT_MAX;
mymax=INT_MIN;
return true;
}
int min1,max1,min2,max2;
bool l=IsBST(root->L,min1,max1);
bool r=IsBST(root->R,min2,max2);
mymin=min(min1,min2);
mymin=min(mymin,root->val);
mymax=max(max1,max2);
mymax=max(mymax,root->val);
return l && r && max1<root->val && min2>root->val;
}






check if a tree is balanced







#include<iostream> struct node { int data; struct node* left; struct node* right; }; bool IsBalanced(struct node* root,int& height) { if(root==NULL) { height=0; return true; } int lh,rh; bool l,r; l=IsBalanced(root->left,lh); r=IsBalanced(root->right,rh); height=(lh>rh?lh:rh)+1; if(abs(lh-rh)>=2) return false; else return l&&r; }