Создание стека по заданному массиву и стеку c#

Недавно я был на собеседовании, и мне задали следующий вопрос:

Given an array A with N integers (different numbers between 1 and N) and a stack B with N integers (different numbers between 1 and N).

The value of the item in array A contains the index in which the item is located on stack B (from the top) and the index number of array A describes the position (from the top) of stack C in which this item should appear.

Write an Algorithm that runs in O(N^2) and without any further Space complexity (Besides one simple variable) that takes A and B as arguments and returns a stack C that contains N items in the order that has been described.

Notice: At the end of the Algorithm, array A and stack B should be in the same form as they were when the Algorithm started.

For example, given an array A that contains the following integers:

|     index in the array    | 1 | 2 | 3 | 4 |
|:-------------------------:|---|---|---|---|
| final location in stack C | 2 | 4 | 1 | 3 |

and Stack B that looks like this (But it doesn't have to look like this):

  • 2
  • 3
  • 4
  • 1

We will return the following Stack C:

  • 3
  • 1
  • 2
  • 4

An example: in array A we are given that the item in the first index should appear on stack B at location 2 (the value 3). We will put this value in the first location (The top) of stack C.

Это мой код на C#, который делает это (хотя у него есть несколько проблем)

    private static Stack generateStackFromArrayAndStack(int[] A, Stack B)
    {
        int N = A.Length;
        Stack C = new Stack();

        // Iterate over the given array. Notice that we start from the end because that is the value we want to push first to the C Stack.
        for (int i = N - 1; i >= 0; i--)
        {
            int value = 0;
            int j;

            // Look for the desired value. When we get to it, stop this iteration. We use the Stack C as a container for now
            for (j = 1; j <= N; j++)
            {
                value = (int)B.Pop();
                C.Push(value);
                if (j == A[i])
                    break;
            }

            // Return all the items we moved to C in the previous iteration back to B.  
            for (int k = j; k > 0; k--)
                B.Push(C.Pop());

            // Push the value we want to C.
            C.Push(value);
        }
        return C;
    }

Мои проблемы с этим кодом:

  1. Я использую более одной простой переменной.
  2. Во время выполнения алгоритма стек C будет содержать более N элементов. Я не уверен, разрешено это или нет. Если вы можете найти реализацию, которая не вызывает этого, было бы здорово.

Конечно, если у вас есть совершенно другая реализация, это тоже может быть полезно.

Вы бы лучше справились с codereview

BugFinder 11.04.2018 11:58

Разве codereview не для экспертных обзоров? Это законный вопрос

RonH 11.04.2018 13:13
2
2
63
1

Ответы 1

Не знаю, если это O (N ^ 2), но это работает ...

private static Stack<int> DoMagic(int[] a, Stack<int> b)
{
    var c = new Stack<int>();
    foreach (int val in a)
        c.Push(b.ElementAt(val-1));
    return c;
}

У меня почему-то нет доступа к методу elementAt. Есть идеи, почему?

RonH 11.04.2018 13:53

Не используете универсальную версию Stack? (Стек <int>)

Jeppe Alkærsig 11.04.2018 14:02

Другие вопросы по теме