I've been trying to kind of teach myself "Modern C++" the last couple of months and I just finished this interview type problem and thought it would be a good one to get some feedback on. I not including the full implementation for brevity, just the relevant parts for the problem.
Random Node.
Implement a binary tree class which, in addition to the usual operations, has a method pick_random() which returns a random node from the tree. All nodes should be equally likely to be chosen.
random_node.h
#include <utility>
#include <random>
#include <memory>
namespace tree_problems
{
/* Random Node.
*
* Implement a binary tree class which, in addition to the usual operations,
* has a method pick_random() which returns a random node from the tree. All
* nodes should be equally likely to be chosen.
*/
template<typename Ty>
class random_node
{
struct tree_node;
using tree_node_ptr = std::unique_ptr<tree_node>;
struct tree_node
{
Ty value;
tree_node_ptr left{}, right{};
const tree_node* parent{};
std::size_t size{};
explicit tree_node( const Ty& value,
const tree_node* parent = nullptr ) :
value{ value }, parent{ parent }, size{ 1 }
{ }
tree_node( const tree_node& other )
: value{ other.value }, parent{ other.parent },
size{ other.size }
{
if( other.left )
left = std::make_unique<tree_node>( other.left->value );
if( other.right )
right = std::make_unique<tree_node>( other.right->value );
}
tree_node( tree_node&& other ) noexcept
: value{ other.value }, parent{ other.parent },
size{ other.size }
{
left = std::move( other.left );
right = std::move( other.right );
}
void insert_child( Ty value )
{
if( value <= this->value )
{
left = std::make_unique<tree_node>( value, this );
}
else
{
right = std::make_unique<tree_node>( value, this );
}
}
};
mutable std::mt19937 gen_;
tree_node_ptr root_;
public:
explicit random_node( const unsigned int seed = std::random_device{}( ) )
: gen_{ seed }
{ }
random_node( const std::initializer_list<Ty>& values,
const unsigned int seed = std::random_device{}( ) )
: random_node( seed )
{
for( const auto& val : values )
insert( val );
}
/// <summary>
/// insert node
///
/// this approach for insertion increments the nodes it passes on the way
/// down the tree to keep track of the total size of each node (total size =
/// the node + all its children) in constant (additional) time to the normal log insert time.
/// This approach does *not* keep the tree balanced or enforce any other invariants other than
/// correct node size and basic left <= current < right.
/// </summary>
/// <param name="value">value to insert</param>
void insert( const Ty& value )
{
if( !root_ )
{
root_ = std::make_unique<tree_node>( value );
return;
}
tree_node* node = root_.get(),
* parent{};
while( node )
{
++node->size;
parent = node;
node = value <= node->value ?
node->left.get() : node->right.get();
}
parent->insert_child( value );
}
[[nodiscard]] auto next( const std::size_t& min, const std::size_t& max ) const -> std::size_t
{
using uniform = std::uniform_int_distribution<std::mt19937::result_type>;
const uniform distribution( min, max );
return distribution( gen_ );
}
// forward the root to the recursive version.
[[nodiscard]] auto pick_random() const -> Ty& { return pick_random( *root_ ); }
/// <summary>
/// pick random
///
/// This routine looks at the "total" size of the node, which is maintained by
/// the insert to be the the current node + the total number of nodes below it,
/// so the root have the size of the total tree. Each call to pick random, we
/// generate a uniform number between 1 and the the node size, this gives us
/// a 1/n chance of picking the current node (and 1/1 for a leaf so we always
/// exit). If the number is [1, left-size] we traverse left, otherwise we traverse
/// right, and then re-roll with that node's size.
///
/// </summary>
/// <complexity>
/// <run-time>O(E[N/2])</run-time>
/// <space>O(E[N/2])</space>
/// </complexity>
/// <param name="node">the starting node</param>
/// <returns>a node between [node, children] with equal probability</returns>
[[nodiscard]] auto pick_random( tree_node& node ) const -> Ty&
{
const auto rnd = next( 1, node.size );
if( rnd == node.size )
return node.value;
if( node.left && rnd <= node.left->size )
{
return pick_random( *node.left );
}
return pick_random( *node.right );
}
};
}
random_node_tests.cpp
#include "pch.h"
#include <gtest/gtest.h>
#include <typeinfo>
#include "../problems/tree.h"
using namespace tree_problems;
namespace tree_tests
{
/// <summary>
/// Testing class for random node.
/// </summary>
class random_node_tests :
public ::testing::Test {
protected:
void SetUp() override
{
}
void TearDown() override
{
}
};
TEST_F( random_node_tests, case1 )
{
// basic functionality.
const auto rand =
random_node<int>( { 1, 2, 3 }, 1234 );
const auto actual = rand.pick_random();
const auto expected = 2;
EXPECT_EQ( actual, expected );
}
TEST_F( random_node_tests, balanced_tree )
{
// actually test the probability function.
// fix the tree to be balanced tree with 7 nodes
const auto values = std::initializer_list<int>
{ 4, 2, 6, 1, 3, 5, 7 };
const auto rand =
random_node<int>( values, 2358 );
// storage for 10k draws
auto results = std::map<int, int>();
const std::size_t iters = 1e6;
for( auto index = std::size_t(); index < iters; ++index )
{
results[ rand.pick_random() ]++;
}
double max = 0.0f, min = 0.0f;
for( const auto& [key, value] : results )
{
auto freq = static_cast< double >( value ) / iters;
max = std::max( max, freq );
min = std::min( max, freq );
}
const auto epsilon = 0.001; // error tolerance
EXPECT_LT( max - min, epsilon );
}
TEST_F( random_node_tests, unbalanced_tree )
{
// actually test the probability function.
// fix the tree to be an unbalanced tree with 11 nodes
const auto values = std::initializer_list<int>
{ 4, 3, 6, 2, 1, 0, 5, 7, 9, 10, 11 };
// seed the generator
const auto rand =
random_node<int>( values, 6358 );
// storage for 10k draws
auto results = std::map<int, int>();
const std::size_t iters = 1e6;
for( auto index = std::size_t(); index < iters; ++index )
{
results[ rand.pick_random() ]++;
}
double max = 0.0f, min = 0.0f;
for( const auto& [key, value] : results )
{
auto freq = static_cast< double >( value ) / iters;
max = std::max( max, freq );
min = std::min( max, freq );
}
const auto epsilon = 0.001; // error tolerance
EXPECT_LT( max - min, epsilon );
}
}
Looking for any design improvements, style suggestions, general approach, etc.
