algorithm - trabajo - preguntas ingreso a google
Tricky pregunta de la entrevista de Google (21)
¿Por qué no intentar mirar esto desde la otra dirección? Use un contador para probar las posibles respuestas contra la fórmula original. Perdón por el pseudo código.
for x = 1 to n
{
i=j=0
y=x
while ( y > 1 )
{
z=y
if y divisible by 2 then increment i and divide y by 2
if y divisible by 5 then increment j and divide y by 5
if y=1 then print i,j & x // done calculating for this x
if z=y then exit while loop // didn''t divide anything this loop and this x is no good
}
}
Un amigo mío está entrevistando por un trabajo. Una de las preguntas de la entrevista me hizo pensar, solo quería algunos comentarios.
Hay 2 enteros no negativos: i y j. Dada la siguiente ecuación, encuentre una solución (óptima) para iterar sobre i y j de tal forma que la salida esté ordenada.
2^i * 5^j
Entonces las primeras rondas se verían así:
2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25
Por más que lo intente, no puedo ver un patrón. ¿Tus pensamientos?
Aquí está mi intento con Scala:
case class IndexValue(twosIndex: Int, fivesIndex: Int)
case class OutputValues(twos: Int, fives: Int, value: Int) {
def test(): Boolean = {
Math.pow(2, twos) * Math.pow(5, fives) == value
}
}
def run(last: IndexValue = IndexValue(0, 0), list: List[OutputValues] = List(OutputValues(0, 0, 1))): List[OutputValues] = {
if (list.size > 20) {
return list
}
val twosValue = list(last.twosIndex).value * 2
val fivesValue = list(last.fivesIndex).value * 5
if (twosValue == fivesValue) {
val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex + 1)
val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.fivesIndex).fives + 1)
run(lastIndex, list :+ outputValues)
} else if (twosValue < fivesValue) {
val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex)
val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.twosIndex).fives)
run(lastIndex, list :+ outputValues)
} else {
val lastIndex = IndexValue(last.twosIndex, last.fivesIndex + 1)
val outputValues = OutputValues(value = fivesValue, twos = list(last.fivesIndex).twos, fives = list(last.fivesIndex).fives + 1)
run(lastIndex, list :+ outputValues)
}
}
val initialIndex = IndexValue(0, 0)
run(initialIndex, List(OutputValues(0, 0, 1))) foreach println
Salida:
OutputValues(0,0,1)
OutputValues(1,0,2)
OutputValues(2,0,4)
OutputValues(0,1,5)
OutputValues(3,0,8)
OutputValues(1,1,10)
OutputValues(4,0,16)
OutputValues(2,1,20)
OutputValues(0,2,25)
OutputValues(5,0,32)
OutputValues(3,1,40)
OutputValues(1,2,50)
OutputValues(6,0,64)
OutputValues(4,1,80)
OutputValues(2,2,100)
OutputValues(0,3,125)
OutputValues(7,0,128)
OutputValues(5,1,160)
OutputValues(3,2,200)
OutputValues(1,3,250)
OutputValues(8,0,256)
Aquí está mi solución
#include <stdio.h>
#include <math.h>
#define N_VALUE 5
#define M_VALUE 5
int n_val_at_m_level[M_VALUE];
int print_lower_level_val(long double val_of_higher_level, int m_level)
{
int n;
long double my_val;
for( n = n_val_at_m_level[m_level]; n <= N_VALUE; n++) {
my_val = powl(2,n) * powl(5,m_level);
if(m_level != M_VALUE && my_val > val_of_higher_level) {
n_val_at_m_level[m_level] = n;
return 0;
}
if( m_level != 0) {
print_lower_level_val(my_val, m_level - 1);
}
if(my_val < val_of_higher_level || m_level == M_VALUE) {
printf(" %Lf n=%d m = %d/n", my_val, n, m_level);
} else {
n_val_at_m_level[m_level] = n;
return 0;
}
}
n_val_at_m_level[m_level] = n;
return 0;
}
main()
{
print_lower_level_val(0, M_VALUE); /* to sort 2^n * 5^m */
}
Resultado:
1.000000 n = 0 m = 0
2.000000 n = 1 m = 0
4.000000 n = 2 m = 0
5.000000 n = 0 m = 1
8.000000 n = 3 m = 0
10.000000 n = 1 m = 1
16.000000 n = 4 m = 0
20.000000 n = 2 m = 1
25.000000 n = 0 m = 2
32.000000 n = 5 m = 0
40.000000 n = 3 m = 1
50.000000 n = 1 m = 2
80.000000 n = 4 m = 1
100.000000 n = 2 m = 2
125.000000 n = 0 m = 3
160.000000 n = 5 m = 1
200.000000 n = 3 m = 2
250.000000 n = 1 m = 3
400.000000 n = 4 m = 2
500.000000 n = 2 m = 3
625.000000 n = 0 m = 4
800.000000 n = 5 m = 2
1000.000000 n = 3 m = 3
1250.000000 n = 1 m = 4
2000.000000 n = 4 m = 3
2500.000000 n = 2 m = 4
3125.000000 n = 0 m = 5
4000.000000 n = 5 m = 3
5000.000000 n = 3 m = 4
6250.000000 n = 1 m = 5
10000.000000 n = 4 m = 4
12500.000000 n = 2 m = 5
20000.000000 n = 5 m = 4
25000.000000 n = 3 m = 5
50000.000000 n = 4 m = 5
100000.000000 n = 5 m = 5
Dijkstra obtiene una solución elocuente en "A Discipline of Programming". Él le atribuye el problema a Hamming. Aquí está mi implementación de la solución de Dijkstra.
int main()
{
const int n = 20; // Generate the first n numbers
std::vector<int> v(n);
v[0] = 1;
int i2 = 0; // Index for 2
int i5 = 0; // Index for 5
int x2 = 2 * v[i2]; // Next two candidates
int x5 = 5 * v[i5];
for (int i = 1; i != n; ++i)
{
int m = std::min(x2, x5);
std::cout << m << " ";
v[i] = m;
if (x2 == m)
{
++i2;
x2 = 2 * v[i2];
}
if (x5 == m)
{
++i5;
x5 = 5 * v[i5];
}
}
std::cout << std::endl;
return 0;
}
El algoritmo implementado por user515430 por Edsger Dijkstra (http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF) probablemente sea lo más rápido que pueda obtener. Llamo a cada número que es una forma de 2^i * 5^j un "número especial". Ahora la respuesta vlads sería O(i*j) pero con un algoritmo doble, uno para generar los números especiales O(i*j) y uno para ordenarlos (según el artículo vinculado también O(i*j) .
Pero revisemos el algoritmo de Dijkstra (ver abajo). En este caso, n es la cantidad de números especiales que estamos generando, por lo que es igual a i*j . Estamos dando vueltas una vez, 1 -> n en cada bucle realizamos una acción constante. Entonces este algoritmo también es O(i*j) . Y con una constante bastante rápida también.
Mi implementación en C ++ con GMP (C ++ wrapper) y dependencia en boost::lexical_cast , aunque eso se puede eliminar fácilmente (soy flojo y ¿quién no usa Boost?). Compilado con g++ -O3 test.cpp -lgmpxx -o test . En Q6600 Ubuntu 10.10 time ./test 1000000 da 1145ms .
#include <iostream>
#include <boost/lexical_cast.hpp>
#include <gmpxx.h>
int main(int argc, char *argv[]) {
mpz_class m, x2, x5, *array, r;
long n, i, i2, i5;
if (argc < 2) return 1;
n = boost::lexical_cast<long>(argv[1]);
array = new mpz_class[n];
array[0] = 1;
x2 = 2;
x5 = 5;
i2 = i5 = 0;
for (i = 1; i != n; ++i) {
m = std::min(x2, x5);
array[i] = m;
if (x2 == m) {
++i2;
x2 = 2 * array[i2];
}
if (x5 == m) {
++i5;
x5 = 5 * array[i5];
}
}
delete [] array;
std::cout << m << std::endl;
return 0;
}
Esto es muy fácil de hacer O(n) en lenguajes funcionales. La lista l de 2^i*5^j números se puede definir simplemente como 1 y luego 2*l y 5*l fusionados. Así es como se ve en Haskell:
merge :: [Integer] -> [Integer] -> [Integer]
merge (a:as) (b:bs)
| a < b = a : (merge as (b:bs))
| a == b = a : (merge as bs)
| b > a = b : (merge (a:as) bs)
xs :: [Integer]
xs = 1 : merge (map(2*)xs) (map(5*)xs)
La función de merge le da un nuevo valor en tiempo constante. Lo mismo ocurre con el map y, por lo tanto, también lo hace l .
Mi implementación se basa en las siguientes ideas:
- Use dos colas Q2 y Q5, ambas inicializadas con 1. Mantendremos ambas colas ordenadas.
- En cada paso, dequeue el elemento numérico MIN más pequeño de Q2 o Q5 e imprímalo. Si tanto Q2 como Q5 tienen el mismo elemento, elimine ambos. Imprime este número. Esto es básicamente la fusión de dos matrices ordenadas: en cada paso, elija el elemento más pequeño y avance.
- Enqueue MIN * 2 a Q2 y MIN * 5 a Q5. Este cambio no rompe la invariante de Q2 / Q5 que se está ordenando, porque MIN es mayor que el número MIN anterior.
Ejemplo:
Start with 1 and 1 (to handle i=0;j=0 case):
Q2: 1
Q5: 1
Dequeue 1, print it and enqueue 1*2 and 1*5:
Q2: 2
Q5: 5
Pick 2 and add 2*2 and 2*5:
Q2: 4
Q5: 5 10
Pick 4 and add 4*2 and 4*5:
Q2: 8
Q5: 5 10 20
....
Código en Java:
public void printNumbers(int n) {
Queue<Integer> q2 = new LinkedList<Integer>();
Queue<Integer> q5 = new LinkedList<Integer>();
q2.add(1);
q5.add(1);
for (int i = 0; i < n; i++) {
int a = q2.peek();
int b = q5.peek();
int min = Math.min(a, b);
System.out.println(min);
if (min == a) {
q2.remove();
}
if (min == b) {
q5.remove();
}
q2.add(min * 2);
q5.add(min * 5);
}
}
Sé que probablemente estoy equivocado, pero aquí hay una heurística muy simple ya que no involucra muchos números como 2,3,5. Sabemos que para cualquier secuencia i, j 2 ^ i * 5 ^ j siguiente sería 2 ^ (i-2) * 5 ^ (j + 1). Al ser un google q debe tener una solución simple.
def func(i, j):
print i, j, (2**i)*(5**j)
imax=i=2
j=0
print "i", "j", "(2**i)*(5**j)"
for k in range(20):
func(i,j)
j=j+1; i=i-2
if(i<0):
i = imax = imax+1
j=0
Esto produce salida como:
i j (2**i)*(5**j)
2 0 4
0 1 5
3 0 8
1 1 10
4 0 16
2 1 20
0 2 25
5 0 32
3 1 40
1 2 50
6 0 64
4 1 80
2 2 100
0 3 125
7 0 128
5 1 160
3 2 200
1 3 250
8 0 256
6 1 320
Si dibuja una matriz con i como la fila yj como la columna, puede ver el patrón. Comience con i = 0 y luego simplemente recorra la matriz subiendo 2 filas y hacia la derecha 1 columna hasta llegar a la parte superior de la matriz (j> = 0). Luego ve i + 1, etc ...
Entonces para i = 7 viajas así:
7, 0 -> 5, 1 -> 3, 2 -> 1, 3
Y para i = 8:
8, 0 -> 6, 1 -> 4, 2 -> 2, 3 -> 0, 4
Aquí está en Java subiendo a i = 9. Imprime la posición de la matriz (i, j) y el valor.
for(int k = 0; k < 10; k++) {
int j = 0;
for(int i = k; i >= 0; i -= 2) {
int value = (int)(Math.pow(2, i) * Math.pow(5, j));
System.out.println(i + ", " + j + " -> " + value);
j++;
}
}
Si observa lo que realmente está sucediendo cuando incrementamos i o j en la expresión 2^i * 5^j , está multiplicando por otro 2 u otro 5. Si reafirmamos el problema como - dado un valor particular de i y j ¿Cómo encontrarías el siguiente valor mayor? La solución se vuelve aparente.
Estas son las reglas que podemos enumerar de manera bastante intuitiva:
- Si hay un par de 2s (
i > 1) en la expresión, debemos reemplazarlos por un 5 para obtener el siguiente número más grande. Por lo tanto,i -= 2yj += 1. - De lo contrario, si hay un 5 (
j > 0), tenemos que reemplazarlo con tres 2s. Entoncesj -= 1ei += 3. - De lo contrario, necesitamos simplemente suministrar otros 2 para aumentar el valor por un mínimo.
i += 1.
Aquí está el programa en Ruby:
i = j = 0
20.times do
puts 2**i * 5**j
if i > 1
j += 1
i -= 2
elsif j > 0
j -= 1
i += 3
else
i += 1
end
end
Si se nos permite usar la colección java, entonces podemos tener este número en O (n ^ 2)
public static void main(String[] args) throws Exception {
int powerLimit = 7;
int first = 2;
int second = 5;
SortedSet<Integer> set = new TreeSet<Integer>();
for (int i = 0; i < powerLimit; i++) {
for (int j = 0; j < powerLimit; j++) {
Integer x = (int) (Math.pow(first, i) * Math.pow(second, j));
set.add(x);
}
}
set=set.headSet((int)Math.pow(first, powerLimit));
for (int p : set)
System.out.println(p);
}
Aquí powerLimit tiene que ser inicializado con mucho cuidado. Dependiendo de cuántos números quieras.
Solo tenía curiosidad por saber qué esperar la próxima semana y he encontrado esta pregunta.
Creo que la idea es 2 ^ i aumenta no en pasos tan grandes como 5 ^ j. Así que aumente i siempre que el próximo j-step no sea más grande.
El ejemplo en C ++ (Qt es opcional):
QFile f("out.txt"); //use output method of your choice here
f.open(QIODevice::WriteOnly);
QTextStream ts(&f);
int i=0;
int res=0;
for( int j=0; j<10; ++j )
{
int powI = std::pow(2.0,i );
int powJ = std::pow(5.0,j );
while ( powI <= powJ )
{
res = powI * powJ;
if ( res<0 )
break; //integer range overflow
ts<<i<<"/t"<<j<<"/t"<<res<<"/n";
++i;
powI = std::pow(2.0,i );
}
}
La salida:
i j 2^i * 5^j
0 0 1
1 1 10
2 1 20
3 2 200
4 2 400
5 3 4000
6 3 8000
7 4 80000
8 4 160000
9 4 320000
10 5 3200000
11 5 6400000
12 6 64000000
13 6 128000000
14 7 1280000000
Tienes que hacer un seguimiento de los exponentes individuales de ellos, y cuáles serían sus sumas
entonces empiezas con f(0,0) --> 1 ahora tienes que incrementar uno de ellos:
f(1,0) = 2
f(0,1) = 5
entonces sabemos que 2 es el siguiente, también sabemos que podemos incrementar el exponente de i hasta que la suma supere 5.
Sigues yendo y viniendo de esta manera hasta que llegas a la cantidad de rondas estimadas.
Una solución basada en FIFO necesita menos capacidad de almacenamiento. Código de Python
F = [[1, 0, 0]] # FIFO [value, i, j]
i2 = -1; n2 = n5 = None # indices, nexts
for i in range(1000): # print the first 1000
last = F[-1][:]
print "%3d. %21d = 2^%d * 5^%d" % tuple([i] + last)
if n2 <= last: i2 += 1; n2 = F[i2][:]; n2[0] *= 2; n2[1] += 1
if n5 <= last: i2 -= 1; n5 = F.pop(0); n5[0] *= 5; n5[2] += 1
F.append(min(n2, n5))
salida:
0. 1 = 2^0 * 5^0
1. 2 = 2^1 * 5^0
2. 4 = 2^2 * 5^0
...
998. 100000000000000000000 = 2^20 * 5^20
999. 102400000000000000000 = 2^27 * 5^17
Usando programación dinámica puede hacer esto en O (n). La verdad fundamental es que ningún valor de i y j puede darnos 0, y para obtener 1, ambos valores deben ser 0;
TwoCount[1] = 0
FiveCount[1] = 0
// function returns two values i, and j
FindIJ(x) {
if (TwoCount[x / 2]) {
i = TwoCount[x / 2] + 1
j = FiveCount[x / 2]
}
else if (FiveCount[x / 5]) {
i = TwoCount[x / 2]
j = FiveCount[x / 5] + 1
}
}
Siempre que llame a esta función, compruebe si i y j están configurados, si no son nulos, TwoCount y FiveCount
C ++ respuesta. Perdón por el mal estilo de codificación, pero estoy apurado :(
#include <cstdlib>
#include <iostream>
#include <vector>
int * TwoCount;
int * FiveCount;
using namespace std;
void FindIJ(int x, int &i, int &j) {
if (x % 2 == 0 && TwoCount[x / 2] > -1) {
cout << "There''s a solution for " << (x/2) << endl;
i = TwoCount[x / 2] + 1;
j = FiveCount[x / 2];
} else if (x % 5 == 0 && TwoCount[x / 5] > -1) {
cout << "There''s a solution for " << (x/5) << endl;
i = TwoCount[x / 5];
j = FiveCount[x / 5] + 1;
}
}
int main() {
TwoCount = new int[200];
FiveCount = new int[200];
for (int i = 0; i < 200; ++i) {
TwoCount[i] = -1;
FiveCount[i] = -1;
}
TwoCount[1] = 0;
FiveCount[1] = 0;
for (int output = 2; output < 100; output++) {
int i = -1;
int j = -1;
FindIJ(output, i, j);
if (i > -1 && j > -1) {
cout << "2^" << i << " * " << "5^"
<< j << " = " << output << endl;
TwoCount[output] = i;
FiveCount[output] = j;
}
}
}
Obviamente, puede utilizar estructuras de datos distintas de la matriz para aumentar dinámicamente su almacenamiento, etc. Este es solo un boceto para demostrar que funciona.
Use un Min-Heap.
Pon 1.
extracto-Min. Digamos que obtienes x.
Empuje 2x y 5x en el montón.
Repetir.
En lugar de almacenar x = 2 ^ i * 5 ^ j, puede almacenar (i, j) y usar una función de comparación personalizada.
Usted sabe que log_2 (5) = 2.32. De esto notamos que 2 ^ 2 <5 y 2 ^ 3> 5.
Ahora mira una matriz de posibles respuestas:
j/i 0 1 2 3 4 5
0 1 2 4 8 16 32
1 5 10 20 40 80 160
2 25 50 100 200 400 800
3 125 250 500 ...
Ahora, para este ejemplo, elija los números en orden. El pedido sería:
j/i 0 1 2 3 4 5
0 1 2 3 5 7 10
1 4 6 8 11 14 18
2 9 12 15 19 23 27
3 16 20 24...
Tenga en cuenta que cada fila comienza 2 columnas detrás de la fila que comienza. Por ejemplo, i = 0 j = 1 viene directamente después de i = 2 j = 0.
Un algoritmo que podemos derivar de este patrón es por lo tanto (supongamos j> i):
int i = 2;
int j = 5;
int k;
int m;
int space = (int)(log((float)j)/log((float)i));
for(k = 0; k < space*10; k++)
{
for(m = 0; m < 10; m++)
{
int newi = k-space*m;
if(newi < 0)
break;
else if(newi > 10)
continue;
int result = pow((float)i,newi) * pow((float)j,m);
printf("%d^%d * %d^%d = %d/n", i, newi, j, m, result);
}
}
NOTA: El código aquí limita los valores de los exponentes de i y j a menos de 10. Puede extender fácilmente este algoritmo para encajar en cualquier otro límite arbitrario.
NOTA: El tiempo de ejecución para este algoritmo es O (n) para las primeras n respuestas.
NOTA: La complejidad del espacio para este algoritmo es O (1)
aquí hay una forma más refinada de hacerlo (más refinada que mi respuesta anterior, es decir):
imagina que los números se colocan en una matriz:
0 1 2 3 4 5 -- this is i
----------------------------------------------
0| 1 2 4 8 16 32
1| 5 10 20 40 80 160
2| 25 50 100 200 400 800
3| 125 250 500 1000 2000 ...
4| 625 1250 2500 5000 ...
j on the vertical
lo que tienes que hacer es "caminar" esta matriz, comenzando en (0,0) . También necesita hacer un seguimiento de cuáles son sus próximos movimientos posibles. Cuando comienzas en (0,0) solo tienes dos opciones: ya sea (0,1) o (1,0) : dado que el valor de (0,1) es menor, lo eliges. luego haz lo mismo para tu próxima elección (0,2) o (1,0) . Hasta ahora, tiene la siguiente lista: 1, 2, 4 . Su próximo movimiento es (1,0) ya que el valor allí es más pequeño que (0,3) . Sin embargo, ahora tiene tres opciones para su próximo movimiento: ya sea (0,3) o (1,1) o (2,0) .
No necesita la matriz para obtener la lista, pero sí necesita hacer un seguimiento de todas sus elecciones (es decir, cuando llegue a más de 125, tendrá 4 opciones).
calcule los resultados y póngalos en una lista ordenada, junto con los valores para i y j
This es la entrada relevante en OEIS.
Parece posible obtener la secuencia ordenada generando los primeros términos, digamos
1 2 4 5
y luego, comenzando desde el segundo término, multiplicando por 4 y 5 para obtener los próximos dos
1 2 4 5 8 10
1 2 4 5 8 10 16 20
1 2 4 5 8 10 16 20 25
y así...
Intuitivamente, esto parece correcto, pero, por supuesto, falta una prueba.
Mi intuición
Si tomo el valor inicial como 1 donde i = 0, j = 0, entonces puedo crear los siguientes números como (2 ^ 1) (5 ^ 0), (2 ^ 2) (5 ^ 0), (2 ^ 0) * (5 ^ 1), ... es decir, 2,4,5 ..
Digamos que en cualquier punto mi número es x. entonces puedo crear los próximos números de las siguientes maneras:
- x * 2
- x * 4
- x * 5
Explicación
Since new numbers can only be the product with 2 or 5.
But 4 (pow(2,2)) is smaller than 5, and also we have to generate
Numbers in sorted order.Therefore we will consider next numbers
be multiplied with 2,4,5.
Why we have taken x*4 ? Reason is to pace up i, such that it should not
be greater than pace of j(which is 5 to power). It means I will
multiply my number by 2, then by 4(since 4 < 5), and then by 5
to get the next three numbers in sorted order.
Prueba de funcionamiento
We need to take an Array-list of Integers, let say Arr.
Also put our elements in Array List<Integers> Arr.
Initially it contains Arr : [1]
Comencemos con x = 1.
Los siguientes tres números son 1 * 2, 1 * 4, 1 * 5 [2,4,5]; Arr [1,2,4,5]
Ahora x = 2
Los siguientes tres números son [4,8,10] {Dado que 4 ya ocurrió, lo ignoraremos} [8,10]; Arr [1,2,4,5,8,10]
Ahora x = 4
Los siguientes tres números [8,16,20] {8 ya ocurrieron, ignórenlo} [16,20] Arr [1,2,4,5,8,10,16,20]
x = 5
Los siguientes tres números [10,20,25] {10,20} ya están [25] agregados Arr [1,2,4,5,8,10,16,20,25]
Condición de terminación
Terminating condition when Arr last number becomes greater
than (5^m1 * 2^m2), where m1,m2 are given by user.
Análisis
Time Complexity : O(K) : where k is numbers possible between i,j=0 to
i=m1,j=m2.
Space Complexity : O(K)