Fondo:
Originalmente publiqué esta pregunta anoche, y recibí críticas por su vaguedad. Desde entonces, he consultado a muchos miembros del personal no solo sobre la redacción del problema, sino también sobre su complejidad (que no es O (1)). Este problema de programación es un giro maligno en una pregunta de entrevista de Amazon.
Pregunta:
Dada una Cadena de enteros concatenados aleatoriamente [0, 250), 0 a 250 exclusivos, falta UN número en la secuencia. Su trabajo es escribir un programa que calcule este número faltante. No hay otros números faltantes en la secuencia además del uno, y eso es lo que hace que este problema sea tan difícil y posiblemente computacionalmente difícil.
Hacer este problema a mano en cadenas más pequeñas, como los ejemplos 1 y 2 a continuación, es obviamente muy fácil. Por el contrario, calcular un número faltante en conjuntos de datos increíblemente grandes que involucran números de tres o cuatro dígitos sería increíblemente difícil. La idea detrás de este problema es construir un programa que haga este proceso por usted.
Información importante:
Una cosa que parecía bastante confusa cuando publiqué este problema anoche fue: exactamente cómo se define un número faltante. Un número faltante es el número DENTRO del rango especificado anteriormente; NO necesariamente el dígito. En el ejemplo 3, verá que el número faltante es 9, aunque aparezca en la secuencia. Hay 3 lugares donde el DIGIT 9 aparecerá en una serie de [0, 30): "9", "19" y "29". Su objetivo es diferenciar entre estos y descubrir que 9 es el NÚMERO faltante (dentro del ejemplo 3). En otras palabras, la parte difícil radica en descubrir qué secuencias de dígitos están completas y cuáles pertenecen a otros números.
Entrada:
La entrada es una Cadena S, que contiene enteros de 0 a 249 inclusive, o de 0 a 250 exclusivos (en otras palabras, [0, 250)). Estos enteros, como se indicó anteriormente, se mezclan para crear una secuencia aleatoria. NO hay delimitadores ("42, 31, 23, 44"), ni relleno de 0 (003076244029002); Los problemas son exactamente como se describe en los ejemplos. Se garantiza que solo hay 1 solución en los problemas reales. No se permiten múltiples soluciones para estos.
Criterios ganadores:
El que tenga el uso de memoria más rápido y más bajo será el ganador. En el caso milagroso de que un tiempo se vincule, se usará menos memoria para el interruptor de tiempo. ¡Enumere Big O si puede!
Ejemplos:
Los ejemplos 1 y 2 tienen un rango de [0, 10)
Los ejemplos 3 y 4 tienen un rango de [0, 30)
(Los ejemplos 1-4 son solo para demostración. Su programa no necesita manejarlos).
Los ejemplos 5 tienen un rango de [0, 250)
1. 420137659
- Missing number => 8
2. 843216075
- Missing number => 9
3. 2112282526022911192312416102017731561427221884513
- Missing number => 9
4. 229272120623131992528240518810426223161211471711
- Missing number => 15
5. 11395591741893085201244471432361149120556162127165124233106210135320813701207315110246262072142253419410247129611737243218190203156364518617019864222241772384813041175126193134141008211877147192451101968789181153241861671712710899168232150138131195104411520078178584419739178522066640145139388863199146248518022492149187962968112157173132551631441367921221229161208324623423922615218321511111211121975723721911614865611197515810239015418422813742128176166949324015823124214033541416719143625021276351260183210916421672722015510117218224913320919223553222021036912321791591225112512304920418584216981883128105227213107223142169741601798025
- Missing number => 71
Test Data:
Problem 1: 6966410819610521530291368349682309217598570592011872022482018312220241246911298913317419721920718217313718080857232177134232481551020010112519172652031631113791105122116319458153244261582135510090235116139611641267691141679612215222660112127421321901862041827745106522437208362062271684640438174315738135641171699510421015199128239881442242382361212317163149232839233823418915447142162771412092492141987521710917122354156131466216515061812273140130240170972181176179166531781851152178225242192445147229991613515911122223419187862169312013124150672371432051192510724356172282471951381601241518410318414211212870941111833193145123245188102
Problem 2: 14883423514241100511108716621733193121019716422221117630156992324819917158961372915140456921857371883175910701891021877194529067191198226669314940125152431532281961078111412624224113912011621641182322612016512820395482371382385363922471472312072131791925510478122073722091352412491272395020016194195116236186596116374117841971602259812110612913254255615723013185162206245183244806417777130181492211412431591541398312414414582421741482461036761192272120204114346205712198918190242184229286518011471231585109384415021021415522313136146178233133168222201785172212108182276835832151134861116216716910511560240392170208215112173234136317520219
Problem 3: 1342319526198176611201701741948297621621214122224383105148103846820718319098731271611601912137231471099223812820157162671720663139410066179891663131117186249133125172622813593129302325881203242806043154161082051916986441859042111711241041590221248711516546521992257224020174102234138991752117924457143653945184113781031116471120421331506424717816813220023315511422019520918114070163152106248236222396919620277541101222101232171732231122301511263822375920856142187182152451585137352921848164219492411071228936130762461191564196185114910118922611881888513917712153146227193235347537229322521516718014542248813617191531972142714505519240144
Problem 4: 2492402092341949619347401841041875198202182031161577311941257285491521667219229672211881621592451432318618560812361201172382071222352271769922013259915817462189101108056130187233141312197127179205981692121101632221732337196969131822110021512524417548627103506114978204123128181211814236346515430399015513513311152157420112189119277138882021676618323919018013646200114160165350631262167910238144334214230146151171192261653158161213431911401452461159313720613195248191505228186244583455139542924222112226148941682087115610915344641782142472102436810828123731134321131241772242411722251997612923295223701069721187182171471055710784170217851
N
, no solo250
? / ¿Qué pasa con el232
problema? Todas las posibilidades o alguna? Me doy cuenta de que sabías sobre ese tema, pero no me queda claro en la pregunta. / Si este es el código más rápido, debe haber una forma de medirlos. Por supuesto, correr en una supercomputadora es diferente de correr en una computadora vieja. / Porque nadie dijo eso, - ¡Bienvenido a PPCG!N
a, digamos, 1000 o 10000.Respuestas:
Clingo , ≈ 0.03 segundos
Esto es demasiado rápido para medirlo con precisión: deberá permitir casos de entrada más grandes en lugar de detenerse artificialmente en 250.
Entrada de ejemplo
La entrada es una lista de pares ( k , k th dígito). Aquí está el problema 1:
Salida de ejemplo
fuente
45879362100
conn = 11
y1
falta (respuestasmissing(0)
).missing(10)
también es válido)?C ++, 5000 casos de prueba aleatorios en 6.1 segundos
Esto es prácticamente rápido, pero puede haber algunos casos de prueba que lo hacen lento. Complejidad desconocida.
Si hay varias soluciones, las imprimirá todas. Ejemplo .
Explicación:
Cuenta las ocurrencias de los dígitos.
Haz una lista de todas las respuestas posibles.
Verifique si un candidato es una respuesta válida:
3-1. Intente dividir la (s) cadena (s) por números que solo ocurren una vez y márquelo como identificado, excepto el candidato.
Por ejemplo,
2112282526022911192312416102017731561427221884513
tiene solo uno14
, por lo que se puede dividir en211228252602291119231241610201773156
y27221884513
.3-2. Si alguna cadena dividida tiene longitud 1, márquela como identificada.
Si se hace alguna contradicción (identificada más de una vez), el candidato no es válido.
Si no podemos encontrar al candidato en la cadena, el candidato es válido.
3-3. Si se realiza alguna división, repita los pasos 3-1. De lo contrario, haga una búsqueda de fuerza bruta para verificar si el candidato es válido.
Pruébalo en línea!
fuente
Limpio , ~ 0.3s
Se corrigió un gran error en el algoritmo, es necesario volver a optimizarlo ahora.
Compilar con
clm -h 1024M -s 16M -nci -dynamics -fusion -t -b -IL Dynamics -IL Platform main
Esto funciona tomando cada número que la cadena debe contener y contando el número de lugares donde la secuencia de dígitos requerida está presente en la cadena. Luego realiza repetidamente estos pasos:
singles
)singles
)fuente