Saturday, June 11, 2016

Data structure challenge

The goal of this challenge is to build a data structure that can:

1. Insert a tuple (a, b) in $O(\log n)$ time, and
2. For a given $A$, return the value of $max_b { (a, b) | a < A }$.
For simplicity, we assume all values of $a$ are distinct.

Here is the solution:
1. Build a balanced binary search tree (e.g. AVL tree) over the tuples using a as its key.
2. At each node, maintain the maximum b over itself and its subtree.
The tree would look like these

case 1

case 2

The tricky part is to answer the query. We can answer the query recursively as follow:

max_b(A)
{
if (A <= self.a)
{
return a.left.max_b(A)
}
else
{
return max(a.left.max_b, a.b, r.right.max_b(A))
}
}

Without further ado, here is the code for the idea

#include <iostream>
#include <algorithm>
using namespace std;

class tree
{
public:
tree();
void insert(int a, int b);
int query(int a) const;
private:
class node
{
public:
node(int a, int b);
node* insert(int a, int b);
void update();
int balance() const;
int query(int a) const;
int m_a;
int m_b;
int m_max_b;
node* m_left;
node* m_right;
int m_height;
};
node* m_root;
};

tree::tree() : m_root(nullptr)
{

}

void tree::insert(int a, int b)
{
if (this->m_root == nullptr)
{
this->m_root = new node(a, b);
}
else
{
this->m_root = this->m_root->insert(a, b);
}
}

int tree::query(int a) const
{
if (this->m_root == nullptr)
{
return -1;
}
else
{
return this->m_root->query(a);
}
}

tree::node::node(int a, int b) : m_a(a), m_b(b), m_max_b(b), m_left(nullptr), m_right(nullptr), m_height(1)
{

}

int tree::node::balance() const
{
int left_height = this->m_left == nullptr ? 0 : this->m_left->m_height;
int right_height = this->m_right == nullptr ? 0 : this->m_right->m_height;
return right_height - left_height;
}

tree::node* tree::node::insert(int a, int b)
{
if (this == nullptr)
{
return new node(a, b);
}
else
{
if (a == this->m_a)
{
this->m_b = max(this->m_b, b);
}
else if (a < this->m_a)
{
this->m_left = this->m_left->insert(a, b);
}
else if (a > this->m_a)
{
this->m_right = this->m_right->insert(a, b);
}
this->update();
if (this->balance() == 2)
{
if (this->m_right->balance() >= 0)
{
node* a = this;
node* b = this->m_right;
node* c = b->m_left;
b->m_left = a;
a->m_right = c;
a->update();
b->update();
return b;
}
else if (this->m_right->balance() == -1)
{
node* a = this;
node* b = this->m_right;
node* c = b->m_left;
node* d = c->m_left;
node* e = c->m_right;
c->m_left = a;
c->m_right = b;
a->m_right = d;
b->m_left = e;
a->update();
b->update();
c->update();
return c;
}
}
else if (this->balance() == -2)
{
if (this->m_left->balance() <= 0)
{
node* a = this;
node* b = this->m_left;
node* c = b->m_right;
b->m_right = a;
a->m_left = c;
a->update();
b->update();
return b;
}
else if (this->m_left->balance() == 1)
{
node* a = this;
node* b = this->m_left;
node* c = b->m_right;
node* d = c->m_right;
node* e = c->m_left;
c->m_right = a;
c->m_left = b;
a->m_left = d;
b->m_right = e;
a->update();
b->update();
c->update();
return c;
}
}
return this;
}
}

void tree::node::update()
{
int max_b = this->m_b;
int height = 1;
if (this->m_left != nullptr)
{
max_b = max(max_b, this->m_left->m_max_b);
height = max(height, this->m_left->m_height + 1);
}
if (this->m_right != nullptr)
{
max_b = max(max_b, this->m_right->m_max_b);
height = max(height, this->m_right->m_height + 1);
}
this->m_max_b = max_b;
this->m_height = height;
}

int tree::node::query(int a) const
{
if (this == nullptr)
{
return -1;
}
else if (a <= this->m_a)
{
return this->m_left->query(a);
}
else
{
int result = this->m_right->query(a);
result = max(result, this->m_b);
if (this->m_left != nullptr)
{
result = max(result, this->m_left->m_max_b);
}

return result;
}
}

int main(int argc, char** argv)
{
tree data;
data.insert(1, 1);
data.insert(2, 2);
data.insert(3, 3);
data.insert(4, 4);
data.insert(5, 5);
data.insert(6, 6);
data.insert(7, 7);
cout << data.query(5) << endl;
return 0;
}