quirk
BAN USERUse two things:
1. A doubly linked list to hold the actual order of the visited URLs
2. A hashset so that we can efficiently check for duplicates and maintain direct pointers to our doubly linked list.
list<string> URLs; // doubly linked list a.k.a. the visit order
unordered_map<string, list<string>::iterator> checkMap; // hashtable
void visit(cosnt string& url) {
auto it = checkMap.find(url);
if(it != checkMap.end())
URLs.erase(it->second); // remove a previous instance of this URL from the visit order
checkMap[url] = URLs.insert(URLs.end(), url); // insert URL at the latest of the visit order
}
void printVisitOrder() {
for(auto it = URLs.rbegin(); it != URLs.rend(); ++it) // reverse iteration to go from latest to oldest
cout << *it << endl;
}
+ Insertion into the list: O(1) (always at the end)
+ Deletion from the list: O(1) (we have a direct pointer to the element to be deleted)
+ Lookups for duplicates: O(1) (because of hashtable)
+ Printing of visit order: O(k) for k unique elements
I made a few assumptions regarding the definition and scope of the question:
1. I assume Balanced tree is referring to Height-balanced tree.
2. I take the following definition of Height balanced trees: A binary tree is height-balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
NOTE the part regarding inner nodes only.
struct node
{
int data;
node* left;
node* right;
};
int checkBalance(node* root) {
// base case
if(node == NULL) return 0;
int leftHeight = checkBalance(node->left);
int rightHeight = checkBalance(node->right);
// propogate error
if(leftHeight == -1 || rightHeight == -1)
return -1;
// give error on non-balance
if(abs(leftHeight - rightHeight) > 1)
return -1;
return max(leftHeight, rightHeight) + 1;
}
bool isHeightBalanced(node* root) {
if(checkBalance(root) == -1)
return false;
return true;
}
If either of the left or right subtrees is unbalanced, the entire tree becomes unbalanced. Hence the propogation of error through the entire depth of the recursive stack.
- quirk April 30, 2016
Repstacimdalton, Dev Lead at ASAPInfosystemsPvtLtd
At the moment I'm implementing Slinkies in the financial sector. My current pet project is researching break up a ...
The O(n) algorithm to find the longest palindromic sub-string is called the Manacher's Algorithm.
- quirk March 30, 2017