What algorithm may be used to solve the re-assembly of shredded papers?
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. 180
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?) 180