Pasante de ingeniería de software de Google, otoño de 2019: América del Norte

1. Considere un árbol binario de N vértices tal que los hijos del Node k sean 2*ky 2*k+1. El vértice 1 es la raíz del árbol y cada Node tiene un valor entero asociado.

Tal árbol puede representarse como una array de N enteros escribiendo valores de Nodes consecutivos.

El árbol se puede representar como una array [-1, 7, 0, 7, -8].
Se dice que un Node está en el nivel x si la longitud del camino más corto entre ese Node y la raíz x-1. Entonces, la raíz está en el nivel 1, los hijos de la raíz están en el nivel 2, y así sucesivamente.

Su tarea es encontrar el número de nivel más pequeño x tal que la suma de todos los Nodes en el nivel x sea máxima.
Ejemplos: Dada la array A tal que: A[0]=-1, A[1]=7, A[2]=0, A[3]=7, A[4]=-8. La función debe devolver 2.

Input : [-1, 7, 0, 7, -8] 
Output : 2

#include <iostream>
using namespace std;
int solution(int a[], int n)
{
    int max = -1;
    int temp = 0;
    for (int i = 0; i < n; i = i + 2) {
        if (i == 0)
            temp = a[i];
        else
            temp = a[i] + a[i - 1];
        if (temp > max)
            max = i;
    }
    return max;
}
  
int main()
{
    int a[4];
    a[0] = -1, a[1] = 7, a[2] = 0, a[3] = 7, a[4] = -8;
    int size = 4;
    cout << solution(a, size);
}

2. Imagina que tienes un teclado especial con todas las teclas en una sola fila. La disposición de los caracteres en un teclado se indica mediante una string S1 de longitud 26. S1 está indexado de 0 a 25. Inicialmente, su dedo está en el índice 0. Para escribir un carácter, debe mover su dedo al índice del carácter deseado. El tiempo necesario para mover el dedo del índice i al índice j es |ji|, donde || denota valor absoluto.

Escriba una función solution(), que, dada una string S1 que describa la distribución del teclado y una string S2, devuelva un número entero que indique el tiempo necesario para escribir la string S2.

Ejemplos:

S1 = abcdefghijklmnopqrstuvwxyz

S2 = cba

Input : S1 = abcdefghijklmnopqrstuvwxyz, S2 = cba 
Output : 4

#include <bits/stdc++.h>
using namespace std;
  
int solution(string& s1, string& s2)
{
    map<char, int> dict;
    for (int i = 0; i < 26; i++) {
        dict[s1[i]] = i;
    }
    int ans = 0;
    int prev = 0;
    for (int i = 0; i < s2.length(); i++) {
        ans = ans + abs(dict[s2[i]] - prev);
        prev = dict[s2[i]];
    }
    return ans;
}
  
int main()
{
    string s1 = "abcdefghijklmnopqrstuvwxyz";
    string s2 = "cba";
    cout << solution(s1, s2);
}