| Author: Eduardo Enriquez

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!

Related Posts