CODEWITHSUNDEEP
javaalgorithm
Shunmugavel Krishnan
Shunmugavel Krishnan

Reputation: 787

Sequence number creation

I have an ask to create numbers sequentially for list of tasks sent in a file.

  1. Sequence Numbers should be assigned in order tasks are arranged
  2. Tasks will be arriving to my application at different intervals. New tasks can be inserted in beginning , end or between existing tasks.
  3. If a task was already assigned with a number, it should not be modified when a new task is added.
  4. Sequence numbers can be integers or decimals with 1 precision. enter image description here

Is there any algorithm which solves this problem?

Upvotes: 0

Views: 99

Answers (1)

Dave
Dave

Reputation: 9085

Unless you have some guarantee on how unlucky you can be (how many times you'd have to insert a task in your smallest session id gap), you can't do better than averaging the neighbors every time. With big enough numbers and a cap of 50 tasks, this is compatible with integers.

Make fictional T endpoints with session IDs of 0 and 2^50 (# of tasks)
Each task gets the average of its neighbors' session ids.
T1 => S 2^49
T2 => S (0+2^49)/2 = 2^48 or (2^49+2^50)/2 = 2^49 + 2^48
etc...

All session id gaps are powers of 2, and we start with a big enough range that we can halve it 50 times if need be.

2^49 = 562,949,953,421,312; idk how much better this is than using a float

Upvotes: 2

Related Questions