Interview Question


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

(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:

string& encode(string& dest, const vector<string>& v)
{
	dest.clear();
	for(size_t i = 0; i < v.size(); ++i){
		dest.append(to_string(v[i].size()));//length
		dest.append(":"); /* note that we add ':' to separate length and content in case that origin string begins with a digit */
		dest.append(v[i]);//origin string
	}
	return dest;
}
bool decode(vector<string>& v, const string& s)
{
	v.clear();

	size_t i = 0, j, len;
	for(; i < s.size(); i = j + 1 + len){
		j = s.find(':', i); //locate ':' between length and content
		if(j == string::npos) return false;
		len = strtoul(v.substr(i, j-i));//parse length
		if(j + 1 + len > s.size()) return false;
		v.push_back(s.substr(j+1, len));
	}

	return true;
}

- uuuouou March 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If a string contains ":" then your decoder will fail, right?

- ninhnnsoc March 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@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.

- uuuouou March 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

great job!

- ninhnnsoc March 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice coding

- nharryp March 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can always do with a special character. You can even make your special character a space (' ') or 'a' etc. Think about it.

The length one is good though.

- Anonymous March 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

string encode(vector<string> v);
{
string buffer;
for(vector<string>::iterator it=v.begin();it++;it!=v.end())
{
buffer+=it
}
}

- Anonymous March 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how to read it back?

- ninhnnsoc March 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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...

- ninhnnsoc March 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- ninhnnsoc March 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Huffman Encoding to encode the String.

- kirankumarcelestial April 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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...

- notthewrongoption May 12, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More