Encode and Decode Strings
Amazon
MicrosoftThe problem
Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.
Machine 1 (sender) has the function: string encode(vector<string> strs) { // ... your code return encoded_string; } Machine 2 (receiver) has the function: vector<string> decode(string s) { //... your code return strs; } So Machine 1 does: string encoded_string = encode(strs); and Machine 2 does: vector<string> strs2 = decode(encoded_string); strs2 in Machine 2 should be the same as strs in Machine 1.
Implement the encode and decode methods. You are not allowed to solve the problem using any serialize methods (such as eval).
Input: dummy_input = ["Hello","World"] Output: ["Hello","World"] Explanation: Machine 1: Codec encoder = new Codec(); String msg = encoder.encode(strs); Machine 1 ---msg---> Machine 2
Machine 2: Codec decoder = new Codec(); String[] strs = decoder.decode(msg);
Input: dummy_input = [""] Output: [""]
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] contains any possible characters out of 256 valid ASCII characters.
cpp
class Codec {
public:
// Encodes a list of strings to a single string.
string encode(vector<string>& strs) {
}
// Decodes a single string to a list of strings.
vector<string> decode(string s) {
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(strs));java
class Codec {
// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
}
// Decodes a single string to a list of strings.
public List<String> decode(String s) {
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));python
class Codec:
def encode(self, strs):
"""Encodes a list of strings to a single string.
:type strs: List[str]
:rtype: str
"""
def decode(self, s):
"""Decodes a single string to a list of strings.
:type s: str
:rtype: List[str]
"""
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(strs))javascript
class Codec {
encode(strs) {
}
decode(s) {
}
}csharp
public class Codec
{
public string encode(List<string> strs)
{
}
public List<string> decode(string s)
{
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));go
func encode(strs []string) string {
// ... your code ...
}
func decode(s string) []string {
// ... your code ...
}Stuck? Show a way to structure it+
- 01Encode each string as its decimal length, a delimiter, then its raw content.
- 02Concatenate all encoded records.
- 03During decoding, parse a length up to the delimiter.
- 04Read exactly that many following characters and repeat.
Reference answer
Then expect these follow-ups
How would you detect malformed or truncated encoded input?
Tests: robust parsing
How would you serialize binary data?
Tests: protocol design
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question