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;
}

}
}

deque

an example:


inline void test_deque()
{
std::deque<int> Q;
Q.push_back(3);
Q.push_front(1);
std::copy(Q.begin(),Q.end(),std::ostream_iterator<int>(std::cout," "));
std::cout<<std::endl;
for(std::deque<int>::iterator iter=Q.begin();iter<Q.end();iter++)
std::cout<<*iter<<" ";

}

continuous memory
const time to insert at front and the end.


inline void test_list()
{
std::list<int> L;
L.push_back(0);
L.push_front(1);
L.insert(++L.begin(),2);

std::copy(L.begin(),L.end(),std::ostream_iterator<int>(std::cout," "));
}


insert takes constant time but need to provide the iterator first.

Solution to cracking coding interview 3.4

MyQueue.h


#pragma once
#include<stack>

template<class T>
class CMyQueue
{
std::stack<T> m_stack1;
std::stack<T> m_stack2;
public:
void push(const T& elem);
T pop();
CMyQueue(void);
~CMyQueue(void);
};

#include"MyQueue.cpp"

MyQueue.cpp



#include "MyQueue.h"

template<class T>
CMyQueue<T>::CMyQueue(void)
{

}

template<class T>
CMyQueue<T>::~CMyQueue(void)
{
}

template<class T>
void CMyQueue<T>::push(const T& elem)
{
m_stack1.push(elem);
}

template<class T>
T CMyQueue<T>::pop()
{
if(m_stack2.empty())
{
while(!m_stack1.empty())
{
T val=m_stack1.top();
m_stack1.pop();
m_stack2.push(val);
}
}
try
{
if(m_stack2.empty())
throw exception("out of range");
T val=m_stack2.top();
m_stack2.pop();
return val;
}
catch(exception e)
{
std::cout<<e.what();
exit(-1);
}
}

an interesting explanation of why pop() in stl does not return value

1. SGI explanation: http://www.sgi.com/tech/stl/stack.html One might wonder why pop() returns void, instead of value_type. That is, why must one use top() and pop() to examine and remove the top element, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the top element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use top() to inspect the value at the top of the stack.
2. std::stack < T > is a template. If pop() returned the top element, it would have to return by value rather than by reference as per the of above explanation. That means, at the caller side it must be copied in an another T type of object. That involves a copy constructor or copy assignment operator call. What if this type T is sophisticated enough and it throws an exception during copy construction or copy assignment? In that case, the rvalue, i.e. the stack top (returned by value) is simply lost and there is no other way to retrieve it from the stack as the stack's pop operation is successfully completed!

some tree operations

<recursion is most common, but there is memory call overhead>
inorder: stack
preorder: dfs
postorder: stack

nonRecursivePostorder(rootNode)
  nodeStack.push(rootNode)
  while (! nodeStack.empty())
    currNode = nodeStack.peek()
    if ((currNode.left != null) and (currNode.left.visited == false))
      nodeStack.push(currNode.left)
    else 
      if ((currNode.right != null) and (currNode.right.visited == false))
        nodeStack.push(currNode.right)
      else
        print currNode.value
        currNode.visited := true
        nodeStack.pop()

stl replacement of tree:

set and map

struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

int main()
{
  const int N = 6;
  const char* a[N] = {"isomer", "ephemeral", "prosaic", 
                      "nugatory", "artichoke", "serif"};
  const char* b[N] = {"flat", "this", "artichoke",
                      "frigate", "prosaic", "isomer"};

  set<const char*, ltstr> A(a, a + N);
  set<const char*, ltstr> B(b, b + N);
  set<const char*, ltstr> C;

  cout << "Set A: ";
  copy(A.begin(), A.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
  cout << "Set B: ";
  copy(B.begin(), B.end(), ostream_iterator<const char*>(cout, " "));   
  cout << endl;

  cout << "Union: ";
  set_union(A.begin(), A.end(), B.begin(), B.end(),
            ostream_iterator<const char*>(cout, " "),
            ltstr());   
  cout << endl;

  cout << "Intersection: ";
  set_intersection(A.begin(), A.end(), B.begin(), B.end(),
                   ostream_iterator<const char*>(cout, " "),
                   ltstr());    
  cout << endl;

  set_difference(A.begin(), A.end(), B.begin(), B.end(),
                 inserter(C, C.begin()),
                 ltstr());
  cout << "Set C (difference of A and B): ";
  copy(C.begin(), C.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
}

hash_map in stl

Hash_map is a Hashed Associative Container that associates objects of type Key with objects of type Data. Hash_map is a Pair Associative Container, meaning that its value type is pair<const Key, Data>. It is also a Unique Associative Container, meaning that no two elements have keys that compare equal using EqualKey.
Looking up an element in a hash_map by its key is efficient, so hash_map is useful for "dictionaries" where the order of elements is irrelevant. If it is important for the elements to be in a particular order, however, then map is more appropriate.

Example

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) == 0;
  }
};

int main()
{
  hash_map<const char*, int, hash<const char*>, eqstr> months;
  
  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;
  
  cout << "september -> " << months["september"] << endl;
  cout << "april     -> " << months["april"] << endl;
  cout << "june      -> " << months["june"] << endl;
  cout << "november  -> " << months["november"] << endl;
}

my experience is that it is important to use hash_map whenever necessary! 

how is std::map implemented

So it can be used to quickly implement a red-black tree!

In an STL map, insertion of key/value pair is in sorted order of key. It uses a tree to store values, which is why an O(log N) insert/lookup is required. There is also no need to handle collisions. An STL map works well for things like:
»»find min element
»»find max element
»»print elements in sorted order
»»find the exact element or, if the element is not found, find the next smallest number

example:


#include<map>
#include<string>
#include<iostream>

using namespace std;

int main()
{
map<string,int> p;
p["jan"]=1;
p["feb"]=2;
cout<<p["feb"]<<p["mar"]<<endl;
system("pause");
}

map is implemented using red-black tree.

Probably the two most common self balancing tree algorithms are Red-Black trees and AVL trees. To balance the tree after an insertion/update both algorithms use the notion of rotations where the nodes of the tree are rotated to perform the re-balancing.

While in both algorithms the insert/delete operations are O(log n), in the case of Red-Black tree re-balancing rotation is an O(1) operation while with AVL this is a O(log n) operation, making the Red-Black tree more efficient in this aspect of the re-balancing stage and one of the possible reasons that it is more commonly used.

Red-Black trees are used in most collection libraries, including the offerings from Java and Microsoft .NET Framework.

using namespace std;

typedef std::map<int,int>  MAP;
typedef std::pair<int,int> PAIR;

int main()
{

    MAP squares_map;

    squares_map.insert( PAIR(2,4) );
    squares_map.insert( PAIR(0,0) );
    squares_map.insert( PAIR(1,1) );
    squares_map.insert( PAIR(6,36) );
    squares_map.insert( PAIR(3,9) );

    if (!squares_map.empty())
    {
        MAP::iterator it_min = squares_map.begin();

        MAP::iterator it_max = squares_map.end();  // points to just past last element
        --it_max;                                  // points to last element

        cout << "min element : " << it_min->first << " " << it_min->second << "\n";
        cout << "max element : " << it_max->first << " " << it_max->second << "\n";
    }

    return 0;
}