igorfact
BAN USERI think, we need two or more nodes holding and exchanging the metadata (about all existing working and non-working nodes and data backups/synchronization). All other nodes should query the other ones as needed to distribute the queries and collecting the results.
- igorfact August 13, 2014I agree that browser needs time stamps (for displaying the history and erasing some of it). So I guess, I would have an unordered map (which is based on hash-table) of URL's with time stamps as keys, and I also would have a list of the same time stamps (or pointers to them in the map) in chronological order. The end of the list would be considered the "top" of it mentioned in the task.
- igorfact July 07, 2014Hi Ricky, I was wondering why you implemented the approach with the limitation rather than the first one, which also seems cleaner and faster:
//commonElements.cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int arr0[] = {20, 15, 3, 10, 14, 35, 21, 14};
int arr1[] = {3, 10, 14, 18, 36, 15, 17, 25, 41};
int arr2[] = {12, 10, 37, 10, 15, 3};
int arr3[] = {22, 14, 25, 10, 15, 28, 3};
int arr4[] = {14, 10, 3, 10, 15, 18, 35};
int size[5];
size[0] = sizeof(arr0)/sizeof(int);
size[1] = sizeof(arr1)/sizeof(int);
size[2] = sizeof(arr2)/sizeof(int);
size[3] = sizeof(arr3)/sizeof(int);
size[4] = sizeof(arr4)/sizeof(int);
//initialize pointers to array elements
int* ip[5] = {arr0, arr1, arr2, arr3, arr4};
//sort the arrays
for (int i=0; i < 5; i++)
sort(ip[i], ip[i] + size[i]);
//vector to collect the common elements
vector<int> result;
while( ip[0] < arr0 + size[0]
&& ip[1] < arr1 + size[1]
&& ip[2] < arr2 + size[2]
&& ip[3] < arr3 + size[3]
&& ip[4] < arr4 + size[4])
{
if( *ip[0] == *ip[1]
&& *ip[1] == *ip[2]
&& *ip[2] == *ip[3]
&& *ip[3] == *ip[4])
{
result.push_back(*ip[0]);
for (int i=0; i < 5; i++)
{
ip[i]++;
goto endWhile;
}
}
//move up the pointer
//when the element can't be common
for (int i=0; i < 4; i++)
{
if(*ip[i] != *ip[i+1])
{
if(*ip[i+1] < *ip[i])
ip[i+1]++;
else
ip[i]++;
goto endWhile;
}
};
endWhile:;
}
for (int i=0; i < result.size(); i++)
{
cout << result[i] << " ";
}
cout << endl;
}
//getCommonAncestor.cpp
#include <iostream>
#include <vector>
#include <cstddef>
using namespace std;
class Node
{
int id;
Node* parent;
public:
Node(int iid, Node* prnt = NULL):id(iid),parent(prnt){}
Node* getParent(){return parent;}
void setParent(Node* n){parent = n;}
int getId(){return id;}
};
Node* commonAncestor(Node* n1, Node* n2)
{
vector<Node*> rootPath1, rootPath2;
Node* np=n1;
while(np != NULL)
{
rootPath1.push_back(np);
np = (*np).getParent();
}
np=n2;
while(np != NULL)
{
rootPath2.push_back(np);
np = (*np).getParent();
}
vector<Node*>::iterator it1 = rootPath1.end()-1;
vector<Node*>::iterator it2 = rootPath2.end()-1;
while((**it1).getId() == (**it2).getId())
{
if ((**it1).getId() != (*n1).getId() && (**it1).getId() != (*n1).getId())
{
it1--; it2--;
}
else
return *it1;
}
return *(++it1);
}
void printAncestor(const vector<Node*>& tree, int nodeId1, int nodeId2)
{
Node* n1 = tree[nodeId1];
Node* n2 = tree[nodeId2];
Node* np = commonAncestor(n1, n2);
cout << "Common ancestor of nodes " << nodeId1 << " and " << nodeId2;
cout << " has Id " << (*np).getId() << '\n';
}
int main()
{
vector<Node*> trie;
for (int id=0; id<19; id++)
trie.push_back(new Node(id));
(*trie[1]).setParent(trie[0]);
(*trie[2]).setParent(trie[0]);
(*trie[3]).setParent(trie[0]);
(*trie[4]).setParent(trie[1]);
(*trie[5]).setParent(trie[1]);
(*trie[6]).setParent(trie[1]);
(*trie[7]).setParent(trie[2]);
(*trie[8]).setParent(trie[3]);
(*trie[9]).setParent(trie[3]);
(*trie[10]).setParent(trie[4]);
(*trie[11]).setParent(trie[4]);
(*trie[12]).setParent(trie[5]);
(*trie[13]).setParent(trie[6]);
(*trie[14]).setParent(trie[7]);
(*trie[15]).setParent(trie[8]);
(*trie[16]).setParent(trie[9]);
(*trie[17]).setParent(trie[9]);
(*trie[18]).setParent(trie[9]);
printAncestor(trie, 0, 0);
printAncestor(trie, 0, 1);
printAncestor(trie, 4, 14);
printAncestor(trie, 4, 12);
printAncestor(trie, 8, 18);
printAncestor(trie, 16, 18);
for (int id=0; id<18; id++)
delete trie[id];
}
We could use sorted or hash maps for quick search by name and the timestamp. Those maps should just deal with the same pointers to records. GetDesriptions may return a vector of strings, and the GetRecords may return a vector of records for your programming convenience.
- igorfact August 13, 2014