Hi all, this week we will be going over arrays, sets and map. Yes, these are all basic data types/structures but they also are used to solve many problems. They allow us to hold multiple values, represent graphs, find unique items and much more. One thing to note is that sometimes they have different implementations in different languages or don't exist as base types for a given language. For instance Python has set as an object type but sets are not a built in type in Golang, they can be made through a clever usage of maps though. Now lets overview the basic info for each.
Arrays:
Memory usage, based on the size of the N objects stored
O(1) access time for a given index
O(1) appends depending on implementation
O(N) to search over N given objects unless the array is ordered
O(N) to deletion at worst case if the index is not known.
An array is a group of items, generally of the same type. They are accessible either by iterating over the items to visit each item or by specifying the index of that item. Common notation for an array of integers would be [0,1,2].
Sets:
O(1) access time for object, if hashset implementation is used
O(1) search time as well
O(1) object insertions
O(1) deletion
A set is a unique grouping of items. In a set the items are accessible by looking for the item. Common notation for a set would be {0,1,2}
Maps:
O(1) insertion time depending on the implementation
O(1) access time if you know the key for the map, and are using a hashmap implementation
O(1) deletions
O(N) search if you don't know the key
A map is a grouping of items that are composed of a key and a value. You can access the items by either iterating over the map keys or by directly getting a value for a given key.
This week the problems will be listed here along with a short approach and the code will be linked. This change has been done at the suggestion of one of our readers so that the answer isn’t immediately there and to prevent spoilers of the solution.
Problem 1: Given an array of numbers find the number of unique numbers.
Loop through the array and then insert the items into the set. Return the set
Complexity O(N) where n is the number of numbers to be processed. Storage of O(N) or less.
Problem 2: Given a list of water animals and a list of mammals return a list that are water mammals.
Loop over the first list and then see if the item is present in the second list. Append animals in both to a list, return the list.
Complexity of O(N^2) for this solution, could be O(N) where a set union can be done from sets created from the animal and mammal lists.
Problem 3: Given a list of letters and a list of words see if the words can be created, return a map of the words and true or false for whether they can be created.
Create a map of the number of letters in the alphabet. Then for the list of words make a map of the letters in the word. Then see if enough letters are present in the alphabet map to meet the number of characters needed.
Complexity of O(N^2) where N is the number of letters you have to go through either in the set of characters being used to build off of or the number of letters in the words being compared.
Thanks for coming and reviewing these interview questions. If you have any critiques to the solutions, recommendation for formatting or any problems that you would like featured, reach out via allen@staysharp.email. Have a good weekend and Happy Prepping!
— Allen