Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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(n2)? 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};
}
share|improve this question
1  
From where do you get these problems? :) –  Simon André Forsberg Apr 4 at 22:49
    
@SimonAndréForsberg TopCoder. :) I have a major interview coming up in September, and I am preparing for it now. –  bazang Apr 4 at 22:54

2 Answers 2

up vote 6 down vote accepted
  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]);
    
share|improve this answer
    
what about the space complexity and time complexity of the problem I solved? –  bazang Apr 5 at 0:37
    
@bazang: Space complexity seems O(n). I can't say too much about time complexity I didn't understand the code completely. –  palacsint Apr 5 at 1:07

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( pc2 + cp log p )

The O(pc2) 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.