Cómo prepararse rápidamente para una entrevista de trabajo con preguntas sobre algoritmos y tecnologías

¡Saludos a todos los lectores de Habr! Mi nombre es Yuriy, he enseñado altas tecnologías, Oracle, Microsoft y otros durante más de 20 años, además de crear, desarrollar y dar soporte a sistemas de información cargados para varios clientes comerciales. Hoy me gustaría contarles sobre la dirección actual: entrevistas sobre tecnologías de procesamiento de datos. La variante rusa de esta publicación la puedes encontrar aquí .

Realmente no tiene sentido que un empleador le pregunte al solicitante sobre las tecnologías de programación tradicionales. Es por eso que le diré cómo prepararse para una entrevista en un área estrecha relacionada con los lenguajes de procesamiento de información, a saber, el procesamiento de enteros largos (aritmética larga) y la identificación de propiedades de información de objetos del mundo real, que se describen en enteros largos.

1. Las entrevistas de tecnología de procesamiento de datos se realizan normalmente para contratar equipos de analistas y desarrolladores que previamente hayan tenido experiencia en desarrollo en lenguajes declarativos, imperativos, orientados a objetos y funcionales.

Tarea Determine el lenguaje de programación mediante el siguiente fragmento de programa.



Primero debe responder la pregunta: ¿qué características en el idioma elegido pueden ser relevantes y atraerán al empleador potencial? Dependiendo de esto, la lista puede variar de una versión a otra, de una biblioteca a otra, de una implementación a otra.



Tarea ¿Qué idiomas admiten aritmética con enteros largos?

Listo para responder? Aquí hay una lista sugerida:
  • C, C ++ - biblioteca libgmp
  • Lisp común: no limita el ancho de bits de los enteros
  • Tipo numérico incorporado en Erlang (entero ())
  • Tipos de entrada y rata de la gran biblioteca.
  • Tipo entero incorporado Haskell
  • Java-java class.math.BigInteger (febrero de 1997)
  • Biblioteca OCaml-num
  • Pascal - Biblioteca Delphi-MPArith
  • Módulos Perl bignum y bigrat
  • Módulo PHP BCMath
  • Python es un tipo largo incorporado (desde que se creó el lenguaje, febrero de 1991)
  • Ruby - tipo Bignum
  • Clase Scala-BigInt
  • Esquema con R6RS
  • Lenguajes .NET: clase de sistema. Numéricos. BigInteger (introducido en .NET Framework 4.0, hace casi 10 años)


2. Si el empleador ya tiene una lista preparada, es necesario seleccionar partes generales de los idiomas que se discutirán en la entrevista.

Tarea ¿Cuáles son, en su opinión, los idiomas más populares desde el punto de vista del empleador? Aquí puede ver la respuesta basada en estadísticas.

Muchas de estas operaciones de rutina a menudo se realizan en sistemas de información grandes y ultragrandes. Existen diferentes tipos de clasificación, búsqueda de ciertos criterios, algoritmos en gráficos, problemas de optimización en conjuntos de diferente naturaleza, tareas de diseño de objetos con propiedades inciertas. Pero debido a la escala de estas tareas, la clasificación más fácil puede llevar un mes, la búsqueda puede llevar una semana. Vea la tarea a continuación para una mejor comprensión.

Tarea Imagina que hay un abedul afuera de tu oficina. Según lo calculado por sus colegas, tiene 100,000 hojas y el diámetro del tronco en su raíz es de 60 centímetros. Escriba estos parámetros en cualquier notación matemática. Demuestre su idoneidad: a) para la comunicación escrita con un colega en caso de que el árbol se vaya a cortar, b) para realizar el procesamiento informático de su imagen.



3. Algunas palabras sobre la parte matemática de la entrevista. En la vida real, rara vez vamos más allá de los límites de la aritmética ordinaria. Algunos de nosotros usamos los logros de álgebra y análisis. Así que decidí agregar algunos problemas de la vida real para poner sus cabezas en marcha.

Tarea ¿Por qué los números de teléfono tenían cinco o seis dígitos durante tanto tiempo? Hay una lista de números, ¿cuáles de ellos no son cuadrados completos? ¿Cuántos autobuses en su ciudad tienen un número que consiste solo en cuadrados completos? ¿Cuántos primos hasta 100 sabes? ¿Cuál es su porcentaje entre la fila de números del 1 al 100? Sea 2, 3, 5, 7 números primos, de acuerdo con este hecho, encuentre la cantidad de números primos hasta 100. ¿Cuántas operaciones aritméticas tendrá que hacer? Resuelva el mismo problema en MS Excel de dos maneras como una autocomprobación.

Tarea ¿Cómo se usan la convexidad y la concavidad en la práctica? Dé 2-3 ejemplos de uso de convexidad-concavidad.



4. A veces es necesario revisar la documentación del sistema / idioma / conjunto de bibliotecas, ejemplos de descripciones técnicas detalladas y detalladas del autor / fabricante. Esto es especialmente necesario si tiene la intención de llamar a bibliotecas no estándar.

Tarea Escriba el algoritmo Euclid extendido en uno de los lenguajes de programación mencionados anteriormente en el paso 1. ¿En qué idioma no es necesario hacerlo? Por qué

5. Sería bueno entender la dirección de la entrevista: si se espera que escriba algoritmos por su cuenta o si tiene que mantener un conjunto de algoritmos de terceros, ¿probablemente tendrá que introducir un orden adecuado más adelante?

Tarea Hay notas hechas por un director médico en el cuaderno de su aprendiz. Es necesario informatizar estas notas para hacer citas correctas con los pacientes. ¿Qué le aconsejarías al interno?



6. Si la elección del idioma de la entrevista está implícita, es mejor seleccionar uno más estandarizado, para que el entrevistador no tenga muchas posibilidades de cambiar las condiciones de las tareas durante la conversación.

Tarea ¿Cuántas versiones de Pascal se han creado durante los últimos 25 años? Especifique las fortalezas y debilidades de cada versión.



7. Sería bueno asistir al menos a un seminario sobre algoritmos y su implementación en el producto de información elegido en un área temática determinada.

Tarea El poeta le preguntó si le es posible escribir un poema "Eugene Onegin" teniendo en cuenta el tesauro de su autor. Da dos soluciones a este problema.

8. En el sitio para programadores hay tareas para capacitar la capacidad de procesar información científica y programar algoritmos complejos. A continuación damos una solución "de frente", pero no es óptima. Es solo una formulación de la condición desde el punto de vista del lenguaje de programación de alto nivel.
Por favor, preste atención al hecho de que a pesar del esfuerzo de todos los autores para formular los problemas, todavía pueden existir algunos errores. Por lo tanto, es posible discutir los problemas ocurridos.

Tarea 489 del Proyecto Euler


Dejar G(a,b) ser el número entero no negativo más pequeño n para que MCD(n3+b,(n+a)3+b) Está maximizado.
Por ejemplo, G(1,1)=5 porque MCD(n3+1,(n+1)3+1) alcanza su valor máximo de 7 para n=5 y es más pequeño para 0≤n<5 .
Dejar H(m,n)=ΣG(a,b) para 1≤a≤m , 1≤b≤n .
Te dan H(5,5)=128878 y H(10,10)=32936544 .

Encontrar H(18,1900) .

Tarea Afortunadamente, este es un problema muy poco resuelto en el Proyecto Euler. Basado en el texto del programa, encuentre las fortalezas y debilidades del algoritmo y especifíquelas. ¿Este programa podrá resolver este problema durante un día de trabajo? ¿Cómo se puede acelerar? Especifique errores en la tarea, si los hay. Encuentre el parámetro " verylargenumber ". ¿Por qué está limitado?

Unas palabras más si no pudieras resolverlo
Si estuviéramos hablando de máximos locales, las respuestas deberían ser menores, pero después de los cálculos, de repente resulta que estamos hablando de máximos globales, que no se mencionan en el texto del problema. Y sin embargo, existe la sospecha de que el MCD(n3+1444,(n+1)3+1444)=1 bajo cualquier n . Que va a n adaptarse a los autores del problema?

Código para la solución de muestra
public class Start { static BigInteger[] GcdExtended(BigInteger a, BigInteger b) { BigInteger res[] = new BigInteger[3]; if (b == BigInteger.valueOf(0)) { res[0] = a; res[1] = BigInteger.valueOf(1); res[2] = BigInteger.valueOf(0); return res; } res = GcdExtended(b,a.divideAndRemainder(b)[1]); BigInteger s = res[2]; res[2] = res[1].subtract((a.divideAndRemainder(b)[0]).multiply(res[2])); res[1] = s; return res; } public static void main(String[]args) throws IOException { BigInteger i; BigInteger j; int n,n1; BigInteger temp; BigInteger temp1; BigInteger count; FileWriter fileWriter = new FileWriter("c:/temp/terribleanswer.txt"); n1=1; count=BigInteger.ZERO; i=BigInteger.ZERO; j=BigInteger.ZERO; temp1=BigInteger.ZERO; temp=BigInteger.ZERO; for (int a=1;a<19;a++) { for (int b=1;b<1901;b++) { for(n=1;n<;n++) { j=((BigInteger.valueOf(n)).pow(3)); j=j.add(BigInteger.valueOf(b)); i=(((BigInteger.valueOf(n)).add(BigInteger.valueOf(a))).pow(3)); i=i.add(BigInteger.valueOf(b)); int comparevalue = j.compareTo(i); if (comparevalue==0) { temp=GcdExtended(i,j); } else if (comparevalue == 1) { temp=GcdExtended(j,i); } else { temp=GcdExtended(i,j); } int compareTemp = temp.compareTo(temp1); if (compareTemp == 1) { temp1=temp; n1=n; continue; } } String fileContent = a + ";" + b +";"+ temp1 +";"+ n1 + "\n"; temp1=BigInteger.ZERO; count=count.add(BigInteger.valueOf(n1)); n1=1; try { fileWriter.append(fileContent); } catch (IOException e) { } } } String fileContent = count + "\n"; try { fileWriter.append(fileContent); } catch (IOException e) { } fileWriter.close(); } } 


9. ¡Deseo que pases la entrevista en el up-and-up!

UPD Especialmente para la publicación de la versión en inglés del artículo, damos algunas relaciones no triviales encontradas después de una profunda modernización de la solución anterior. Al calcular a n=$500,000,00 .
MCD(n3+1444,(n+1)3+1444)=56298673,n=28147170 ; MCD(n3+1445,(n+1)3+1445)=14094169,n=14092001 ; MCD(n3+1446,(n+1)3+1446)=56454733,n=28225197 ; MCD(n3+1447,(n+1)3+1447)=14133211,n=14131040 .

Source: https://habr.com/ru/post/445002/


All Articles