Hingle McCringleBerry
BAN USERThe (in) famous median of median based partitioning algorithm.
Running Time : O(n)
Or its simpler cousin. Simple Selection Algorithm
Running Time :O(n) Expected
Good point. I overlooked it. Here is a better code based on DFA which works.
- Hingle McCringleBerry October 23, 2013EDIT: I overlooked certain restrictions. My solution would be to design a simple Automata that handles this (In this case, a simple 5 state DFA can handle this). Here is a code. I think it works.
bool check(std::string str)
{
int state = 1;
bool fail = false;
for(int i=0;i<str.length();i++)
{
char x = str[i];
switch(x)
{
case 'h' :
if(state==1)
state =2;
else if(state==2)
state=2;
else if(state==5)
state = 2;
else
fail = true;
break;
case 'i' :
if(state==2)
state =3;
else if(state==3)
state = 3;
else
fail = true;
break;
case 'r':
if(state==3)
state =4;
else if(state==4)
state = 4;
else
fail = true;
break;
case 'e':
if(state==4)
state =5;
else if(state==5)
state = 5;
else
fail = true;
break;
default:
fail = true;
break;
}
if(fail)
break;
}
if(state==5)
return true;
else
return false;
}
The way I solved it was first to find the grandfather node of a tree(if one exists) using recursion. Then I checked if the target node was a part of the subtree rooted at the left child of grandfather. If so, there is a rightmost cousin. And we find the same in the subtree rooted at the right child of grandfather. Here is the code in C++.
General::TreeNode<int>* getGrandFather(General::TreeNode<int>* root, int target,
General::TreeNode<int>* father,General::TreeNode<int>* grand_father)
{
if(!root)
return NULL;
if(root->value()==target)
return grand_father;
General::TreeNode<int>* left_res;
General::TreeNode<int>* right_res;
left_res = getGrandFather(root->getLeftChild(),target,root,father);
right_res = getGrandFather(root->getRightChild(),target,root,father);
if(!left_res)
return right_res;
else if(!right_res)
return left_res;
else return NULL;
}
General::TreeNode<int>* getCousin(General::TreeNode<int>* root,int target)
{
General::TreeNode<int>* grandpa = getGrandFather(root,target,NULL,NULL);
std::cout << grandpa->value();
int grandson1,grandson2,grandson3,grandson4;
if(grandpa)
{
grandson1 = grandpa->getLeftChild()->getLeftChild()->value();
grandson2 = grandpa->getLeftChild()->getRightChild()->value();
if(grandson1==target || grandson2==target)
{
if(grandpa->getRightChild())
if(grandpa->getRightChild()->getRightChild())
return grandpa->getRightChild()->getRightChild();
else
return grandpa->getRightChild()->getLeftChild();
else
return NULL;
}
}
return NULL;
}
Since you didn't mention anything, I will assume its a general tree. In that case, one of the ways is the following.
1. Print out the path from root to each node.
2. Find the common substring to this path.
3. The last node is the least common ancestor.
There are various implementations to this method including Dynamic Programming. (Due to no link restriction, I can't give a relevant link but a simple google search should do it)
Imagine a rectangle represented as a ordered pair of 2 points. One on the upper left and the other on the lower right. Define a weak ordering comparator function first on the point (check if p1.x < p2.x and then p1.y < p2.y), then on the rectangle overall.
Now you can sort the two lists and check if they are the same.
Complexity O(n log n).
(Based on the assumption from the second part of your question, that is there is some well defined ordering on the rectangles : That is rectangles that start on a smaller x coordinate is "smaller")
Every node is visited exactly twice. Once while going down and the other time while the calls are being returned. That is why the time complexity is O(N).
In general if the number of times an algorithm visits the tree node is upper bounded by some constant "k", then the running time is O(N).
For further practice, try to solve problem no 12.2-7 in the CLRS book(3rd edtn)
Selection Sort : Best Worst Average Case running time all O(n^2). However the number of swaps required is always n-1. Hence it is useful when the amount of satellite data(auxiliary data aside from the key) is large and for some reason pointer based swapping is not feasible.
Insertion Sort : Best case running time is O(n). Hence useful for adding new data to a presorted list. Also this is fast when the number of elements is small/ you need an online algorithm.
Bubble Sort:Where we know the data is very nearly sorted. Say only two elements are out of place. Then in one pass, BS will finish it and in the second pass, it will see everything is sorted and then exit. Only takes 2 passes of the array.
Merge Sort : For external sorting algorithms, it is the choice of sort.
Quicksort : Remember that quicksort is dependent on choice of pivot. So when we have absolutely random data values, and we will need to sort them, we have to use quick sort. Even for very unbalanced split QS produces good results.
Heap Sort: It is an inplace O(n logn) algorithm hence we can use it when we cannot afford the extra space required for merge sort. Also has a O(n logn) worst case time as compared to O(n^2) of quicksort.
+1
Nice solution. Certainly more simpler and elegant than my complex one which uses operator overloading.
Here is a solution in CPP. I tested the code and I think it works. The main takeaway of this problem was that the interviewer wanted to see if you understod strict weak ordering and comparator function overloading or not.
#include <iostream>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <set>
class Domino
{
public:
Domino()
{
num1 = -1;
num2= -1;
}
void setPair(int n1,int n2)
{
if(n1>n2)
{
num1 = n2;
num2 = n1;
}
else
{
num1 = n1;
num2 = n2;
}
}
bool operator<(const Domino &obj) const
{
if(num1<obj.num1)
return true;
else if(num1==obj.num1)
return num2<obj.num2;
else
return false;
}
friend std::ostream& operator<<(std::ostream& o,const Domino &d);
int num1;
int num2;
};
std::ostream& operator<<(std::ostream& o,const Domino &d)
{
o << "[" << d.num1 << "," << d.num2 << "]" ;
return o;
}
class DominoBox
{
public:
DominoBox(int arr[])
{
for(int i=0;i<10;i=i+2)
{
boxset[i/2].setPair(arr[i],arr[i+1]);
}
}
friend std::ostream& operator<<(std::ostream& o,const DominoBox &b) ;
bool operator<(const DominoBox &box)const
{
for(int i=0;i<5;i++)
{
if(boxset[i].num1<box.boxset[i].num1 || boxset[i].num2<box.boxset[i].num2)
{
return true;
}
}
return false;
}
void sortInOrder()
{
std::sort(boxset,boxset+5);
}
Domino boxset[5];
};
std::ostream& operator<<(std::ostream& o,const DominoBox &b)
{
int i;
for(i=0;i<5;i++)
o << b.boxset[i];
return o;
}
class DominoChecker
{
public:
bool addBox(int arr[])
{
DominoBox* newBox = new DominoBox(arr);
std::cout <<"Trying to insert:";
newBox->sortInOrder();
std::cout << *newBox << "\n";
std::pair<std::set<DominoBox>::iterator,bool> ret;
ret = set_ds.insert(*newBox);
return ret.second;
}
void print()
{
std::set<DominoBox>::iterator it;
for(it=set_ds.begin();it!=set_ds.end();it++);
std::cout << *it;
}
private:
std::set<DominoBox> set_ds;
};
int main()
{
int x1[] = {7,4,0,2,9,1,3,3,5,6};
int x2[] = {7,4,0,2,3,3,6,5,9,9};
int x3[] = {2,0,9,1,3,3,6,5,4,7};
DominoChecker* myObj = new DominoChecker();
std::cout << "Inserting 1st element.\n";
bool res1 = myObj->addBox(x1);
std::cout << "Insertion successful:" << res1 << "\n";
std::cout << "Inserting 2nd element.\n";
bool res2 = myObj->addBox(x2);
std::cout << "Insertion successful:" << res2 << "\n";
std::cout << "Inserting 3rd element.\n";
bool res3 = myObj->addBox(x3);
std::cout << "Insertion successful:" << res3 << "\n";
return(EXIT_SUCCESS);
}
First put all the 1000 elements in an hash table. Then take each of the one million elements and look for them in the hash table. If match is found report them as a solution.
Also works if you don't have enough memory to bring all the 1mil elements. Then just drag a chunk to disk, check and then drag the next chunk.
Space Complexity : O(m)
Time Complexity : O(n)
m size of smaller bag n: size of larger bag
I wrote a tail recursive version of the program. I ran the code. It works.
Here it is:
#include <iostream>
#include <cstdlib>
void print_wildcard(std::string str,std::string prefix)
{
if(str[0]=='\0')
{
std::cout << prefix << "\n";
return;
}
std::string from1 = "";
from1 = str.substr(1);
if(str[0]=='?')
{
print_wildcard("0"+from1,prefix);
print_wildcard("1"+from1,prefix);
}
else
{
prefix += str[0];
print_wildcard(from1,prefix);
}
}
int main()
{
std::string x = "1?00?101";
print_wildcard(x,"");
return(EXIT_SUCCESS);
}
- Hingle McCringleBerry October 13, 2015