StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>For the first one, let's assume n is even. You have:</p> <p>first half: <code>1 2 3 4</code><br> second : <code>5 6 7 8</code></p> <p>Let x1 = first[1], x2 = second[1].</p> <p>Now, you have to print one from first half, one from second, one from first, one from second... </p> <p>Meaning first[1], second[1], first[2], second[2], ...<br> 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?</p> <p>The second is a bit harder. Consider: <br> <code>12345</code><br> <code>abcde</code><br> <code>..cde</code><br> <code>.....ab</code><br> <code>..cdeab</code><br> <code>cdeab</code><br></p> <p>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.</p> <p>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 <strong>understand</strong> the stuff you read before you move on.</p> <p>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:</p> <p><code>1, 2, 3, 4, ..., i, i + 1, i + 2, ..., N</code><br> reverse [1, i] =><br> <code>i, i - 1, ..., 4, 3, 2, 1, i + 1, i + 2, ..., N</code><br> reverse [i + 1, N] =><br> <code>i, i - 1, ..., 4, 3, 2, 1, N, ..., i + 1</code><br> reverse [1, N] =><br> <code>i + 1, ..., N, 1, 2, 3, 4, ..., i - 1, i</code><br>, which is what you wanted. Writing the reverse function using O(1) memory should be trivial.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload