C# Online Compiler | .NET Fiddle

<no name> by Anonymous

//The code may have been optimized by removing unused “using” references

 

using Amazon.AmazingGame.Model;

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

 

namespace Amazon.AmazingGame

{

    class Program

    {

        static void Main(string[] args)

        {

            //This is a simple test to prove that the algorithm works according to the given specification

            //After ensuring that all test cases are implemented, the code may be safely refactored

            //to optimize the algorithm

            const long totalNumberOfScoreSubmission = 100000;

 

            var amazingGameTestBed = new AmazingGameTestBed(totalNumberOfScoreSubmission);

            

            amazingGameTestBed.ExecuteTest();

 

            Console.ReadKey();

        }

    }

}

 

 

 

 

using Amazon.AmazingGame.Model;

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

 

namespace Amazon.AmazingGame

{

    //This class is implemented just as a proof of concept.

    //Professional tests can be performed by means of test framework for example as 'nunit"

    public class AmazingGameTestBed

    {

        private const int PRINT_PERIOD = 1000; // number of score required to print the top scores

 

        private const int SIZE_OF_TOP_LIST = 100;

 

        private const string RANK_FORMAT = "{0,-4} | {1,-5} | {2,-20}";

 

        private PlayerScoreRepository _playerScoreRepository;

 

        private RandomPlayerScoreGenerator _randomPlayerScoreGenerator;

 

        private long _totalNumberOfScoreSubmission;

 

        public AmazingGameTestBed(long totalNumberOfScoreSubmission)

        {

            //Tip 1: Although this class has no inherited or inheriting class, 

            //       and although we prefered the underscore prefix for instance variables,

            //       the keyword "this" is used to avoid potential "variable shadowing" error.

            //Tip 2: The number of submission is limited to the range of long for simplicity

            this._totalNumberOfScoreSubmission = totalNumberOfScoreSubmission;

            this._playerScoreRepository = new PlayerScoreRepository();

            this._randomPlayerScoreGenerator = new RandomPlayerScoreGenerator();

        }

 

        private void SubmitRandomPlayerScore()

        {

            PlayerScore randomPlayerScore = _randomPlayerScoreGenerator.Next();

 

            _playerScoreRepository.InsertScore(randomPlayerScore);

        }

 

        public void ExecuteTest()

        {

            for (long i = 0; i < _totalNumberOfScoreSubmission; i++)

            {

                SubmitRandomPlayerScore();

 

                if(( (i + 1) % PRINT_PERIOD ) == 0)

                {

                    IEnumerable<PlayerScore> topScores = _playerScoreRepository.GetTopScoresDescendingly(SIZE_OF_TOP_LIST);

 

                    //Apply a sample and simple assertion

                    AssertIfTheListIsDescendinglySorted(topScores);

 

                    PrintPlayerScores(topScores);

                }

            }

            

        }

 

        //This method doesnt depent on any instance variables.

        //So it can be declared as static.

        //Yet, no need to expose it to public.

        private static void AssertIfTheListIsDescendinglySorted(IEnumerable<PlayerScore> topScores)

        {

            long prevScore = topScores.First().Score;

 

            foreach (var playerScore in topScores)

            {

                if (prevScore < playerScore.Score)

                    throw new ArgumentException("The top scores are not in descending order");

            }

        }

 

        //This method doesnt depent on any instance variables.

        //So it can be declared as static.

        //Yet, no need to expose it to public.

        private static void PrintPlayerScores(IEnumerable<PlayerScore> topScores)

        {

            // Print header

            string printedRow = string.Format(RANK_FORMAT,"Rank","Score","Player Name");

            Console.WriteLine(printedRow);

            printedRow = string.Format(RANK_FORMAT, "----", "


            Console.WriteLine(printedRow);

            

            int rank = 1;

 

            foreach (var playerScore in topScores)

            {

                printedRow = string.Format(RANK_FORMAT, rank, playerScore.Score, playerScore.GetPlayerName());

                Console.WriteLine(printedRow);

                rank++;

            }

            Console.WriteLine("*************************************");

        }

    }

 

 

 

}

 

 

using Amazon.AmazingGame.Model;

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

 

namespace Amazon.AmazingGame

{

    //Generates random scores along woth random player names

    //It assumes that the score has a maximum value, i.e.1000

    //It simply leverages framework's random function.

    //More complex algorithm could also be implemented based on different types of probability density functions.

    public class RandomPlayerScoreGenerator

    {

        private const int MAX_SCORE = 1000; //

 

        private int playerIndex;

 

        private Random randomGenerator;

 

        public RandomPlayerScoreGenerator()

        {

            randomGenerator = new Random();//No seed is provided for simplicity

            playerIndex = 0;

        }

 

        public PlayerScore Next()

        {

            playerIndex++;

 

            long randomScore = randomGenerator.Next(MAX_SCORE);

            string randomPlayerName = "Player_" + playerIndex;

 

            PlayerScore playerScore = new PlayerScore()

            {

                Player = new Player()

                {

                    Name = randomPlayerName

                },

                Score = randomScore

            };

 

            return playerScore;

        }

 

    }

}

 

 

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

 

namespace Amazon.AmazingGame.Model

{

    public class Player

    {

        public int Id { get; set; }

 

        public string Name { get; set; }

    }

}

 

 

 

 

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

 

namespace Amazon.AmazingGame.Model

{

    public class PlayerScore : IComparable<PlayerScore>

    {

        public Player Player { get; set; }

 

        public long Score { get; set; }

 

        //Provides the name of the player to avoid violations of "Don't talk to friend of friend" principle.

        public string GetPlayerName()

        {

            return this.Player.Name;

        }

 

        public int CompareTo(PlayerScore other)

        {

            if (null == other)

                return 1;

 

            int comparisonResult = this.Score.CompareTo(other.Score);

 

            return comparisonResult;

        }

 

        public bool IsGreaterThan(long score)

        {

            bool isGreater = this.Score > score;

 

            return isGreater;

        }

 

        public bool IsLowerThan(long score)

        {

            bool isLower = this.Score < score;

 

            return isLower;

        }

    }

}

 

 

 

 

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using Amazon.AmazingGame.DataStructures;

using Amazon.AmazingGame.Model;

 

namespace Amazon.AmazingGame

{

    public class PlayerScoreRepository

    {

        private Heap<PlayerScore> _datasource;

 

        public PlayerScoreRepository()

        {

            //Eager loading is prefered.

            //No need to lazy initialization since it will be accessed almost infinitely

            _datasource = new Heap<PlayerScore>();

        }

 

        public void InsertScore(PlayerScore playerScore)

        {

            if (null == playerScore)

                return;

 

            _datasource.Add(playerScore);

        }

 

        public IEnumerable<PlayerScore> GetTopScoresDescendingly(long n)

        {

            long numberOfScores = _datasource.Count; // Time complexity of calling Count property is O(1).

 

            long sizeOfTopList = Math.Min(numberOfScores, n);

 

            return _datasource.GetTop(n);

        }

    }

}

 

 

 

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace Amazon.AmazingGame.DataStructures

{

    //This class is needed for only internal purpose

    //In order to test this class, the assembly of test project may be defined as friend assembly in this project

    internal class HeapNode<T> : IComparable<HeapNode<T>> where T : IComparable<T>

    {

        public T Data { get; set; }

 

        public HeapNode<T> Left { get; set; }

 

        public HeapNode<T> Right { get; set; }

 

        public HeapNode(T data)

        {

            this.Data = data;

        }

 

        public bool HasChild()

        {

            if (null == Left && null == Right)

                return false;

 

            return true;

        }

 

        public IEnumerable<T> GetChildren()

        {

            if (null != Left)

                yield return Left.Data;

 

            if (null != Right)

                yield return Data;

 

            yield break;

        }

 

        public int CompareTo(HeapNode<T> other)

        {

            int comparisonResult = this.Data.CompareTo(other.Data);

 

            return comparisonResult;

        }

    }

 

    //Tip 1: This class is created for internal use only.

    //       So it doesnt necessarily need to be exposed as public.

    //       In order to test this class, the assembly of test project may be defined as friend assembly in this project

    //Tip 2: The iterator pattern is implemented so that the top n entities can be easily traversed by the clients of the class

    //       As the iterator interface the framework's IEnumerator interface is chosen for common use and simplicity.

    internal class Heap<T> : IEnumerable<T>

        where T : IComparable<T>

    {

        private T minumumTopScore;

 

        private HeapNode<T> _rootNode;

 

        private long _numberOfItems = 0;

 

        public long Count

        {

            get

            {

                return _numberOfItems;

            }

        }

 

        public void Add(T newData)

        {

            //Since T is derived from IComparable<T> null checking can be performed

            //It it wasnt derived from IComparable<T>, either it should have been derived from another class like this ==> where T:class

            //or it could be checked against its default value like this ==> (newData == default(T)).

            if (null == newData)

                return;

 

            HeapNode<T> newNode = new HeapNode<T>(newData);

 

            if(null == _rootNode)

            {

                _rootNode = newNode;

                

                return;

            }

            

            InsertNewNode(_rootNode, newNode);

 

            _numberOfItems++;

        }

 

        //Time Complexity:O(log(n))

        //      Reasoning:The method is recursively called until it find the node that is smaller than newNode

        //                In each call at most one level dept is traversed if all children of current node are greater than newNode

        //                Maximum level to be traversed is log(n) .

        //                Therefore time complexity in the worst case is O(log(n)) while in the best case it is O(1)

     //Space Complexity: O(1) Since no additional space relative to n is used, the space complexity can be of insert function is O(1). On the other hand the space complexity of the heap structure overall is O(n) since there are only 1 node for each item inserted.

 

        private void InsertNewNode(HeapNode<T> topNode, HeapNode<T> newNode)

        {

            HeapNode<T> current = topNode;

 

            HeapNode<T> maxNode = FindMax(current, newNode);

 

            //check current

            if (maxNode == newNode)

            {

                newNode.Left = current;

 

                if(current == _rootNode)

                    _rootNode = newNode;

            }

            else

            {

                //check left

                maxNode = FindMax(newNode, current.Left);

 

                if (maxNode == newNode)

                {

                    newNode.Left = current.Left;

                    current.Left = newNode;

                }

                else // This "else" means current.Left is not null since FindMax will return newNode if current.Left was null

                {

                    //check right

                    maxNode = FindMax(newNode, current.Right);

 

                    if (maxNode == newNode)

                    {

                        newNode.Right = current.Right;

                        current.Right = newNode;

                    }

                    else // This "else" means current.Right is not null since FindMax will return newNode if current.Right was null

                    {

                        //Inserting either left or right subtree doesnt matter

                        //Inserting into the right subtree is chosen.

                        //Therefore the following line of code is commented conciously.

                        //Neither current.Left nor current.Right is null (See the comments that start with "This "else" means ...")

 

                        //Insert to the left subtree

                        //InsertNewNode(current.Left, newNode); //This line is commented conciously for abovementioned reason.

 

                        //Insert to the right subtree

                        InsertNewNode(current.Right, newNode);

                    }

                }

            }

        }

 

        //This method has no behavior that is dependent of an instance of the class.  

        //So, it may be stored in the static section of code block

        //On the other hand, there is no reason to expose it as public. So it may be declared as private or protected.

        //It is declared as protected since the potential inheriting classes will need to access it

        protected static HeapNode<T> FindMax(HeapNode<T> firstNode, HeapNode<T> secondNode)

        {

            if (null == firstNode && null == secondNode)

                return null;

 

            if (null == firstNode)

                return secondNode;

 

            if (null == secondNode)

                return firstNode;

 

            //The implementation below violates the software principle of "Don't talk to friends of friend"

            //int comparisonResult = current.Data.CompareTo(newNode.Data);

 

            //Instead the following implementation is preferred by deriving HeapNode<T> from IComparable<HeapNode<T>>

            int comparisonResult = firstNode.CompareTo(secondNode);

 

            // The following line may be replaced with simple if/else condition if necessary

            // Code review session will help to decide if it is necessary or not.

            HeapNode<T> maxNode = comparisonResult >0 ? firstNode:secondNode;

 

            return maxNode;

        }

 

 

        //Algorithm of GetTop method:

        //*) results is the list to return as the top n results

        //*) Traverse the tree in pre order

        //*) Implement insertion sort and try to insert the visited/traversed current node to results

        //*) If insertion requires any swap operation, which means the item is inserted into result list, 

        //   enqueue the existing children of the current node

        //*) Iterate through until the queue is emptied.

        // Time Complexity: Between O(n) and O(n^2) where n is the number of max value returned.  It is closer to O(n).

        //Reasoning: There are n item to be populated as the maximum values of the heap. To populate these item, insertion sort is implemented.

                          Worst case of insertion sort is O(n^2) while best base is O(n) for almost sorted inputs.  Since the values that are read from the heap is almost sorted, the time complexity is much closer to O(n).

                          As an alternative to insertion sort which is a good fit here since the number of maximum items (n) are as low as 100, the merge sort may also be a good alternative if n is getting too big.  If merge sort would have been implemented the time complexity would decrease up to O(log(n)) in return for increasing space complexity for temporary storage.

  

       //Space Complexity: O(n)

       //Reasoning: Since there are only n items to return and insertion sort is an in-place sorting algorithm, the number of space allocated is n.

                       

        public IEnumerable<T> GetTop(long n)

        {

            if (n <= 0)

                throw new ArgumentException("The input must be greater than zero");

 

            if (null == _rootNode)

                yield break;

 

            long maxIteration = Math.Min(this.Count, n);

 

            //I assume that maxIteration wont be too large.  So I chose to keep the top scores in an array.

            T[] results = new T[maxIteration];

            results[0] = _rootNode.Data;

            

            Queue<HeapNode<T>> queue = new Queue<HeapNode<T>>();

 

            if (null != _rootNode.Left)

                queue.Enqueue(_rootNode.Left);

 

            if (null != _rootNode.Right)

                queue.Enqueue(_rootNode.Right);

 

            int sortedItemCount = 1;

 

            while (queue.Count > 0 && sortedItemCount < n && sortedItemCount < this.Count)

            {

                var currentNode = queue.Dequeue();

 

                if (currentNode.Data.CompareTo(minumumTopScore) < 0)

                {

                    //skip currentNode if it is lower than the lowest item in the array

                    continue;

                }

 

                results[sortedItemCount] = currentNode.Data;

                

                int j = sortedItemCount;

                

                while (j > 0 && results[j].CompareTo(results[j - 1]) > 0)

                {

                    Swap(ref results[j], ref results[j - 1]);

                    j = j - 1;

                }

 

 

                if (j < results.Length-1) // Was the current item inserted into result list?

                {

                    if (null != currentNode.Left)

                        queue.Enqueue(currentNode.Left);

 

                    if (null != currentNode.Right)

                        queue.Enqueue(currentNode.Right);

                }

 

                sortedItemCount++;

            }

 

            minumumTopScore = results[n - 1];

 

            foreach (var result in results)

            {

                yield return result;

            }

        }

 

        private void Swap(ref T node1, ref T node2)

        {

            T tmp = node1;

            node1 = node2;

            node2 = tmp;

        }

 

        public IEnumerator<T> GetEnumerator()

        {

            throw new NotImplementedException();

        }

 

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()

        {

            throw new NotImplementedException();

        }

    }

}

​x
 
//The code may have been optimized by removing unused “using” references
​
 
​
using Amazon.AmazingGame.Model;
​
using System;
​
using System.Collections.Generic;
​
using System.Linq;
​
using System.Text;
​
using System.Threading.Tasks;
​
 
​
namespace Amazon.AmazingGame
​
{
​
    class Program
​
    {
​
        static void Main(string[] args)
​
        {
​
            //This is a simple test to prove that the algorithm works according to the given specification
​
            //After ensuring that all test cases are implemented, the code may be safely refactored
​
            //to optimize the algorithm
​
            const long totalNumberOfScoreSubmission = 100000;
​
 
​
            var amazingGameTestBed = new AmazingGameTestBed(totalNumberOfScoreSubmission);
​
            
​
            amazingGameTestBed.ExecuteTest();
​
 
​
            Console.ReadKey();
​
        }
​
    }
​
}
​
 
​
 
​
 
​
 
​
using Amazon.AmazingGame.Model;
​
using System;
​
using System.Collections.Generic;
​
using System.Linq;
​
using System.Text;
​
using System.Threading.Tasks;
​
 
​
namespace Amazon.AmazingGame
​
{
​
    //This class is implemented just as a proof of concept.
​
    //Professional tests can be performed by means of test framework for example as 'nunit"
​
    public class AmazingGameTestBed
​
    {
​
        private const int PRINT_PERIOD = 1000; // number of score required to print the top scores
​
 
​
        private const int SIZE_OF_TOP_LIST = 100;
​
 
​
        private const string RANK_FORMAT = "{0,-4} | {1,-5} | {2,-20}";
​
 
​
        private PlayerScoreRepository _playerScoreRepository;
​
 
​
        private RandomPlayerScoreGenerator _randomPlayerScoreGenerator;
​
 
​
        private long _totalNumberOfScoreSubmission;
​
 
​
        public AmazingGameTestBed(long totalNumberOfScoreSubmission)
​
        {
​
            //Tip 1: Although this class has no inherited or inheriting class, 
​
            //       and although we prefered the underscore prefix for instance variables,
​
            //       the keyword "this" is used to avoid potential "variable shadowing" error.
​
            //Tip 2: The number of submission is limited to the range of long for simplicity
​
            this._totalNumberOfScoreSubmission = totalNumberOfScoreSubmission;
​
            this._playerScoreRepository = new PlayerScoreRepository();
​
            this._randomPlayerScoreGenerator = new RandomPlayerScoreGenerator();
​
        }
​
 
​
        private void SubmitRandomPlayerScore()
​
        {
​
            PlayerScore randomPlayerScore = _randomPlayerScoreGenerator.Next();
​
 
​
            _playerScoreRepository.InsertScore(randomPlayerScore);
​
        }
​
 
​
        public void ExecuteTest()
​
        {
​
            for (long i = 0; i < _totalNumberOfScoreSubmission; i++)
​
            {
​
                SubmitRandomPlayerScore();
​
 
​
                if(( (i + 1) % PRINT_PERIOD ) == 0)
​
                {
​
                    IEnumerable<PlayerScore> topScores = _playerScoreRepository.GetTopScoresDescendingly(SIZE_OF_TOP_LIST);
​
 
​
                    //Apply a sample and simple assertion
​
                    AssertIfTheListIsDescendinglySorted(topScores);
​
 
​
                    PrintPlayerScores(topScores);
​
                }
​
            }
​
            
​
        }
​
 
​
        //This method doesnt depent on any instance variables.
​
        //So it can be declared as static.
​
        //Yet, no need to expose it to public.
​
        private static void AssertIfTheListIsDescendinglySorted(IEnumerable<PlayerScore> topScores)
​
        {
​
            long prevScore = topScores.First().Score;
​
 
​
            foreach (var playerScore in topScores)
​
            {
​
                if (prevScore < playerScore.Score)
​
                    throw new ArgumentException("The top scores are not in descending order");
​
            }
​
        }
​
 
​
        //This method doesnt depent on any instance variables.
​
        //So it can be declared as static.
​
        //Yet, no need to expose it to public.
​
        private static void PrintPlayerScores(IEnumerable<PlayerScore> topScores)
​
        {
​
            // Print header
​
            string printedRow = string.Format(RANK_FORMAT,"Rank","Score","Player Name");
​
            Console.WriteLine(printedRow);
​
            printedRow = string.Format(RANK_FORMAT, "----", "
​
​
            Console.WriteLine(printedRow);
​
            
​
            int rank = 1;
​
 
​
            foreach (var playerScore in topScores)
​
            {
​
                printedRow = string.Format(RANK_FORMAT, rank, playerScore.Score, playerScore.GetPlayerName());
​
                Console.WriteLine(printedRow);
​
                rank++;
​
            }
​
            Console.WriteLine("*************************************");
​
        }
​
    }
​
 
​
 
​
 
​
}
​
 
​
 
​
using Amazon.AmazingGame.Model;
​
using System;
​
using System.Collections.Generic;
​
using System.Linq;
​
using System.Text;
​
using System.Threading.Tasks;
​
 
​
namespace Amazon.AmazingGame
​
{
​
    //Generates random scores along woth random player names
​
    //It assumes that the score has a maximum value, i.e.1000
​
    //It simply leverages framework's random function.
​
    //More complex algorithm could also be implemented based on different types of probability density functions.
​
    public class RandomPlayerScoreGenerator
​
    {
​
        private const int MAX_SCORE = 1000; //
​
 
​
        private int playerIndex;
​
 
​
        private Random randomGenerator;
​
 
​
        public RandomPlayerScoreGenerator()
​
        {
​
            randomGenerator = new Random();//No seed is provided for simplicity
​
            playerIndex = 0;
​
        }
​
 
​
        public PlayerScore Next()
​
        {
​
            playerIndex++;
​
 
​
            long randomScore = randomGenerator.Next(MAX_SCORE);
​
            string randomPlayerName = "Player_" + playerIndex;
​
 
​
            PlayerScore playerScore = new PlayerScore()
​
            {
​
                Player = new Player()
​
                {
​
                    Name = randomPlayerName
​
                },
​
                Score = randomScore
​
            };
​
 
​
            return playerScore;
​
        }
​
 
​
    }
​
}
​
 
​
 
​
 
​
using System;
​
using System.Collections.Generic;
​
using System.Linq;
​
using System.Text;
​
using System.Threading.Tasks;
​
 
​
namespace Amazon.AmazingGame.Model
​
{
​
    public class Player
​
    {
​
        public int Id { get; set; }
​
 
​
        public string Name { get; set; }
​
    }
​
}
​
 
​
 
​
 
​
 
​
 
​
using System;
​
using System.Collections.Generic;
​
using System.Linq;
​
using System.Text;
​
using System.Threading.Tasks;
​
 
​
namespace Amazon.AmazingGame.Model
​
{
​
    public class PlayerScore : IComparable<PlayerScore>
​
    {
​
        public Player Player { get; set; }
​
 
​
        public long Score { get; set; }
​
 
​
        //Provides the name of the player to avoid violations of "Don't talk to friend of friend" principle.
​
        public string GetPlayerName()
​
        {
​
            return this.Player.Name;
​
        }
​
 
​
        public int CompareTo(PlayerScore other)
​
        {
​
            if (null == other)
​
                return 1;
​
 
​
            int comparisonResult = this.Score.CompareTo(other.Score);
​
 
​
            return comparisonResult;
​
        }
​
 
​
        public bool IsGreaterThan(long score)
​
        {
​
            bool isGreater = this.Score > score;
​
 
​
            return isGreater;
​
        }
​
 
​
        public bool IsLowerThan(long score)
​
        {
​
            bool isLower = this.Score < score;
​
 
​
            return isLower;
​
        }
​
    }
​
}
​
 
​
 
​
 
​
 
​
 
​
using System;
​
using System.Collections.Generic;
​
using System.Linq;
​
using System.Text;
​
using Amazon.AmazingGame.DataStructures;
​
using Amazon.AmazingGame.Model;
​
 
​
namespace Amazon.AmazingGame
​
{
​
    public class PlayerScoreRepository
​
    {
​
        private Heap<PlayerScore> _datasource;
​
 
​
        public PlayerScoreRepository()
​
        {
​
            //Eager loading is prefered.
​
            //No need to lazy initialization since it will be accessed almost infinitely
​
            _datasource = new Heap<PlayerScore>();
​
        }
​
 
​
        public void InsertScore(PlayerScore playerScore)
​
        {
​
            if (null == playerScore)
​
                return;
​
 
​
            _datasource.Add(playerScore);
​
        }
​
 
​
        public IEnumerable<PlayerScore> GetTopScoresDescendingly(long n)
​
        {
​
            long numberOfScores = _datasource.Count; // Time complexity of calling Count property is O(1).
​
 
​
            long sizeOfTopList = Math.Min(numberOfScores, n);
​
 
​
            return _datasource.GetTop(n);
​
        }
​
    }
​
}
​
 
​
 
​
 
​
 
​
using System;
​
using System.Collections.Generic;
​
using System.Linq;
​
using System.Text;
​
 
​
namespace Amazon.AmazingGame.DataStructures
​
{
​
    //This class is needed for only internal purpose
​
    //In order to test this class, the assembly of test project may be defined as friend assembly in this project
​
    internal class HeapNode<T> : IComparable<HeapNode<T>> where T : IComparable<T>
​
    {
​
        public T Data { get; set; }
​
 
​
        public HeapNode<T> Left { get; set; }
​
 
​
        public HeapNode<T> Right { get; set; }
​
 
​
        public HeapNode(T data)
​
        {
​
            this.Data = data;
​
        }
​
 
​
        public bool HasChild()
​
        {
​
            if (null == Left && null == Right)
​
                return false;
​
 
​
            return true;
​
        }
​
 
​
        public IEnumerable<T> GetChildren()
​
        {
​
            if (null != Left)
​
                yield return Left.Data;
​
 
​
            if (null != Right)
​
                yield return Data;
​
 
​
            yield break;
​
        }
​
 
​
        public int CompareTo(HeapNode<T> other)
​
        {
​
            int comparisonResult = this.Data.CompareTo(other.Data);
​
 
​
            return comparisonResult;
​
        }
​
    }
​
 
​
    //Tip 1: This class is created for internal use only.
​
    //       So it doesnt necessarily need to be exposed as public.
​
    //       In order to test this class, the assembly of test project may be defined as friend assembly in this project
​
    //Tip 2: The iterator pattern is implemented so that the top n entities can be easily traversed by the clients of the class
​
    //       As the iterator interface the framework's IEnumerator interface is chosen for common use and simplicity.
​
    internal class Heap<T> : IEnumerable<T>
​
        where T : IComparable<T>
​
    {
​
        private T minumumTopScore;
​
 
​
        private HeapNode<T> _rootNode;
​
 
​
        private long _numberOfItems = 0;
​
 
​
        public long Count
​
        {
​
            get
​
            {
​
                return _numberOfItems;
​
            }
​
        }
​
 
​
        public void Add(T newData)
​
        {
​
            //Since T is derived from IComparable<T> null checking can be performed
​
            //It it wasnt derived from IComparable<T>, either it should have been derived from another class like this ==> where T:class
​
            //or it could be checked against its default value like this ==> (newData == default(T)).
​
            if (null == newData)
​
                return;
​
 
​
            HeapNode<T> newNode = new HeapNode<T>(newData);
​
 
​
            if(null == _rootNode)
​
            {
​
                _rootNode = newNode;
​
                
​
                return;
​
            }
​
            
​
            InsertNewNode(_rootNode, newNode);
​
 
​
            _numberOfItems++;
​
        }
​
 
​
        //Time Complexity:O(log(n))
​
        //      Reasoning:The method is recursively called until it find the node that is smaller than newNode
​
        //                In each call at most one level dept is traversed if all children of current node are greater than newNode
​
        //                Maximum level to be traversed is log(n) .
​
        //                Therefore time complexity in the worst case is O(log(n)) while in the best case it is O(1)
​
     //Space Complexity: O(1) Since no additional space relative to n is used, the space complexity can be of insert function is O(1). On the other hand the space complexity of the heap structure overall is O(n) since there are only 1 node for each item inserted.
​
 
​
        private void InsertNewNode(HeapNode<T> topNode, HeapNode<T> newNode)
​
        {
​
            HeapNode<T> current = topNode;
​
 
​
            HeapNode<T> maxNode = FindMax(current, newNode);
​
 
​
            //check current
​
            if (maxNode == newNode)
​
            {
​
                newNode.Left = current;
​
 
​
                if(current == _rootNode)
​
                    _rootNode = newNode;
​
            }
​
            else
​
            {
​
                //check left
​
                maxNode = FindMax(newNode, current.Left);
​
 
​
                if (maxNode == newNode)
​
                {
​
                    newNode.Left = current.Left;
​
                    current.Left = newNode;
​
                }
​
                else // This "else" means current.Left is not null since FindMax will return newNode if current.Left was null
​
                {
​
                    //check right
​
                    maxNode = FindMax(newNode, current.Right);
​
 
​
                    if (maxNode == newNode)
​
                    {
​
                        newNode.Right = current.Right;
​
                        current.Right = newNode;
​
                    }
​
                    else // This "else" means current.Right is not null since FindMax will return newNode if current.Right was null
​
                    {
​
                        //Inserting either left or right subtree doesnt matter
​
                        //Inserting into the right subtree is chosen.
​
                        //Therefore the following line of code is commented conciously.
​
                        //Neither current.Left nor current.Right is null (See the comments that start with "This "else" means ...")
​
 
​
                        //Insert to the left subtree
​
                        //InsertNewNode(current.Left, newNode); //This line is commented conciously for abovementioned reason.
​
 
​
                        //Insert to the right subtree
​
                        InsertNewNode(current.Right, newNode);
​
                    }
​
                }
​
            }
​
        }
​
 
​
        //This method has no behavior that is dependent of an instance of the class.  
​
        //So, it may be stored in the static section of code block
​
        //On the other hand, there is no reason to expose it as public. So it may be declared as private or protected.
​
        //It is declared as protected since the potential inheriting classes will need to access it
​
        protected static HeapNode<T> FindMax(HeapNode<T> firstNode, HeapNode<T> secondNode)
​
        {
​
            if (null == firstNode && null == secondNode)
​
                return null;
​
 
​
            if (null == firstNode)
​
                return secondNode;
​
 
​
            if (null == secondNode)
​
                return firstNode;
​
 
​
            //The implementation below violates the software principle of "Don't talk to friends of friend"
​
            //int comparisonResult = current.Data.CompareTo(newNode.Data);
​
 
​
            //Instead the following implementation is preferred by deriving HeapNode<T> from IComparable<HeapNode<T>>
​
            int comparisonResult = firstNode.CompareTo(secondNode);
​
 
​
            // The following line may be replaced with simple if/else condition if necessary
​
            // Code review session will help to decide if it is necessary or not.
​
            HeapNode<T> maxNode = comparisonResult >0 ? firstNode:secondNode;
​
 
​
            return maxNode;
​
        }
​
 
​
 
​
        //Algorithm of GetTop method:
​
        //*) results is the list to return as the top n results
​
        //*) Traverse the tree in pre order
​
        //*) Implement insertion sort and try to insert the visited/traversed current node to results
​
        //*) If insertion requires any swap operation, which means the item is inserted into result list, 
​
        //   enqueue the existing children of the current node
​
        //*) Iterate through until the queue is emptied.
​
        // Time Complexity: Between O(n) and O(n^2) where n is the number of max value returned.  It is closer to O(n).
​
        //Reasoning: There are n item to be populated as the maximum values of the heap. To populate these item, insertion sort is implemented.
​
                          Worst case of insertion sort is O(n^2) while best base is O(n) for almost sorted inputs.  Since the values that are read from the heap is almost sorted, the time complexity is much closer to O(n).
​
                          As an alternative to insertion sort which is a good fit here since the number of maximum items (n) are as low as 100, the merge sort may also be a good alternative if n is getting too big.  If merge sort would have been implemented the time complexity would decrease up to O(log(n)) in return for increasing space complexity for temporary storage.
​
  
​
       //Space Complexity: O(n)
​
       //Reasoning: Since there are only n items to return and insertion sort is an in-place sorting algorithm, the number of space allocated is n.
​
                       
​
        public IEnumerable<T> GetTop(long n)
​
        {
​
            if (n <= 0)
​
                throw new ArgumentException("The input must be greater than zero");
​
 
​
            if (null == _rootNode)
​
                yield break;
​
 
​
            long maxIteration = Math.Min(this.Count, n);
​
 
​
            //I assume that maxIteration wont be too large.  So I chose to keep the top scores in an array.
​
            T[] results = new T[maxIteration];
​
            results[0] = _rootNode.Data;
​
            
​
            Queue<HeapNode<T>> queue = new Queue<HeapNode<T>>();
​
 
​
            if (null != _rootNode.Left)
​
                queue.Enqueue(_rootNode.Left);
​
 
​
            if (null != _rootNode.Right)
​
                queue.Enqueue(_rootNode.Right);
​
 
​
            int sortedItemCount = 1;
​
 
​
            while (queue.Count > 0 && sortedItemCount < n && sortedItemCount < this.Count)
​
            {
​
                var currentNode = queue.Dequeue();
​
 
​
                if (currentNode.Data.CompareTo(minumumTopScore) < 0)
​
                {
​
                    //skip currentNode if it is lower than the lowest item in the array
​
                    continue;
​
                }
​
 
​
                results[sortedItemCount] = currentNode.Data;
​
                
​
                int j = sortedItemCount;
​
                
​
                while (j > 0 && results[j].CompareTo(results[j - 1]) > 0)
​
                {
​
                    Swap(ref results[j], ref results[j - 1]);
​
                    j = j - 1;
​
                }
​
 
​
 
​
                if (j < results.Length-1) // Was the current item inserted into result list?
​
                {
​
                    if (null != currentNode.Left)
​
                        queue.Enqueue(currentNode.Left);
​
 
​
                    if (null != currentNode.Right)
​
                        queue.Enqueue(currentNode.Right);
​
                }
​
 
​
                sortedItemCount++;
​
            }
​
 
​
            minumumTopScore = results[n - 1];
​
 
​
            foreach (var result in results)
​
            {
​
                yield return result;
​
            }
​
        }
​
 
​
        private void Swap(ref T node1, ref T node2)
​
        {
​
            T tmp = node1;
​
            node1 = node2;
​
            node2 = tmp;
​
        }
​
 
​
        public IEnumerator<T> GetEnumerator()
​
        {
​
            throw new NotImplementedException();
​
        }
​
 
​
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
​
        {
​
            throw new NotImplementedException();
​
        }
​
    }
​
}
​
​

♠ ♣ ♥ ♦ ♥

Last Run:	10:52:55 am
Compile:	0.007s
Execute:	0.05s
Memory:	2.69Mb
CPU:	0.057s

View IL Code