views:

443

answers:

5

I am preparing for a software job interview, and I have trouble with in-place array modifications. For example, in the out-shuffle problem you interleave two halves of an array, so that 1 2 3 4 5 6 7 8 would become 1 5 2 6 3 7 4 8. This question asks for a constant-memory solution (and linear-time, although I'm not sure that's even possible).

First I thought a linear algorithm is trivial, but then I couldn't work it out. Then I did find a simple O(n^2) algorithm but it took me a long time. And I still don't find a faster solution.

I remember also having trouble solving a similar problem from Bentley's Programming Pearls, columnn 2: Rotate an array left by i positions (e.g. abcde rotated by 2 becomes cdeab), in time O(n) and with just a couple of bytes extra space.

Does anyone have tips that help wrap my head around such problems? Are there specific tutorials for such questions? Thanks!

A: 

Generally speaking, the idea is to loop through the array once, while

  • storing the value at the position you are at in a temporary variable
  • finding the correct value for that position and writing it
  • either move on to the next value, or figure out what to do with your temporary value before continuing.
calmh
+1  A: 

For the first one, let's assume n is even. You have:

first half: 1 2 3 4
second : 5 6 7 8

Let x1 = first[1], x2 = second[1].

Now, you have to print one from first half, one from second, one from first, one from second...

Meaning first[1], second[1], first[2], second[2], ...
Obviously you don't keep two halves in memory, as that will be O(n) memory. You keep pointers to the two halves. Do you see how you'd do that?

The second is a bit harder. Consider:
12345
abcde
..cde
.....ab
..cdeab
cdeab

Do you notice anything? You should notice that the question basically asks you to move the first i characters to the end of your string, without affording the luxury of copying the last n - i in a buffer then appending the first i and then returning the buffer. You need to do with O(1) memory.

To figure how to do this you basically need a lot of practice with these kind of problems, as with anything else. Practice makes perfect basically. If you've never done these kinds of problems before, it's unlikely you'll figure it out. If you have, then you have to think about how you can manipulate the substrings and / or indices such that you solve your problem under the given constraints. The general rule is to work as much as possible and learn as much as possible so you'll figure out solutions to these problems very fast when you see them, but the solution differs quite a bit from problem to problem. There's no clear recipe for success I'm afraid. Just read a lot and understand the stuff you read before you move on.

The logic for the second problem is this: what happens if we reverse the substring [1, 2], the substring [3, 5] and then concatenate them and reverse that? We have, in general:

1, 2, 3, 4, ..., i, i + 1, i + 2, ..., N
reverse [1, i] =>
i, i - 1, ..., 4, 3, 2, 1, i + 1, i + 2, ..., N
reverse [i + 1, N] =>
i, i - 1, ..., 4, 3, 2, 1, N, ..., i + 1
reverse [1, N] =>
i + 1, ..., N, 1, 2, 3, 4, ..., i - 1, i
, which is what you wanted. Writing the reverse function using O(1) memory should be trivial.

IVlad
Thanks for the explanations. As for the first one, printing them out in the different order is easy, but actually modifying the array itself in-place so that its elements are out-shuffled is harder.
Frank
Oh I missed that. I'll think about it and edit my post if I figure it out.
IVlad
A: 

Frank,

For programming with loops and arrays, nothing beats David Gries's textbook The Science of Programming. I studied it over 20 years ago, and there are ideas that I still use every day. It is very mathematical and will require real effort to master, but that effort will repay you many times over for your whole career.

Norman Ramsey
+3  A: 

The basic strategy with in place algorithms is to figure out the rule for moving a entry from slot N to slot M.

So, your shuffle, for instance. if A and B are cards and N is the number of chards. the rules for the first half of the deck are different than the rules for the second half of the deck

 // A is the current location, B is the new location.
 // this math assumes that the first card is card 0
 if (A < N/2)
    B = A * 2;
 else
    B = (A - N/2) * 2 + 1;

Now we know the rule, we just have to move each card, each time we move a card, we calculate the new location, then remove the card that is currently in B. place A in slot B, then let B be A, and loop back to the top of the algorithm. Each card moved displaces the new card which becomes the next card to be moved.

I think the analysis is easier if we are 0 based rather than 1 based, so

 0 1 2 3 4 5 6 7  // before
 0 4 1 5 2 6 3 7  // after

So we want to move 1->2 2->4 4->1 and that completes a cycle then move 3->6 6->5 5->3 and that completes a cycle and we are done.

Now we know that card 0 and card N-1 don't move, so we can ignore those, so we know that we only need to swap N-2 cards in total. The only sticky bit is that there are 2 cycles, 1,2,4,1 and 3,6,5,3. when we get to card 1 the second time, we need to move on to card 3.

 int A = 1;
 int N = 8;
 card ary[N]; // Our array of cards
 card a = ary[A];

 for (int i = 0; i < N/2; ++i)
 {
     if (A < N/2)
        B = A * 2;
     else
        B = (A - N/2) * 2 + 1;

     card b = ary[B];
     ary[B] = a;
     a = b;
     A = B;

     if (A == 1)
     {
        A = 3;
        a = ary[A];
     }
 }   

Now this code only works for the 8 card example, because of that if test that moves us from 1 to 3 when we finish the first cycle. What we really need is a general rule to recognize the end of the cycle, and where to go to start the next one.

That rule could be mathematical if you can think of a way, or you could keep track of which places you had visited in a separate array, and when A is back to a visited place, you could then scan forward in your array looking for the first non-visited place.

For your in-place algorithm to be 0(n), the solution will need to be mathematical.

I hope this breakdown of the thinking process is helpful to you. If I was interviewing you, I would expect to see something like this on the whiteboard.

Note: As Moron points out, this doesn't work for all values of N, it's just an example of the sort of analysis that an interviewer is looking for.

John Knoeller
-1: This is incorrect. Won't work for all n.
Moron
@Moron: Excuse me? If you actually read what I wrote I _said_ it won't work for all N. The point is that an interviewer isn't looking for a correct answer, he's looking for a good _analysis_
John Knoeller
@John. Fair enough, I didn't read the question properly. Unfortunately, vote is too old.
Moron
@Moron: I clarified based on your comment, you should be able to change your vote now if you still want to.
John Knoeller
+5  A: 
Moron
I ended up googling the problem after not getting anywhere for 20 minutes :). Hard indeed. Just **printing** the numbers in the correct order like I suggested is trivial (and O(n) by the way, not O(nlogn)), but admittedly cheating.
IVlad
@IVlad: Yes, but divide and conquer does given an O(nlogn) time , O(1) space algorithm for outshuffle (without cheating!). I suggest you try it, it is interesting :-)
Moron
`Not sure why people think it is easy and are suggesting you try something else.` Not sure that anyone wrote that it's "easy" anywhere on the page. As many suggested, not the correct answer, but the approach is important. The approach demonstrated by Frank is not that of a programmer. That's all I was talking about.
Pavel Shved
Finding an approach to solve in O(n^2) time and O(1) space is reasonable, given how tough the problem is. Even O(nlogn) time and O(1) space is tough enough (as it uses the cyclic shift as a sub-method). Only reason I can think of, for suggesting they take something else up is if you think this problem is trivially solved. Sorry if that is not what you meant, but sure came off as that (to me at least).
Moron