Beginner
1. Binary Search2. Linear Search3. Fibonacci Search4. Bubble Sort5. Insertion Sort6. Selection Sort7. Quick Sort8. Merge Sort9. Addition of two matrixes10. Subtraction of two matrixes11. Multiplication of two matrixes12. Transpose of given Matrix13. EUCLIDIAN GCD ALGORITHM14. Fabinocci Numbers with matrix multiplication15. Fast Exponential16. Modular inversion17. Prime seiving18. Heap(using array)19. Heapify20. Heap Sort21. Linear Probing22. Open Addressing23. Collision Avoidance24. Binary Search Tree Traversal Techniques25. Finding Kth Largest Element in Binary Tree26. Diameter of a Binary search tree27. Depth of Binary Tree28. Number of Nodes in BST29. Convert Array to Binary Tree30. Convert Array to General Tree31. Lowest Common AncestorOpen Addressing
LEVEL:Beginner
Description
For the given input array perform open addressing and print the output
Input Format
First line contains n representing length of array Second line contains n elemnents
Output Format
Perform Open Addressing and print the table
10
1 for insert 2 for remove 3 to get 4 to max size 1 1 10 1 10 Do you want to continue y or n n
10
1 for insert 2 for remove 3 to get 4 to max size 1 1 10 1 10 Do you want to continue y or n y 1 for insert 2 for remove 3 to get 4 to max size 4 10 1 10 Do you want to continue y or n n
5
1 for insert 2 for remove 3 to get 4 to max size 1 1 2 1 2 Do you want to continue y or n y 1 for insert 2 for remove 3 to get 4 to max size 2 1 Do you want to continue y or n n
Login to see Discussion
Approach
Step-i)create variable curr size, max size and arrays keys and vals
Step-ii)assign 0 to curr size and capacity to max size create memory for two arrays using the constructor
Step-iii)create contains method which return true if key not equal to 0
Step-iv)create hash function which return the value of key%max_size
Step-v)create hash_2 funtion which return the value of hash(key)+i*i % max_size
Step-vi)create insert method and assign value of hash(key) to tmp , tmp to i and 1 to n
Step-vii)if keys[i] == 0 assign key to keys[i] , val to vals[i] increment curr size and return
Step-viii) update i to hash1(key,n) and increment n by one value
Step-ix)perform vii and viii while i is not equal to tmp
Step-x)create get method and assign value of hash(key) to i and 1 to n
Step-xi) if keys[i] equal to key return vals[i]
Step-xii) update i to hash1(key,n) and increment n by one value
Step-xiii)repeat xi and xii while keys[i] is not equal to 0
Step-xix)return -1
Step-xx) create a remove method
Step-xxi) return 0 if k is equal to 0
Step-xxii)assign hash(k) to i and 1 to n
Step-xxiii) update hash1(k,n) to i and increment i by one value while not k equals to keys[i]
Step-xxiv) assign 0 to keys[i] and vals[i] and n
Step-xxv) run loop from i+1%max_size assign tmp1 to keys[i] and vals[i] to tmp2 and make both key[i] and vals[i] to 0
Step-xxvi) decrement curr size and increment n and insert tmp1 and tmp2
Step-xxvii)follow above two steps till keys[i] not equal to 0 by updating i to hash1(k,n)
Step-xxviii)decrement curr size
Step-xxix)create a method print table to print the values of hash table
Step-xxx)in main method take the required inpus such as array size and elements and print the output as per users choice
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution