Experiencia de entrevista de Moonfrog Labs | conjunto 3

Q1. Dada una secuencia de números enteros, encuentre la subsecuencia creciente más larga. Ejemplo:
arr = [1, 2, 5, 3, 7]
y : [1, 2, 5, 7] o [1, 2, 3, 7]

arr = [4, 3, 1, 2]
respuesta: [1, 2].

Solución:

import java.util.Arrays;
  
/** @author hiccup  */
class LIS
{
    static int[] maxLIS;
    static int[] result;
  
    public static void getLCS(int[] arr)
    {
        if (null == arr || 0 == arr.length)
            return;
  
        maxLIS = new int[arr.length];
        /* At least LCS is 1 i.e. element is the
                   only one in given sequence */
        Arrays.fill(maxLIS, 1);
  
  
        /**
         *
         */
        for (int curIdx = 1; curIdx < arr.length; curIdx++)
        {
            for (int beginIdx = 0; beginIdx <= curIdx - 1; beginIdx++)
            {
                if (arr[curIdx] > arr[beginIdx])
                {
                    if (maxLIS[curIdx] < maxLIS[beginIdx] + 1)
                    {
                        //System.out.print(arr[curIdx] + "  ");
                        maxLIS[curIdx] = maxLIS[beginIdx] + 1;
                    }
                }
            }
        }
  
        int max = maxLIS[0];
        result = new int[arr.length];
        Arrays.fill(result, -1);
  
        int cpIdx = 0;
        for (int idx = 0; idx < maxLIS.length; idx++)
        {
            /* Put sequence at cpIdx   */
            if (-1 == result[maxLIS[idx] - 1])
            {
                result[cpIdx++] = arr[idx];
            }
        }
  
        /*  Print sequence       */
        for (int idx = 0; idx < result.length; idx++)
        {
            System.out.print(result[idx] + " ");
        }
    }
  
    public static void main(String[] args)
    {
        int[] arr = {1, 2, 5, 3, 7};
        LIS.getLCS(arr);
    }
}

[1, 2, 3, 3, 4]

——————————————————————————————————————————————–
P2. Dados unos vectores de números de longitud fija, por ejemplo:

v1 = [4, 3, 1, 2] v2 = [2, 4, 3, 5]

La relación anidada entre dos vectores se define de la siguiente manera:

si las entradas correspondientes de un vector son todas más pequeñas que el otro vector, después de reorganizar las entradas del vector si es necesario,
se dice que el primer vector está anidado en el otro. Ejemplo

No anidado
v1 – [4, 3, 1, 2] v2 – [2, 4, 3, 5]
v2 – [2, 4, 3, 5] v1 – [4, 3, 1, 2]

Después de reorganizar:

Anidado
v1 – [4, 3, 1, 2]
v2 – [5, 4, 2, 3]

Por lo tanto, v1 está anidado en v2.

Dado un par de tales vectores, escriba una función de la siguiente manera:

la función está anidada (Vec a, Vec b);

Resultado:
-1 si a está anidado en b
1 si b está anidado en a
0 si no es posible anidar.

—————————————————————————————————————————-

Q3. Dada una lista de números en orden aleatorio. ¿Es posible emparejar todos los elementos de la lista de tal manera que no haya dos pares que compartan un elemento
y la suma de los elementos de un par sea divisible por 101? Ejemplo:

v1 [ 1, 100, 1]
Respuesta: No

v2 [1, 100, 100, 1] [2, 98, 101, 1]
Respuesta: Sí

v3 [1, 200, 100, 100, 2, 1]
Respuesta: sí

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.