Jobs

Interviews

Discussions

Compact Object

Medium

Asked by:

3 views

Topics:

RecursionArrays

Given an object or array obj, return a compact object.

A compact object is the same as the original object, except with keys containing falsy values removed. This operation applies to the object and any nested objects. Arrays are considered objects where the indices are keys. A value is considered falsy when Boolean(value) returns false.

You may assume the obj is the output of JSON.parse. In other words, it is valid JSON.

Example 1:

Input: obj = [null, 0, false, 1]
Output: [1]
Explanation: All falsy values have been removed from the array.

Example 2:

Input: obj = {"a": null, "b": [false, 1]}
Output: {"b": [1]}
Explanation: obj["a"] and obj["b"][0] had falsy values and were removed.

Example 3:

Input: obj = [null, 0, 5, [0], [false, 16]]
Output: [5, [], [16]]
Explanation: obj[0], obj[1], obj[3][0], and obj[4][0] were falsy and removed.

Constraints:

obj is a valid JSON object
2 <= JSON.stringify(obj).length <= 10⁶

Try coding it in LeetCode

Compact Object

Medium

Asked by:

3 views

Topics:

RecursionArrays

Given an object or array obj, return a compact object.

You may assume the obj is the output of JSON.parse. In other words, it is valid JSON.

Example 1:

Input: obj = [null, 0, false, 1]
Output: [1]
Explanation: All falsy values have been removed from the array.

Example 2:

Input: obj = {"a": null, "b": [false, 1]}
Output: {"b": [1]}
Explanation: obj["a"] and obj["b"][0] had falsy values and were removed.

Example 3:

Input: obj = [null, 0, 5, [0], [false, 16]]
Output: [5, [], [16]]
Explanation: obj[0], obj[1], obj[3][0], and obj[4][0] were falsy and removed.

Constraints:

obj is a valid JSON object
2 <= JSON.stringify(obj).length <= 10⁶

Try coding it in LeetCode

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 object contain other data types besides objects, arrays, null, and undefined (e.g., numbers, strings, booleans)? If so, how should those be handled?
If an array contains only null or undefined values and is subsequently compacted to an empty array, should it be removed from its parent object/array?
If an object contains only keys with null or undefined values and is subsequently compacted to an empty object, should it be removed from its parent object/array?
Should the original object be modified in place, or should a new compacted object be returned?
What is the maximum depth of nesting I should expect in the input object?

Brute Force Solution

Approach

The brute-force approach to compacting an object involves exhaustively exploring all possible object structures. We achieve this by recursively examining each element within the object and deciding whether to include it or exclude it. This generates every possible compacted object variation, and we then select the desired result.

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

Start with an empty object as one possible result.
Look at the first item in the original object.
Consider two possibilities: either keep this item or remove it.
If you keep the item, include it in a new object.
If you remove the item, proceed without adding it to the new object.
Now move to the next item in the original object and repeat the 'keep or remove' decision.
Keep doing this for every item in the original object.
Each time you go through all the items, you'll have built a new possible compacted object.
After you've explored all the 'keep or remove' options for every item, you will have a collection of compacted objects.
Finally, choose the version that meets whatever criteria defines 'compact' in your problem.

Code Implementation

def compact_object(input_object):
    # Helper function to determine if a value is falsey
    def is_falsey(value):
        return value is None or value is False

    # This function recursively compacts the object
    def compact_recursive(current_object):
        if isinstance(current_object, dict):
            compacted_object = {}
            for key, value in current_object.items():
                compacted_value = compact_recursive(value)
                # Only include values that aren't falsey
                if not is_falsey(compacted_value):
                    compacted_object[key] = compacted_value
            return compacted_object
        elif isinstance(current_object, list):
            # Filter out falsey values from lists
            compacted_list = [compact_recursive(item) for item in current_object if not is_falsey(item)]
            return compacted_list
        else:
            # Base case: return the value if not a dict or list
            return current_object

    # Start the recursive compaction process
    return compact_recursive(input_object)

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible subsets of the input object by considering each element and deciding whether to keep or remove it. This creates a binary decision tree where each level corresponds to an element in the input object, and each branch represents the 'keep' or 'remove' choice. Because there are n elements, the algorithm explores 2^n possible combinations. Therefore, the time complexity grows exponentially with the input size n, resulting in O(2^n).

Space Complexity

O(2^N) – The algorithm recursively explores all possible subsets of the input object, where N represents the number of items in the original object. Each 'keep or remove' decision branches the execution, leading to a binary tree structure of recursive calls. In the worst-case, this creates 2^N possible compacted objects, with each potentially requiring memory to store, plus function call stack overhead during recursion. Therefore, the auxiliary space complexity is O(2^N).

Optimal Solution

Approach

The challenge is to create a new object that contains only the truthy values from the original object. We will essentially be filtering the original object, keeping only what we want.

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

Create a new empty object to store the truthy values.
Go through each key-value pair in the original object.
For each value, check if it is truthy. In Javascript, that means it's not false, 0, an empty string, null, undefined, or NaN.
If the value is truthy, add the key-value pair to the new object.
After going through all the key-value pairs in the original object, return the new object with only the truthy values.

Code Implementation

def compact_object(input_object):
    if input_object is None:
        return None

    if isinstance(input_object, dict):
        # Create a new dictionary to store the compacted object.
        compacted_object = {}
        for key, value in input_object.items():
            compacted_value = compact_object(value)
            if compacted_value:
                compacted_object[key] = compacted_value
        return compacted_object

    if isinstance(input_object, list):
        # Create a new list to store the compacted array.
        compacted_array = []
        for item in input_object:
            compacted_item = compact_object(item)
            # Only append items that are not nullish.
            if compacted_item:
                compacted_array.append(compacted_item)
        return compacted_array

    # Return non-nullish primitive values as is.
    return input_object if input_object else None

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each key-value pair in the original object once. The input size, n, represents the number of key-value pairs in the original object. Inside the loop, a truthiness check and a potential assignment to the new object are performed, both of which take constant time. Since we perform a constant amount of work for each of the n key-value pairs, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm creates a new object to store the truthy key-value pairs. In the worst-case scenario, all values in the original object are truthy, meaning the new object will contain all N key-value pairs from the original object, where N is the number of key-value pairs in the original object. Thus, the auxiliary space used is proportional to the number of key-value pairs in the original object. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or undefined input object	Return an empty object if the input is null or undefined to prevent errors.
Empty object as input	Return an empty object immediately since there is nothing to compact.
Input object with only null or undefined values at the top level	Return an empty object because after removal of null/undefined, the result is empty.
Nested objects and arrays with a mix of valid and invalid values	Recursively process each level to remove null, undefined, empty arrays and objects appropriately.
Deeply nested objects and arrays causing potential stack overflow	While Javascript has recursion limits, the object structure should generally not be so deeply nested as to cause stack overflow for typical interview problems; however iterative approach avoids stackoverflow issue entirely.
Object containing circular references	Circular references could lead to infinite loops; use a Set to keep track of visited objects and arrays to prevent infinite recursion.
An array containing only null/undefined values	Should compact down to an empty array which is then removed if it's the value of a key in the parent object.
Object with number as key and null/undefined value	Should compact as with other cases - remove key-value pair where value is null/undefined.

Null or undefined input object

How to Handle:

Return an empty object if the input is null or undefined to prevent errors.

Empty object as input

How to Handle:

Return an empty object immediately since there is nothing to compact.

Input object with only null or undefined values at the top level

How to Handle:

Return an empty object because after removal of null/undefined, the result is empty.

Nested objects and arrays with a mix of valid and invalid values

How to Handle:

Recursively process each level to remove null, undefined, empty arrays and objects appropriately.

Deeply nested objects and arrays causing potential stack overflow

How to Handle:

While Javascript has recursion limits, the object structure should generally not be so deeply nested as to cause stack overflow for typical interview problems; however iterative approach avoids stackoverflow issue entirely.

Object containing circular references

How to Handle:

Circular references could lead to infinite loops; use a Set to keep track of visited objects and arrays to prevent infinite recursion.

An array containing only null/undefined values

How to Handle:

Should compact down to an empty array which is then removed if it's the value of a key in the parent object.

Object with number as key and null/undefined value

How to Handle:

Should compact as with other cases - remove key-value pair where value is null/undefined.

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 object contain other data types besides objects, arrays, null, and undefined (e.g., numbers, strings, booleans)? If so, how should those be handled?
If an array contains only null or undefined values and is subsequently compacted to an empty array, should it be removed from its parent object/array?
If an object contains only keys with null or undefined values and is subsequently compacted to an empty object, should it be removed from its parent object/array?
Should the original object be modified in place, or should a new compacted object be returned?
What is the maximum depth of nesting I should expect in the input object?

Brute Force Solution

Approach

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

Start with an empty object as one possible result.
Look at the first item in the original object.
Consider two possibilities: either keep this item or remove it.
If you keep the item, include it in a new object.
If you remove the item, proceed without adding it to the new object.
Now move to the next item in the original object and repeat the 'keep or remove' decision.
Keep doing this for every item in the original object.
Each time you go through all the items, you'll have built a new possible compacted object.
After you've explored all the 'keep or remove' options for every item, you will have a collection of compacted objects.
Finally, choose the version that meets whatever criteria defines 'compact' in your problem.

Code Implementation

def compact_object(input_object):
    # Helper function to determine if a value is falsey
    def is_falsey(value):
        return value is None or value is False

    # This function recursively compacts the object
    def compact_recursive(current_object):
        if isinstance(current_object, dict):
            compacted_object = {}
            for key, value in current_object.items():
                compacted_value = compact_recursive(value)
                # Only include values that aren't falsey
                if not is_falsey(compacted_value):
                    compacted_object[key] = compacted_value
            return compacted_object
        elif isinstance(current_object, list):
            # Filter out falsey values from lists
            compacted_list = [compact_recursive(item) for item in current_object if not is_falsey(item)]
            return compacted_list
        else:
            # Base case: return the value if not a dict or list
            return current_object

    # Start the recursive compaction process
    return compact_recursive(input_object)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The challenge is to create a new object that contains only the truthy values from the original object. We will essentially be filtering the original object, keeping only what we want.

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

Create a new empty object to store the truthy values.
Go through each key-value pair in the original object.
For each value, check if it is truthy. In Javascript, that means it's not false, 0, an empty string, null, undefined, or NaN.
If the value is truthy, add the key-value pair to the new object.
After going through all the key-value pairs in the original object, return the new object with only the truthy values.

Code Implementation

def compact_object(input_object):
    if input_object is None:
        return None

    if isinstance(input_object, dict):
        # Create a new dictionary to store the compacted object.
        compacted_object = {}
        for key, value in input_object.items():
            compacted_value = compact_object(value)
            if compacted_value:
                compacted_object[key] = compacted_value
        return compacted_object

    if isinstance(input_object, list):
        # Create a new list to store the compacted array.
        compacted_array = []
        for item in input_object:
            compacted_item = compact_object(item)
            # Only append items that are not nullish.
            if compacted_item:
                compacted_array.append(compacted_item)
        return compacted_array

    # Return non-nullish primitive values as is.
    return input_object if input_object else None

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or undefined input object	Return an empty object if the input is null or undefined to prevent errors.
Empty object as input	Return an empty object immediately since there is nothing to compact.
Input object with only null or undefined values at the top level	Return an empty object because after removal of null/undefined, the result is empty.
Nested objects and arrays with a mix of valid and invalid values	Recursively process each level to remove null, undefined, empty arrays and objects appropriately.
Deeply nested objects and arrays causing potential stack overflow	While Javascript has recursion limits, the object structure should generally not be so deeply nested as to cause stack overflow for typical interview problems; however iterative approach avoids stackoverflow issue entirely.
Object containing circular references	Circular references could lead to infinite loops; use a Set to keep track of visited objects and arrays to prevent infinite recursion.
An array containing only null/undefined values	Should compact down to an empty array which is then removed if it's the value of a key in the parent object.
Object with number as key and null/undefined value	Should compact as with other cases - remove key-value pair where value is null/undefined.

Null or undefined input object

How to Handle:

Return an empty object if the input is null or undefined to prevent errors.

Empty object as input

How to Handle:

Return an empty object immediately since there is nothing to compact.

Input object with only null or undefined values at the top level

How to Handle:

Return an empty object because after removal of null/undefined, the result is empty.

Nested objects and arrays with a mix of valid and invalid values

How to Handle:

Recursively process each level to remove null, undefined, empty arrays and objects appropriately.

Deeply nested objects and arrays causing potential stack overflow

How to Handle:

Object containing circular references

How to Handle:

Circular references could lead to infinite loops; use a Set to keep track of visited objects and arrays to prevent infinite recursion.

An array containing only null/undefined values

How to Handle:

Should compact down to an empty array which is then removed if it's the value of a key in the parent object.

Object with number as key and null/undefined value

How to Handle:

Should compact as with other cases - remove key-value pair where value is null/undefined.