Question : During the interview with GlobalLogic, I was asked to find the duplicate numbers
in the given array of random number.
Numbers are random & you don't know in what range these numbers lie, i.e. you
just know the size of array but no information is available about the numbers in it
before hand. No collection can be used.
And the complexity of this should be O(n). Another issue is with these interviewers,
they themselves are not ready to clear the question & force you to make mistakes.
Solution : I am not sure about an effective solution here.
Though we can find the such duplicate numbers in below ways. Coding for this is
quite simple & I am not giving any code for these, will just give the approach.
Case 1 : If collections can be used then we can use -
(A) HashSet, keep on adding the elements in this hashset & if add() returns false
then it means number is repeated & add this number to your result array. This
array you will return from your method as you are giving all the repeated
numbers
(B) If you need to find how many times each number is appearing in the array or
repeating in the array. Use HashMap, where key will be the number & value will
be the count of appearance. So keep on updating this hashmap while iterating
through the received array of numbers.
Once done, you can browse/iterate the above hashmap to get the required
results. So here running complexity, you can get around O(n) but will take extra
space for collections.
Case 2 : If collections can't be used -
Sort the received array of numbers with your favourite sorting algorithm. And then
iterate through the sorted array, every repeated number will adjacent to each other in
sorted array & that you can identify.
So here running time will be quite dependent on the sorting algorithm used.
If you have better approach please let me know.
in the given array of random number.
Numbers are random & you don't know in what range these numbers lie, i.e. you
just know the size of array but no information is available about the numbers in it
before hand. No collection can be used.
And the complexity of this should be O(n). Another issue is with these interviewers,
they themselves are not ready to clear the question & force you to make mistakes.
Solution : I am not sure about an effective solution here.
Though we can find the such duplicate numbers in below ways. Coding for this is
quite simple & I am not giving any code for these, will just give the approach.
Case 1 : If collections can be used then we can use -
(A) HashSet, keep on adding the elements in this hashset & if add() returns false
then it means number is repeated & add this number to your result array. This
array you will return from your method as you are giving all the repeated
numbers
(B) If you need to find how many times each number is appearing in the array or
repeating in the array. Use HashMap, where key will be the number & value will
be the count of appearance. So keep on updating this hashmap while iterating
through the received array of numbers.
Once done, you can browse/iterate the above hashmap to get the required
results. So here running complexity, you can get around O(n) but will take extra
space for collections.
Case 2 : If collections can't be used -
Sort the received array of numbers with your favourite sorting algorithm. And then
iterate through the sorted array, every repeated number will adjacent to each other in
sorted array & that you can identify.
So here running time will be quite dependent on the sorting algorithm used.
If you have better approach please let me know.
