Arrays/Java/Finding Duplicates - Revision history

Admin: /* Single element case */

2017-06-06T02:39:31Z

Single element case

← Older revision		Revision as of 02:39, 6 June 2017
Line 26:		Line 26:
	The cost of finding duplicates depends on problem parameters and tradeoffs. Assuming we want the absolute fastest algorithm, we are looking for a constant-time or logarithmic algorithm. (There are no O(1) algorithms here.)		The cost of finding duplicates depends on problem parameters and tradeoffs. Assuming we want the absolute fastest algorithm, we are looking for a constant-time or logarithmic algorithm. (There are no O(1) algorithms here.)

	~~To find duplicates in logarithmic~~ time~~, we have~~ to ~~have the data~~ in a ~~pre-sorted data structure. Then we are looking for an element that meets a particular criteria: normally in~~ binary ~~sort the criteria is a~~ (~~greater than/~~less ~~than/equal to~~) ~~condition. Here, the criteria is the place where the value of element i~~ (~~at zero-indexed i~~) ~~changes from i+1 to i. The binary search algorithm can be outfitted to find this change point, using its head, tail, and middle pointers.~~		'''Log time algorithms:'''
			* O(n log n) one-time cost to sort
			* O(log n) lookup time in a binary tree (less memory)
			* O(1) lookup time in a hash table (more memory)

	~~The next~~-~~fastest, which does not rely on any sorting~~, is a ~~simple enumeration of all the elements of the data structure, adding them~~ to ~~a hash map~~. ~~This operation checks~~ the ~~hash of each object to see if it already exists in~~ the ~~key pool, and if it does, it adds~~ the ~~object to a set~~ of ~~duplicate values. This key lookup is O~~(1). The ~~downside~~ to this ~~approach is that it can be memory intensive~~, ~~or depend on the implementation of the hashtable~~, ~~which needs to balance memory usage with low probability of collisions - two colliding needs~~.		In the particular case given, of the integers 1 through n corresponding to indices 0 through (n-1), we are looking for an element that meets a particular criteria: normally in binary sort the criteria is a (greater than/less than/equal to) condition. Here, the criteria is the place where the value of element i (at zero-indexed i) changes from i+1 to i. The binary search algorithm can be outfitted to find this change point, using its head, tail, and middle pointers.

	~~In Java we can use~~ a ~~HashMap~~, ~~which uses~~ a ~~hash table in its implementation~~.		'''Linear time algorithms:'''
			* O(n) add each element to a set, checking membership each time. O(1) lookup for membership in a set, iterating one item at a time, leads to O(n) time.

			'''One-time expense algorithms:'''
			* O(1) lookup for O(n) cost of building a hash table, at a potentially high memory cost.
			* O(log n) binary search lookup for O(n log n) cost of sorting into a binary tree or similar structure, more efficient memory usage.

	~~Using arrays:~~		If we are going to be moving items in and out, what's the best approach? It all depends... Let's explore.

	~~Sorted array~~, ~~single element duplicate:~~		NOTE: Remember the ghost log. The cost of doing something with frequency of 1/j for j=1 to n is the harmonic number, which is O(log n).
	* O(log n) ~~- each element's index correlates to the element's value, so use a binary search to find the location where the correlation is off~~

	~~Unsorted array, single element duplicate~~:		'''Java Implementation:'''
	* ~~O(n) - to iterate through each element and check for membership in~~ a ~~set: if not a member then add it~~, ~~otherwise it's a duplicate element.~~		* Use a HashMap, with the key being the element in the array, the value being an integer counter.

	~~Using trees:~~
	* If we can build a search tree filled with ~~references,~~ the ~~cost of constructing~~ the ~~tree is O(n)~~, ~~with each node~~ being ~~composed of a fixed number of pointers (to parent/child nodes).~~
	* Underlying data can be anything - a bunch of indexes in an ~~array, or items in a queue, or pointers to locations in memory, etc., but must be accessible in O(1) time.~~

	~~To get a slightly more expensive answer but make it reusable,~~
	* O(n log n) - build a binary tree or other sorted data structure. Comoparable to cost of one-time sort. Heap sort is basically constructing a binary tree and doing a binary tree sort.
	* One-time cost, it is now sorted, and can do O(log n) searches. Like binary searches.

	~~Add entries to a counts hashtable. O(1) lookups for each element in hash table. sum them up.~~
	* O(n) to add each element to a hashtable and get back a counter ~~that is incremented~~.

	~~In-place sort and binary search for duplicates:~~
	* O(n log n) - to sort the array, O(n log n), then costs O(log n) to find duplicates, sequentially, using binary search

	===Multi element case===		===Multi element case===

Admin: /* Single element case */

2017-06-06T02:30:28Z

Single element case

← Older revision		Revision as of 02:30, 6 June 2017
Line 24:		Line 24:
	===Single element case===		===Single element case===

	The fastest ~~case~~ is using a ~~sorted~~ structure, ~~such as~~ a ~~binary search tree~~, to ~~constructor~~ (or ~~reconstruct)~~ the ~~object~~.		The cost of finding duplicates depends on problem parameters and tradeoffs. Assuming we want the absolute fastest algorithm, we are looking for a constant-time or logarithmic algorithm. (There are no O(1) algorithms here.)

			To find duplicates in logarithmic time, we have to have the data in a pre-sorted data structure. Then we are looking for an element that meets a particular criteria: normally in binary sort the criteria is a (greater than/less than/equal to) condition. Here, the criteria is the place where the value of element i (at zero-indexed i) changes from i+1 to i. The binary search algorithm can be outfitted to find this change point, using its head, tail, and middle pointers.

			The next-fastest, which does not rely on any sorting, is a simple enumeration of all the elements of the data structure, adding them to a hash map. This operation checks the hash of each object to see if it already exists in the key pool, and if it does, it adds the object to a set of duplicate values. This key lookup is O(1). The downside to this approach is that it can be memory intensive, or depend on the implementation of the hashtable, which needs to balance memory usage with low probability of collisions - two colliding needs.

			In Java we can use a HashMap, which uses a hash table in its implementation.

	~~To check for a duplicate:~~

	Using arrays:		Using arrays:

Admin: /* Single element case */

2017-06-06T01:54:11Z

Single element case

← Older revision		Revision as of 01:54, 6 June 2017
Line 26:		Line 26:
	The fastest case is using a sorted structure, such as a binary search tree, to constructor (or reconstruct) the object.		The fastest case is using a sorted structure, such as a binary search tree, to constructor (or reconstruct) the object.

	~~If we can build a search tree filled with references, the cost of constructing the tree is O(n), with each node being composed of a fixed number of pointers (to parent/child nodes).~~		To check for a duplicate:

	~~Underlying data can be anything - a bunch of indexes in an array, or items in a queue, or pointers to locations in memory, etc., but must be accessible in O(1) time.~~

	~~Now, to~~ check for a duplicate:

	Using arrays:		Using arrays:
Line 39:		Line 35:
	Unsorted array, single element duplicate:		Unsorted array, single element duplicate:
	* O(n) - to iterate through each element and check for membership in a set: if not a member then add it, otherwise it's a duplicate element.		* O(n) - to iterate through each element and check for membership in a set: if not a member then add it, otherwise it's a duplicate element.

			Using trees:
			* If we can build a search tree filled with references, the cost of constructing the tree is O(n), with each node being composed of a fixed number of pointers (to parent/child nodes).
			* Underlying data can be anything - a bunch of indexes in an array, or items in a queue, or pointers to locations in memory, etc., but must be accessible in O(1) time.

	To get a slightly more expensive answer but make it reusable,		To get a slightly more expensive answer but make it reusable,

Admin: /* Multi element case */

2017-06-06T01:52:49Z

Multi element case

← Older revision		Revision as of 01:52, 6 June 2017
Line 53:		Line 53:

	In the multi-element duplicate case:		In the multi-element duplicate case:
	*

	==Code==		==Code==

Admin: /* Solution approach */

2017-06-06T01:52:40Z

Solution approach

← Older revision		Revision as of 01:52, 6 June 2017
Line 13:		Line 13:
	==Solution approach==		==Solution approach==

	There are a few different solution approaches.		There are a few different solution approaches, depending on the problem constraints:
			* Is the array sorted, or unsorted?
			* What if we have a one-time O(n) cost of construction?
			* Are we after a space-efficient or operationally-efficient algorithm?
			* What kind of data - primitive types or objects?
			* Do we have to use an array? Why not use a collections object?

			(Square-bracket indexing is nice to have.)

	===Single element case===		===Single element case===

	In the ~~single element~~ duplicate ~~case~~:		The fastest case is using a sorted structure, such as a binary search tree, to constructor (or reconstruct) the object.

			If we can build a search tree filled with references, the cost of constructing the tree is O(n), with each node being composed of a fixed number of pointers (to parent/child nodes).

			Underlying data can be anything - a bunch of indexes in an array, or items in a queue, or pointers to locations in memory, etc., but must be accessible in O(1) time.

			Now, to check for a duplicate:

			Using arrays:

	Sorted array, single element duplicate:		Sorted array, single element duplicate:
Line 23:		Line 38:

	Unsorted array, single element duplicate:		Unsorted array, single element duplicate:
	* O(n) - to iterate through each element and check for membership in a set; if not a member then add it, otherwise it's a duplicate element~~; subsequent~~ O(1) lookups in hash table.		* O(n) - to iterate through each element and check for membership in a set: if not a member then add it, otherwise it's a duplicate element.
	* O(n log n) - to sort the array, then O(log n) to find duplicates, sequentially, using binary search
			To get a slightly more expensive answer but make it reusable,
			* O(n log n) - build a binary tree or other sorted data structure. Comoparable to cost of one-time sort. Heap sort is basically constructing a binary tree and doing a binary tree sort.
			* One-time cost, it is now sorted, and can do O(log n) searches. Like binary searches.

			Add entries to a counts hashtable. O(1) lookups for each element in hash table. sum them up.
			* O(n) to add each element to a hashtable and get back a counter that is incremented.

			In-place sort and binary search for duplicates:
			* O(n log n) - to sort the array, O(n log n), then costs O(log n) to find duplicates, sequentially, using binary search

	===Multi element case===		===Multi element case===

	In the multi-element duplicate case:		In the multi-element duplicate case:
			*

			==Code==

Admin: /* Multi element case */

2017-06-05T23:23:57Z

Multi element case

← Older revision		Revision as of 23:23, 5 June 2017
Line 29:		Line 29:

	In the multi-element duplicate case:		In the multi-element duplicate case:



			{{DataStructuresFlag}}

			[[Category:Arrays]]
			[[Category:Java]]

Admin: /* Solution approach */

2017-06-05T23:20:51Z

Solution approach

← Older revision		Revision as of 23:20, 5 June 2017
Line 14:		Line 14:

	There are a few different solution approaches.		There are a few different solution approaches.

			===Single element case===

	In the single element duplicate case:		In the single element duplicate case:
Line 23:		Line 25:
	* O(n) - to iterate through each element and check for membership in a set; if not a member then add it, otherwise it's a duplicate element; subsequent O(1) lookups in hash table.		* O(n) - to iterate through each element and check for membership in a set; if not a member then add it, otherwise it's a duplicate element; subsequent O(1) lookups in hash table.
	* O(n log n) - to sort the array, then O(log n) to find duplicates, sequentially, using binary search		* O(n log n) - to sort the array, then O(log n) to find duplicates, sequentially, using binary search

			===Multi element case===

	In the multi-element duplicate case:		In the multi-element duplicate case:

Admin: /* Solution approach */

2017-06-05T23:20:25Z

Solution approach

← Older revision		Revision as of 23:20, 5 June 2017
Line 13:		Line 13:
	==Solution approach==		==Solution approach==

	~~The basic algorithm~~		There are a few different solution approaches.

			In the single element duplicate case:

			Sorted array, single element duplicate:
			* O(log n) - each element's index correlates to the element's value, so use a binary search to find the location where the correlation is off

			Unsorted array, single element duplicate:
			* O(n) - to iterate through each element and check for membership in a set; if not a member then add it, otherwise it's a duplicate element; subsequent O(1) lookups in hash table.
			* O(n log n) - to sort the array, then O(log n) to find duplicates, sequentially, using binary search

			In the multi-element duplicate case:

Admin: /* Questions */

2017-06-05T23:11:42Z

Questions

← Older revision		Revision as of 23:11, 5 June 2017
Line 1:		Line 1:
	==Questions==		==Questions==

			===Finding one duplicate===

	Question C-3.17) A is an array of size n>=2 containing integers from 1 to n-1, inclusive, one of which is repeated. Describe an algorithm for finding the integer in A that is repeated.		Question C-3.17) A is an array of size n>=2 containing integers from 1 to n-1, inclusive, one of which is repeated. Describe an algorithm for finding the integer in A that is repeated.

	A special case of this question is when array A is sorted, since then we know that each array element should correspond to its own index plus 1, and we can do a binary search to locate the array index that does not match the criteria. In this case, the runtime is O(log n).		A special case of this question is when array A is sorted, since then we know that each array element should correspond to its own index plus 1, and we can do a binary search to locate the array index that does not match the criteria. In this case, the runtime is O(log n).

			===Finding multiple duplicates===

	Question C-3.18) Let B be an array of size n>=6 containing integers from 1 to n-5, inclusive. Five of the integers are repeated. Describe an algorithm for finding the five integers in B that are repeated.		Question C-3.18) Let B be an array of size n>=6 containing integers from 1 to n-5, inclusive. Five of the integers are repeated. Describe an algorithm for finding the five integers in B that are repeated.

			==Solution approach==

			The basic algorithm

Admin: Created page with "==Questions== Question C-3.17) A is an array of size n>=2 containing integers from 1 to n-1, inclusive, one of which is repeated. Describe an algorithm for finding the intege..."

2017-06-05T22:43:42Z

Created page with "==Questions== Question C-3.17) A is an array of size n>=2 containing integers from 1 to n-1, inclusive, one of which is repeated. Describe an algorithm for finding the intege..."

New page

==Questions==

Question C-3.17) A is an array of size n>=2 containing integers from 1 to n-1, inclusive, one of which is repeated. Describe an algorithm for finding the integer in A that is repeated.

A special case of this question is when array A is sorted, since then we know that each array element should correspond to its own index plus 1, and we can do a binary search to locate the array index that does not match the criteria. In this case, the runtime is O(log n).

Question C-3.18) Let B be an array of size n>=6 containing integers from 1 to n-5, inclusive. Five of the integers are repeated. Describe an algorithm for finding the five integers in B that are repeated.