Strings: Microsoft interview

Question

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 ?

Answer 1

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.

For your example, using Python

>>> 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']

Answer 2

JavaScript, 6

This evaluates to a function. Works in Firefox.

uneval