Interview Question
Country: United States
Interview Type: Phone Interview
@ninhnnsoc, no, it won't fail. Because here ":" is just used to separate one string's length and its content. Let's take ":::123abc*?." as an example, in above way its encoded string will be "12::::123abc*?.", when we apply the retrieve function:
(1)first we find the position of the first ":", say at idx
(2)then we slice out the length being "12",
(3)we slice out [idx+1, idx+1+length), which is exactly the origin string content.
string encode(vector<string> v);
{
string buffer;
for(vector<string>::iterator it=v.begin();it++;it!=v.end())
{
buffer+=it
}
}
I think the question asks how to encode a vector of string into a string, and decode the encoded string back to the original string array. So, the hard part is how to decode back...
My approach:
I need to add a "specifically formatted header" into the resulting string, like
resultString = [header][data-from-array];
The header must help us to decode back the data.
So, my header should contain following information:
1. number of strings in the array;
2. length of each string;
Format of the header may look like this:
header="n <space> L1 <space> ... Ln <space>"
where n = number of strings in the array; Li = length of i-th string;
Note: each field of header is separated by EXACTLY 1 space.
Example:
V = { "First", "2nd String", "Last"};
S = "3 5 10 4 First2nd StringLast";
How to DECODE it back?
1. Read n = the number of strings as the first integer in S;
2. Read next n integers L1, L2, ..., Ln;
3. Read from the data field n strings each of length L1, L2, ..., Ln, respectively.
4. Form the array of strings...
An implementation in perl may look like:
sub encode{
my @arrStr = @_;
$numStr = scalar @arrStr;
$header = "$numStr "; # a space at last position
for(int $i = 0; $i <n; $i++){
$len = length($arrStr[$i]));
$header = $header ."$len "; # a space at last position
};
$data = join("",@arrStr);
$encoded = $header.$data;
return $encoded;
};
sub decode{
my $encoded = shift;
($numStr) = split(/\s/,$encoded); # first number separated by a space
$encoded =~ s/^\S+\s*//; # delete the first number and a space
@Lens = ();
for(int $i = 0; $i <numStr; $i++){
($len) = split(/\s/,$encoded); # length of i-th string;
push(@Lens, $len);
$encoded =~ s/^\S+\s//; # delete the number and a space at beginning
};
# $encoded now contains only data;
my @arrStr = ();
for(int $i = 0; $i <numStr; $i++){
$aStr = substr($encoded, 0, $Lens[$i]);
$encoded = substr($encoded, $Lens[$i]);
push(@arrStr, $aStr);
};
return @arrStr;
};
# code isn't debugged!
Really... strings by definition are delimited by the character '\0' or numeric value 0 (equivalent)...
It should be as simple as concatenating each string into a serialised buffer and including the null terminator to delimit where each string ends.
To read it back you would simply read each character sequentially until you hit the null terminator and then add that string to the output container before moving onto the next string and so on...
(1)We don't know exactly what charset is used by these string, so we may not simply add a special character in between to separate these strings.
(2)But we can add the length info before each string, so that when we want to retrieve them, we figure out the length then slice out the origin string:
- uuuouou March 29, 2014