Entrevista con Bloomberg | Grupo 2 (videoconferencia)

Haga clic aquí para ver la documentación de la primera entrevista telefónica.

La videoconferencia se dio luego de pasar la entrevista telefónica, se realizó por Skype con 2 entrevistadores de Bloomberg: Freddy y Chad.

La llamada comenzó cuando ambos se presentaron, y yo también, y nuevamente se me pidió que dijera lo que sé sobre Bloomberg y por qué quiero trabajar allí.

Luego, los entrevistadores saltaron a la primera pregunta, era directa, para el siguiente código, responda las 9 preguntas dadas.

#include <string.h>
int main(int argc, char *argv[])
{
    char    abc[27];
    char    *ptr = abc;
    strcpy(abc, "abcdefgxyz");
     /*
     * What are the types and values of expressions:
     *
   
     * 1. abc
     * 2. *abc
     * 3. abc[2]
     * 4. &abc[3] //&abc[3] = abc + 3*sizeof(char)
     * 5. abc+4
     * 6. *(abc+5) + 20000  //h  long long x = int * 1LL * int
     * 7. abc[10] //'\0'
     * 8. abc[12] //memset ()
     * 9. &ptr //char**
     */
     return 0;
}

La segunda pregunta fue la siguiente:

El código que se muestra está diseñado para imprimir la fecha actual, pero por alguna razón no lo hace.
Usted está obligado a averiguar la razón.

#include <stdio.h>
#include <string.h>
#include <time.h>
   
char *get_date()
{
    char    buf[80];
    time_t  now = time(0);
    strcpy(buf, ctime(&now));
    return buf;
}
  
int main(int argc, char *argv[])
{
    char *date = get_date();
    printf("date=%s\n", date);
    return 0;
}

Al principio, el código me parecía bien, lo único que pensé que sería el problema, es la declaración de la array de caracteres buf en la pila en lugar del montón.
Entonces, sugerí que la asignación dinámica debería resolver el problema y que deberíamos usar malloc(80*sizeof(char)) en lugar de buf[80].
Los entrevistadores dijeron que era el paso correcto, pero aún necesita una razón.
Los entrevistadores dieron una pista de que, en caso de que se estableciera un punto de interrupción justo antes de printf if, el depurador muestra que la fecha contiene el resultado correcto, por lo que el problema está en printf.
Después de que tuve suficiente tiempo, el entrevistador decidió darme la respuesta para continuar.
El problema era que cuando se llama a printf, necesita una parte de la pila, y esto puede afectar la array de caracteres reservada por la pila buf.

La siguiente pregunta fue la siguiente:
dado un número entero n, devuelva el número de formas en que se puede representar como una suma de 1 y 2, el orden es importante.

Sugerí que usáramos una función recursiva para calcularlo.
Y luego sugirió usar algún tipo de memorización.
El código era el siguiente:

////////////////// 
//
// number of ways 
// n = 3
// 3 = 1,2
// 1,1,1,
// 2,1
  
int memo[1000000]; // memset (memo, -1, sizeof(memo));
int ways_of_sum_up(int n)
{
    if (n == 0)
        return 1;
    if (n < 0)
        return 0;
    if (memo[n] != -1)
        return memo[n];
    int ans = ways_of_sum_up (n-1) + ways_of_sum_up (n-2);
    return memo[n] = ans;
}

Luego me di cuenta de que el problema forma una recurrencia lineal, donde f(n) = f(n-1) + f(n-2), por lo que puede resolverse usando la exponenciación matricial.
Dediqué alrededor de 15 minutos a explicar la solución a los entrevistadores y no parecieron entender ni una palabra.

f(0) = 1
f(1) = 1

f(n) = f(n-1) + f(n-2)

[1 1][f(n)]         [f(n)+f(n-1)]
[1 0][f(n-1)]     [f(n)]

[1 1]^m
[1 0]

x^y  =  x^(y/2) * x^(y/2) = x^(y/4) * x^(y/4) * x^(y/4) * x^(y/4) 
     = ...... = x^1 ............ x^1

x^5 = x^2 * x^2 * x

[1 1]^2     [1 1]^1     x*x
[1 0]       [1 0] 

La complejidad del tiempo de ejecución de la solución es O(log(n)), igual que la complejidad de la memoria.

Había otra solución que no tuve tiempo de decir, que tiene una complejidad de tiempo de O(n) y una complejidad de memoria de O(1), que modela este problema al problema de Fibonacci.

La última pregunta fue tan trivial, me pidieron que invirtiera una string en su lugar, usé los 2 punteros, aquí estaba el código:

//////////
// "hello world" -> "dlrow olleh"
  
void reverse_word( char* str, int size )
{
    int p1, p2;
    p1 = 0;
    p2 = size-1;
      
    while (p1 < p2){
        char tmp = str[p1];
        str[p1] = str[p2];
        str[p2] = tmp;
        p1++;
        p2--;
    }
      
}

Finalmente, me pidieron que usara este código para invertir palabras dentro de una oración, en su lugar, aquí estaba el código:

// "hello world" -> "world hello"
//    "hello world" -> "dlrow olleh"
// "hello there everyone" -> "everyone there hello"
  
// "hello" -> ?
  
void reverse_sentence( char* str, int size )
{
    int p1;
    p1 = 0;
      
    //"hello world"
    reverse_word (str, size); //linear
    //"dlrow olleh"
  
    //"world olleh"
    //"world hello"
  
    for (int i=0;i<size;i++){
        p1 = i;
        while (p1 < size && str[p1] != ' ')
            p1++;
        reverse_word (str + i*sizeof(char), p1-i);
        i = p1;
    }
}

Resultado: Rechazado.

Resumen: Los entrevistadores no son tan buenos resolviendo problemas, son buenos implementadores, así que escriba un código limpio y ordenado, use las ideas obvias, no haga soluciones complicadas, porque lo más probable es que no lo entiendan.
Si cometí un error en esta entrevista, diría que estaba usando la exponenciación matricial en lugar de la solución de memoria constante de tiempo lineal más fácil.
Buena suerte con eso, pasar esta videoconferencia significa que irá a Londres para una entrevista final en el lugar, por lo que tiene otra razón para hacer lo mejor que pueda.

Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.