Sorting and searching problem related to a group of people standing in a rectangle

Question

Please be brutal, and let me know how I've done on this problem, provided I coded it at an interview for a top tech firm.

Time it took me: 44 minutes

Worst case time complexity: O(n²)? Am I right?

Space Complexity: O(n)?

Problem:

A group of people stand before you arranged in rows and columns. Looking from above, they form an R by C rectangle of people. You will be given a String[] people containing the height of each person. Elements of people correspond to rows in the rectangle. Each element contains a space-delimited list of integers representing the heights of the people in that row.

Your job is to return 2 specific heights in a int[]. The first is computed by finding the shortest person in each row, and then finding the tallest person among them (the "tallest-of-the-shortest"). The second is computed by finding the tallest person in each column, and then finding the shortest person among them (the "shortest-of-the-tallest").

Definition:

Class: TallPeople

Method: getPeople

Parameters: String[]

Returns: int[]

Method signature: int[] getPeople(String[] people) (be sure your method is public)

Constraints:

• people will contain between 2 and 50 elements inclusive.
• Each element of people will contain between 3 and 50 characters inclusive.

• Each element of people will be a single space-delimited list of positive integers such that:

  1. Each positive integer is between 1 and 1000 inclusive with no extra leading zeros.

  2. Each element contains the same number of integers.

  3. Each element contains at least 2 positive integers.

  4. Each element does not contain leading or trailing whitespace.

Examples:

{"9 2 3",
 "4 8 7"}

Returns: { 4, 7 }

The heights 2 and 4 are the shortest from the rows, so 4 is the taller of the two. The heights 9, 8, and 7 are the tallest from the columns, so 7 is the shortest of the 3. 1)

{"1 2",
 "4 5",
 "3 6"}

Returns: { 4, 4 }

{"1 1",
 "1 1"}

Returns: { 1, 1 }

Answer:

public static int[] getPeople(String[] people){
    int maxOfMinHeight = Integer.MIN_VALUE;
    int minOfMaxHeight = Integer.MAX_VALUE;
    int count=0;

    String[][]findMaxOfMin = new String[people.length][people[0].split(" ").length];
    int[][] findMinOfMax = new int[people[0].split(" ").length][people.length];

    for(String s : people){
        String[] sort  = s.split(" ");
        Arrays.sort(sort);
        findMaxOfMin[count++]=sort;
    }
    for(int i=0; i<findMaxOfMin.length; i++){
        maxOfMinHeight = Math.max(maxOfMinHeight, Integer.valueOf(findMaxOfMin[i][0])); 
    }
    count=0;
    int cols = people[0].split(" ").length;
    for(int i=0; i<cols; i++){
        int[] temp = new int[people.length];
        for(int j=0; j<people.length; j++){
            temp[j] = Integer.valueOf( ((String[])people[j].split(" "))[i]);
        }
        Arrays.sort(temp);
        findMinOfMax[count++]=temp;
    }
    for(int i=0; i<findMinOfMax.length; i++){
        minOfMaxHeight = Math.min(minOfMaxHeight, findMinOfMax[i][people.length-1]);
    }
    return new int[] {minOfMaxHeight, maxOfMinHeight};
}

Answer 1

1. Split it up! The current method does more than one thing, I'd create at least three helper methods:

   int[][] parseInput(String[] input);
   int getMaxOfMinHeightInColumns(int[][] peoples);
   int getMinOfMaxHeightInRows(int[][] peoples);
   

   It would be easier to follow and understand.

2. I looks like a bug that the following testcase fails:

   @Test
   public void test() {
       String[] input = {"9 2 3",
        "4 8 7"};
       int[] result = getPeople(input);
       assertArrayEquals(new int[] {4, 7}, result);
   }
   

3. Reusing the count variable is a bad sing:

   count=0;
   

   Try to use two different variables for different purposes and more descriptive names. What does it count? Put that into the name of the variable.

4. A few explanatory variable would be more readable here and remove some duplication:

   String[][]findMaxOfMin = new String[people.length][people[0].split(" ").length];
   int[][] findMinOfMax = new int[people[0].split(" ").length][people.length];
   

   Consider creating one for people.length and another for people[0].split(" ").length (columnNumber, rowNumber, for example).

5. (String[]) casting seems unnecessary here:

   temp[j] = Integer.valueOf( ((String[])people[j].split(" "))[i]);
   

Answer 2

Complexity will essentially be defined by this structure:

for(int i=0; i<cols; i++){
    int[] temp = new int[people.length];
    for(int j=0; j<people.length; j++){
        temp[j] = Integer.valueOf( ((String[])people[j].split(" "))[i]);
    }
    Arrays.sort(temp);
    findMinOfMax[count++]=temp;
}

which, using 'c' for cols, and 'p' for people.length will produce a complexity of:

• O( p * c ) for the inner for-loop

  • the loop itself is is O(p) and
  • O(c) for the ((String[])people[j].split(" "))

• O(p log p) for the Arrays.sort(temp)

Putting those together in the outer O(c) loop, I calculate the complexity to be in the order of:

O( pc² + cp log p )

The O(pc²) will be the dominant complexity.

If you move the Split to be outside the outer loop, and do something like:

int[][] data = new int[people.length][cols];
for (int j = 0; j < people.length; j++) {
    String[] parts = people[j].split(" ");
    for (int i = 0; i < cols; i++) {
        data[j][i] = Integer.valueOf(parts[i]);
    }
}
for(int i=0; i<cols; i++){
    int[] temp = new int[people.length];
    for(int j=0; j<people.length; j++){
        temp[j] = data[j][i];
    }
    Arrays.sort(temp);
    findMinOfMax[count++]=temp;
}

Then your overall complexity will drop to O(pc log p) because that part of the complexity will bcome dominant.