Merge Arrays: un ejercicio tipico de entrevista
A medida que pasa el tiempo, y uno pasa por distintos trabajos y por distintas entrevistas técnicas, descubre que algunos ejercicios son siempre los mismos. Les comparto uno que me tomaron varias veces: apareo de vectores o, en inglés, merge arrays.
"Complete the mergeArrays function which has two parameters-arrays, a and b. Both arrays contains m elements and the function needs to return a single, non-decreasing array of size 2m and returns the merged array..."
Aquí va mi solución, con un poquito de ayuda de stackoverflow:
def mergeArrays(aList, bList):
a1 = aList is None or len(aList) == 0
a2 = bList is None or len(bList) == 0
if a1 or a2:
return None
c = []
while aList and bList:
if aList[0] < bList[0]:
c.append(aList.pop(0))
else:
c.append(bList.pop(0))
return c + aList + bList
El punto clave de este algoritmo es el while. Lo primero a tener en cuenta es que las listas que recibimos, según el enunciado, ya están ordenadas de menor a mayor. Por esta razón no tengo que preocuparme por ordenar o recorrer la lista para buscar el menor y ubicarlo en mi lista c (hacer algo de este estilo solo haría que mi programa sea más lento y consuma más memoria)
Entonces, aprovechando el ordenamiento previo, comparo siempre el primer elemento (que es el menor) de cada lista y me quedo con el menor de los dos. Pero me lo quedo no como una copia, sino que lo quito de la lista con un pop, es decir que mi lista c gana un elemento y la otra lo pierde. Así continuará hasta que una de las dos listas quede sin elementos. Si esto sucede es porque todos esos elementos de la lista eran todos menores de los que quedaron en la otra lista.
Finalmente, unimos la lista C que tiene los números mas chicos y después, gracias a que python permite unir listas, vacías o no vacías, respentando el orden devolvemos nuestra única lista ordenada y con repetidos!