Jobs

Interviews

Discussions

Convert Object to JSON String

Medium

Google

4 views

Implement a function jsonStringify(object) that converts a JavaScript object into a JSON string. You cannot use the built-in JSON.stringify() method.

The function should handle the following data types:

Null
Boolean
Number (including NaN and Infinity)
String (escape special characters)
Array
Object

Special considerations:

Handle circular references to prevent infinite loops. Return a string "[Circular]" in case of circular references
undefined values in objects should be excluded from the final JSON string.
NaN and Infinity should be represented as null.

Example:

const obj = { a: 1, b: "hello", c: [true, false, null] };
jsonStringify(obj); // Output: '{"a":1,"b":"hello","c":[true,false,null]}'

const arr = [1, "world", { x: null }];
jsonStringify(arr); // Output: '[1,"world",{"x":null}]'

const circularObj = { };
circularObj.myself = circularObj;
jsonStringify(circularObj); // Output: '{\"myself\":\"[Circular]\

Convert Object to JSON String

Medium

Google

4 views

Implement a function jsonStringify(object) that converts a JavaScript object into a JSON string. You cannot use the built-in JSON.stringify() method.

The function should handle the following data types:

Null
Boolean
Number (including NaN and Infinity)
String (escape special characters)
Array
Object

Special considerations:

Handle circular references to prevent infinite loops. Return a string "[Circular]" in case of circular references
undefined values in objects should be excluded from the final JSON string.
NaN and Infinity should be represented as null.

Example:

const obj = { a: 1, b: "hello", c: [true, false, null] };
jsonStringify(obj); // Output: '{"a":1,"b":"hello","c":[true,false,null]}'

const arr = [1, "world", { x: null }];
jsonStringify(arr); // Output: '[1,"world",{"x":null}]'

const circularObj = { };
circularObj.myself = circularObj;
jsonStringify(circularObj); // Output: '{\"myself\":\"[Circular]\

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:

What data types can the object's values be? Should I expect primitive types, other objects, arrays, null values, or a combination?
Are there any limitations on the depth or complexity of the object? Could it contain circular references?
How should I handle special values like Infinity, NaN, or undefined in the object?
Is there a specific format or encoding required for the output JSON string (e.g., dealing with special characters like quotes or backslashes)?
Should the order of the keys in the resulting JSON string be preserved from the input object, or is any order acceptable?

Brute Force Solution

Approach

The brute force approach to converting an object to a JSON string involves handling each possible data type separately and recursively. It essentially inspects every field in the object and transforms it based on its type. This method explores all potential string representations until the entire object is converted.

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

First, check if the input is a simple type, like a number, text, true, false, or null. If so, convert it directly to its text representation.
If the input is a list or collection, go through each item in the list one by one. Convert each item individually using these same steps, and then combine the converted items into a text string representing the entire list.
If the input is a dictionary or object with key-value pairs, look at each key-value pair individually. Convert both the key and the value into their text representation, and combine them into a text string representing the key-value pair.
Make sure to add special characters like commas, colons, brackets, and braces in the correct places to make the final text follow the correct JSON structure.
Repeat these steps for every nested object, list, or dictionary within the original object, until everything is converted to a single, complete text string.
Handle any special characters or edge cases, such as empty lists or objects, to avoid errors in the final JSON output.

Code Implementation

def convert_to_json_string(object_to_convert):

    if object_to_convert is None:
        return "null"

    if isinstance(object_to_convert, bool):
        return "true" if object_to_convert else "false"

    if isinstance(object_to_convert, (int, float)): # Numbers are converted directly
        return str(object_to_convert)

    if isinstance(object_to_convert, str):
        return '"' + object_to_convert + '"'

    if isinstance(object_to_convert, list):
        list_elements = []
        for element in object_to_convert:
            list_elements.append(convert_to_json_string(element))

        return '[' + ','.join(list_elements) + ']'

    if isinstance(object_to_convert, dict):
        # Dictionaries need special formatting of keys and values
        dictionary_elements = []
        for key, value in object_to_convert.items():

            key_string = convert_to_json_string(key)
            value_string = convert_to_json_string(value)

            dictionary_elements.append(key_string + ':' + value_string)

        # Construct the JSON representation of the dictionary
        return '{' + ','.join(dictionary_elements) + '}'

    # Raise exception in case we cannot serialize the given object
    raise TypeError(f"Object of type '{type(object_to_convert).__name__}' is not JSON serializable")

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the structure of the input object. The algorithm visits each element in the object (or nested objects, lists, dictionaries) exactly once to convert it to its JSON string representation. Thus, if n is the total number of elements (primitive values, keys, objects, list items) within the object, the algorithm performs a constant amount of work for each of these elements. The overall complexity is therefore directly proportional to the number of elements in the input, resulting in O(n).

Space Complexity

O(D) – The space complexity of this recursive approach is primarily determined by the maximum depth of the recursion, D, where D represents the maximum nesting level of objects, lists, and dictionaries within the input. Each recursive call adds a new frame to the call stack, storing local variables and function arguments for that level of nesting. In the worst-case scenario, the object is deeply nested, leading to a call stack of depth D. Therefore, the auxiliary space used is proportional to the maximum depth of nesting.

Optimal Solution

Approach

To transform an object into a text format resembling its structure, we need to handle different types of data within the object. The best approach is to systematically examine each part of the object and convert it into the correct text representation while following specific formatting rules.

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

First, check what kind of thing we are dealing with. It could be a simple value like a number or text, or it could be a more complicated structure like another object or a list.
If it's a simple value, just convert it directly into text format based on its type. For text, make sure to add quotation marks.
If it's another object, we'll need to go through each piece of information inside that object and convert each piece into text format. Then, surround all these pieces with curly braces.
If it's a list, we'll convert each item in the list into text format, just like we handled single values or other objects. Then, surround all these converted items with square brackets.
For each object, also make sure to add commas to separate each pair of information within it.
Remember to handle special cases, like when a value is 'nothing' or 'missing'. Convert these to the text 'null'.
Finally, piece everything together according to the structural hierarchy of the original object. Start with the outside layer, work your way inward, and remember to add all the necessary text markers (like curly braces, square brackets, commas, and quotation marks).

Code Implementation

def convert_object_to_json_string(object_to_convert):

    if object_to_convert is None:
        return "null"

    object_type = type(object_to_convert)

    if object_type is str:
        return '"' + object_to_convert + '"'
    elif object_type is int or object_type is float or object_type is bool:
        return str(object_to_convert)
    elif object_type is list:
        # Recursively convert each list element to JSON.
        json_list = [convert_object_to_json_string(item) for item in object_to_convert]
        return '[' + ','.join(json_list) + ']'
    elif object_type is dict:
        # This block handles dictionaries/objects.
        json_pairs = []
        for key, value in object_to_convert.items():
            json_key = convert_object_to_json_string(key)
            json_value = convert_object_to_json_string(value)
            json_pairs.append(json_key + ':' + json_value)

        # Join key-value pairs with commas, enclose in curly braces.
        return '{' + ','.join(json_pairs) + '}'
    else:
        return '"' + str(object_to_convert) + '"'

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the object's structure, potentially traversing all its elements. In the worst-case scenario, where the object is deeply nested or contains a large number of key-value pairs or list elements, the algorithm needs to visit each of these elements once to convert them into their JSON string representation. Therefore, the time complexity is directly proportional to the number of elements (n) in the object structure, resulting in a time complexity of O(n).

Space Complexity

O(N) – The algorithm's space complexity is primarily determined by the depth of nested objects and lists within the input object. In the worst-case scenario, the object could have a nesting depth of N, where N represents the total number of elements across all levels of nesting. Each level of nesting potentially adds a frame to the call stack due to recursion. Thus, the auxiliary space used by the recursion stack can grow linearly with the depth of nesting, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or undefined object input	Return 'null' string to represent null/undefined objects in JSON.
Empty object input ({})	Return '{}' to represent an empty JSON object.
Object with circular references	Detect cycles using a Set to track visited objects and throw an error or return 'null' to prevent infinite recursion.
Object containing primitive types (string, number, boolean, null)	Convert primitive values directly to their JSON representation (e.g., number to string, true to 'true').
Object containing arrays of different data types	Recursively convert array elements to their JSON representations, handling nested objects and arrays.
Object with properties containing special characters (e.g., quotes, backslashes, newline)	Properly escape special characters in property names and string values using backslashes.
Object with Date objects	Convert Date objects to their ISO string representation using toISOString().
Large object with many nested levels	Implement iterative solution to avoid stack overflow errors or limit the recursion depth and return an error.

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:

What data types can the object's values be? Should I expect primitive types, other objects, arrays, null values, or a combination?
Are there any limitations on the depth or complexity of the object? Could it contain circular references?
How should I handle special values like Infinity, NaN, or undefined in the object?
Is there a specific format or encoding required for the output JSON string (e.g., dealing with special characters like quotes or backslashes)?
Should the order of the keys in the resulting JSON string be preserved from the input object, or is any order acceptable?

Brute Force Solution

Approach

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

First, check if the input is a simple type, like a number, text, true, false, or null. If so, convert it directly to its text representation.
If the input is a list or collection, go through each item in the list one by one. Convert each item individually using these same steps, and then combine the converted items into a text string representing the entire list.
If the input is a dictionary or object with key-value pairs, look at each key-value pair individually. Convert both the key and the value into their text representation, and combine them into a text string representing the key-value pair.
Make sure to add special characters like commas, colons, brackets, and braces in the correct places to make the final text follow the correct JSON structure.
Repeat these steps for every nested object, list, or dictionary within the original object, until everything is converted to a single, complete text string.
Handle any special characters or edge cases, such as empty lists or objects, to avoid errors in the final JSON output.

Code Implementation

def convert_to_json_string(object_to_convert):

    if object_to_convert is None:
        return "null"

    if isinstance(object_to_convert, bool):
        return "true" if object_to_convert else "false"

    if isinstance(object_to_convert, (int, float)): # Numbers are converted directly
        return str(object_to_convert)

    if isinstance(object_to_convert, str):
        return '"' + object_to_convert + '"'

    if isinstance(object_to_convert, list):
        list_elements = []
        for element in object_to_convert:
            list_elements.append(convert_to_json_string(element))

        return '[' + ','.join(list_elements) + ']'

    if isinstance(object_to_convert, dict):
        # Dictionaries need special formatting of keys and values
        dictionary_elements = []
        for key, value in object_to_convert.items():

            key_string = convert_to_json_string(key)
            value_string = convert_to_json_string(value)

            dictionary_elements.append(key_string + ':' + value_string)

        # Construct the JSON representation of the dictionary
        return '{' + ','.join(dictionary_elements) + '}'

    # Raise exception in case we cannot serialize the given object
    raise TypeError(f"Object of type '{type(object_to_convert).__name__}' is not JSON serializable")

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, check what kind of thing we are dealing with. It could be a simple value like a number or text, or it could be a more complicated structure like another object or a list.
If it's a simple value, just convert it directly into text format based on its type. For text, make sure to add quotation marks.
If it's another object, we'll need to go through each piece of information inside that object and convert each piece into text format. Then, surround all these pieces with curly braces.
If it's a list, we'll convert each item in the list into text format, just like we handled single values or other objects. Then, surround all these converted items with square brackets.
For each object, also make sure to add commas to separate each pair of information within it.
Remember to handle special cases, like when a value is 'nothing' or 'missing'. Convert these to the text 'null'.
Finally, piece everything together according to the structural hierarchy of the original object. Start with the outside layer, work your way inward, and remember to add all the necessary text markers (like curly braces, square brackets, commas, and quotation marks).

Code Implementation

def convert_object_to_json_string(object_to_convert):

    if object_to_convert is None:
        return "null"

    object_type = type(object_to_convert)

    if object_type is str:
        return '"' + object_to_convert + '"'
    elif object_type is int or object_type is float or object_type is bool:
        return str(object_to_convert)
    elif object_type is list:
        # Recursively convert each list element to JSON.
        json_list = [convert_object_to_json_string(item) for item in object_to_convert]
        return '[' + ','.join(json_list) + ']'
    elif object_type is dict:
        # This block handles dictionaries/objects.
        json_pairs = []
        for key, value in object_to_convert.items():
            json_key = convert_object_to_json_string(key)
            json_value = convert_object_to_json_string(value)
            json_pairs.append(json_key + ':' + json_value)

        # Join key-value pairs with commas, enclose in curly braces.
        return '{' + ','.join(json_pairs) + '}'
    else:
        return '"' + str(object_to_convert) + '"'

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or undefined object input	Return 'null' string to represent null/undefined objects in JSON.
Empty object input ({})	Return '{}' to represent an empty JSON object.
Object with circular references	Detect cycles using a Set to track visited objects and throw an error or return 'null' to prevent infinite recursion.
Object containing primitive types (string, number, boolean, null)	Convert primitive values directly to their JSON representation (e.g., number to string, true to 'true').
Object containing arrays of different data types	Recursively convert array elements to their JSON representations, handling nested objects and arrays.
Object with properties containing special characters (e.g., quotes, backslashes, newline)	Properly escape special characters in property names and string values using backslashes.
Object with Date objects	Convert Date objects to their ISO string representation using toISOString().
Large object with many nested levels	Implement iterative solution to avoid stack overflow errors or limit the recursion depth and return an error.