2692. Make Object Immutable
Problem Description
The given problem requires the creation of a function that transforms any object or array into an immutable one. An "immutable" object or array is one that cannot be changed after its creation. If an attempt is made to modify it in any way, it should throw a specific error message. The instructions specify three situations where error messages should be returned:
-
Modifying a property of an object: Attempting to change any property on the object should result in an error with the message in the format
Error Modifying: ${key}, where${key}is the property key attempted to be modified. -
Modifying an index of an array: Attempting to change any index on the array should result in an error with the message in the format
Error Modifying Index: ${index}, where${index}is the array index attempted to be modified. -
Calling a method that mutates the array: Applying any method that can alter the array (such as 'pop', 'push', 'shift', 'unshift', 'splice', 'sort', 'reverse') should result in an error with the message in the format
Error Calling Method: ${methodName}, where${methodName}is the name of the mutating method that was attempted to be called.
Moreover, the object that will be passed into our function is a regular JSON object or array, which implies that it is a structure that resulted from JSON.parse().
Intuition
To solve this task, the Proxy object in JavaScript is an ideal candidate. A Proxy object is used to define custom behavior for fundamental operations on objects (like property lookup, assignment, enumeration, function invocation, etc.). Therefore, Proxies can be used to create immutable objects by intercepting and customizing operation behaviors.
The approach is to use recursive depth-first search (DFS) to traverse through the given object or array and wrap all objects and arrays within it using Proxy. If the current value is an array, we additionally wrap each of the array's mutating methods in a Proxy.
The solution can be broken down into three main parts:
-
Handling object property assignments: For objects, we define a Proxy handler that intercepts any attempt to set a property value and instead throws the corresponding error message.
-
Handling array index assignments: Similarly, for arrays, we define another Proxy handler that intercepts any attempt to set a value at an array index and throws the relevant error message.
-
Handling mutating method calls on arrays: Lastly, for arrays, we define a third Proxy handler that intercepts any call to a mutating method and throws the appropriate error message.
By wrapping each of these parts in a Proxy with the corresponding handler, we ensure that any attempts to mutate the object or array will be caught and the appropriate error will be thrown, effectively achieving immutability.
Which one best describes the time complexity of the following code?
1int factorial(int n) {
2 if (n < 0) {
3 return -1;
4 } else if (n == 0) {
5 return 1;
6 } else {
7 return n * factorial(n - 1);
8 }
9}
Solution Approach
The provided TypeScript solution employs a design pattern commonly known as a Proxy to wrap objects, arrays, and certain methods to intercept operations that modify them. When such operations are attempted, the Proxy intercepts them and throws a string literal representing the appropriate error message.
Here's a step-by-step breakdown of the approach:
Wrapping in Proxy using Recursive DFS
- The
dfsfunction is employed to perform a depth-first search on the input object (or array). This function recursively processes each property or element in the object/array. - If a property's value is an object or array (determined using
typeof obj[key] === 'object'andobj[key] !== null), the function is recursively called for that value (nested structure). - This ensures that every nested object or array within the original input is processed and wrapped in a Proxy if necessary.
Handling Array Mutations
- Once a nested structure is identified as an array, each of the specified mutating methods is wrapped in a Proxy using the
fnHandler. This handler intercepts and throws an error if one of the mutating methods ('pop','push','shift','unshift','splice','sort','reverse') is called. - A separate Proxy, with
arrayHandleras the handler, wraps the array itself. This handles any attempts to modify an array's indices directly, such asarray[1] = 'new value';.
Preventing Object Mutations
- If the nested structure is an object, the
objectHandlerhandler is used to wrap it in a Proxy. This prevents any property assignments, such asobj.prop = 'new value';.
Error Handling and Proxy Handlers
- The Proxy handlers (
arrayHandler,objectHandler, andfnHandler) utilize thesettrap (for properties and indices) and theapplytrap (for function application) to catch attempted modifications or function calls. - When a trap is triggered, the corresponding error message is thrown. For example, if
setis invoked on a property, the errorError Modifying: ${String(prop)}is thrown. For a mutating method call,Error Calling Method: ${target.name}is the error.
Finalizing and Returning the Immutable Structure
- After wrapping the object/array elements with the appropriate Proxies, the
dfsfunction ensures the modified structure is returned up the call stack. - The initial call to
dfsfrom themakeImmutablefunction returns the fully processed and now immutable (through Proxies) object or array.
By using Proxies and this recursive strategy, the code ensures that any attempt to alter the original structure of the given object or array at any level throws an error and prevents the alteration, effectively making the structure immutable.
Which of these pictures shows the visit order of a depth-first search?
Example Walkthrough
Let's go through a small example to illustrate the solution approach. Suppose we have an object like this:
1let mutableObject = { 2 user: { 3 name: "Alice", 4 age: 30 5 }, 6 scores: [78, 95, 88] 7};
Our goal is to make this object immutable using the solution approach described. We'll invoke our makeImmutable function with mutableObject as the argument. Here's what happens in the background:
- The
dfsfunction is called, which starts to traverse themutableObject. - It encounters an object at
mutableObject.user, which it then wraps in a Proxy with theobjectHandler.- Now, if we try to do something like
mutableObject.user.age = 31;, it will throw an error:Error Modifying: age.
- Now, if we try to do something like
- It then encounters an array at
mutableObject.scores.- Each mutating array method such as
push,pop, etc., is wrapped in a Proxy with thefnHandler. Any subsequent call likemutableObject.scores.push(100);will throw an error:Error Calling Method: push. - The array itself is also wrapped in a Proxy with the
arrayHandler. An attempted index modification likemutableObject.scores[0] = 79;results inError Modifying Index: 0.
- Each mutating array method such as
After the process completes, any attempt to alter mutableObject will result in an error, and the structure becomes effectively immutable. For example:
1// Example execution after making mutableObject immutable
2const immutableObject = makeImmutable(mutableObject);
3
4try {
5 immutableObject.user.name = "Bob";
6} catch (e) {
7 console.log(e); // Output: Error Modifying: name
8}
9
10try {
11 immutableObject.scores[1] = 100;
12} catch (e) {
13 console.log(e); // Output: Error Modifying Index: 1
14}
15
16try {
17 immutableObject.scores.push(100);
18} catch (e) {
19 console.log(e); // Output: Error Calling Method: push
20}
By utilizing Proxies combined with the recursive depth-first search, the example shows how the original object mutableObject is transformed into immutableObject, which preserves the original state by preventing any modifications.
Solution Implementation
1from types import FunctionType
2from collections.abc import MutableMapping, MutableSequence
3
4# Define a type for objects that can be either lists or dictionaries.
5ImmutableObject = MutableSequence | MutableMapping
6
7# This function takes an object and returns an immutable version of it.
8# Any attempt to modify the object will raise a runtime error.
9def make_immutable(obj: ImmutableObject) -> ImmutableObject:
10
11 # Function to raise an error for an attempted property modification.
12 def error_modifier(property_name):
13 raise AttributeError(f"Error Modifying Property: {property_name}")
14
15 # Function to raise an error for an attempted method call.
16 def error_calling_method(method_name):
17 raise AttributeError(f"Error Calling Method: {method_name}")
18
19 # Wrapper that prevents attribute setting and method calls on objects.
20 class FrozenObject:
21 def __init__(self, obj):
22 object.__setattr__(self, '_obj', obj)
23
24 def __setattr__(self, key, value):
25 error_modifier(key)
26
27 def __getitem__(self, key):
28 return object.__getitem__(self._obj, key)
29
30 def __setitem__(self, key, value):
31 error_modifier(key)
32
33 def __getattr__(self, item):
34 attr = getattr(self._obj, item)
35 if isinstance(attr, FunctionType):
36 if item in modifying_methods:
37 return lambda *args, **kwargs: error_calling_method(item)
38 else:
39 return attr
40 else:
41 return attr
42
43 # List of method names that modify the list. These will be disabled.
44 modifying_methods = ['pop', 'push', 'append', 'extend', 'insert', 'remove', 'sort', 'reverse', 'clear']
45
46 # Recursive function to convert all nested objects and lists into immutable versions.
47 def deep_freeze(current_obj: ImmutableObject) -> ImmutableObject:
48 if isinstance(current_obj, dict):
49 for key, value in current_obj.items():
50 if isinstance(value, (dict, list)):
51 current_obj[key] = deep_freeze(value)
52 elif isinstance(current_obj, list):
53 for index in range(len(current_obj)):
54 if isinstance(current_obj[index], (dict, list)):
55 current_obj[index] = deep_freeze(current_obj[index])
56
57 return FrozenObject(current_obj)
58
59 # Start the deep freeze process from the root object.
60 return deep_freeze(obj)
61
62# Usage example:
63# my_immutable_obj = make_immutable({'x': 5})
64# my_immutable_obj.x = 6 # Raises "AttributeError: Error Modifying Property: x"
651import java.lang.reflect.Array;
2import java.lang.reflect.Proxy;
3import java.util.HashMap;
4import java.util.Map;
5import java.util.List;
6
7public class ImmutableObjectHelper {
8
9 // This interface defines a type that can be either a List or a Map.
10 public interface ImmutableObject {}
11
12 // This function takes an object and returns an immutable version of it.
13 // Any attempt to modify the object will result in a runtime error.
14 public static ImmutableObject makeImmutable(ImmutableObject obj) {
15 // Begin the process of deep freezing the given object.
16 return deepFreeze(obj);
17 }
18
19 // Proxy handler for Lists to prevent modification operations.
20 private static InvocationHandler listHandler = (proxy, method, args) -> {
21 throw new UnsupportedOperationException("Error Modifying Method: " + method.getName());
22 };
23
24 // Proxy handler for Maps to prevent modification operations.
25 private static InvocationHandler mapHandler = (proxy, method, args) -> {
26 throw new UnsupportedOperationException("Error Modifying Property: " + method.getName());
27 };
28
29 // Recursive function to convert all nested Maps and Lists into immutable versions.
30 private static ImmutableObject deepFreeze(ImmutableObject currentObj) {
31 // Proxy Maps (similar to records or plain objects in TypeScript) with a handler to block modifications.
32 if (currentObj instanceof Map) {
33 Map<?, ?> currentMap = (Map<?, ?>) currentObj;
34 Map<Object, Object> newMap = new HashMap<>();
35 currentMap.forEach((k, v) -> {
36 if (v instanceof ImmutableObject) {
37 newMap.put(k, deepFreeze((ImmutableObject) v));
38 } else {
39 newMap.put(k, v);
40 }
41 });
42 return (ImmutableObject) Proxy.newProxyInstance(
43 ImmutableObject.class.getClassLoader(),
44 new Class[]{Map.class},
45 mapHandler
46 );
47 }
48
49 // Proxy Lists (equivalent to Arrays in TypeScript) with a handler to block modifications.
50 if (currentObj instanceof List) {
51 return (ImmutableObject) Proxy.newProxyInstance(
52 ImmutableObject.class.getClassLoader(),
53 new Class[]{List.class},
54 listHandler
55 );
56 }
57
58 return currentObj;
59 }
60
61 // Usage example:
62 public static void main(String[] args) {
63 Map<String, Object> mutableObj = new HashMap<>();
64 mutableObj.put("x", 5);
65 ImmutableObject myImmutableObj = makeImmutable(mutableObj);
66 // The next line would throw an exception:
67 // ((Map)myImmutableObj).put("x", 6);
68 }
69}
701#include <iostream>
2#include <vector>
3#include <map>
4#include <functional>
5#include <stdexcept>
6
7// Define a variant type for objects that can be either vectors or maps.
8using ImmutableObject = std::variant<std::vector<any>, std::map<any, any>>;
9
10// This function takes an object and returns an immutable version of it.
11// Any attempt to modify the object will result in a runtime error.
12ImmutableObject MakeImmutable(const ImmutableObject& obj) {
13 // Visitor that handles the respective types of objects (vectors or maps).
14 class : public std::visitor<ImmutableObject> {
15 public:
16 // Handle vector type (immutable array in the JavaScript equivalent)
17 ImmutableObject operator()(const std::vector<any>& vec) const {
18 std::vector<any> immutableVec(vec); // Make a copy to ensure the original is not modified.
19
20 // Disable methods that would modify the vector.
21 // Note: C++ does not directly allow the proxying of individual functions as JavaScript does.
22 // This would need to be handled by providing a custom vector implementation or another method.
23 // For this example, assume we've disabled them by an unspecified mechanism.
24 // DisableModifyingMethods(immutableVec);
25
26 return immutableVec;
27 }
28
29 // Handle map type (immutable object in the JavaScript equivalent)
30 ImmutableObject operator()(const std::map<any, any>& map) const {
31 std::map<any, any> immutableMap(map); // Make a copy to ensure the original is not modified.
32
33 // Create a proxy object that would throw an exception upon modification.
34 // Note: C++ does not have a built-in Proxy equivalent as JavaScript does.
35 // Proxying would need to be handled by providing custom methods or another approach.
36 // For this example, assume we've proxied it by an unspecified mechanism.
37 // ProxyModifyingOperations(immutableMap);
38
39 return immutableMap;
40 }
41 } visitor;
42
43 // Apply the visitor to the object to make it immutable.
44 return std::visit(visitor, obj);
45}
46
47// In C++, we can't simply emulate the JavaScript behavior of making objects immutable at runtime due to
48// language constraints. Proxying would require a different approach, like using custom classes to prevent
49// modifications, using const wherever possible, and/or making use of C++'s strong type system to limit
50// access to modification methods. However, neither proxies nor runtime type mutation are idiomatic C++.
51
52// Usage example:
53// std::map<any, any> myMap = {{std::string("x"), 5}};
54// auto myImmutableObj = MakeImmutable(myMap);
55// myImmutableObj["x"] = 6; // This operation would throw an error, if we had a proxy mechanism in place.
56
57int main() {
58 // Usage demonstration goes here.
59 return 0;
60}
611// Define a type for objects that can be either arrays or plain objects.
2type ImmutableObject = Array<any> | Record<any, any>;
3
4// This function takes an object and returns an immutable version of it.
5// Any attempt to modify the object will result in a runtime error.
6function makeImmutable(obj: ImmutableObject): ImmutableObject {
7 // Proxy handler for arrays to prevent modification operations.
8 const arrayHandler: ProxyHandler<Array<any>> = {
9 set: (_, property) => {
10 throw new Error(`Error Modifying Index: ${String(property)}`);
11 },
12 };
13
14 // Proxy handler for objects to prevent modification operations.
15 const objectHandler: ProxyHandler<Record<any, any>> = {
16 set: (_, property) => {
17 throw new Error(`Error Modifying Property: ${String(property)}`);
18 },
19 };
20
21 // Proxy handler for functions to prevent them from being called.
22 // This is specifically used to disable array-modifying methods.
23 const functionHandler: ProxyHandler<Function> = {
24 apply: target => {
25 throw new Error(`Error Calling Method: ${target.name}`);
26 },
27 };
28
29 // Array of method names that modify the array. These will be disabled.
30 const modifyingMethods = ['pop', 'push', 'shift', 'unshift', 'splice', 'sort', 'reverse'];
31
32 // Recursive function to convert all nested objects and arrays into immutable versions.
33 const deepFreeze = (currentObj: ImmutableObject): ImmutableObject => {
34 for (const key in currentObj) {
35 if (typeof currentObj[key] === 'object' && currentObj[key] !== null) {
36 currentObj[key] = deepFreeze(currentObj[key]);
37 }
38 }
39
40 // Proxy arrays with a handler to block modifications.
41 if (Array.isArray(currentObj)) {
42 modifyingMethods.forEach(method => {
43 currentObj[method] = new Proxy(currentObj[method], functionHandler);
44 });
45 return new Proxy(currentObj, arrayHandler);
46 }
47
48 // Proxy objects with a handler to block modifications.
49 return new Proxy(currentObj, objectHandler);
50 };
51
52 // Start the deep freeze process from the root object.
53 return deepFreeze(obj);
54}
55
56// Usage example:
57// const myImmutableObj = makeImmutable({ x: 5 });
58// myImmutableObj.x = 6; // Throws "Error Modifying Property: x"
59What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Time and Space Complexity
The time complexity of the makeImmutable function is O(n), where n is the total number of properties (including nested properties) in the obj. This is because the function uses depth-first search (DFS) to traverse all properties of the object (and any nested objects or arrays), applying a Proxy to each property. Each property is visited exactly once.
The space complexity of the makeImmutable function is also O(n), due to the creation of a new Proxy object for each property in the original object. Additionally, if an array contains mutating methods like 'pop', 'push', etc., it wraps those in Proxies as well, although it doesn't create more than one proxy per method. The space is used for storing the Proxies and the call stack during the recursive DFS traversal.
Which technique can we use to find the middle of a linked list?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.