CODEWITHSUNDEEP
javalist
Hari Gudigundla
Hari Gudigundla

Reputation: 822

Java - Recover the original order of a list after its elements had been randomized

The Title is self explanatory. This was an interview question. In java, List is an interface. So it should be initialized by some collection.

I feel that this is a tricky question to confuse. Am I correct or not? How to answer this question?

Upvotes: 0

Views: 384

Answers (3)

Avi
Avi

Reputation: 16176

There's a user's view, and there's internals. There's the question as understood and the question as can be interpreted.

The user's view is that list items are blocks of memory, and that the pointer to the next item is a set of (4?8? they keep changing the numbers:) bytes inside this memory. So when the list is randomized and the pointer to the next item is changed, that area of memory is overriden and can't be recovered.

The question as understood is that you are given a list after it had been randomized.

Internals - I'm not a Java or an OS guy, but you should look into situations where the manner in which the process is executed differs from the naive view: Maybe Java randomizes lists by copying all the cells, so the old list is still kept in memory somewhere? Maybe it keeps backup values of pointers? Maybe the pointers are kept at an external table, separate from the list, and can be reconstructed? Maybe. Internals.

Understanding - Who says you haven't got an access to the list before it was randomized? You could have just printed it out! Or maybe you have a trace of the execution? Or who said you're using Java's built it list? Maybe you are using your own version controlled list? Or maybe you're using your own reversable-randomize method?

Edwin Buck's answer is great but it all depends what the interviewer was looking for.

Upvotes: 0

Edwin Buck
Edwin Buck

Reputation: 70909

Assuming you don't have a copy of the original List, and the randomizing algorithm is truly random, then no, you cannot restore the original List.

The explanation is far more important on this type of question than the answer. To be able to explain it fully, you need to describe it using the mathematical definitions of Function and Map (not the Java class definitions).

A Function is a Map of Elements in one Domain to another Domain. In our example, the first domain is the "order" in the first list, and the second domain is the "order" in the second list. Any way that can get from the first domain to the second domain, where each element in the first domain only goes to one of the elements in the second domain is a Function.

What they want is to know if there is an Inverse Function, or a corresponding function that can "back map" the elements from the second domain to the elements in the first domain. Some functions (squaring a number, or F(x) = x*x ) cannot be reversed because one element in the second domain might map back to multiple (or none) elements in the first domain. In the squaring a number example

F(x) = x * x
F(3) = 9     or (  3 -> 9)
F(12) = 144  or ( 12 -> 144)
F(-11) = 121 or (-11 -> 121)
F(-3) = 9    or ( -3 -> 9)

attempting the inverse function, we need a function where

9 maps to 3
144 maps to 12
121 maps to -11
9 maps to -3

Since 9 must map to 3 and -3, and a Map must have only one destination for every origin, constructing an inverse function of x*x is not possible; that's why mathematicians fudge with the square root operator and say (plus or minus).

Going back to our randomized list. If you know that the map is truly random, then you know that the output value is truly independent of the input value. Thus if you attempted to create the inverse function, you would run into the delimma. Knowledge that the function is random tells you that the input cannot be calculated from the output, so even though you "know" the function, you cannot make any assumptions about the input even if you have the output.

Unless, it is pseudo-random (just appears to be random) and you can gather enough information to reverse the now-not-truly random function.

Upvotes: 3

Borealid
Borealid

Reputation: 98469

If you have not kept some external order information (this includes things like JVM trickery with ghost copies), and the items are not implicitly ordered, you cannot recover the original ordering.

When information is lost, it is lost. If the structure of the list is the only place recording the order you want, and you disturb that order, it's gone for good.

Upvotes: 2

Related Questions