W
William
I would appreciate your help on the following programming questions:
1. Given an array of length N containing integers between 1 and N,
determine if it contains any duplicates.
HINT: [Is there an O(n) time solution that uses only O(1) extra space and
does not destroy the original array?]
The solution is:
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/January2004.html
but I don't understand what they meant by "Let f(x) be the location of the
array at address x."
2. Sort an array of size n containing integers between 1 and K, given a
temporary scratch integer array of size K.
HINT: Compute cumulative counts of integers in the auxiliary array. Now
scan the original array, rotating cycles!
3. An array of size k contains integers between 1 and n. You are given
an additional scratch array of size n. Compress the original array by
removing duplicates in it. What if k << n?
HINT: Can be done in O(k) time i.e. without initializing the auxiliary
array!
Any solutions, partial solutions, or algorithms to the above problems is
greatly appreciated.
William
1. Given an array of length N containing integers between 1 and N,
determine if it contains any duplicates.
HINT: [Is there an O(n) time solution that uses only O(1) extra space and
does not destroy the original array?]
The solution is:
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/January2004.html
but I don't understand what they meant by "Let f(x) be the location of the
array at address x."
2. Sort an array of size n containing integers between 1 and K, given a
temporary scratch integer array of size K.
HINT: Compute cumulative counts of integers in the auxiliary array. Now
scan the original array, rotating cycles!
3. An array of size k contains integers between 1 and n. You are given
an additional scratch array of size n. Compress the original array by
removing duplicates in it. What if k << n?
HINT: Can be done in O(k) time i.e. without initializing the auxiliary
array!
Any solutions, partial solutions, or algorithms to the above problems is
greatly appreciated.
William