Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Create 09 linearProbing.cpp #71

Closed
wants to merge 2 commits into from

Conversation

Juro221
Copy link

@Juro221 Juro221 commented May 23, 2021

We compute the position where arr[i] should be placed and if it is already taken we look at the next position.
Time complexity : O(n)

We compute the position where arr[i] should be placed and if it is already taken we look at the next position.
Time complexity : O(n)
Copy link
Owner

@FazeelUsmani FazeelUsmani left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Wrong Answer. !!!Wrong Answer

Possibly your code doesn't work correctly for multiple test-cases (TCs).

The first test case where your code failed:

Input:
467
6811
6500 9169 5724 1478 9358 6962 4464 5705 8145 3281 6827 9961 491 2995 1942 4827 5436 2391 4604 3902 153 292 2382 7421 8716 9718 9895 5447 1726 4771 1538 1869 9912 5667 6299 7035 9894 8703 3811 1322 333 7673 4664 5141 7711 8253 6868 5547 7644 2662 2757 37 2859 8723 9741 7529 778 2316 3035 2190 1842 288 106 9040 8942 9264 2648 7446 3805 5890 6729 4370 5350 5006 1101 4393 3548 9629 2623 4084 9954 8756 1840 4966 7376 3931 6308 6944 2439 4626 1323 5537 1538 6118 2082 2929 6541 4833 1115 4639 .................

Its Correct output is:
467 1869 8875 6541 5141 472 466 2658 9815 7371 4678 2813 3281 1881 6549 1416 945 3753 9358 4221 2355 3290 485 7958 491 21 4688 8433 1426 3757 7035 9832 1425 2368 7506 9374 8909 37 3297 6105 481 24 7487 7982 7505 974 7518 2382 6118 8896 6576 2386 3788 53 5484 55 2391 2859 7529 523 9866 527 8935 5667 4734 5200 9869 1924 8007 8942 3805 537 8009 4272 1942 3811 1008 1478 8476 6617 6618 1003 6139 7088 6154 4745 1020 9894 9895 2421 2888 555 2423 8022 8480 5699 1023 4767 9905 8492 2413 5705 4771 4270 24.................

And Your Code's output is:
467 1869 8875 6541 5141 472 466 2695 9815 1694 2658 2813 3281 1881 6549 1416 945 3753 9358 4221 2355 3290 485 7958 491 21 4688 8433 1426 3757 7035 9832 1425 2368 7506 9374 8909 37 3297 6105 481 24 7958 7982 7487 7505 7518 2382 6118 974 8896 2386 3788 53 53 55 2391 2859 7529 523 9866 527 8935 5667 4734 5200 9869 1924 8007 8942 3805 537 8009 4272 1942 3811 1008 1478 8476 6617 6618 1003 6139 7088 6154 4745 1020 9894 9895 2421 2888 555 2423 8022 8480 5699 1023 4767 9905 1003 8492 5705 4771 2413 2439.................

Test against custom input

vector<int> linearProbing(int hashSize, int arr[], int N)

@FazeelUsmani FazeelUsmani linked an issue May 30, 2021 that may be closed by this pull request
Hopefully this will fix the problem. Before I have never checked if the element is already in a list and i added it. Now if the element that i want to add is already in a list I drop it.
@FazeelUsmani
Copy link
Owner

This PR has not been updated for a while, closing it. Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

05 Hashing --> 9 Linear Probing in Hashing
3 participants