9

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

  • range1 start="9899123446" end="9912345678" location="a"

  • range2 start="9912345679" end="9999999999" location="b"

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

Improve this question
0

2 Answers 2

Reset to default
10

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].

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Plz consider the fact that , while changing location of number i have to make insertion in sorted array. That would be too costly
Sorry, I only mean you should sort the data by [begin]. You can use a binary search tree or some more advanced data structure like AVL tree, B tree, etc.
i will use balanced binary search tress. When Location change operation called . say i have nodeoriginal [10,16,b]. I need to change location of number 13 to a. I will break the nodeoriginal to 3 nodes node1[10,12,b] node2[13,13,a] node3[14,16,b]. After that will replace the nodeoriginal with node2 and its left child is node1 and right child is node3 .Any best way to achieve this process so that tree remain balanced
You can simply delete the old code and insert the three new node. The algorithm for balanced binary search tree always ensures it is balanced
If phone number from 10 to 14 is for location b, why would the number 13 be a? Does this case really exist?
|
3

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
Improve this answer

6 Comments

Thanks For suggestion.I will face problem while insertion in array. Say I have range1 = [1,7,a] range2 = [10,16,b] . the sorted array will store [1,10] If i have to change location of 5 from a to b . Now the ranges will be range1 =[1,4,a] range2 =[5,5,b] range3=[6,7,b] range4[10,16,b] Now I have to add the extra begin in array and finally array will become sorted array [1,5,6,10] since insertion is very costly..can not use list also that would effect search...
@user2537119 just add whole your 5000000 ranges begins to array and then sort it.
@user2537119 and then if you will manually add some values to sorted array, this will be not very slow... How fast will you do it? Once per 10 secs? 20 secs? I think insertion time 0.01s is not slow for manually insertion...
I can not add whole range.
To insert in sorted array , i have to shift all the element after inserted element
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.