Folding an array into one element

Question

This is an interview question, not a homework assignment.

For an array from 1 to 2 ^ N. For example: 1 2 3 4 5 6 7 8 (2 ^ 3). Let this array be written on paper, we need to fold it in half, so that the left half will be mirrored, and then move under the right half, like this

1 2 3 4 5 6 7 8 left | right half | half 

becomes

 5 6 7 8 4 3 2 1 

And the next fold we take the right half instead, reflecting it and moving it below the left half,

  5 6 4 3 8 7 1 2 

The paper needs to be bent, changing direction (left-right) every time, until we have all the elements in one column, such as

  6 3 7 2 5 4 8 1 

My solution, First step: Create a linked list for the second half of the original array and flip the first half and connect it with the chapter pointers,

 5 6 7 8 | | | | 4 3 2 1 

And store the main pointers of the linked list in an array called headarray

Iteratively:

collapse the head array, for each fold the first halves and the second half of the headers will be connected. Remove the main pointers from the headarray after connecting it.

Continue until there is a pointer to one pointer in the main array.

But the interviewer asked me to solve it on the stack. Can someone help in solving this problem on the stack, and also indicate if I made any mistakes in my solution. Thanks in advance.

Answer 1

This problem can be solved using the stack and the original array. I will not code the solution for you, but I will indicate how to solve it.

• push the elements of the array onto the stack, following the rules that we discuss below.
• right after that, return the stack back to the array, starting at index 0
• repeated until the final condition is met.

Rule for filling the stack:

• first consider your array as one "segment"
• divide the segment in half; in the first half you will iterate in the reverse order (right-> left), the second in the natural order (left-> right)

• You start pushing the stack from the end of the array:

  • If the iteration is odd, first click the odd half (s),

  • if the iteration starts with an even half (s) first

• repeat and continue half the segments until they contain only one element; this is your stopping condition.

This is a bit abstract, so consider your example:

iter = 1 ->1234 <-5678 Arrows indicate the direction of iteration

start from the end and fill the stack; inter odd so start with the first odd half occurring

 5 6 7 8 4 <-notice that the order of pushing the halfs on the stack is shown by the arrows 3 2 1 

put the stop back: 5 6 7 8 4 3 2 1

Keep halving:

iter = 2 <-56 ->78 <-43 ->21 ; odd halves 56 , 43 ; even half 78 , 21

start from the end and fill the stack; inter even starts with the first even halves

 5 6 4 3 8 <-even halfs end, odd halfs start 7 1 2 

Put the stack back: 5 6 4 3 8 7 1 2

Separate the segments again, since in each new half of the arrow only one element will be used to highlight the rule:

iter = 3 ->5 <-6 ->4 <-3 ->8 <-7 ->1 <-2

iter is odd, so fill the stack with odd halves first

  6 3 7 2 5 4 8 1 

Put the stack back and you 63725481 done: 63725481

Hope this makes sense; happy coding :)

Answer 2

I found a law, an element in an array with an index (2*n-1, 2*n) , n is odd, always an array in front of the other elements, regardless of the direction of your addition. For example, an array of 12345678 , elements 2367 always in front of 1458 . Now I used dichotomy to get two arrays. Then you can find the law in two arrays. Hope this helps you.

Answer 3

Perhaps your interviewer was expecting something like:

 private int[] Fold(int pow) { if (pow < 0) throw new Exception("illegal input"); int n = 1; for (int factor = 1; factor <= pow; factor++) n *= 2; Stack<int> storage = new Stack<int>(n); this.Add(n, 1, storage); int[] result = new int[n]; for (int k = 0; k < n; k++) result[k] = storage.Pop(); return result; } private void Add(int n, int value, Stack<int> storage) { storage.Push(value); int m = n; while (true) { int mirror = m + 1 - value; if (mirror <= value) break; this.Add(n, mirror, storage); m /= 2; } } 

{demonstrating what you know about stacks and recursion ;-)}

Answer 4

Here the recursive solution turned out to be iterative; therefore, the stack, although probably not as intended. The function returns the initial position of the element based on the given position. It seems to be O(1/2n(log n + 1)) and O(log n) space.

JavaScript Code:

 function f(n,y,x,l){ var stack = [[n,y,x,l]]; while (stack[0]){ var temp = stack.pop(); var n = temp[0], y = temp[1], x = temp[2], l = temp[3]; var m = 1 << l; if (m == 1) return x; if (l % 2 == 0){ if (y > m / 2) stack.push([n * 2,y - m / 2,n + n - x + 1,l - 1]); else stack.push([n * 2,y,x,l - 1]); } else if (y > m / 2){ stack.push([n * 2,y - m / 2,n - x + 1,l - 1]); } else stack.push([n * 2,y,x + n,l - 1]); } } function g(p){ var n = 1 << p; for (var i=1; i<n; i+=2){ var a = f(1,i,1,p); console.log(a); console.log(n - a + 1); } } g(3)