¿Cómo trabajar en Google? Analizando preguntas de entrevista

Uno de los lugares donde la mayor parte de los desarrolladores desea trabajar es Google, en este post analizaremos algunos problemas que exponen en su canal de youtube y daremos las soluciones en código Java, el problema que analizaremos el día de hoy es el siguiente:

Dado un arreglo de números determinar si dentro de este se encuentra el par de números que de la suma proporcionada

Datos de entrada:

  • Arreglo de números que podemos asumir que se encuentran ordenados
  • Valor entero que representa una suma

Datos de salida:

  • Expresión boolean de acuerdo a lo siguiente:
    • Verdadero: Si dentro del arreglo se encuentran dos números que al sumarlos dan el valor entero recibido
    • Falso : Si dentro del arreglo no se encuentran dos números que al sumarlos den el valor entero recibido

Ejemplos:

array = [1 , 2 , 3 , 9]   sum=8    salida=false

array = [1 , 2 , 4 , 4]   sum=8    salida=true

Antes de continuar te recomendamos que intentes resolverlo por ti mismo.

Solución 1

La primera solución y más sencilla es realizar todas las sumas posibles y validar si alguna de ellas genera el resultado esperado.

public class SearchSums {
	public static boolean searchSumInArray(int arr[], int sum) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j <arr.length; j++) {
				if (i != j && arr[i] + arr[j] == sum) {
					return true;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		int arr[] = { 1, 2, 4, 4 };
		int sum = 8;
		boolean response = searchSumInArray(arr, sum);
		System.out.println(response);
	}
}

Como se puede observar el programa anterior cumple con los requerimientos en el enunciado, pero si vas a una entrevista a Google esta no es la respuesta que debes dar por lo siguiente:

Aunque el código es simple y fácil de leer esta no es una solución óptima debido a que su complejidad (Hablando de notación Big O) es muy grande así que aunque tu pienses que lo resolviste de forma correcta esta respuesta será marcada como incorrecta.

Solución 2

La solución dos tiene un poco más de ciencia pero es mucho más óptima, para la explicación utilizaremos los siguientes datos de entrada:

array = [1 , 2 , 4 , 4]   sum=8

Analicemos el problema:

  • Recordemos que el arreglo esta ordenado de menor a mayor
  • La suma  posible más grande será con los dos últimos valores debido a que son los más grandes
  • La suma posible más pequeña será con los primeros dos valores debido a que son los más pequeños

Una vez mencionado lo anterior comencemos a diseñar la solución del problema siguiendo los siguientes pasos:

  • Colocaremos dos indices en nuestro arreglo uno en el último valor (j) y el otro en el primero (i).
  • Sumaremos el valor que se encuentra en esos dos indices, en este ejemplo serían 1 y 4.
    • Si el valor es igual a la suma que es 8 devolveremos verdadero y terminaremos el problema.
    • Si el valor es mayor a la suma que es 8 decrementaremos el indice j
    • Si el valor es menor a la suma que es 8 incrementaremos el indice i
  • Repetiremos este proceso hasta que siempre y cuando i sea menor que j

Veamos el código resolviendo lo anterior:

public class SearchSums {
	public static boolean searchSumInArray(int arr[], int sum) {
		for (int i = 0, j = (arr.length - 1); i < j;) {
			int localSum = arr[j] + arr[i];
			if (localSum == sum) {
				return true;
			} else if (localSum > sum) {
				j--;
			} else if (localSum < sum) {
				i++;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		int arr[] = { 1, 2, 3, 5, 9 };
		int sum = 8;
		boolean response = searchSumInArray(arr, sum);
		System.out.println(response);
	}
}

Con esta solución se puede conseguir el mismo objetivo que con la anterior pero de una manera mucho más óptima.

Recordemos que este algoritmo esta basado en que los datos están ordenados del mayor al menor, si este no fuera el caso la forma en la que se resolvería sería diferente.

Este problema se tomó de la cuenta de Youtube Life at Google y es el siguiente:

En este post solo se explicó la solución del problema asumiendo que el arreglo está ordenado en un próximo post se explicará la solución cuando el arreglo no está ordenado y más problemas de Google. Si tienes más soluciones coméntanoslas en la sección de comentarios.

Si te gusta el contenido compártelo y no olvides seguirnos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com

 

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s