Рубрики

Moonfrog Labs Интервью Опыт | Набор 3

Q1. Учитывая последовательность целых чисел, найдите самую длинную возрастающую подпоследовательность. Пример:
обр = [1, 2, 5, 3, 7]
ans: [1, 2, 5, 7] или [1, 2, 3, 7]

обр = [4, 3, 1, 2]
ans: [1, 2].

Решение:

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];

        / * По крайней мере, LCS равен 1, т.е. элемент является

                   только один в данной последовательности * /

        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++)

        {

            / * Поместить последовательность в cpIdx * /

            if (-1 == result[maxLIS[idx] - 1])

            {

                result[cpIdx++] = arr[idx];

            }

        }

  

        / * Последовательность печати * /

        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]

———————————————-
Q2. Даны векторы чисел фиксированной длины, например:

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

Взаимосвязь между двумя векторами определяется следующим образом:

если соответствующие элементы вектора все меньше, чем другой вектор, после перестановки элементов вектора, если необходимо, тогда первый вектор
Говорят, вложенный в другой. пример

Не вложенный
v1 — [4, 3, 1, 2] v2 — [2, 4, 3, 5]
v2 — [2, 4, 3, 5] v1 — [4, 3, 1, 2]

После перестановки:

Уплотненный
v1 — [4, 3, 1, 2]
v2 — [5, 4, 2, 3]

Следовательно, v1 вложено в v2.

Учитывая пару таких векторов, напишите функцию следующим образом:

функция isNested (Vec a, Vec b);

Результат:
-1 если a вложено в b
1, если b вложено в
0, если вложение невозможно.

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

Q3. Дан список номеров в случайном порядке. Можно ли связать все элементы в списке таким образом, чтобы ни одна пара не имела общий элемент?
и сумма элементов в паре делится на 101. Пример:

v1 [1, 100, 1]
Ответ: нет

v2 [1, 100, 100, 1] [2, 98, 101, 1]
Ответ: да

v3 [1, 200, 100, 100, 2, 1]
Ответ: да

Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Напишите свой опыт интервью или отправьте его по электронной почте на адрес contrib@geeksforgeeks.org

Рекомендуемые посты:

Moonfrog Labs Интервью Опыт | Набор 3

0.00 (0%) 0 votes