I got this problem in the real interview, and I thought it was interesting. I used the divide and conquer paradigm and came up with a linearithmic solution. After the interview, I could not help thinking about potential linear solution. Read on to see what I found with a little help from the number theory.
This problem is also known as "in-shuffle". Think about cutting a deck of cards into equal halves, and interleaving them perfectly, like some of poker junkies can do. It's easy to solve this problem in linear time if you can use additional memory, but the point here is to do it in-place.
Problem Statement
"Given array [a1, a2, ..., an, b1, b2, ..., bn], interleave it in-place to [a1, b1, a2, b2, ..., an, bn]"
