Categorías
Interview

¿Cómo responder a las preguntas de codificación para su entrevista?

He estado entrevistando empresas recientemente. Aquí resumo lo que aprendí de mi experiencia. La entrevista es solo un espectáculo en el que actúas lo mejor que puedes. Si al entrevistador le gusta tu programa, tú ganas; de lo contrario, pierde. Existe la posibilidad de que juegues mejor de lo que eres, esto es BUENO y esto es lo que queremos.

Comprenda lo que quieren las empresas

En primer lugar, sepa qué es lo que realmente quieren las empresas.

Utilice un patrón para resolver el problema

  1. Ejemplifique: use un ejemplo y visualice el problema.
  2. Simplifica: Simplemente la pregunta y haz que sea lo suficientemente simple para resolver, y luego resuelve lo complicado.
  3. Reflexión: Piense y resuelva el problema utilizando los métodos que conoce, p. Ej., Búsqueda binaria, varios tipos de ordenación, manejar la matriz desde ambos extremos, etc.
  4. Lluvia de ideas sobre todas las estructuras de datos posibles: matriz, lista enlazada, pila, cola, tabla hash, montón, etc.

Mantenga la conversación en marcha

Puede que le resulte difícil mantener la conversación. Una forma es comenzar con una solución sencilla e ingenua.

Por ejemplo, dada una matriz de números enteros, todos los elementos están en pares excepto uno, ¿cómo encontrar el número único?

Ingenuamente, se puede usar un mapa de hash para resolver el problema. Entonces pensamos en un enfoque más avanzado.

Práctica

Categorías
Algorithms Interview

LeetCode – Particionamiento Palindrome (Java)

Problema

Dada una cadena s, la partición es tal que cada subcadena de la partición sea un palíndromo.

Devuelve todas las posibles particiones palindrómicas de s.

Por ejemplo, dado s = «aab»,
Regreso

  [
    ["aa","b"],
    ["a","a","b"]
  ]

1. Búsqueda en profundidad

public ArrayList<ArrayList<String>> partition(String s) {
	ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
 
	if (s == null || s.length() == 0) {
		return result;
	}
 
	ArrayList<String> partition = new ArrayList<String>();//track each possible partition
	addPalindrome(s, 0, partition, result);
 
	return result;
}
 
private void addPalindrome(String s, int start, ArrayList<String> partition,
		ArrayList<ArrayList<String>> result) {
	//stop condition
	if (start == s.length()) {
		ArrayList<String> temp = new ArrayList<String>(partition);
		result.add(temp);
		return;
	}
 
	for (int i = start + 1; i <= s.length(); i++) {
		String str = s.substring(start, i);
		if (isPalindrome(str)) {
			partition.add(str); 
			addPalindrome(s, i, partition, result);
			partition.remove(partition.size() - 1);
		}
	}
}
 
private boolean isPalindrome(String str) {
	int left = 0;
	int right = str.length() - 1;
 
	while (left < right) {
		if (str.charAt(left) != str.charAt(right)) {
			return false;
		}
 
		left++;
		right--;
	}
 
	return true;
}

2. Programación dinámica

El enfoque de programación dinámica es muy similar al problema de la subcadena palíndromo más larga.

public static List<String> palindromePartitioning(String s) {
 
	List<String> result = new ArrayList<String>();
 
	if (s == null)
		return result;
 
	if (s.length() <= 1) {
		result.add(s);
		return result;
	}
 
	int length = s.length();
 
	int[][] table = new int[length][length];
 
	// l is length, i is index of left boundary, j is index of right boundary
	for (int l = 1; l <= length; l++) {
		for (int i = 0; i <= length - l; i++) {
			int j = i + l - 1;
			if (s.charAt(i) == s.charAt(j)) {
				if (l == 1 || l == 2) {
					table[i][j] = 1;
				} else {
					table[i][j] = table[i + 1][j - 1];
				}
				if (table[i][j] == 1) {
					result.add(s.substring(i, j + 1));
				}
			} else {
				table[i][j] = 0;
			}
		}
	}
 
	return result;
}

Categorías
Algorithms Interview

LeetCode – Caché LRU (Java)

Diseñe e implemente una estructura de datos para la caché de uso menos reciente (LRU), que admita obtener y poner.

Análisis

La clave para resolver este problema es utilizar una lista de doble enlace que nos permite mover nodos rápidamente.

La caché LRU es una tabla hash de claves y nodos de doble enlace. La tabla hash hace que el tiempo de get () sea O (1). La lista de nodos de doble enlace hace que las operaciones de adición / eliminación de nodos sean O (1).

Solución Java

Defina una lista de doble enlace.

class Node{
    int key;
    int value;
    Node prev;
    Node next;
 
    public Node(int key, int value){
        this.key=key;
        this.value=value;
    }
}

Al analizar get y put, podemos resumir que hay 2 operaciones básicas: 1) removeNode (Nodo t), 2) offerNode (Nodo t).

class LRUCache {
    Node head;
    Node tail;
    HashMap<Integer, Node> map = null;
    int cap = 0;
 
    public LRUCache(int capacity) {
        this.cap = capacity;
        this.map = new HashMap<>();
    }
 
    public int get(int key) {
        if(map.get(key)==null){
            return -1;
        }
 
        //move to tail
        Node t = map.get(key);
 
        removeNode(t);
        offerNode(t);
 
        return t.value;
    }
 
    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node t = map.get(key);
            t.value = value;
 
            //move to tail
            removeNode(t);
            offerNode(t);
        }else{
            if(map.size()>=cap){
                //delete head
                map.remove(head.key);
                removeNode(head);
            }
 
            //add to tail
            Node node = new Node(key, value);
            offerNode(node);
            map.put(key, node);
        }
    }
 
    private void removeNode(Node n){
        if(n.prev!=null){
            n.prev.next = n.next;
        }else{
            head = n.next;
        }
 
        if(n.next!=null){
            n.next.prev = n.prev;
        }else{
            tail = n.prev;
        }
    }
 
    private void offerNode(Node n){
        if(tail!=null){
            tail.next = n;
        }
 
        n.prev = tail;
        n.next = null;
        tail = n;
 
        if(head == null){
            head = tail;   
        }
    }
}

Categorías
Concurrency Interview

¿Cómo hacer que un método sea seguro para subprocesos en Java?

Pregunta de la entrevista:

¿El siguiente método es seguro para subprocesos? ¿Cómo hacerlo seguro para subprocesos?

class MyCounter {
	private static int counter = 0;
 
	public static int getCount() {
		return counter++;
	}
}

Esta publicación explica una pregunta de entrevista general que ha sido formulada por Google y muchas empresas. Es de bajo nivel y no se trata de cómo diseñar un programa concurrente.

En primer lugar, la respuesta es NO. El método no es seguro para subprocesos, porque el contador ++ La operación no es atómica, lo que significa que consta de más de una operación atómica. En este caso, uno accede al valor y el otro aumenta el valor en uno.

Cuando el subproceso 1 accede al método en t1, es posible que el subproceso 2 no se complete con el método. Por tanto, el valor devuelto al hilo 1 es el valor que no se ha aumentado.

Hacer un método seguro para subprocesos – Método 1

Agregar sincronizado a este método lo hará seguro para subprocesos. Cuándo sincronizado se agrega a un método estático, el Clase objeto es el objeto que está bloqueado.

¿Marcarlo está lo suficientemente sincronizado? La respuesta es sí.

class MyCounter {
	private static int counter = 0;
 
	public static synchronized int getCount() {
		return counter++;
	}
}

Si el método no es estático, agregue sincronizado La palabra clave sincronizará la instancia de la clase, no la Clase objeto.

Hacer un método seguro para subprocesos – Método 2

En este contraejemplo en particular, podemos hacer contar ++ atomic utilizando AtomicInteger del paquete «java.util.concurrent.atomic».

import java.util.concurrent.atomic.AtomicInteger;
 
public class MyCounter {
	private static AtomicInteger counter = new AtomicInteger(0);
 
	public static int getCount() {
		return counter.getAndIncrement();
	}
}

Algunos otros datos útiles sobre la seguridad para subprocesos

Las variables locales son seguras para subprocesos en Java.

Cada hilo tiene su propia pila. Dos subprocesos diferentes nunca comparten la misma pila. A todas las variables locales definidas en un método se les asignará memoria en la pila. Tan pronto como el hilo actual complete la ejecución del método, se eliminará el marco de pila.

Categorías
Algorithms Interview

LeetCode – Prefijo común más largo (Java)

Problema

Escriba una función para encontrar la cadena de prefijo común más larga entre una matriz de cadenas.

Análisis

Para resolver este problema, necesitamos encontrar las dos condiciones de bucle. Uno es la longitud de la cuerda más corta. La otra es la iteración sobre cada elemento de la matriz de cadenas.

Solución Java

public String longestCommonPrefix(String[] strs) {
    if(strs==null || strs.length ==0){
        return "";
    }
 
    if(strs.length == 1){
        return strs[0];
    }
 
    int i=0;
    while(true){
        boolean flag = true;
        for(int j=1; j<strs.length; j++){
            if(strs[j].length()<=i || strs[j-1].length() <=i 
               || strs[j].charAt(i) != strs[j-1].charAt(i)){
                flag = false;
                break;
            }               
        }
 
        if(flag){
            i++;
        }else{
            break;
        }
    }
 
    return strs[0].substring(0, i);
}

Categorías
Algorithms Interview

LeetCode – Intersección de dos listas enlazadas (Java)

Problema

Escriba un programa para encontrar el nodo en el que comienza la intersección de dos listas enlazadas individualmente.

Por ejemplo, las siguientes dos listas enlazadas:

A:          a1 -> a2
                    ->
                      c1 -> c2 -> c3
                    ->           
B:     b1 -> b2 -> b3

comienzan a cruzarse en el nodo c1.

Solución Java

Primero calcule la longitud de dos listas y encuentre la diferencia. Luego, comience desde la lista más larga en el desplazamiento diferencial, recorra 2 listas y encuentre el nodo.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len1 = 0;
        int len2 = 0;
        ListNode p1=headA, p2=headB;
        if (p1 == null || p2 == null)
            return null;
 
        while(p1 != null){
            len1++;
            p1 = p1.next;
        }
        while(p2 !=null){
            len2++;
            p2 = p2.next;
        }
 
        int diff = 0;
        p1=headA;
        p2=headB;
 
        if(len1 > len2){
            diff = len1-len2;
            int i=0;
            while(i<diff){
                p1 = p1.next;
                i++;
            }
        }else{
            diff = len2-len1;
            int i=0;
            while(i<diff){
                p2 = p2.next;
                i++;
            }
        }
 
        while(p1 != null && p2 != null){
            if(p1.val == p2.val){
                return p1;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
 
        return null;
    }
}

Categorías
Algorithms Interview Java

LeetCode – Número más grande (Java)

Dada una lista de números enteros no negativos, organícelos de manera que formen el número más grande.

Por ejemplo, dado [3, 30, 34, 5, 9], el número formado más grande es 9534330. (Nota: el resultado puede ser muy grande, por lo que debe devolver una cadena en lugar de un número entero).

Análisis

Este problema se puede resolver ordenando cadenas, no ordenando enteros. Defina un comparador para comparar cadenas por concat () de derecha a izquierda o de izquierda a derecha.

Solución Java

public String largestNumber(int[] nums) {
    String[] arr = new String[nums.length];
    for(int i=0; i<nums.length; i++){
        arr[i]=String.valueOf(nums[i]);
    }
 
    Arrays.sort(arr, new Comparator<String>(){
        public int compare(String a, String b){
            return (b+a).compareTo(a+b);
        }
    });
 
    StringBuilder sb = new StringBuilder();
    for(String s: arr){
        sb.append(s);
    }
 
    while(sb.charAt(0)=='0'&&sb.length()>1)
        sb.deleteCharAt(0);
 
    return sb.toString();
}

Categorías
Algorithms Interview

LeetCode – Combinaciones (Java)

Dados dos enteros n y k, devuelve todas las combinaciones posibles de k números de 1 … n.

Por ejemplo, si n = 4 y k = 2, una solución es:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solución Java

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 
	if (n <= 0 || n < k)
		return result;
 
	ArrayList<Integer> item = new ArrayList<Integer>();
	dfs(n, k, 1, item, result); // because it need to begin from 1
 
	return result;
}
 
private void dfs(int n, int k, int start, ArrayList<Integer> item,
		ArrayList<ArrayList<Integer>> res) {
	if (item.size() == k) {
		res.add(new ArrayList<Integer>(item));
		return;
	}
 
	for (int i = start; i <= n; i++) {
		item.add(i);
		dfs(n, k, i + 1, item, res);
		item.remove(item.size() - 1);
	}
}

Categorías
Algorithms Interview

LeetCode – Encuentra el mínimo en la matriz ordenada rotada II (Java)

Seguimiento de «Encontrar mínimo en matriz ordenada rotada»: ¿Qué sucede si se permiten duplicados?

¿Afectaría esto la complejidad del tiempo de ejecución? ¿Como y por qué?

Solución Java 1: recursividad

Este es un problema de seguimiento de encontrar un elemento mínimo en una matriz ordenada rotada sin elementos duplicados. Solo necesitamos agregar una condición más, que verifica si el elemento más a la izquierda y el elemento más a la derecha son iguales. Si es así, simplemente podemos soltar uno de ellos. En mi solución a continuación, dejo caer el elemento izquierdo siempre que el más a la izquierda sea igual al más a la derecha.

public int findMin(int[] num) {
    return findMin(num, 0, num.length-1);
}
 
public int findMin(int[] num, int left, int right){
    if(right==left){
        return num[left];
    }
    if(right == left +1){
        return Math.min(num[left], num[right]);
    }
    // 3 3 1 3 3 3
 
    int middle = (right-left)/2 + left;
    // already sorted
    if(num[right] > num[left]){
        return num[left];
    //right shift one
    }else if(num[right] == num[left]){
        return findMin(num, left+1, right);
    //go right    
    }else if(num[middle] >= num[left]){
        return findMin(num, middle, right);
    //go left    
    }else{
        return findMin(num, left, middle);
    }
}

Solución Java 2: iteración

public int findMin(int[] nums) {
    int i=0;
    int j=nums.length-1;
 
    while(i<=j){
 
        //handle cases like [3, 1, 3]
        while(nums[i]==nums[j] && i!=j){
            i++;
        }
 
        if(nums[i]<=nums[j]){
            return nums[i];
        }
 
        int m=(i+j)/2;
        if(nums[m]>=nums[i]){
            i=m+1;
        }else{
            j=m;
        }
    }
 
    return -1;
}

Categorías
Algorithms Interview

LeetCode – Subarreglo de producto máximo (Java)

Encuentre el subarreglo contiguo dentro de un arreglo (que contenga al menos un número) que tenga el producto más grande.

Por ejemplo, dada la matriz [2,3,-2,4], el subarreglo contiguo [2,3] tiene el producto más grande = 6.

Solución Java – Programación dinámica

Esto es similar al subarreglo máximo. En lugar de suma, el signo del número afecta el valor del producto.

Al iterar la matriz, cada elemento tiene dos posibilidades: número positivo o número negativo. Necesitamos rastrear un valor mínimo, de modo que cuando se dé un número negativo, también pueda encontrar el valor máximo. Definimos dos variables locales, una rastrea el máximo y la otra rastrea el mínimo.

public int maxProduct(int[] nums) {
    int[] max = new int[nums.length];
    int[] min = new int[nums.length];
 
    max[0] = min[0] = nums[0];
    int result = nums[0];
 
    for(int i=1; i<nums.length; i++){
        if(nums[i]>0){
            max[i]=Math.max(nums[i], max[i-1]*nums[i]);
            min[i]=Math.min(nums[i], min[i-1]*nums[i]);
        }else{
            max[i]=Math.max(nums[i], min[i-1]*nums[i]);
            min[i]=Math.min(nums[i], max[i-1]*nums[i]);
        }
 
        result = Math.max(result, max[i]);
    }
 
    return result;
}

El tiempo es O (n).