h4x0r
BAN USERO(n)
#include <iostream>
using namespace std;
class Node
{
public:
int value;
Node* next;
bool flipped;
Node(int, Node*);
virtual ~Node();
bool operator==(Node&);
};
Node::Node(int value, Node* next) : value(value), next(next), flipped(false) {}
Node::~Node() {
if (next != 0) delete next;
}
bool Node::operator==(Node& other) {
return value == other.value;
}
Node* reverse(Node* head) {
if (head == 0) return 0;
Node* current = head;
while (head->next != 0) {
Node* next = head->next;
Node* next2next = next->next;
next->next = current;
if (next->flipped) throw next;
current = next;
current->flipped = true;
head->next = next2next;
}
return current;
}
Node* n(const int& value, Node* next) {
return new Node(value, next);
}
int main(int argc, char** argv) {
Node* n6 = n(6, 0);
Node* n4 = n(4, n(5, n6));
n6->next = n4;
Node* head = n(1, n(2, n(3, n4)));
try {
head = reverse(head);
} catch (Node* node) {
cout << "Cycle starts at node with value: " << node->value << endl;
return 0;
}
cout << "No cycle found" << endl;
return 0;
}
max-heap keyed on frequency of price will allow insertion in O(log(n)) time, so takes O(n*log(n)) time for the entire problem, considering lookup of the most popular prices is O(1).
hash-table allows insertion in O(1) and lookup of most popular price in O(n), so insertion takes n*O(1) operations, so overall O(n).
For solving this problem just once, hash-table does best. If the lookup may be done several times with insertions in-between, max-heap will work best.
However, fibonacci-heap can be used to get O(1) insertion time(amortized), and then it beats hash-table if queried several times.
For m queries, hash-table implementation takes O(m*n) time, and fibonacci-heap takes O(m + n) time(n for insertion).
O(nlogn)
#include <iostream>
#include <algorithm>
using namespace std;
struct Node {
int value;
Node* left;
Node* right;
Node(int value, Node* left, Node* right) : value(value), left(left), right(right) {}
Node(int value) : value(value), left(0), right(0) {}
~Node() {
delete left, right;
}
};
Node* n(const int& x, Node* left, Node* right) {
return new Node(x, left, right);
}
Node* n(const int& x) {
return new Node(x, 0, 0);
}
template<class T, class K> struct Tuple {
T one;
K other;
Tuple(T one, K other) : one(one), other(other) {}
};
template<class T> struct LikeTuple : Tuple<T, T> {
LikeTuple(T one, T other) : Tuple<T, T>(one, other) {}
};
typedef Tuple<Node*, int> Height;
Height height(Node* root, Node* parent) {
if (root == 0) return Height(parent, 0);
Height left_height = height(root->left, root);
Height right_height = height(root->right, root);
if (left_height.other > right_height.other) {
left_height.other++;
return left_height;
} else {
right_height.other++;
return right_height;
}
}
Height height(Node *root) {
return height(root, 0);
}
typedef Tuple<LikeTuple<Node*>, int> FarthestNodes;
FarthestNodes farthest_nodes(Node* root) {
if (root == 0) return FarthestNodes(LikeTuple<Node*>(0, 0), 0);
FarthestNodes left_farthest = farthest_nodes(root->left);
FarthestNodes right_farthest = farthest_nodes(root->right);
Height l_height = height(root->left);
Height r_height = height(root->right);
int root_dia = l_height.other + r_height.other + 1;
if (root_dia > left_farthest.other && root_dia > right_farthest.other)
return FarthestNodes(LikeTuple<Node*>(l_height.one, r_height.one), root_dia);
else if (left_farthest.other > right_farthest.other)
return left_farthest;
else
return right_farthest;
}
int main(int argc, char** argv) {
Node* root = n(10,
n(5,
n(2,
n(0,
n(-1),
n(2, n(1), 0)),
0),
n(7,
n(6),
n(9, n(8), 0))),
n(12,
n(11),
n(15,
n(13, 0, n(14)),
0)));
FarthestNodes nodes = farthest_nodes(root);
cout << "Farthest nodes are: " << nodes.one.one->value << " <-> " << nodes.one.other->value << " and distance between them is " << nodes.other << endl;
delete root;
return 0;
}
O(n)
#include <iostream>
using namespace std;
struct Node {
int value;
Node* next;
Node(int value): value(value) {}
};
Node* mkNode(const int& x, Node* after) {
Node* newNode = new Node(x);
newNode->next = after;
return newNode;
}
Node* rev_first_few(Node* head, int few) {
if (head == 0) return 0;
Node *current = head;
int i = 0;
while(++i < few) {
Node* next = head->next;
if (next == 0) break;
Node* next_2_next = next->next;
next->next = current;
head->next = next_2_next;
current = next;
}
head->next = rev_first_few(head->next, few);
return current;
}
int main(int argc, char** argv) {
Node* head = mkNode(1, mkNode(2, mkNode(3, mkNode(4, mkNode(5, mkNode(6, mkNode(7, mkNode(8, 0))))))));
head = rev_first_few(head, 3);
while(head != 0) {
cout << head->value << " ";
Node* next = head->next;
delete head;
head = next;
}
cout << endl;
return 0;
}
O(n) (even though it has a nested loop, it only traverses each element thrice in the worst case. 3n = O(n).
- h4x0r June 01, 2012