[Solved]Given Array N Positive Numbers Give Algorithm Finding First Element Array Repeated May Rep Q37187692
Given an array of n positive numbers, give an algorithm forfinding the first element in the array which is repeated (may berepeated more than once). For example, in the array {0,3,2,1,2,2,3}the first repeated number is 3 (not 2). Utilize hashing where thekey is the element, and the valueis the position of the element in the array. Initially we store theposition of the element in the array as the value for this key. Ifwe get the same element again however, we just negate the currentvalue in the hash table. The negative value in the hash tableindicates that we have seen the same element more than once. Afterprocessing the complete input array, we scan the hash table withthe values iterator and return the highest negative indexed valuefrom it. The highest negative value indicates that we have seenthat element first among repeated elements.
Step1: You will utilize HashedDictionary classthat implements DictionaryInterface. Make yourself familiar withthe class implementation. Next, implement displayHashTable() methodin this class. SolveWithHashing class has testDisplayHashTablemethod you will use to test it.
Step2: Implement the algorithm ingetFirstRepeatedElement method. Note: the algorithm assumes thatrecorded positions are 1-based, for example the element at index 0has position 1.
public class SolveWithHashing{ private DictionaryInterface<Integer, Integer> hashedDictionary; private final int DEFAULT_CAPACITY = 5; public SolveWithHashing() { createHashedDictionary(); } public void createHashedDictionary() { this.hashedDictionary = new HashedDictionary<>(DEFAULT_CAPACITY); } private void testDisplayHashTable() { System.out.println(“displaying empty dictionary”); this.hashedDictionary.displayHashTable(); this.hashedDictionary.add(1, 1); this.hashedDictionary.add(7, 7); System.out.println(“displaying dictionary after 2 entries have been added”); this.hashedDictionary.displayHashTable(); this.hashedDictionary.add(13, 13); this.hashedDictionary.add(17, 17); this.hashedDictionary.add(8, 8); System.out.println(“displaying dictionary after 3 additional entries have been added”); this.hashedDictionary.displayHashTable(); this.hashedDictionary.remove(1); this.hashedDictionary.remove(17); System.out.println(“displaying dictionary after 2 entries have been removed”); this.hashedDictionary.displayHashTable(); } public Integer getFirstRepeatedElement(int[] a) { // TODO Project1 #1 return null; }public class HashedDictionary<K,V> implements DictionaryInterface<K,V>,Serializable{ // The dictionary: private int numberOfEntries; private static final int DEFAULT_CAPACITY = 5; // Must be prime private static final int MAX_CAPACITY = 10000; // The hash table: private TableEntry<K, V>[] hashTable; private static final int MAX_SIZE = 2 * MAX_CAPACITY; private boolean initialized = false; private static final double MAX_LOAD_FACTOR = 0.5; // Fraction of hash table that can be filled private int probes; public HashedDictionary() { this(DEFAULT_CAPACITY); // Call next constructor } // end default constructor public HashedDictionary(int initialCapacity) { initialCapacity = checkCapacity(initialCapacity); this.numberOfEntries = 0; // Dictionary is empty // Set up hash table: // Initial size of hash table is same as initialCapacity if it is prime; // otherwise increase it until it is prime size int tableSize = getNextPrime(initialCapacity); checkSize(tableSize); // The cast is safe because the new array contains null entries @SuppressWarnings(“unchecked”) TableEntry<K, V>[] temp = (TableEntry<K, V>[])new TableEntry[tableSize]; this.hashTable = temp; this.initialized = true; this.probes = 0; } // end constructor // We’ve added this method to display the hash table for illustration and testing public void displayHashTable() { System.out.println(“The size of hash table is: ” + this.hashTable.length); System.out.println(“In displayHashTable – implement me”); // TODO Project1 #1 // displays “null” if there is no entry in the slot // displays “notIn” if an entry used to be there but was removed // displays the “KEY:” and its “VALUE:” if the entry is there System.out.println(); } // end displaypublic interface DictionaryInterface<K, V>{ /** Adds a new entry to this dictionary. If the given search key already exists in the dictionary, replaces the corresponding value. @param key An object search key of the new entry. @param value An object associated with the search key. @return Either null if the new entry was added to the dictionary or the value that was associated with key if that value was replaced. */ public V add(K key, V value); /** Removes a specific entry from this dictionary. @param key An object search key of the entry to be removed. @return Either the value that was associated with the search key or null if no such object exists. */ public V remove(K key); /** Retrieves from this dictionary the value associated with a given search key. @param key An object search key of the entry to be retrieved. @return Either the value that is associated with the search key or null if no such object exists. */ public V getValue(K key); /** Sees whether a specific entry is in this dictionary. @param key An object search key of the desired entry. @return True if key is associated with an entry in the dictionary. */ public boolean contains(K key); /** Creates an iterator that traverses all search keys in this dictionary. @return An iterator that provides sequential access to the search keys in the dictionary. */ public Iterator<K> getKeyIterator(); /** Creates an iterator that traverses all values in this dictionary. @return An iterator that provides sequential access to the values in this dictionary. */ public Iterator<V> getValueIterator(); /** Sees whether this dictionary is empty. @return True if the dictionary is empty. */ public boolean isEmpty(); /** Gets the size of this dictionary. @return The number of entries (key-value pairs) currently in the dictionary. */ public int getSize(); /** Removes all entries from this dictionary. */ public void clear(); public void displayHashTable(); public int getNumberOfProbes();} // end DictionaryInterface
Expert Answer
Answer to Given an array of n positive numbers, give an algorithm for finding the first element in the array which is repeated (ma… . . .
OR
