CODEWITHSUNDEEP
algorithmtime-complexitycomputer-science
Noam Rodrik
Noam Rodrik

Reputation: 550

Most efficient algorithm for this problem

Problem: Let's say I have an array of size N, in range [1, N]. I want to generate a random number k such that 1 <= k <= N, and occupy arr[k] with a random letter. I will get another random number p, that is different from k, randomly and occupy that slot. I'll repeat this over and over until there are no slots left. Also, there might be a chance where one of these randomly generated letters might be removed from a slot they previously occupied.

The problem here is that every time I pick a new number, it'll be harder for me to guess a random number that wasn't occupied yet.

I'm trying to find a solution for this problem, obviously in the most efficient way possible (both space and complexity).

I've come up with several solutions but I don't think they're too efficient and I'm having a hard time calculating their complexity.

Plan A) For each integer I randomly choose in the range [1, N], I check if it's occupied. If it is, I re-roll until I get one that isn't occupied. This becomes inefficient with high orders of N as the collisions are pretty high.

Plan B) For each iteration I go over all values of the array, those who I don't occupy I write down in a list. Afterwards I shuffle the list (via Fisher-Yates shuffle for example?) and get arbitrarily the first object. This isn't space efficient, and for my problem, I can't just keep one list and shuffle from there, since in my program there might be multiple threads calculating this.

Plan C) A slight change of plan A: I randomly choose in the range [1, N], I check if it's occupied. If it is, I +1 and try the next one, if it is, again +1. Worst case all array slots are occupied except one -> O(N).

Is there a better way to approach this problem? This specific problem is a very important module in my software so time complexity is vital. If there isn't, which way do you think I should go with (For those who have talent on calculating time complexity). Thank you!

Upvotes: 2

Views: 105

Answers (1)

btilly
btilly

Reputation: 46408

I would suggest that you use both plans A and B.

Use A until the array is mostly filled. Then search for the unused indices, put them into an array, and use plan B. You will have to experiment with your constraints to figure out when to switch.

Your comment about multiple threads doing this is concerning though. Be aware that when multiple threads access the same memory, race conditions are easy and contention for access slows you down.

Upvotes: 1

Related Questions