Hace unas semanas tuve una entrevista de trabajo para una posición como desarrollador Python en la empresa x, esta empresa necesitaba alguien que supiera de algoritmos, optimizacion y un conocimiento aceptable de Python. La segunda entrevista fue técnica sobre Python en la cual falle por que no esperaba tales preguntas, llevo aproximadamente unos 3 años usando Python para proyectos pequeños pero nunca lo aprendí formalmente, simplemente lo empece a usar como cualquier otro lenguaje y aprendí lo que iba necesitando. La primera pregunta fue sobre los objetos mutables e inmutables en Python. En Python TODO es un objeto, pero unos son mutables y otros no, la diferencia entre uno y el otro es simplemente que uno puede ser alterado (mutable) y el otro[…]

Problema: You are given N counters, initially set to 0, and you have two possible operations on them: increase(X) − counter X is increased by 1, max counter − all counters are set to the maximum value of any counter. A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations: if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X), if A[K] = N + 1 then operation K is max counter. For example, given integer N = 5 and array A such that: A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4the values of the counters[…]

Problema: Write a function: def solution(A) that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer (greater than 0) that does not occur in A. For example, given: A[0] = 1 A[1] = 3 A[2] = 6 A[3] = 4 A[4] = 1 A[5] = 2 the function should return 5. Assume that: N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−2,147,483,648..2,147,483,647]. Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified. Solución: El problema nos dice que dado un array de N[…]

Hace poco empece a resolver los problemas de codility y al final de cada explicación del problema te ponen algo como esto: Complexity: expected worst-case time complexity is O(1); Ya había escuchado y leído un poco sobre Big O y entendía un poco a que se referían con O(n) pero nunca se me hizo útil ni tampoco le tome importancia. Hasta que me tope con varios problemas de codility que pedían O(1) y en mi resultado daba algo como “10% performance, O(n) detectado”, ahí fue cuando dije ah ok quieren O(1) y lo hice O(n) y ahora que hago? Antes que nada aclarar que esta no es una publicación donde veremos a fondo la definición teórica y matemática, es simplemente para[…]

Problema: A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river. You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds. The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X. You may assume that the speed of the current in the river[…]

Problema: A non-empty zero-indexed array A consisting of N integers is given. A permutation is a sequence containing each element from 1 to N once, and only once. For example, array A such that: A[0] = 4 A[1] = 1 A[2] = 3 A[3] = 2 is a permutation, but array A such that: A[0] = 4 A[1] = 1 A[2] = 3 is not a permutation, because value 2 is missing. The goal is to check whether array A is a permutation. Write a function: int solution(int A[], int N); that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not. For example, given array A such that: A[0] =[…]

Problema: A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape. Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], …, A[P − 1] and A[P], A[P + 1], …, A[N − 1]. The difference between the two parts is the value of: |(A[0] + A[1] + … + A[P − 1]) − (A[P] + A[P + 1] + … + A[N − 1])| In other words, it is the absolute difference between the sum of the first part and the sum of the second part. For example, consider array A such that: A[0] = 3 A[1] = 1 A[2] = 2[…]

Problema: A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing. Your goal is to find that missing element. Write a function: def solution(A) that, given a zero-indexed array A, returns the value of the missing element. For example, given array A such that: A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5 the function should return 4, as it is the missing element. Assume that: N is an integer within the range [0..100,000]; the elements of A are all distinct; each element of array A is an integer within the range [1..(N + 1)]. Complexity: expected worst-case[…]

Problema: A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D. Count the minimal number of jumps that the small frog must perform to reach its target. Write a function: def solution(X, Y, D) that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y. For example, given: X = 10 Y = 85 D = 30 the function should return 3, because the frog will be positioned as follows: after the[…]

En este problema usaremos uno de los operadores bitwise disponibles en Python (<<, >>, &, |, ~, ^). Que es un operador bitwise? Es simplemente un operador lógico que funciona nivel de bits, bit a bit. Cual vamos a usar? XOR Para darles un ejemplo claro de como funciona XOR, miremos primero su tabla de verdad: ———– A B Output ———– 0 0 0 0 1 1 1 0 1 1 1 0 Es 0 si el par de bits es igual y 1 si el par de bits es diferente. Entonces por ejemplo: 9 ^ 3 ^ 9 = 3 Pasemos los 3 valores a binario: 9 = 1001 3 = 0011 9 = 1001 Primero tomamos 9 y 3[…]