0
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$
        explicit tree_node( const Ty& value,
            const tree_node* parent = nullptr ) :

Might be better for parent to not be a default argument. (The root node is the special case for which it would be better to explicitly specify the nullptr).


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

Maybe check that left and right are null before setting the value, or rename this function to replace_child or something.

Also, is it intentional to allow equal values? (This has consequences for finding nodes.)


Speaking of which, the instructions say "in addition to the usual operations"...

I'd say this lacks a lot of the "usual operations", e.g. finding, iteration, erasure etc.


    mutable std::mt19937 gen_;

Hmm. I think it might be better to have the user pass in the rng as a parameter to the pick_random function. That would allow using multiple rng's to access the same data.


        tree_node* node = root_.get(),
            * parent{};

Ick. Separate definitions would be much clearer.


        const uniform distribution( min, max );

        return distribution( gen_ );

This causes a compiler error for me because uniform_int_distribution::operator() isn't const.


    [[nodiscard]] auto next( const std::size_t& min, const std::size_t& max ) const -> std::size_t

I doubt passing std::size_t by const& is faster than by value.

Specifying the return type as auto, and then listing the return type after the function seems like unnecessary typing. We could just specify the return type up front.


    [[nodiscard]] auto pick_random() const -> Ty& { return pick_random( *root_ ); }
    [[nodiscard]] auto pick_random( tree_node& node ) const -> Ty& ...

These should return Ty const& (or by value) not Ty&. Changing the values in the nodes will break the tree!

Since we have no access to tree_nodes outside the class, that second function should probably be private.

We might want to throw a specific error for an empty tree. (If we implemented iterators, we could return an end iterator, which would be better still.)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is great feedback, exactly what I was looking for. Cheers! \$\endgroup\$ – Brandon Moretz May 23 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.