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