algorithm - data - Estructura de datos para almacenar el rango de enteros, consultar los rangos y modificar los rangos

tree structure architecture

Question

Necesitamos mantener mobileNumber y su ubicación en la memoria. El desafío es que tenemos más de 5 millones de usuarios y el almacenamiento de la ubicación de cada usuario será como un mapa hash de 5 millones de registros. Para resolver este problema, tenemos que trabajar en rangos

Nos dan rangos de números de teléfono como

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

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

Un número puede pertenecer solo a una ubicación.

Necesitamos una estructura de datos para almacenar estos rangos en la memoria.

Tiene que soportar dos funciones

1. findLocation (Número entero) debe devolver el nombre de la ubicación a la que pertenece el número
2. changeLocation (Número entero, rango de cadenas). Cambia la ubicación del número de la ubicación anterior a la nueva ubicación

Esto está completamente en el diseño de la memoria.

Estoy planeando utilizar la estructura de árbol con cada nodo contiene (inicio de rango, rango final, ubicación). Mantendré los nodos en orden ordenado. No he finalizado nada todavía. El principal problema es-- cuando la segunda función para cambiar la ubicación se llama decir 9899123448 ubicación a b

El nodo range1 debe dividirse en 3 nodos 1st node (9899123446,9899123447,a) 2nd node (9899123448,9899123448,b) 3rd node (9899123449,9912345678,a) .

Por favor, sugiera el enfoque adecuado Gracias de antemano

Answer 1

En primer lugar range = [ begin ; end ; location ]

Usa dos estructuras:

• La matriz ordenada para almacenar el range s begin s
• Hash-table para acceder a los end y a las location por s

Aplicar el siguiente algo:

1. Utilice la búsqueda binaria para encontrar el valor "más cercano"
2. Usa hash-table para encontrar el end y la location para begin

Answer 2

Normalmente puede usar estructuras de datos especializadas para almacenar rangos e implementar consultas, por ejemplo, Interval Tree .

Sin embargo, dado que los rangos de números telefónicos no se superponen , puede almacenar los rangos en una estructura de datos estándar basada en árboles ( árbol de búsqueda binaria , árbol AVL , árbol rojo-negro , árbol B , todo funcionaría) ordenados solo por [comenzar] .

Para findLocation (número), use el algoritmo de búsqueda arbórea correspondiente para encontrar el primer elemento que tenga un valor [begin] menor que el número, verifique su valor [end] y verifique si el número se encuentra en ese rango. Si se encuentra una coincidencia, devuelva la ubicación; de lo contrario, el número no se encuentra en ningún rango.

Para la operación changeLocation ():

1. Encuentre el nodo antiguo que contiene el número
2. Si se encuentra un nodo existente en el paso 1, elimínelo e inserte nuevos nodos
3. Si no se encuentra ningún nodo existente, inserte un nuevo nodo e intente fusionarlo con nodos adyacentes.

Supongo que está utilizando la misma operación para simplemente agregar nuevos nodos.

Más prácticamente, puede almacenar todas las entradas en una base de datos, crear un índice en [comenzar].