Jobs

Interviews

Discussions

Sort the People

Easy

Uber

2 views

Topics:

ArraysStrings

You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n. For each index i, names[i] and heights[i] denote the name and height of the i<sup>th</sup> person.

Return names* sorted in descending order by the people's heights*.

Example 1:

names = ["Mary","John","Emma"], heights = [180,165,170]

Output: ["Mary","Emma","John"]

Example 2:

names = ["Alice","Bob","Bob"], heights = [155,185,150]

Output: ["Bob","Alice","Bob"]

How would you approach solving this problem efficiently? Consider both time and space complexity. Also, discuss any edge cases that might affect your solution.

Sort the People

Easy

Uber

2 views

Topics:

ArraysStrings

Return names* sorted in descending order by the people's heights*.

Example 1:

names = ["Mary","John","Emma"], heights = [180,165,170]

Output: ["Mary","Emma","John"]

Example 2:

names = ["Alice","Bob","Bob"], heights = [155,185,150]

Output: ["Bob","Alice","Bob"]

How would you approach solving this problem efficiently? Consider both time and space complexity. Also, discuss any edge cases that might affect your solution.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `names` and `heights` arrays be empty or null?
Are the lengths of the `names` and `heights` arrays guaranteed to be the same?
What is the range of values for the `heights`? Are they all positive integers?
Are the names guaranteed to be unique, or can there be duplicate names?
What is the expected output if the input arrays are empty?

Brute Force Solution

Approach

The brute force approach involves checking all possible arrangements of people according to their heights. Think of it like shuffling a deck of cards and checking if the order is correct. We continue shuffling until we find an order that satisfies the height requirements.

Here's how the algorithm would work step-by-step:

Start with the people in their original order.
Consider every single possible order the people could be in. This means rearranging their positions in every conceivable way.
For each of these orderings, check if the heights are sorted from tallest to shortest.
If the heights are sorted correctly, then you've found a solution.
If you check every single possible ordering and haven't found a solution, then there is no possible ordering that fulfills the requirements.

Code Implementation

import itertools

def sort_the_people_brute_force(names, heights):
    number_of_people = len(names)

    # Generate all possible permutations of indices
    index_permutations = itertools.permutations(range(number_of_people))

    for permutation in index_permutations:
        is_sorted = True
        # Check if the current permutation sorts heights
        for i in range(number_of_people - 1):
            if heights[permutation[i]] < heights[permutation[i + 1]]:
                is_sorted = False
                break

        # If the permutation is sorted, construct the result
        if is_sorted:
            sorted_names = [names[permutation[i]] for i in range(number_of_people)]
            return sorted_names

    # If no permutation sorts the heights, return an empty list
    return []

Big(O) Analysis

Time Complexity

O(n! * n) – The algorithm explores every possible permutation of the input array of n people. There are n! (n factorial) possible permutations. For each permutation, the algorithm checks if the heights are sorted in descending order, which takes O(n) time, as it iterates through all the elements to compare adjacent heights. Therefore, the overall time complexity is O(n! * n).

Space Complexity

O(N) – The brute force approach described involves generating all possible permutations of the input array of size N. To explore each permutation, a temporary copy of the input array is likely created at each step. Therefore, the auxiliary space used would be proportional to the size of the input array itself, as we need to hold a potentially different ordering of all N people. This copy accounts for O(N) space. Hence, the overall space complexity is O(N).

Optimal Solution

Approach

The problem asks us to sort people based on their heights. The clever trick is to use the heights as a direct link to the people's names, because the heights are unique. This allows us to avoid slow comparisons.

Here's how the algorithm would work step-by-step:

Create a direct link between each person's height and their name, using the height as a special identifier.
Sort the heights from smallest to largest.
Using the sorted heights, look up the corresponding name for each height.
List the names in the order that their heights were sorted.

Code Implementation

def sort_the_people(names, heights):
    height_to_name = {}
    # Create a dictionary to map heights to names.
    for index in range(len(names)):
        height_to_name[heights[index]] = names[index]

    sorted_heights = sorted(heights)

    sorted_names = []

    # Build the result by looking up names using sorted heights.
    for height in sorted_heights:
        sorted_names.append(height_to_name[height])

    sorted_names.reverse()
    # Reverse to get names sorted by height descending

    return sorted_names

Big(O) Analysis

Time Complexity

O(n log n) – The time complexity is dominated by the sorting of the heights. Creating the mapping between height and name takes O(n) time. Sorting the heights, assuming a typical comparison-based sorting algorithm like merge sort or quicksort, takes O(n log n) time. Looking up the names based on the sorted heights takes O(n) time. Since O(n log n) grows faster than O(n), the overall time complexity is O(n log n).

Space Complexity

O(N) – The algorithm creates a mapping between heights and names, requiring auxiliary space proportional to the number of people, N. Sorting the heights also generally requires auxiliary space, which in the worst case can be proportional to the number of people, N. Finally, the output list of sorted names also uses space proportional to N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty names or heights array	Return an empty array immediately as there's nothing to sort.
Arrays of unequal length	Throw an IllegalArgumentException (or similar) indicating invalid input, or return an empty array.
Single element array	Return the input names array directly, as it is already sorted.
All heights are the same	The sorting algorithm should still function correctly, returning names in the order they appeared in the original array based on stability.
Heights are in reverse sorted order	Check that the sorting algorithm performs reasonably well (e.g., doesn't degrade to O(n^2) for quicksort).
Very large number of people (nearing memory limits)	Consider the memory footprint of the sorting algorithm and data structures used (e.g., avoid unnecessary copies).
Heights containing duplicate values with different corresponding names	The algorithm will sort based on the height values, maintaining the original ordering of names for equal heights if the sort is stable.
Names containing Unicode characters or special characters	Ensure the sorting algorithm and string comparison handles Unicode characters correctly to avoid unexpected behavior.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `names` and `heights` arrays be empty or null?
Are the lengths of the `names` and `heights` arrays guaranteed to be the same?
What is the range of values for the `heights`? Are they all positive integers?
Are the names guaranteed to be unique, or can there be duplicate names?
What is the expected output if the input arrays are empty?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the people in their original order.
Consider every single possible order the people could be in. This means rearranging their positions in every conceivable way.
For each of these orderings, check if the heights are sorted from tallest to shortest.
If the heights are sorted correctly, then you've found a solution.
If you check every single possible ordering and haven't found a solution, then there is no possible ordering that fulfills the requirements.

Code Implementation

import itertools

def sort_the_people_brute_force(names, heights):
    number_of_people = len(names)

    # Generate all possible permutations of indices
    index_permutations = itertools.permutations(range(number_of_people))

    for permutation in index_permutations:
        is_sorted = True
        # Check if the current permutation sorts heights
        for i in range(number_of_people - 1):
            if heights[permutation[i]] < heights[permutation[i + 1]]:
                is_sorted = False
                break

        # If the permutation is sorted, construct the result
        if is_sorted:
            sorted_names = [names[permutation[i]] for i in range(number_of_people)]
            return sorted_names

    # If no permutation sorts the heights, return an empty list
    return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Create a direct link between each person's height and their name, using the height as a special identifier.
Sort the heights from smallest to largest.
Using the sorted heights, look up the corresponding name for each height.
List the names in the order that their heights were sorted.

Code Implementation

def sort_the_people(names, heights):
    height_to_name = {}
    # Create a dictionary to map heights to names.
    for index in range(len(names)):
        height_to_name[heights[index]] = names[index]

    sorted_heights = sorted(heights)

    sorted_names = []

    # Build the result by looking up names using sorted heights.
    for height in sorted_heights:
        sorted_names.append(height_to_name[height])

    sorted_names.reverse()
    # Reverse to get names sorted by height descending

    return sorted_names

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty names or heights array	Return an empty array immediately as there's nothing to sort.
Arrays of unequal length	Throw an IllegalArgumentException (or similar) indicating invalid input, or return an empty array.
Single element array	Return the input names array directly, as it is already sorted.
All heights are the same	The sorting algorithm should still function correctly, returning names in the order they appeared in the original array based on stability.
Heights are in reverse sorted order	Check that the sorting algorithm performs reasonably well (e.g., doesn't degrade to O(n^2) for quicksort).
Very large number of people (nearing memory limits)	Consider the memory footprint of the sorting algorithm and data structures used (e.g., avoid unnecessary copies).
Heights containing duplicate values with different corresponding names	The algorithm will sort based on the height values, maintaining the original ordering of names for equal heights if the sort is stable.
Names containing Unicode characters or special characters	Ensure the sorting algorithm and string comparison handles Unicode characters correctly to avoid unexpected behavior.