How to reverse string which place 2/3 of heap?

Question

Recently I've had an interview and I was asked a strange(at least for me) question:

I should write a method which would inverse a string.

public static String myReverse(String str){
    ...
}

The problem is that str is a very very huge object (2/3 of memory).

I suppose only one solution:

create a new String where I will store the result, then reverse 1/2 of the source String. After using reflection, clear the second half(already reversed) of the source string underlying array and then continue to reverse.

Am I right?

Any other solutions?

"very very huge" is very very vague. What are the constraints of the problem? — shmosel, Jan 24 '17 at 07:06
I see. Please include that in the body as it's essential to the question. — shmosel, Jan 24 '17 at 07:08
Using reflection to change a `final` field in an unmodifiable object isn't really a solution. For one thing, you will have incorrect results from the `hashCode` function if you did invoke `hashCode` on the string earlier, and who knows what else, either now or in future versions of Java. I think the only solution is to increase the amount of memory available to your VM so that you can keep 2 strings and a StringBuffer or char[] to do the reversing in. — Erwin Bolwidt, Jan 24 '17 at 07:22
If you're using reflection to modify a string (a very dangerous idea), you can do it at basically full capacity. See [this article](http://philosopherdeveloper.com/posts/are-strings-really-immutable-in-net.html) for a related discussion. — shmosel, Jan 24 '17 at 07:23

jesper_bk · Answer 1 · 2017-01-24T07:31:57.213

4

If you are using reflection anyway, you could access the underlying character array of the string and reverse it in place, by traversing from both ends and swapping the chars at each end.

public static String myReverse(String str){
    char[] content;
    //Fill content with reflection

    for (int a = 0, b = content.length - 1; a < b; a++, b--) {
        char temp = content[b];
        content[b] = content[a];
        content[a] = temp;
    }

    return str;
}

I unfortunately can't think of a way that doesn't use reflection.

edited Jan 24 '17 at 07:31

answered Jan 24 '17 at 07:25

jesper_bk

503
2
9

It looks sensibly – gstackoverflow Jan 24 '17 at 07:30
Try toCharArray – Jan 24 '17 at 08:24
1

toCharArray creates a new copy of the underlying char array, which in this case would result in something like an OutOfMemoryError, as it fills up the remaining memory. – jesper_bk Jan 24 '17 at 08:27
@jesper_bk but could it not then be reversed without using more memory? You'd only need 2 more bytes for a temporary `char` variable. – Jan 24 '17 at 09:27
I am not sure I understand your point. The existing `str` variable fills 2/3 of the total memory. If a use the `toCharArray()` method, Java will create a new distinct copy of the `str` varaible's internal char array. This new array won't fit into the remaining memory, since the existing array already takes up more than half of the total memory. – jesper_bk Jan 24 '17 at 09:30
Note that this would be very dangerous in the real world. See [this article](http://philosopherdeveloper.com/posts/are-strings-really-immutable-in-net.html) for a related discussion. Also, it suspiciously overlooks the available 1/3 memory in the problem. – shmosel Jan 24 '17 at 10:24
@shmosel Yes, you should not manipulate the underlying data of an immutable problem, but I am doing exactly that to circumvent the memory problem. Since the memory problem prevents me from manipulating a mutable copy of the data, it is necessary to manipulate the data in place. As I said, I don't see a way to solve the problem without reflection, given the memory constraints. – jesper_bk Jan 24 '17 at 10:29
The immutable part is not such a big deal. The real problem is that string instances can be shared via interning, whether implicit or explicit. Modifying a string can cause code to misbehave in unexpected places. See my answer for a possible alternative. – shmosel Jan 24 '17 at 10:35
Exactly. So it's a choice between modifying something that should not be modified, and assuming it's ASCII only. Nice solution BTW. – jesper_bk Jan 24 '17 at 10:45

shmosel · Answer 2 · 2017-01-24T10:17:55.697

2

A String is internally a 16-bit char array. If we know the character set to be ASCII, meaning each char maps to a single byte, we can encode the string to a 8-bit byte array at only 50% of the memory cost. This fully utilizes the available memory during the transition. Then we let go of the input string to reclaim 2/3 of the memory, reverse the byte array and reconstruct the string.

public static String myReverse(String str) {
    byte[] bytes = str.getBytes("ASCII");
    // memory at full capacity
    str = null;
    // memory at 1/3 capacity
    for (int i = 0; i < bytes.length / 2; i++) {
        byte tmp = bytes[i];
        bytes[i] = bytes[bytes.length - i - 1];
        bytes[bytes.length - i - 1] = tmp;
    }
    return new String(bytes, "ASCII");
}

This, of course, assumes you have a little extra memory available for temporary objects created by the encoding process, array headers, etc.

edited Jan 24 '17 at 10:17

answered Jan 24 '17 at 08:07

shmosel

49,289
6
73
138

Do you believe that input string will be collected by gc? – gstackoverflow Jan 24 '17 at 08:18
@gstackoverflow The GC will be forced to do a cleanup once we try creating the new string. – shmosel Jan 24 '17 at 08:20
@skyking The key is that `bytes` is only half the size of `str`, which perfectly fits our memory constraints. – shmosel Jan 24 '17 at 09:04
@gstackoverflow I've clarified the explanation since there may have been some misunderstandings. – shmosel Jan 24 '17 at 10:21
This only works if the string consists of ASCII characters only, but you cannot assume that, based on the question. – Ridcully Jan 24 '17 at 10:39
@Ridcully I'm not assuming it as fact. But it seems plausible, given the constraints. More plausible (to me) than assuming reflection would be allowed. – shmosel Jan 24 '17 at 10:49
@shmosel Don't you think, when complete memory is used, gc won't be able to free the memory. Instead, it will rise the CPU utilization to 100% pausing the complete execution? – Amber Beriwal Jan 24 '17 at 13:10
@AmberBeriwal No, not at all. It sounds to me like you're conflating memory and CPU usage. Also, keep in mind the question was likely theoretical. – shmosel Jan 24 '17 at 19:26
@shmosel In practical scenario, it happens with GC that due to less memory it takes too much time to complete its task and as GC is heavy operation, it also raises the CPU. I have seen it in production environment in JBOSS as well. I agree, the question is theoretical so these considerations can be skipped. – Amber Beriwal Jan 25 '17 at 07:00
@AmberBeriwal "Too much time" for what? Was there a time constraint? It "raises the CPU"? Literally every operation does; so what? Besides, I don't imagine it's very difficult to clean a single object. – shmosel Jan 25 '17 at 07:05
@shmosel too much time for GC to complete. Raises the CPU means to 100% causing a pause in execution. Yes, it could be fast for a single object. I didn't take that in account. – Amber Beriwal Jan 25 '17 at 07:07
@AmberBeriwal I get that heavy GC can lock up the JVM temporarily, and I've also seen it in production. My point is that it doesn't make the solution any less correct, just less practical. But practicality was obviously never the goal. – shmosel Jan 25 '17 at 07:15
@shmosel I agree that's why I have already said as the question is theoretical so these considerations can be skipped . – Amber Beriwal Jan 25 '17 at 07:21
The `String` being internally a 16-bit `char` array is an implementation detail. Java 9 is going to use a `byte[]` array for all-ASCII strings. If it still occupies ⅔ of the heap, this trick won’t work, and if it contains non-latin-1 characters, if wouldn’t work at all. Further, a solution needing ⅓+⅔ of the memory has the problem, that the surrounding rest of the application, JRE and JVM needs memory too (might be ignorable for very large heaps due to rounding). We could ignore these aspects and say the question is not specific enough, though… – Holger Feb 02 '17 at 18:28
@Holger I read the question as discussing available memory, not total memory. Though my solution still requires a small amount of additional memory, as I stated. I was also clear that my solution expects only ASCII characters. As for Java 9's character representation, that's the last thing I'd be worried about for a theoretical interview question. – shmosel Feb 02 '17 at 18:43
Indeed, you already stated the shortcomings. One interesting point, I’ve noted when looking for alternatives, is how hard it is to construct a `String` from mutable data without having a temporary array or buffer created under the hood. Your combination of byte array and `"ASCII"` is one of the rare cases where it works. Besides that, every non-reflective solution must assume that the caller has no additional reference to the original string instance, which is quite far fetched. And the reflective solution doesn’t work on every JVM/JRE anyway… – Holger Feb 02 '17 at 19:23

skyking · Answer 3 · 2017-01-24T09:42:37.217

It's unlikely that you can do that without using tricks like reflection or assuming that the String is stored in an efficient way (for example knowing it to be only ASCII characters). The problems in your way is that in java Strings are immutable. The other is the likely implementation of garbage collection.

The problem with the likely implementation of garbage collection is that the memory is reclaimed after the object can no longer be accessed. This means that there would be a brief period where both the input and the output of a transformation would need to occupy memory.

For example one could try to reverse the string by successively build the result and cut down the original string:

rev = rev + orig.substring(0,1);
orig = orig.substring(1);

But this relies oth that the previos incarnation of rev or orig respectively is collected as the new incarnation of rev or orig is being created so that they never occupy up to 2/3 of the memory at the same time.

To be more general one would study such a process. During the process there would be a set of objects that evolve throughout the process, both the set it self and (some of) the objects. At the start the original string would be in the set and at the end the reversed string would be there. It's clear that due to information content the total size of the objects in the set can never be lower than the original. The crucial point here is that the original string have to be deleted at some point. Before that time at most 50% of the information may exist in the other objects. So we need a construct that would at the same time delete a String object as it retains more than half of the information therein.

Such a construct would need you basically to call a method to an object returning another object an in the process remove the object as the result is being constructed. It's unlikely that the implementation would work in that way.

Your approach seem to rely on that String are indeed mutable somehow, and then there would be no problem in just reversing the string in place without having to use a lot of memory. You don't need to copy out anything there, you can do the whole thing in place: swap the [j] and then [len-1-j] (for all j<(len-1)/2)

I don't think it will work, because second line `orig=orig.substring(1)` will need 4/3 i.e. 133% of total available memory. — Amber Beriwal, Jan 24 '17 at 07:53
@AmberBeriwal You didn't read thoroughly did you? For that construct to work it requires the old incarnation of the `orig` to be reclaimed as the new is created. That is an implementation where memory for both will never be needed. I wrote that it's unlikely that the implementation does that. I also started out stating that I don't think you can do that - do you really think that would mean that I would present a working solution? C'mon! — skyking, Jan 24 '17 at 08:58
I understood the answer earlier as well, but my point is: if the suggested approach cannot be implemented in any manner and based upon assumptions only, then it should not be presented as an answer to the question. — Amber Beriwal, Jan 24 '17 at 09:20
@AmberBeriwal I don't think you understand. Some question really don't have answers because they are basically unsolvable. Do you really mean it's improper to answer the question by pointing this fact out? — skyking, Jan 24 '17 at 09:39

How to reverse string which place 2/3 of heap?

3 Answers3