Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 943
Saqib Avatar asked Jul 31 '13 19:07

Saqib


People also ask

Which algorithm runs in O n 2 time?

Let's go into detail about why they are constant time. If you use the schoolbook long multiplication algorithm, it would take O(n2) to multiply two numbers.

What is linear-time complexity?

An algorithm is said to take linear time, or time, if its time complexity is . Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constant c such that the running time is at most. for every input of size n.

Is n log n linear?

So what is O(n log n)? Well, it's just that. It's n, a linear time complexity, multiplied by log n, a logarithmic time complexity.

Is linear-time constant time?

Title. Constant time is when the algorithm does not depend on the size of the input. Linear time is when the algorithm is proportional to the size of the input.


1 Answers

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.

like image 149
Kevin DiTraglia Avatar answered Oct 01 '22 17:10

Kevin DiTraglia