2
$\begingroup$

I was once given this question in an interview:

Suppose a piece of paper has 80 columns of alphabets with a fixed size font, and now the paper is shredded vertically, into 80 vertical pieces (so each piece can show a series of alphabets going down vertically), and there are 300 pages of such paper shredded total. Assume they are just English words with no proper names (for people / places). Find a method to reassemble all the papers and give the O() complexity time and space.

I proposed a solution where we take one piece of stripe, and go down the row to match for consecutive occurring alphabets, for a proper stripe. So we would build up a dictionary of all English words, for example, for the word Apple, that will mean ap, pp, pl, and le are all valid. And if we go down both stripes, we should expect most (or all) of them match with each other if they were adjacent.

But doing this way, it looks like it would be (180 * 300)! = 24000! (factorial) steps, before we can finish the task? I can only find a complicated paper about re-constructing non-fixed size font paper (and it seemed way too complicated for a 20 minute interview question), and another paper that is not public. Is there a good solution to this problem?

(Actually, it seems that if it is not fixed size font, it is a easier problem? Because we can just look at the left and right edge: along the left edge, for example, if there is ink, we call it as 1, and no ink, we call it a 0. Or we can just scan and collect data: from top edge, go down 3.232cm of blank space, and then 0.012cm of ink, and then 0.027cm of blank space, all the way down to the end of paper, and then we can create a signature. If we do the signature for all 80 x 300 stripes, now we have 48000 signatures. Now we can actually just match the signatures up to tell which strips is adjacent to which stripe. So that would be a linear O(n) solution?)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

If the cuts are in the middle of letters, then I think your solution in the last paragraph is a good one.

If the cuts go between letters, then I think your approach of finding pairs of strips of papers is a good one. I would start by finding all pairs of strips that could have been adjacent, based on which digraphs (pairs of characters) can appear in some word. Then, I would try to extend to find all triples of strips that could have been adjacent: for each possible pair of adjacent strips $s_1,s_2$, find all $s_3$ such that $s_2,s_3$ is a pair of possible adjacent strips; then test whether if you past together $s_1,s_2,s_3$ that all trigraphs (triples of characters) can appear in some word. Then, I would extend to 4-tuples of strips, filtering them based on 4-graphs of characters, and so on. The worst-case complexity could be horrible in principle, but in practice I expect that you'll very quickly filter out all false matches, so running time will probably be very good.

For fun, you might enjoy reading about the DARPA shredding challenge (summary on Wikipedia).

Improve this answer
$\endgroup$
8
  • $\begingroup$ if it is in between characters, would it be 24000! (factorial)? It seems like even 70! = 1.19785716699699e100 would not make it practical... if the match is on average made half way through, then 24000! / 2 would still be not practically possible $\endgroup$
    – nonopolarity
    Commented Dec 18, 2019 at 22:15
  • $\begingroup$ correction: if on average, we can make a match half way through, it should be 12000! $\endgroup$
    – nonopolarity
    Commented Dec 19, 2019 at 2:59
  • $\begingroup$ @nopole, In practice, only a tiny fraction of all possible pairs of strips will be valid; and only a tiny fraction of all possible triples will be valid; and so on. As I wrote, "The worst-case complexity could be horrible in principle, but in practice I expect that you'll very quickly filter out all false matches, so running time will probably be very good." I don't see much point in calculating precisely how horrible it could be; it's clear that it could be atrociously bad. $\endgroup$
    – D.W. ♦
    Commented Dec 19, 2019 at 4:33
  • $\begingroup$ now is it true in real life, if we have got 24,000 pieces of stripes, and now we are holding one, just to match this one, it is not easy? We could be matching 24,000 stripe (12,000 match on average) before we get the match. $\endgroup$
    – nonopolarity
    Commented Dec 19, 2019 at 5:35
  • 1
    $\begingroup$ Nopole, a six year old child can easily put a 100 piece jigsaw puzzle together. It doesn’t take n! steps. $\endgroup$
    – gnasher729
    Commented Dec 19, 2019 at 14:48
2
$\begingroup$

So... for the fixed-size font problem, if it were me, I'd use a stochastic global optimisation method. Specifically, I would try to find the permutation of the columns which optimises the compressibility of the text if it were compressed using a static model (e.g. PPM or DMC) trained on English text.

I'd probably use simulated annealing to start with. I'd pick some mutation operations, one of which is "swap two columns", one of which is "move a column to a random other place", and one of which (chosen with low probability) is "restart with a random permutation", and then let Metropolis and Hastings do their thing.

I can't think of a good "crossover" operation off the top of my head, but if so, a genetic algorithm might also be appropriate.

The space usage is $O(nk)$ where $k$ is the population size that you want to retain. The run time is exponential in the worst case, but likely faster than most deterministic algorithms.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.