# Strings: Microsoft interview

You are given an array of strings , you have to construct a single array containing all of them so that the same array of strings can be reconstructed from the large array. The strings may contain any ASCII character. How to determine length of the single large array?

Example= let a = ["asd";"dfg";"rew"]. Problem is to combine them in a single string in such a way that it can reconstructed. How to figure out the size of the string which will store the concatenation ?

• Why is it even an array? Shouldn’t the result just be one string?
– Ry-
Commented Jul 6, 2013 at 20:59
• Simple - since ASCII is only 7 bits you can just use a value > 127 as a separator character between strings and some other value > 127 as a final terminator. Commented Jul 6, 2013 at 21:17
• What are you actually asking for? A program? A mathematical expression of the output size as a function of input size? (The latter would seem to be ill-defined, because there are an infinite number of injections from arrays of strings to strings). Commented Jul 6, 2013 at 21:50

This was a very common in style in Apple ][ binaries. The high bit of the first character of each word was set. You know you can do this since ASCII was specifically mentioned and the high bit is never set for ASCII. This technique relies on strings that know their own length. We can assume this is the case, since the strings can "contain any ASCII" characters, so C style (null terminated) strings can't work.

>>> a = ["asd", "dfg", "rew"]
>>> ''.join(chr((ord(s[0])) | 128) + s[1:] for s in a)
'\xe1sd\xe4fg\xf2ew'


converting back to the original list

>>> (''.join('\x80'+chr((ord(c)) & 127) if c>'\x7f' else c for c in '\xe1sd\xe4fg\xf2ew')).split('\x80')[1:]
['asd', 'dfg', 'rew']


# JavaScript, 6

This evaluates to a function. Works in Firefox.

uneval

• More portably: JSON.stringify Commented Oct 30, 2013 at 1:40
• @recursive: Oh, I missed that this wasn’t code golf.
– Ry-
Commented Oct 30, 2013 at 1:41