Zynga Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
This approach doesn't seem to be constant space. It's linear space - i.e. creating a new array that's within a constant of n, the length of the original array.
If the array isn't sorted, this cannot be done in linear time, so I'm assuming that the array is sorted.
Sorry I'm just a little confused by the question. Am I way off base here?
Suppose the array has numbers ranging from 20 to 200. Declare an array of size (200 - 20) = 180 and initialize all values to 0. Let's call this array duplicates.
Suppose the array in which we have to find duplicates is named arr.
Loop through arr. For every arr[i] increment duplicates[arr[i] - 20].
After the loop is complete, duplicates[i] will hold the number of times (i + 20) occurred in arr.
Its O(lg n) for each node. You will end up inserting n nodes in worst case, that's O(n lg n).
Yes, thats correct, each insertion will taken O(log n) time and overall it will take O(nlogn)
How will you do it in linear time and constant space?
- A July 08, 2012