Hot Topics

Morgan Stanley Solution
Technical Round
In this implementation, we use a dictionary self.data
to store the key-value pairs. The put
method adds a new key-value pair to the map, the get
method returns the value associated with a given key, the remove
method removes a key-value pair from the map, the keys
method returns a list of all keys, the values
method returns a list of all values, the items
method returns a list of all key-value pairs as tuples, the is_empty
method returns True
if the map is empty and False
otherwise, and the size
method returns the number of key-value pairs in the map.
The time complexity of the put
, get
, and remove
operations is O(1) on average, as they use the dictionary data structure, which has average constant-time performance for these operations. The time complexity of the keys
, values
, and items
methods is O(n), where n is the number of key-value pairs in the map, as they need to return a list of all keys, values, or key-value pairs. The is_empty
and size
methods have a time complexity of O(1).
The idea behind this solution is to use two pointers, one starting from the beginning of the array (left
) and one starting from the end (right
). The left
pointer moves right until it finds an odd number, and the right
pointer moves left until it finds an even number. When both pointers have found an odd number and an even number, respectively, they are swapped. The loop continues until the pointers cross each other, meaning that all even numbers are now at the beginning of the array and all odd numbers are at the end.
The time complexity of this solution is O(n), where n is the number of elements in the array, as it visits each element at most twice, once with the left
pointer and once with the right
pointer.
This solution uses a dictionary (frequency
) to keep track of the frequency of each number in the array. The dictionary maps each number to its frequency, so if the same number appears multiple times, its frequency is updated in the dictionary. After looping through all the numbers in the array, the function then finds the number with the highest frequency by looping through the items in the dictionary and keeping track of the number with the maximum frequency.
The time complexity of this solution is O(n), where n is the number of elements in the array, as it visits each element once to update its frequency in the dictionary, and then visits each item in the dictionary once to find the most frequent number. The space complexity is O(n), as the frequency dictionary takes up O(n) space.




Popular Category
Hot Topics
Go through our study material. Your Job is awaiting.