online advertising

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;
}

No comments :

Post a Comment