Amazon | "Phone" (Chime Video Call) | Maximum Colleagues in a Given Year

Anonymous User

522

I’ve been asked this recently, and I want to hear how the community would approach it. The question was unusually vaguely stated (I've done several interviews at Amazon), however I have asked and clarified everything I could think of, so I have confirmed all of the following specifications and assumptions.

“Given the following, suggest the best data structure / workflow to achieve the desired output, where we need to find out the maximum number of employees the company ever had in any 1 year.”

This is a Java-specific question, but with no limitations: we’re free to go between 8 / 11 / 17; vendors (Oracle / Open JDK / etc.), as well as non-JDK data structures (for example, Eclipse Collections are fine).

Given: Ambiguous Input

We are given employee “years of service”, with two years per each unique employee. Our inputs are vaguely specified: all we know is that we are given distinct (individual) year ranges for each employee id. So each record represents an employee id and the corresponding year range. Interviewer’s example:

    000001 1990 1999
    000002 1991 1995
    000003 1993 1994
    000004 1994 1997

We can handle both the employees and the years as integers (int or Integer, where appropriate).

Given: Interviewer’s specifications

For simplicity of the example, we treat all employees’ years of service as whole integers, or complete years. For example: an employee with a “1990 1991” record indicates that the person worked the entire 1990 (1 whole year) + the entire 1991 (1 whole year) = 2 complete years. Likewise, if someone had a “1990 1990” record, that would indicate 1 year.

In other words, our inputs are guaranteed to not have anyone with less than 1 year of service. If an employee record exists, the minimum length of service for any employee is 1 year.

Given: Interviewer’s guidelines

The records are given to us in a list of some Java Object, such as a List interface containing "Object" as elements.
The approach of extracting the employee ids and years from the Employee object can be whatever we want.

Our Task: The Output

Find out and return maxEmployeesEver, as well as the corresponding year maxEmployeesYear.

We need to return the maximum number of employees the company ever had in any 1 year.
We need to be able to return how many employees worked in any given year, for example employeesInSpecificYear.
The shape of the output isn’t important: for simplicity, we’re allowed to just return the maxEmployeesEver as an int via one method and maxEmployeesYear as an int via another method. We are also allowed to do this any other way as well, for example:
o Via an int array
o Via generic Pair class
o We can create a class that represents the result (combination of maxEmployeesEver and maxEmployeesYear represented in some form) and return an instance of that class.

Again, the primary question I was asked is: “What Java data structure, in your opinion, would serve this purpose best? (It does need to be implemented, at least in part)”

The interviewer gave me a completely blank sheet to answer this.

The answer I gave:

Given a blank sheet, I began by offering the interviewer the following conceptual input implementation (something simple for me to start with), placed in a static block of code in our class for now. The interviewer confirmed that this is exactly correct, and good, in terms of the sample input our system can expect:

public class Solution {
        private static List<String> employeeRecords = new ArrayList<>();
        static {
            employeeRecords.add("000001 1990 1999");
            employeeRecords.add("000002 1991 1995");
            employeeRecords.add("000003 1993 1994");
            employeeRecords.add("000004 1994 1997");
        } 
		
		// My methods will be implemented below
}

The interviewer then told me that I can start with just implementing one method that can return the maxEmployeesEver as an int (leaving maxEmployeesYear and employeeTenure to be done later).

This is the final answer I gave:

Because the number of years our system would be confronted with is in the low hundreds (or less), my first intuition is to use the Map interface with the HashMap implementation to create some key-value pairs. The keys would be the individual calendar years, and the values would be the total employees working that year - for example: <1991, 2> would mean that the company had 2 employees in 1991.

I added a private field within the same class like so:

private Map<Integer,Integer> employeesPerYear = new HashMap<>();

Then I wrote my implementation of the maxEmployeesEver method as below: (breaking out some of the logic into helper method)

public int maxEmployeesEver() {
	int maxEmployees = 0;
	for (String record : employeeRecords) {
		int startYear = Integer.parseInt(record.split(" ")[1]);
		int endYear = Integer.parseInt(record.split(" ")[2]);
		updateAnnualHeadcount(startYear, endYear);
	}
    for (int value : annualHeadcount.values())
        maxEmployees = Math.max(maxEmployees, value);
    return maxEmployees;
}

private void updateAnnualHeadcount(int startYear, int endYear) {
    for (int i = startYear; i <= endYear; i++) {
        if (!annualHeadcount.containsKey(i)) {
            annualHeadcount.put(i, 1);
            continue;
        }
        annualHeadcount.put(i, (annualHeadcount.get(i) + 1));
    }
}

The interviewer’s response was positive, however he didn’t agree that a Map was the best data structure in this case.

I asked to clarify, because my understanding was that we need to maintain the ‘ability’ to somehow be able to answer the question “how many employees worked in a particular year” in another method, such as employeesInSpecificYear (returning an int) - which is why I thought keeping a pair of values in a Map was useful.

However, the interviewer strongly hinted that there should be a more elegant / simplified way to implement this. He mentioned that even though our system may deal with around only ~100 distinct years, the Map wouldn’t be the ideal choice of a data structure.

My question is:

Placing yourself in the shoes of the interviewer, what are your thoughts? How would you approach this?

The complete code for this interview is below:

public class Solution {

        private static List<String> employeeRecords = new ArrayList<>();
		private Map<Integer,Integer> employeesPerYear = new HashMap<>();
		
        static {
            employeeRecords.add("000001 1990 1999");
            employeeRecords.add("000002 1991 1995");
            employeeRecords.add("000003 1993 1994");
            employeeRecords.add("000004 1994 1997");
        } 
		
		public int maxEmployeesEver() {
			int maxEmployees = 0;
			for (String record : employeeRecords) {
				int startYear = Integer.parseInt(record.split(" ")[1]);
				int endYear = Integer.parseInt(record.split(" ")[2]);
				updateAnnualHeadcount(startYear, endYear);
			}
			for (int value : annualHeadcount.values())
				maxEmployees = Math.max(maxEmployees, value);
			return maxEmployees;
			}
	
		private void updateAnnualHeadcount(int startYear, int endYear) {
			for (int i = startYear; i <= endYear; i++) {
				if (!annualHeadcount.containsKey(i)) {
					annualHeadcount.put(i, 1);
					continue;
				}
				annualHeadcount.put(i, (annualHeadcount.get(i) + 1));
			}
		}
}

Comments (5)