CODEWITHSUNDEEP
algorithmsearchdata-structurestree
user2537119
user2537119

Reputation: 139

Data Structure to store Integer Range , Query the ranges and modify the ranges

We need to maintain mobileNumber and its location in memory. The challenge is that we have more than 5 million of users and storing the location for each user will be like hash map of 5 million records. To resolve this problem, we have to work on ranges

We are given ranges of phone numbers like

A number can belong to single location only.

We need a data structure to store these ranges in the memory.

It has to support two functions

  1. findLocation(Integer number) it should return the location name to which number belongs
  2. changeLocation( Integer Number , String range). It changes location of Number from old location to new location

This is completely in memory design.

I am planning to use tree structure with each node contains ( startofrange , endofrange ,location). I will keep the nodes in sorted order. I have not finalized anything yet. The main problem is-- when 2nd function to change location is called say 9899123448 location to b

The range1 node should split to 3 nodes 1st node (9899123446,9899123447,a) 2nd node (9899123448,9899123448,b) 3rd node (9899123449,9912345678,a).

Please suggest the suitable approach Thanks in advance

Upvotes: 9

Views: 11406

Answers (2)

Chen Pang
Chen Pang

Reputation: 1388

Normally you can use specialized data structures to store ranges and implement the queries, e.g. Interval Tree.

However, since phone number ranges do not overlap, you can just store the ranges in a standard tree based data structure (Binary Search Tree, AVL Tree, Red-Black Tree, B Tree, would all work) sorted only by [begin].

For findLocation(number), use corresponding tree search algorithm to find the first element that has [begin] value smaller than the number, check its [end] value and verify if the number is in that range. If a match if found, return the location, otherwise the number is not in any range.

For changeLocation() operation:

  1. Find the old node containing the number
  2. If an existing node is found in step 1, delete it and insert new nodes
  3. If no existing node is found, insert a new node and try to merge it with adjacent nodes.

I am assuming you are using the same operation for simply adding new nodes.

More practically, you can store all the entries in a database, build an index on [begin].

Upvotes: 10

k06a
k06a

Reputation: 18745

First of all range = [begin;end;location]

Use two structures:

  • Sorted array to store ranges begins
  • Hash-table to access ends and locations by begins

Apply following algo:

  1. Use binary search to find "nearest less" value ob begin
  2. Use hash-table to find end and location for begin

Upvotes: 3

Related Questions