can it be solved in linear time, did this in n^2 time

Question

the problem goes like this

suggest a data structure and write a program to count the number of employees referred by an employee(directly or indirectly) in linear time. for example

  A B C D E F G 
A 0 1 0 0 0 0 0 A referred 4 (A referred B, B referred C and D and D referred E)
B 0 0 1 1 0 0 0 B referred 3 
C 0 0 0 0 0 0 0
D 0 0 0 0 1 0 0 D referred 1
E 0 0 0 0 0 0 0
F 0 0 0 0 0 0 1 F referred 1
G 0 0 0 0 0 0 0 

did this using a two dimensional array, can it be done in linear time?

Note that an employee can obviously not be recommended by someone he directly or indirectly recommended, so there will be no cycles in the graph. A new employee can be recommended by only one employee. while each employee can recommend multiple employees.

Answer 1

You can maintain adjacency list for all the employees (N space). Then for each employee, maintain a Bag like data structure for all the referred employees. Then to count the references for Employee A, you can run DFS (Depth First Search) starting from A which is linear time algorithm.

Java code is here -

http://yogeshsp.blogspot.com/2013/04/graph-api.html

http://yogeshsp.blogspot.com/2013/05/depth-first-search-dfs-graph-processing.html

Answer 2

This is a tree (more precisely a forest). Read the edges in O(n) time. Construct the tree in O(n.log(n)). Given a node, visit and count descendants in O(n).

Answer 3

Java If cheating is allowed: an enum might represent the graph. Write first A(B), B(C, D), ... and then reorder so there is no forward reference on which the compiler complains. (This is always possible for non-cyclic references. Even a compile-time check against cyclic references.)

public class Refers {
    enum RefEnum {
        C(),
        E(),
        G(),
        D(E),
        F(G),
        B(C, D),
        A(B);

        //private final RefEnum[] refs;
        public final int refCount;

        private RefEnum(final RefEnum... refs) {
            //this.refs = refs;
            int n = 0;
            for (RefEnum ref : refs) {
                 n += 1 + ref.refCount;
            }
            refCount = n;
        }
    }

    public static void main(String[] args) {
        for (RefEnum ref : RefEnum.values()) {
            System.out.printf("%s has %d refers%n",
                    ref.toString(), ref.refCount);
        }
    }
}

The algorithm stays O(N²) however.

Answer 4

You can build a graph first. This mustn't be included in the O(n) as it is clearly O(n^2)

It is not clear if you optimise the duplicate references (Imagine all the values are 1)

At this point you can start at one node and add all the referred nodes e.g. in a bit mask. Any values which were added you need to navigate recursively until you are adding no new nodes.

The number of nodes you visit is O(N) as each employee can refer one person.

Answer 5

Graph method: first construct a directed graph (a tree in this case) where each node represents an employee and points to the node of the employee that referred them. This should take O(N^2) worst case ((N^2)/2 checks to be precise) where N is the number of employees. You should, as you're constructing this graph, keep track of the leaves of this tree (the employees that did not refer anyone) and then trim these nodes (assigning zero to their number of referrals) and adding 1 to the number of referrals of the employees that referred them. Then repeat with the new leaves, except add 2 to each of their referring nodes number of referrals. This whole trimming and counting process should take O(N) as well, and at the end all of the nodes contain the number of referrals each employee made.

This is assuming there are no cycles or weird two-employees-referring-the-same-employee situations in your graph (i.e. it is in fact a tree).

So, no, can't be done linearly if the input data to the problem is the binary vectors you have described. If we were given simply the names of the hired employees with each node, then O(N) would be possible.

Answer 6

My solution using C#, I'm pretty sure this is less than N^2 but I'll need to look at it a little longer. Posting for critique while I do so.

public class Employee
{
    public List<Employee> Referred { get; set; }
    public string Name { get; set; }
    public int CountOfRefer { get; set; }
    public bool BeenCounted { get; set; }
    public Employee()
    {
        Referred = new List<Employee>();
    }
}

    public static void main()
    {
        Employee A = new Employee(){ Name="A" };
        Employee B = new Employee(){ Name="B" };
        Employee C = new Employee(){ Name="C" };
        Employee D = new Employee(){ Name="D" };
        Employee E = new Employee(){ Name="E" };
        Employee F = new Employee(){ Name="F" };
        Employee G = new Employee(){ Name="G" };

        A.Referred.Add(B);
        B.Referred.Add(C);
        B.Referred.Add(D);
        D.Referred.Add(E);
        F.Referred.Add(G);
        List<Employee> employees = new List<Employee>()
        {
            A, B, C, D, E, F, G
        };

        foreach (var emp in employees)
        {
            if (!emp.BeenCounted) countRefers(emp);
        }
    }

    private static int countRefers(Employee emp)
    {
        if (!emp.BeenCounted && emp.Referred.Count != 0)
        {
            foreach (var refs in emp.Referred)
            {
                emp.CountOfRefer += countRefers(refs);
            }
        }

        emp.BeenCounted = true;
        emp.CountOfRefer += emp.Referred.Count;
        return emp.CountOfRefer;
    }

Basically when counting an employee it recurses down the tree until it finds a person who has no refers (which should be guaranteed to be there, since people can't refer eachother (I guess unless there is only 1 person, ignoring that case for now)). Then if it has to calculate anybody through the recursion it sets a flag so it doesn't need to calculate it again.