dpalmasan / code-challenges Goto Github PK

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Actualizar pyproject.toml y coverage para tener un umbral más alto y probar soluciones en completitud (casos de borde, etc.)

Dado un array de enteros, ordenado en forma creciente, encontrar la posición inicial y final de un valor dado.

Si el valor no se encuentra en el array, retornar [-1, -1].

Se debe escribir un algoritmo que tenga una complejidad en tiempo de ejecución de O(log n)

Ejemplo 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Ejemplo 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Ejemplo 3:

Input: nums = [], target = 0
Output: [-1,-1]

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.

Ejemplo:

• Linters
• Code format
• Type Checks

Dado un array de enteros ordenados de forma ascendente, encontrar la posición inicial y final de un valor dado. Si el valor no se encuentra en el array, retornar [-1, 1]. El algoritmo debe ser de complejidad O(log n) en tiempo de ejecución.

Ejemplo 1:

Entrada: nums = [5,7,7,8,8,10], target = 8
Salida: [3,4]

Ejemplo 2:

Entrada: nums = [5,7,7,8,8,10], target = 6
Salida: [-1,-1]

Escriba una función con la siguiente firma bool oneEditApart(string s1, string s2). La función debe retornar true si con una sola edición el string s1/s2 puede ser transformado a s2/s1. Una edición consiste en:

• Insertar un caracter en cualquier posición del string
• Eliminar un caracter
• Reemplazar un caracter

Ejemplos:

OneEditApart("cat", "dog") = false
OneEditApart("cat", "cats") = true
OneEditApart("cat", "cut") = true
OneEditApart("cat", "cast") = true
OneEditApart("cat", "at") = true
OneEditApart("cat", "act") = false

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Inicialmente, había puesto imágenes dentro del repo, pero decidí alojarlas en un gist para no ensuciar el repo. Tengo que mover las imágenes que aún existen, al gist.

Actualmente las explicaciones de las soluciones, viven en el directorio sols-expl en un README.md por tipo de problema. El problema es que no hay forma de enlazar la solución al problema de origen. Idealmente, debiese haber un link al issue con el enunciado del problema.

Dada la raíz de un árbol binario, se dice que un nodo X en el árbol es "bueno" si en el camino desde la raíz hasta X no hay nodos que tengan un valor mayor que el que tenga X.

Se pide crear una función que dada la raíz de un árbol binario, retorne la cantidad de nodos "buenos".

Ejemplo 1

Salida: 4
Explicación: Los nodos en azul son "buenos".
La raíz del árbol, (nodo (3)) siempre es un nodo "bueno"
Nodo 4 -> (3,4) Es el valor máximo visto empezando desde la raíz.
Nodo 5 -> (3,4,5) Es el valor máximo en el camino
Node 3 -> (3,1,3) idem

Ejemplo 2

Salida: 3
Explicación: Nodo 2 -> (3, 3, 2) no es bueno porque "3" es mayor que 2.

Ejemplo 3

Árbol con 1 solo nodo:

Salida: 1
Explicación: La raíz siempre es un nodo "bueno"

Para ser consistente con lo esperado y modelado, coverage debe configurarse con. 100%

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Se tiene un array nums ordenado de forma no decreciente.

Construya y retorne un array de enteros de la misma longitud que nums, de tal forma que cada elemento result[i] es igual a la suma de las diferencias absolutas entre nums[i] y el resto de los elementos de nums.

En otras palabras, result[i] se calcula como sum(|nums[i]-nums[j]|) donde 0 <= j < nums.length && j != i (indexado desde 0).

Input: nums = [2,3,5]
Output: [4,3,5]

Explicación:

result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.

Se tiene un array de enteros nums ordenados en forma ascendente (todos los valores del array son distintos)

Antes de llegar a la función, el array nums está posiblemente rotado en un valor k desconocido (1 <= k <= nums.size), de manera que el array resultante es [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. Por ejemplo, el array [0,1,2,4,5,6,7] podría ser rotado 4 veces y quedar como [4,5,6,7,0,1,2].

Dado un array nums que podría estar rotado, y un valor a buscar, retornar el índice (posición) del valor en nums, o -1 si el valor no se encuentra en nums.

La solución debe tener una complejidad en tiempo de ejecución de O(log n)

Ejemplo 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Ejemplo 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Implemente una función que imprima en pantalla la secuencia Look and Say, hasta un término n:

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

Dada la raíz de un árbol binario, retorne el recorrido en orden zig-zag de sus nodos (es decir, de izquierda a derecha, luego de derecha a izquierda y así hasta recorrer todos los nodos alternando entre niveles).

Ejemplo:

Entrada: raíz (nodo con valor 3)
Salida: [[3],[20,9],[15,7]]

Como referencia, la clase nodo puede definirse como:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Dado un árbol binario:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Crear cada puntero para que apunte al nodo que tenga más próximo a la derecha. Si no hay un nodo a la derecha, el puntero next debe apuntar a NULL.

Inicialmente, todos los punteros a next están inicializados como NULL.

Ejemplo 1:

Dada una matriz board de mxn donde cada celda es una letra, y una palabra word, cree un algoritmo que retorne true si la palabra se puede encontrar dentro de la matriz.

La palabra debe poder formarse por letras que se encuentren adyacentes, esto es, que se encuentren en la vecindad horizontal o vertical de una celda dada (no en diagonal). La misma celda, no puede usarse más de una vez.

Ejemplo:

Entrada: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Salida: true

Entrada: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Salida: false

Se tiene una grilla de mxn que contiene 0's y 1's. Se define como una isla a un conjunto de 1's conectados ya sea horizontal o verticalmente. Se puede asumir que fuera de los límites, sólo hay agua.

El área de una isla es el número de celdas cuyo valor es 1.

El objetivo es retornar el área máxima de una isla dada una grilla. Si no hay islas, retornar 0.

Ejemplo 1

Entrada: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Salida: 6

Ejemplo 2

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Dado el primer elemento de una lista enlazada ordenada, eliminar todos los nodos que tienen valores duplicados, dejando únicamente los nodos con valores distintos de la lista original. Retornar la lista ordenada

Ejemplo 1:

Ejemplo 2:

Escriba un algoritmo eficiente que búsque un valor dado en una matriz de m x n. La matriz tiene las siguientes propiedades:

• Los enteros de cada fila estan ordenados desde la izquierda hacia la derecha en orden ascendente.
• El primer entero de cada fila es mayor que el último entero de la fila anterior

Ejemplo:

Encuentre el patrón de los siguientes ejemplos y cree una función con la siguiente firma (n: int) -> int[][], donde n es la dimensión del array 2D de salida (nxn):

n = 3
123
894
765

n = 4
01 02 03 04
12 13 14 05
11 16 15 06
10 09 08 07

n = 8
1 2 3 4 5 6 7 8
28 29 30 31 32 33 34 9
27 48 49 50 51 52 35 10
26 47 60 61 62 53 36 11
25 46 59 64 63 54 37 12
24 45 58 57 56 55 38 13
23 44 43 42 41 40 39 14
22 21 20 19 18 17 16 15

Se tienen dos strings s1 y s2. Se puede escoger cualquier substring de s1 y reorganizar los caracteres del substring escogido. Calcule la longitud mínima del substring de s1 tal que s2 es un substring del substring escogido.

La función a implementar debe tener la siguiente firma:

int minLengthSubstring(String s1, String s2)

Entrada: s1 y s2 son dos strings de largo >= 1, que pueden contener hasta 1.000.000 de caracteres.

Salida: El largo mínimo del substring de s, si no es posible, retornar -1.

Ejemplo:

s1 = "dcbefebce"
s2 = "fd"

Salida = 5

Explicación:

El substring "dcbef" se puede reorganizar de forma tal de contener el substring "fd", por ejemplo: "cfdeb", "cefdb", etc. Por lo tanto la longitud mínima requerida es 5.

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Dado un array de enteros (nums), encontrar el subarray contiguo (que tenga al menos un número) que tenga la máxima suma y retornar dicha suma.

Ejemplo:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explicación: [4,-1,2,1] tiene la máxima suma = 6.

Dados dos strings s1 y s2, retornar true si s2 contiene una permutación de s1, o false en caso contrario. En otras palabras, retornar true si una permutación de s1 es un substring de s2.

Ejemplos:

Entrada: s1 = "ab", s2 = "eidbaooo"
Salida: true
Explicación: s2 contiene una permutación de s1 ("ba").

Entrada: s1 = "ab", s2 = "eidboaoo"
Salida: false

Restricciones:

• 1 <= s1.length, s2.length <= 104
• s1 y s2 contienen el siguiente conjunto de caracteres: abcdefghijklmnopqrstuvwxyz

• Agregar a CI
• Agregar configuración de coverage (> 90%)

Dado un array, rote el array hacia la derecha k pasos, donde k es un entero positivo.

Ejemplo 1

Entrada: nums = [1,2,3,4,5,6,7], k = 3
Salida: [5,6,7,1,2,3,4]
Explicación:
Rotar 1 paso hacia la derecha: [7,1,2,3,4,5,6]
Rotar 2 pasos hacia la derecha: [6,7,1,2,3,4,5]
Rotar 3 pasos hacia la derecha: [5,6,7,1,2,3,4]

Ejemplo 2

Entrada: nums = [-1,-100,3,99], k = 2
Salida: [3,99,-1,-100]
Explicación: 
Rotar 1 paso hacia la derecha: [99,-1,-100,3]
Rotar 2 pasos hacia la derecha: [3,99,-1,-100]

Dado un array nums, mover todos los 0s de nums hacia la derecha, manteniendo el orden relativo de los elementos de nums.

Ejemplo 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Ejemplo 2:

Input: nums = [0]
Output: [0]

Preguntas de seguimiento:

• ¿Se puede hacer in place? (es decir, O(1) en memoria?
• ¿Cuál es el número de operaciones óptimas que se puede llegar a tener?

Una imagen se representa como una grilla m x n enteros, donde cada celda image[i][j] representa el valor del pixel (i, j) en la imagen.

Se te proporcionan tres enteros, sr, sc y newColor. El objetivo es hacer un llenado de la imagen comenzando por el pixel image[sr][sc].

Para hacer un llenado, se considera el pixel inicial y todos los pixeles colindantes a este (arriba, abajo, izquierda y derecha) que tengan el mismo color que el pixel inicial, y así sucesivamente con el resto de los pixeles colindantes al resto de los pixeles. Posteriormente, se debe reemplazar el color de los pixeles mencionados a newColor.

Retornar la imagen modificada después del proceso de llenado.

Ejemplo 1

Entrada: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Salida: [[2,2,2],[2,2,0],[2,0,1]]
Explicación: Desde el centro de la imagen `(sr, sc) = (1, 1)` (pixel rojo), todos los pixeles conectados son del mismo color que el pixel inicial (pixeles azules), por lo tanto se colorean con el color `newColor`.

Ejemplo 2:

Entrada: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
Salida: [[2,2,2],[2,2,2]]

Dado el primer elemento de una lista (head), remover el n-ésimo elemento de la lista empezando la cuenta desde el final y retornar el primer elemento de la lista (head).

Ejemplos:

Para definir la lista, considerar la siguiente estructura:

class ListNode:
    val: int
    next: ListNode

Por ejemplo, en python:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Entrada: [1, 2, 3, 4, 5], head = 1, n = 2
Salida: [1, 2, 3, 5]

Entrada: [1], head = 1, n = 1
Output: []

Restricciones:

El número de nodos de la lista es sz

• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Definir:

• Badges de pipelines
• Estructura del proyecto
• Cómo utilizar el proyecto