using System;

using System.Collections.Generic;   

using System.Linq;

using System.Diagnostics;

​

public class Program

{

    public static void Main()

    {

        var rnd = new Random();

        // Create 4000 Departments

        var departments = Enumerable.Range(1, 4000).OrderBy(r => rnd.NextDouble())

            .Select(id => new Department()

            {

                Id = id,

                Name = "Dept " + id,

                CreatedDate = DateTime.Now

            }).ToList();

        // Create 100,000 Employees

        var employees = Enumerable.Range(0, 100000).Select(n => new Employee()

        {

            Id = n,

            DepartmentId = rnd.Next(1, 4001)

        }).ToList();

​

        var stopwatch = Stopwatch.StartNew();

        var results = Run(employees, departments);        

        if (results.Count() != 100000)

            throw new System.Exception("wrong answer");

        stopwatch.Stop();

        Console.WriteLine(stopwatch.ElapsedMilliseconds);

    }

    //This method takes about 4-5 seconds to run. The goal is to make it run in less than 50ms. RULES: ONLY CHANGE THIS METHOD, DON'T TOUCH SIGNATURE

    public static List<EmployeeDepartment> Run(IEnumerable<Employee> employees, IEnumerable<Department> departments)

    {

        var results = new List<EmployeeDepartment>();

        foreach (var employee in employees)

        {

            var res = new EmployeeDepartment()

            {

                Employee = employee,

                Department = departments.First(d=>d.Id == employee.DepartmentId)

            };

            results.Add(res);

        }

        return results;

    }

}

public class Employee

{

    public int Id {get;set;}

    public int DepartmentId {get;set;}

}

public class Department

{

    public int Id {get;set;}

    public string Name {get;set;}

    public DateTime CreatedDate {get;set;}

}

public class EmployeeDepartment

{

    public Department Department {get;set;}

    public Employee Employee {get;set;}

}