No puedo resolver n = 8 log n. ¿Debería preocuparme como un ingeniero de software con experiencia de 8 años que aspira a trabajar con empresas líderes como Google, Apple, Facebook y Palantir? ¿Las personas en Google, Facebook, etc. saben todo esto? ¿Cómo puedo mejorar?

Aquí hay una derivación. Tenga en cuenta que el ejercicio no está claro sobre si es un registro natural o un registro basado en 2, pero podemos suponer que log2 porque es un algoritmo.

dejar K = 8 / log (2)
n = 8 log_2 (n) = 8 log (n) / log (2) = K log (n)
e ^ n = n ^ K
1 = e ^ (- n) n ^ K
1 ^ (- 1 / K) = e ^ (- n / K) n [elevar ambos lados para potenciar 1 / K]
1 = ne ^ (- n / K) n
-1 / K = -n / K e ^ (- n / K)

Ahora vamos a la función W (también conocido como ProductLog en Mathematica): W (z) e ^ W (z) = z. Tomando W () de ambos lados:

W (-1 / K) = -n / K
n = -KW (-1 / K)

Sin embargo, tenga en cuenta que la función W es desagradable, ya que tiene múltiples soluciones sobre algunos de sus dominios. (en este caso, refleja múltiples soluciones al problema subyacente; puede ver esto graficando n-8 * log2 (n) de 1.01 a 50, donde verá que cruza el eje X dos veces). Desafortunadamente, la respuesta que queremos No es la solución principal:

>> K = 8 / log (2);
>> -K * lambertw (-1 / K)
ans = 1.1000 <- respuesta inútil
>> -K * lambertw (-1, -1 / K)
ans = 43.5593 <- este es el correcto

Es muchísimo más fácil resolverlo numéricamente usando MATLAB u Octave:
>> fzero (@ (n) n – 8 * log (n) / log (2), [2, 100])
ans = 43.5593

Durante varios años al principio de mi carrera, uno de mis deberes fue entrevistar a programadores de primer nivel. Ritualmente lanzamos “acertijos” (por ejemplo, dilemas clásicos de ‘The Monty Hall Show’) a los candidatos como formas de sacarlos de su zona de confort y poner a prueba su pensamiento creativo.

Encontrar la “respuesta correcta” nunca fue el punto.

El objetivo era ver las formas en que alguien abordaba un problema poco ortodoxo. ¿Simplemente se rindieron? ¿Podrían hacer buenas preguntas? ¿Eran sistémicos en su enfoque? ¿Podrían al menos reducir el espacio de la solución? ¿Parecían (en realidad) “disfrutar de un desafío”?

Recuerda el contexto: es una entrevista. Se están evaluando muchas cualidades diferentes. Y (como en la vida) nadie sabe todas las respuestas.

Trabajo para Microsoft y no tengo idea de qué demonios fue esa ecuación (aunque un poco más de declaración). Bueno, hay algunos trabajos en Microsoft en los que tendrá que resolver eso y más para poder hacer su trabajo, pero no todos los trabajos son así. Soy un tipo que aprecia los programas de escritura y la integración de diferentes plataformas de Microsoft y en mis 13 años de trabajo, nunca me encontré con una situación que tuve que resolver una de esas ecuaciones. Y la ventaja, no me hicieron esa pregunta durante ninguna de mis rondas de entrevistas.

Por cierto, no soy un graduado. No puedo hablar de Google / Facebook, pero en Microsoft no es necesario tener un grado sofisticado y conocimientos matemáticos para ingresar. Sin embargo, cada trabajo tiene su propia necesidad. Si está apuntando a Microsoft Research, el título importa y si está apuntando a un trabajo en el equipo CLR o Core OS, esas ecuaciones lo perseguirán en las entrevistas. Espero que ayude.

No es muy importante conocer la función Lambert W.

Es muy importante (para algunos trabajos de todos modos) saber que cuando tiene una ecuación que no se puede resolver simbólicamente fácilmente, debe resolverla numéricamente; y conocer algunas técnicas para ello, como el método secante y el método Newton-Raphson (que son más rápidos que la búsqueda binaria que se mencionó en otra respuesta).

Bienvenido al club. Tampoco tenía idea de cómo resolverlo hasta que busqué la respuesta que mostrabas, y al mirarla, estoy bastante seguro de que la mayoría de los ingenieros de esas compañías nunca han oído hablar de la función Lambert W.

¡No! No necesita saber nada sobre la función Lambert W para obtener un buen trabajo de software. La mayoría de los ingenieros de Google, etc., nunca han oído hablar de él.

Aquí está el mismo tipo que tiene la misma preocupación que tú.

Nivel de Fb durante 8 años trabajo ex con maestros

Y la respuesta es..

“Depende de tu tipo de experiencia laboral y de cómo te entrevistes. Tu título no tiene nada que ver con eso. Viniendo de Riverbed Technologies, es posible que no tenga la experiencia exacta (no positiva), por lo que probablemente sea un 4, pero podría ser un 5. El nivel no es todo lo que parece ser. Llegué a un 4, me subí de nivel a un 5 en el primer ciclo y ahora estoy estresado. Todos en mi equipo que son 5+ están estresados; Preferiría ser un 4 y luego, una vez que tuviera más tiempo para saber cómo funcionan las cosas, sería promovido. – Del empleado de Facebook ”

Probablemente alguien en el comité de contratación debería responder a esto, sin embargo, lo más probable es que no esté buscando una respuesta exacta, sino que quiera probar el conocimiento general y las habilidades para resolver este o otros problemas similares. Al mismo tiempo, tenga en cuenta que nLog [n] o Log [n] / n aparece en muchas ocasiones en informática (matemáticas y física), debe conocer algunos detalles sobre ellos. Primero, mediante una pequeña manipulación, este problema se convierte en 1/8 = Log [n] / n. Ahora, uno debe saber que Log [n] / n no es una función monotónica ya que es cero en n = 1 y n-> [math] \ infty [/ math]. El máximo aparece de manera interesante en n = e (para cualquier valor base) que es aproximadamente 2.7. El valor de este máximo es de alrededor de 0.16 (para iniciar sesión en la base 10). Entonces, para cualquier valor mayor que 0.16 no hay solución y para cualquier valor menor que 0.16 hay dos soluciones. La primera solución se encuentra entre [0, e] y la segunda solución se encuentra entre [e, [matemáticas] \ infty [/ matemáticas]]. Para este caso particular de 1/8, con un poco de experimentación o aproximando Log [x] / x al segundo orden alrededor de 1, encontrará que una de las soluciones es alrededor de 1.6 y la otra es alrededor de 6.5.

Primero, antes de proporcionar la respuesta, es útil leer la pregunta:

“Supongamos que estamos comparando implementaciones de clasificación de inserción y clasificación de fusión en la misma máquina. Para entradas de tamaño n, la ordenación por inserción se ejecuta en 8n ^ 2 pasos, mientras que la ordenación por fusión se ejecuta en 64n lg n pasos. ¿Para qué valores de n la clasificación de inserción supera la combinación de clasificación?

Tres observaciones:

1. La pregunta es del primer capítulo del libro, por lo que debe ser simple.
2. Como estamos hablando de informática, el logaritmo es la base 2.
3. n es tamaño, por lo que debe ser un número natural.

Entonces, tenemos n = 8log (n). Para n = 32, tenemos 32 <40. Para n = 64, tenemos 64> 48. Entonces, la respuesta está entre 32 y 64. Ahora, puede ser aburrido y solo encontrar el número más cercano a la respuesta (recordando que n es un entero). Alternativamente, puede detenerse aquí y simplemente decir que el análisis del número de pasos, especialmente para la ordenación rápida, es aproximado de todos modos, por lo que no es necesario ser preciso. Porque si necesita ser preciso, ejecutará simulaciones de todos modos, pero ahora al menos sabrá por dónde comenzar.

Considero que por log te refieres a log in base 10.
La solución aproximada será 6.50711 (correcta a 3 decimales, al menos).
Entonces para comenzar con la solución.
Podemos tener n> 0 ya que log (n) solo se define para n> 0.
aquí nuestra función F (n) = (8 * log (n)) / n
Entonces ponga n = 1,2,, 3..10 y marque (8 * log (n)) / n y vea si está cerca de 1 o no.
se obtiene la siguiente tabla. Todos los cálculos se realizan con aproximación (correcto a 3 decimales)

tenemos que acercarnos lo más posible a 1, por lo que la solución debe estar entre 6 y 7.
n f (n)
Al verlo, puede encontrar que la solución se encuentra entre 6.5 y 6.6.

entonces el valor está entre 6.5 y 6.51

entonces el valor está entre 6.507 y 6.508

ahora alcanzamos el valor de 6.5071
de manera similar alcanzaremos el valor de 6.50711 si tomamos más precisión