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.
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.
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.
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.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With