structures interview data book and algorithms aho algorithm data-structures

algorithm - interview - Almacenando 1 millón de números telefónicos



data structures and algorithms pdf (14)

8 millones de bits con cada bit 1 (usado) o 0 (disponible) para uno de los ejemplos de 8 millones de números

100 0000 900 0000 = 8 million phone numbers, bit 1 = 1000000 and bit 8 million = 9000000

¿Cuál es la forma más eficiente, en cuanto a la memoria, de almacenar 1 millón de números telefónicos?

Al parecer, esta es una pregunta de la entrevista en Google, por favor, den sus ideas.

Creo que podemos usar Bit Vector aquí de tamaño 1 millón.

Ejemplo de Java:

private BitSet dir = new BitSet(1000000); public void addTelephoneNumber(int number) { dir.set(number); } public void removeTelephoneNumber(int number) { if (dir.get(number)) { dir.flip(number); } } public boolean isNumberPresent(int number) { return dir.get(number); }

En una entrevista de trabajo, el objetivo de esta pregunta es evaluar las habilidades de resolución de problemas del solicitante. Debido a que el enfoque de la pregunta es la eficiencia de la memoria , en mi opinión, la respuesta correcta es preguntar al entrevistador: "¿Los números de teléfono son internacionales o están limitados a un solo país?" Si los números están limitados a un solo país, la tarea de maximizar la eficiencia de la memoria se simplifica por el hecho de que cada país tiene reglas simples para la distribución de números de teléfono por estado y ciudad.

Escríbelos en ASCII, separados por espacios.

Zip la cadena resultante, utilizando su algoritmo de compresión favorito. Si el orden no es importante, ordenarlos primero podría ayudar a la compresión, le da más repetición más cerca.

Oh, ¿querías un acceso aleatorio eficiente? Entonces deberías haber dicho.

La codificación de Huffman en bloques de dígitos probablemente daría muy buenos resultados. Si los números fueran de tipo mixto (por ejemplo, algunos EE. UU., Algunos en el extranjero, incluido el código de acceso) necesitaría otro par de bits para especificar qué tipo eran (y, por lo tanto, qué bloques usar).

Si los números estuvieran en un rango pequeño, por ejemplo, siete dígitos, la forma más compacta de almacenarlos sería tratarlos como enteros, clasificarlos y almacenar las diferencias (en valores) de Huffman. Por ejemplo, con 10 ^ 6 números en 7 dígitos (10 ^ 7 posibilidades), esperaría necesitar aproximadamente log2 (10) ~ = 3.3 bits por número.

Primero observo que nunca comienzan con 0 ya que 0 se usa como carácter de escape al principio. Entonces, simplemente puedo considerar los números de teléfono como enteros. Si este no fuera el caso, simplemente anteponer un "1" al número y luego convertirlo a entero. Esto no afectaría significativamente la eficiencia de la codificación (Probablemente una sobrecarga constante de algunos bytes). Si hay otros caracteres fuera de los 10 dígitos dentro de los números de teléfono, simplemente codifica con una base superior a 10. Sin embargo, esto perjudicará la eficiencia.

Los ordenaría por tamaño ascendente. Luego calcule las diferencias. Y luego serialice las diferencias usando protobuf como campos repetidos empaquetados.

Este método es similar al método de RexKerr, excepto que utilizo la solución perezosa de protobuf sobre un codificador Huffman. Probablemente sea un poco más grande ya que la codificación de entero protobuf es de propósito general y no tiene en cuenta la distribución de probabilidad de los números de teléfono. Pero es mucho más fácil codificar ya que solo necesito usar un serializador protobuf existente. Esto será problemático una vez que exceda el tamaño de un UInt64, es decir, hay números de teléfono de más de 19 dígitos. El formato de archivo aún lo admite, pero la mayoría de las implementaciones no.

Sin un índice, los tiempos de acceso serán bastante malos, pero deberían ser bastante compactos.

Realmente depende de qué operaciones desee ejecutar en la base de datos almacenada.

El enfoque trivial es el uso de enteros sin signo, si solo necesita almacenarlos, probablemente alguna compresión en la representación de texto sin formato con un diccionario sería más pequeña.

Si la memoria es nuestra mayor consideración, entonces no necesitamos almacenar el número, solo el delta entre i e i + 1.

Ahora si los números van desde 200 0000 - 999 9999, entonces hay 7,999,999 números de teléfono posibles. Como tenemos 1 millón de números, y si suponemos que están distribuidos uniformemente, tenemos una distancia esperada de E = n_i + 1 - n_i ~ 8 (3 bits) entre los números secuenciales n_i y n_i + 1. Entonces, para un int de 32 bits podríamos almacenar hasta 10 offsets secuenciales (~ 400kb de huella de memoria total óptima), sin embargo, es probable que tengamos algunos casos en los que necesitemos un offset mayor que 8 (Tal vez tengamos 400, o 1500 ??). En ese caso, podemos simplemente reservar los primeros 2 bits del int como un encabezado que nos dice qué tamaño de marco usamos para leer los bits que almacena. Por ejemplo, tal vez usemos: 00 = 3x10, 01 = 5x6, 10 = 7x4, 11 = 1 * 30.

Si observa las representaciones de campo de datos del Plan de numeración de América del Norte , concluirá que los números de teléfono de EE. UU. De 1+ NPA + NXX + xxxx se pueden almacenar en menos de 22 bits por campo de número de teléfono en cada código de área. Agregue los códigos de área y los datos que representan cualquier número de teléfono de EE. UU. (Más canadiense) pueden caber cómodamente en 32 bits. Esto es como una representación de campo de bit, no como una int.

Sin embargo, tu forma de pensar sobre esto no debería ser centrada en los EE. UU. Seguramente la pregunta no es solo que un ejercicio está comprimiendo 1 millón de números de teléfono en la menor cantidad posible de bits.

Los números de teléfono de EE. UU. Pueden tener un límite de 3 dígitos (planes de marcado de PBX internos) hasta 22 dígitos (1 + NPA + NXX + xxxx + plan de marcado interno de PBX de 11 dígitos). Si el número de teléfono se limitó al formato de número especificado de la ITU , tiene hasta 15 dígitos más 1 bit para el ''+''.

Probablemente deba definir una representación de campo de bit variable de cualquier número de teléfono entre 3 dígitos y 22 dígitos (o 15 dígitos para ITU) con cada campo de bit que tenga un campo de encabezado de X bits para indicar el formato del campo.

A continuación, coloque estos campos de bits en una matriz de bits comprimida. Potencialmente, esa matriz de bits se puede indexar con un trie o algún otro método.

La eficacia de esto se basa en el formato del millón de números de teléfono, la rapidez con la que desea acceder a ellos y la flexibilidad de la estructura de datos para más números de teléfono en el futuro en diferentes formatos. No se trata solo de contar bits para la respuesta "correcta" en mi humilde opinión.

Supongamos que suponemos que cada número de teléfono es coherente con el formato estadounidense de (código de área de 3 dígitos) - (número de 7 dígitos)

Este es un número de 10 dígitos.

Sin embargo, existen reglas para el compromiso cuando se trata de números de teléfono. Son escasos, por ejemplo, lo que significa que no se usan todos los códigos de área posibles. En este caso, un árbol simple es a-ok. Me refiero a pensar en eso ... solo necesitas 269 + 26 para Canadá. Eso es bastante pequeño, y has recortado una gran porción de espacio MÁS el tiempo de búsqueda aumentado. No solo eso, sino que puede aumentarse para la información de ubicación.

Después de eso, tienes un número de 7 dígitos. Esto se puede almacenar en un solo entero de 32 bits. Ordenar en insertar, y tienes un mecanismo bastante rápido para la recuperación ya que puedes hacer búsquedas binarias en el resto del número.

Supongo que un Int32 sin firmar o para números internacionales un Int64 sin firmar

Usando entradas sin signo de 32 bits que serían 4MB

Una posible solución es

  1. ordenar los números
  2. codificar deltas de un número al siguiente

La distribución de frecuencia delta será muy sesgada.

Hice un experimento usando un enfoque simple de empaquetado tipo BER para deltas usando una codificación de 7 + 3 + 3 + ... bits; función de codificación era

def delta_write(x, b1, b2): lim = 1 << (b1 - 1) if x < lim: bit_write(x, b1) else: bit_write(lim + (x & (lim - 1)), b1) delta_write(x >> (b1 - 1), b2, b2)

(los dos parámetros 7 y 3 se determinaron experimentalmente)

Con este enfoque obtuve un millón de números de 10 dígitos con los primeros 5 dígitos elegidos entre mil prefijos aleatorios con un promedio de 8,83 bits por número (tamaño compacto 1104188).

/******************************************************************************** Filename: Phone_Numbers.c Author: Paul Romsky Company: Autoliv AEL Date: 11 MAR 2013 Problem: What is the most efficient way, memory-wise, to store 1 million phone numbers? Caveats: There is no mention if the numbers are contiguous or not, so, to save space the numbers should be contiguous. The problem (as a specification) is rather vague and leaves a lot to interpretation, so many different methods may be desired, but which one(s) desired is not surely known. Are the phone numbers just the extension (last four digits), or do they include the exchange (the leading 3 digits), or do they also include area code and/or international numbers? There is no mention of the first number, only the range of numbers, so the first number 000-0000 is used. Although many numbers are not normally used, they could in fact be used as valid number sequences within the phone companies and are thus phone numbers nonetheless. Solution: A simple algorithm. If the numbers are not contiguous a fractal algorithm could be used. A standard ANSI C compiler should pack this program into a very small assembly module of only a few bytes. Revisions: Rev Date By Description --- ----------- -------------------- ------------------------------------------- - 11 MAR 2013 P. Romsky Initial Coding ********************************************************************************/ /* Includes */ #include <stdio.h> /* Functions */ /******************************************************************************** * * Main Entry Point * ********************************************************************************/ int main() { unsigned int Number; /* 1,000,000 Phone Number Storage 000-0000 through 999-9999 */ for(Number = 0000000; Number < 10000000; Number++) { /* Retrieve Numbers */ printf("%07u/n", Number); } return 0; } /* End */