SRM 603, D2, 250-Pointer (MiddleCode)
James S. Plank
Sun Jul 7 10:36:33 EDT 2019
I'm going to walk you through two solutions to a rather simple problem. This is the kind
of thing that interviewers like to do on a job interview -- see you evaluate a simple-but-bad,
and a harder-but-good solution to a problem. So walk through every detail of this one
so that you could do this on a whiteboard in front of some job interviewers!
In case Topcoder's servers are down
Here is a summary of the problem:
- You are given a string s, whose size is 50 characters or less.
- Your job is create a new string t, from s. You start with t
being empty, and then you repeat the following, until s is empty:
- If the size of s is odd, then remove the middle character from s, and
append it to t.
- If the size of s is even, then look at the two middle characters of s.
Whichever of these is smaller than the other, remove it from s and append it
to t. (If they are equal, simply remove one of them and add it to t).
The examples
| Example |
s |
t |
| 0 |
"word" |
"ordw" |
| 1 |
"aaaaa" |
"aaaaa" |
| 2 |
"abacaba" |
"caabbaa" |
| 3 |
"shjegr" |
"ejghrs" |
| 4 |
"adafaaaadafawafwfasdaa" |
"afawadafawafaafsadadaa" |
Let's walk through the first example:
- s is "word". It is even, and the two middle characters are 'o'
and 'r'. Since 'o' is the smaller of these, add it to t and
remove it from s.
- s is now "wrd" and t is "o". Because s is odd,
remove the middle character -- 'r' and add it to t.
- s is now "wd" and t is "or". s is even, and
the two middle characters are 'w'
and 'd'. Since 'd' is the smaller of these, add it to t and
remove it from s.
- s is now "w" and t is "ord". Remove the
'w' from s, add it to t, and you're done: t is "ordw".
Testing yourself
Like the Cryptography Problem,
I have a shell script
tests.sh, that you can use to test your program. When you
run tests.sh, your answer should be identical to
answers.txt.
An Expedient Solution
Because the constraints on this one are so low, you can solve it with an expedient
solution that follows the algorithm above very closely:
- Find the index of the character you will remove in s.
- Add that character to t.
- "Remove" it from s by recreating s with two s.substr() calls.
Go ahead and write that one -- it will be fast enough to pass Topcoder's system test (or
tests.sh if Topcoder's servers are down).
Evaluating the Expedient Solution
As is often the case, the expedient solution is easy to write, but is not the best
solution. In this case, think about how you "delete" the character from s,
when it has n characters. The two s.substr() calls create a new
string of size n-1, which means that they take n-1 operations, and
you are left with a new s, whose size is n-1.
Let's add up the number of operations:
| Size of s |
Operations to "delete" the character |
| n | n-1 |
| n-1 | n-2 |
| n-2 | n-3 |
| ... | ... |
| 2 | 1 |
| 1 | 0 |
That's the sum of i for i = 0 to n-1, which is (n-1)*(n-2)/2 =
(n2 - 3n + 2) / 2. That's a quadratic equation (later in the semester,
we will call it O(n2)), which means it blows up as you increase n.
For example, if the size of x is 500,000, then this solution takes
250,001,500,002 operations.
In the shell script test-harder.sh, I include some larger tests, the last of which
uses a string with 500,000 characters as input. On my Macintosh (in 2019), it took three
minutes and 51 seconds.
A Better Solution
The culprit here is how you "delete" the character from s. If you think about the
problem some more, you'll see that you don't need to delete the character from s. You
can simply keep track of the middle characters without deleting them.
Go ahead and try to write a solution that doesn't delete any characters of s. I'll
outline it below, but give it a try on your own before reading further.
My solution relies on the observation that when s is even, you add one of the middle
characters to t, and then you add the other one (because s is now odd, and
that character is the middle one). In the example above, when you're considering
'o' and
'r', you first add the
'o' and then you add the
'r'. So, I did the following:
- If s is odd, then let i be the index of the middle character. Add that
character to t and then set j to (i+1) and i to (i-1)
- If s is even, then
set i to be the smaller index of the two middle characters, and
j to be the larger index.
- Then repeat until you're done: add the smaller of s[i] and
s[j] to t, and then the larger. Then increment j and decrement i.
If you evaluate this solution, it does a handful of operations at each iteration, and
there are n/2 iterations.
Call it 10 operations. That means a total of 5n operations, which is linear rather
than quadratic. Compare 5*500,000 = 2,500,000 operations to the
250,001,500,002 operations for the quadratic solution!
Try your new answer on test-harder.sh (check your correctness with tests.sh first), and
it should be much faster. You can check your timing as follows:
UNIX> time sh -c 'sh test-harder.sh > /dev/null'
0.921u 0.068s 0:00.90 108.8% 0+0k 0+0io 0pf+0w
UNIX>
Under a second for all of the tests!