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 AncestorLinear Probing
LEVEL:Beginner
Description
Perform linear probing on the given set of inputs
Input Format
First line contains max size of hash table next line ask to choose from menu
Output Format
Provide output as choosen by the user
5
1 for insert 2 for remove 3 to get 4 to max size 1 1 5 1 5 Do you want to continue y or n y 1 for insert 2 for remove 3 to get 4 to max size 1 2 50 1 5 2 50 Do you want to continue y or n n
3
1 for insert 2 for remove 3 to get 4 to max size 1 4 52 4 52 Do you want to continue y or n y 1 for insert 2 for remove 3 to get 4 to max size 2 4 Do you want to continue y or n n
10
1 for insert 2 for remove 3 to get 4 to max size 3 2 -1 Do you want to continue y or n y 1 for insert 2 for remove 3 to get 4 to max size 4 10 Do you want to continue y or n n
Login to see Discussion
Approach
Step-i)create a class Linear probing
Step-ii)create variables curr size and max size
Step-iii)create array key and vals of int type
Step-iv)assign 0 to curr and capacity to max_size
Step-v)create memory of max size for keys and vals
Step-vi)create contains method which returns true if keys equal to 0
Step-vii)create insert method which takes keys and values as argument
Step-viii) assing key%max_size to tmp and tmp to i
Step-ix) if keys[i]equal to 0 assing key to keys[i] and val to vals[i] increment curr_size
Step-x) assign (i+1) % max_size to i and perform ix and x while i is not equal to tmp
Step-xi) create a get method which takes key as argument
Step-xii)assign key % max_size to i
Step-xiii) if keys[i] equal to key return vals[i]
Step-xiv) assign i+1 % max_size to i
Step-xv)perform xiii and xiv while keys[i] not equal to 0
Step-xvi) return -1
Step-xvii)create a remove method which takes k as argument
Step-xviii)if k is zero return
Step-xix)assign k%max_size to i
Step-xx) while not k equals to keys[i] update i to i+1 % max_size
Step-xxi)update keys[i] and vals[i] to 0
Step-xxii) assign i+1 % max_size to i and keys[i] to tmp1 and vals[i] to tmp2
Step-xxiii) assign 0 to keys[i] and vals[i] decrement curr size and insert tmp1 and tmp2
Step-xxiv)update i to i+1 % max size
Step-xxv)perform xxii to xxiv till keys[i] != 0 and then decrement curr_size
Step-xxvi)write a print method which print the elements of the array
Step-xxvii)in main method take the required inputs like n and array elements
Step-xxviii)ask user what he wants to perform using switch and perform those and then print the output
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