2
\$\begingroup\$

the question is taken from Pramp(really cool site!)
there is a more straight forward solution.
using recursion. but I thought trying it using BFS.
please review only the code of GetCheapestCost function and comment on space and time complexity

The car manufacturer Honda holds their distribution system in the form of a tree (not necessarily binary). The root is the company itself, and every node in the tree represents a car distributor that receives cars from the parent node and ships them to its children nodes. The leaf nodes are car dealerships that sell cars direct to consumers. In addition, every node holds an integer that is the cost of shipping a car to it.

Take for example the tree below:

                  0
              /   |   \ 
             5    3      6
            /    /  \    / \
           4    2    0   1   5
               /     /
               1    10 
               \
                1

A path from Honda’s factory to a car dealership, which is a path from the root to a leaf in the tree, is called a Sales Path. The cost of a Sales Path is the sum of the costs for every node in the path. For example, in the tree above one Sales Path is 0→3→0→10, and its cost is 13 (0+3+0+10).

Honda wishes to find the minimal Sales Path cost in its distribution tree. Given a node rootNode, write a function getCheapestCost that calculates the minimal Sales Path cost in the tree.

Implement your function in the most efficient manner and analyze its time and space complexities.

For example:

Given the rootNode of the tree in diagram above

Your function would return:

7 since it’s the minimal Sales Path cost (there are actually two Sales Paths in the tree whose cost is 7: 0→6→1 and 0→3→2→1→1)

using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
    /// <summary>
    /// Sales Path

    [TestClass]
    public class PrampSalesPath
    {
        [TestMethod]
        public void TestMethod1()
        {
            SalesNode rootNode = new SalesNode();
            rootNode.children = new SalesNode[3];
            rootNode.cost = 0;
            rootNode.children[0] = new SalesNode {cost = 5};
            rootNode.children[1] = new SalesNode {cost = 3};
            rootNode.children[2] = new SalesNode {cost = 6};
            Assert.AreEqual(3, PrampSalesPathelper.GetCheapestCost(rootNode));
        }
    }

    public class SalesNode
    {
        public int cost;
        public SalesNode[] children;
        public SalesNode parent;

        public SalesNode()
        {
            children = null;
            parent = null;
        }
    }

    public class PrampSalesPathelper
    {
        public static int GetCheapestCost(SalesNode rootNode)
        {
            //check root node is not null was not defined.

            Queue<SalesNode> Q = new Queue<SalesNode>();
            Q.Enqueue(rootNode);
            int min = Int32.MaxValue;
            while (Q.Count != 0)
            {
                var tempNode = Q.Dequeue();

                //this is a leaf
                if (tempNode.children == null)
                {
                    min = Math.Min(min, tempNode.cost);
                }
                else
                {
                    foreach (var node in tempNode.children)
                    {
                        node.cost += tempNode.cost;
                        Q.Enqueue(node);
                    }
                }
            }
            return min;
        }
    }

}
\$\endgroup\$
2
\$\begingroup\$

Just a short answer, because I havn't the energy to type a long one.

Algorithm

This is indeed a Breadth-First-Search.

If you can assume that the costs will never be negative (i.e. path cost grows monotonically) then in either BFS or DFS it is easy to cut short paths which are more expensive than an already determined lower-bound. It's an assumption, but in the interest of fun if nothing else, taking all costs to be non-negative means you can reject (i.e. don't enqueue the children of) any path which is depper than the minimum path you have already found (if you have found such a path). In your code, the addition of a single if can give you this:

if (node.cost < min)
{
    Q.Enqueue(node);
}

Such a change means that your BFS has time and space complexity which are a function of the depth of the minimum path, rather than the depth of the whole tree. (It does of course need documenting)

Though it's pretty meaningless to ask for the 'most efficient' manner (I really dislike these kinds of problem definitions), this is not the algorithm with lowest time and space complexity. BFS has a high space complexity, but has the same time-complexity as an iterative deepening search. Alternatively, you could employ a heuristic search (i.e. A*) so that you explore only as much of the tree as necessary to find the minimum route. This doesn't come for free, as a heurisitic search requires a non-trivial ordering of nodes in the frontier, but a Priority Queue is ideal for this task. Without a better definition of the types of trees to expect, you can't know which algorithm is most suitable.

As always, I'll meantion that you code does not defend against cycles, but that's OK. It also won't work for a DAG (because it modifies the tree), which is still OK because the spec specifies a tree, but it's not documented.

Complexity

Without pruning trees (if you don't assume costs can be negative), this has time and space complexity linear in the size of the tree. If you do prune trees, then it has time and space complexity b^s, where s is the depth of the shallowest node with the minimum cost, and b is the slightly-fuzzy 'branching factor' (i.e. average-ish number of children per node). The second one is clearly exponential, the first only looks linear because I've changed the terms: instead we could consider the complexity of your algorithm to be b^d, where d is the average-ish depth of the tree.

Any DFS variant can give you space-complexity linear in d. An iterative deepening DFS will give you this linear space complexity and the same exponential time complexity as BFS. A heuristic search is a bit harder to classify (all the more so with such a limited specification), but essentially it's a better BFS.

API

It's mildly horrifying that your search modified the input as it does. This means that if the method is called twice with the same parameters that it could give a different answer. More importantly, this property is not documented, making it impossible for a consumer to know what is going on without careful debugging/looking at your code.

Though I'm sure you weren't asking about SalesNode... basically everything in SalesNode ought to be hidden away and (as a minimum) initialised by constructor. There is nothing preventing you from mis-using the class (e.g. by forgetting to set the parent attribute on children. You should provide methods to transform your objects from one consistent state to another.

You've clearly documented the fact that you are not checking for null with a comment. This is probably because you anticipate some miserable person like me telling you that this is a design decision, and you're not allowed to make those without documentation to go with it. However... you know that a null will cause the system to throw anyway, which means that implicitly you have made that decision, and you have essentially decided that it should throw (as opposed to returning something made-up-but-meaningful like 0; my opinion is you made the right decision). Do your callers a favour by catching this early and providing a meaningful error ArgumentNull exception: you can document that you assumed this behaviour, and you're justified (in my opinio) in your assumption because the software has to do something, and crashing is a really helpful thing to do when an assumption (that rootNode is non-null) is violated. Throw a nice exception, add some inline doc, and in the worst instance someone can write an exception method which doesn't throw on null which wraps your code with confidence. Alternatively, adding an assertion (e.g. Debug.Assert) so that you explicitly document the assumption that rootNode is non-null is another way to communicate all this.

Boring stuff

  • You know what I'm going to say about Q :) it should ideally be lower-case, and it should absolutely have a more meaningful name. Even queue wouldn't be great, because it describes how the thing is implemented, not what it is.

  • tempNode is not a good name here: this is not a temporary node at all; it is the current node we are looking at, or perhaps the next node to expand.

  • I would put this comment inside the if; it's unclear otherwise:

    //this is a leaf
    
  • A blank line either side of the while loop would make me happier.

  • That single test method is woefully inadequate... but I'm guessing you knew that ;)

\$\endgroup\$

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.