Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
public class StringListEncoder {
private static final char SEPARATOR = ' ';
/**
* The key here is that we are putting the string length and separator before every String
* So that we can distinguish always.
*/
public String encodeStringList(final List<String> strings) {
final StringBuffer buffer = new StringBuffer();
for (final String s : strings) {
buffer.append(s.length());
buffer.append(' ');
buffer.append(s);
}
return buffer.toString();
}
public List<String> decodeString(final String value) {
String s = value;
final List<String> decodedList = new ArrayList<>();
int start = 0;
while (!s.isEmpty()) {
/**
* The first SEPARATOR will be the one we put during the serialization
*/
int idx = s.indexOf(SEPARATOR);
int strLen = Integer.parseInt(s.substring(start, idx));
int curStrStart = idx + 1;
int curStrEnd = idx + strLen + 1;
final String currStr = s.substring(curStrStart, curStrEnd);
decodedList.add(currStr);
s = s.substring(curStrEnd);
}
return decodedList;
}
}
public class StringListEncoder {
private static final char SEPARATOR = ' ';
/**
* The key here is that we are putting the string length and separator before every String
* So that we can distinguish always.
*/
public String encodeStringList(final List<String> strings) {
final StringBuffer buffer = new StringBuffer();
for (final String s : strings) {
buffer.append(s.length());
buffer.append(' ');
buffer.append(s);
}
return buffer.toString();
}
public List<String> decodeString(final String value) {
String s = value;
final List<String> decodedList = new ArrayList<>();
int start = 0;
while (!s.isEmpty()) {
/**
* The first SEPARATOR will be the one we put during the serialization
*/
int idx = s.indexOf(SEPARATOR);
int strLen = Integer.parseInt(s.substring(start, idx));
int curStrStart = idx + 1;
int curStrEnd = idx + strLen + 1;
final String currStr = s.substring(curStrStart, curStrEnd);
decodedList.add(currStr);
s = s.substring(curStrEnd);
}
return decodedList;
}
}
@ artur.ghandilyan :
Nope dude. The solution works with or without the character ',' in the strings. In fact the choice of SEPARATOR does NOT matter at all. Please read the code more carefully or at least provide one counter case.
Your method works exactly the same as mine, only with different parameter naming.
Replacing the while loop with find() won't make any difference other than shortening the code by one line.
Given the strings are non empty, ZoomBA has some awesome one liners:
a = [ 'hi am cool', 'boo hahah' ]
es = str(a,'_') -> { hash( 'e64' , $.o ) }
println ( es )
ds = tokens ( es , '[^_]+' ) -> { hash ( 'd64', $.o ) }
println ( ds )
In case the strings can be empty - we have to do something manually :
a = [ 'hi am cool', '' , 'boo hahah' , '' ]
es = str( a , '_' ) -> { empty( $.o ) ?'' : hash( 'e64', $.o ) }
println(es)
ds = list ( es.split('_',-1) ) -> { empty($.o) ? '' : hash('d64', $.o ) }
println ( ds )
public class StringEncoderDecoder {
static String encode(List<String> list) {
StringBuffer sb = new StringBuffer();
Iterator<String> it = list.iterator();
while(it.hasNext()) {
String s = it.next();
sb.append(s);
if(it.hasNext())
sb.append("|");
}
return sb.toString();
}
static List<String> decode(String s) {
return Arrays.asList(s.split("\\|"));
}
public static void main(String args[]) {
List<String> list = Arrays.asList(new String[] { "Juliana", "Roberta", "Julia", "Açucena" });
System.out.println("list: "+list);
String encoded = encode(list);
System.out.println("encoded: "+encoded);
List<String> decoded = decode(encoded);
System.out.println("decoded: "+decoded);
}
}
class StringListEncoder {
private static final char separator = ',';
public String encode(List<String> list) {
if (list == null || list.size() == 0) return null;
StringBuilder sb = new StringBuilder();
for (String str : list) {
sb.append(str.length());
sb.append(separator);
sb.append(str);
}
return sb.toString();
}
public List<String> decode(String strs) {
if (strs == null || strs.isEmpty()) return null;
ArrayList<String> list = new ArrayList<>();
int index = 0;
while (index < strs.length()) {
StringBuilder sb = new StringBuilder();
/* Get length of the string */
while (strs.charAt(index) != separator) {
sb.append(strs.charAt(index++));
}
int length = Integer.parseInt(sb.toString());
/* Skip separator and get word from substring */
String str = strs.substring(++index, index + length);
list.add(str);
index = index + length;
}
return list;
}
}
Since String can be combination of any character. I think using a separator is inefficient. Instead, I used the length of individual strings to identify the string. Here is my solution:
public static void main(String[] args) {
List<String> listOfStrings = new ArrayList<String>();
listOfStrings.add("ABCD");
listOfStrings.add("1234");
listOfStrings.add("$%^>?,");
listOfStrings.add("{}&!~_)");
listOfStrings.add("abc123&8'");
listOfStrings.add("");
String strEncoded = encodeString(listOfStrings);
System.out.println(strEncoded);
System.out.println(decodeString(strEncoded));
}
public static String encodeString(List<String> listOfStrings) {
if (listOfStrings == null) {
return null;
}
StringBuffer sb = new StringBuffer();
for (String str : listOfStrings) {
sb.append(str.length());
sb.append(str);
}
return sb.toString();
}
public static List<String> decodeString(String encodedString) {
if (encodedString == null) {
return null;
}
List<String> decodedList = new ArrayList<String>();
int strLength = 0;
int index = 0;
while (index < encodedString.length()) {
strLength = Character.getNumericValue(encodedString.charAt(index));
if (strLength == 0) {
decodedList.add("");
} else if ((index + strLength + 1) < encodedString.length()) {
decodedList.add(encodedString.substring((index + 1), (index + strLength + 1)));
} else {
decodedList.add(encodedString.substring((index + 1)));
}
index += strLength + 1;
}
return decodedList;
}
Using prefix delimiter as (length of string) + "#", Following is the code in Java:
static public String encode(ArrayList<String> al){
int l = al.size();
if(l == 0)
return "0#";
StringBuffer res = new StringBuffer();
for(String str: al){
int l1 = str.length();
res.append(l1 + "#" + str);
}
return res.toString();
}
static public ArrayList<String> decode(String a){
int l = a.length();
ArrayList<String> res = new ArrayList<String>();
int i = 0;
while(i < l){
int l1 = 0;
while(i < l && a.charAt(i) != '#'){
l1 = l1*10 + Character.getNumericValue(a.charAt(i));
i++;
}
res.add(a.substring(i + 1, i + 1 + l1));
i = i + 1 + l1;
}
return res;
}
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string EncodeString(vector<string> toBeEncodedStrings )
{
string encodedString = "";
for( string n : toBeEncodedStrings)
{
encodedString += to_string(n.size()) +".";
}
encodedString += ".";
for( string n : toBeEncodedStrings)
{
encodedString += n;
}
return encodedString;
}
void DecodeString( string encodedString )
{
vector<int> stringSizes;
string currentSize;
int headerEnd = 0;
for( int n = 0; n < encodedString.size() - 2 && !(encodedString[n] == '.' && encodedString[n+1] == '.'); n++ )
{
if( encodedString[n] == '.' && currentSize.size() > 0 )
{
stringSizes.push_back(atoi( currentSize.c_str() ) );
currentSize = "";
}
else
{
currentSize += encodedString[n];
cout << "Size " << currentSize << endl;
}
headerEnd = n;
}
headerEnd += 3;
vector<string> decodedStrings;
for(int n = headerEnd, m = 0; n < encodedString.size(); m++)
{
decodedStrings.push_back(encodedString.substr(n, stringSizes[m]));
n += stringSizes[m];
}
cout << "DecodedStrings" << endl;
for( string n : decodedStrings)
{
cout << n << endl;
}
}
int main()
{
vector<string> toBeEncodedStrings = {"apple","banana","applepineapple","pear"};
string encodedString = EncodeString(toBeEncodedStrings);
cout << "encodedString = " << encodedString << endl;
DecodeString(encodedString);
return 0;
}
How about this:
public static String encode(List<String> stringList) {
StringBuilder encodedString = new StringBuilder();
for (String str : stringList) {
int length = str.length();
encodedString.append(length).append(str);
}
return encodedString.toString();
}
public static List<String> decode(String encodedString) {
List<String> list = new ArrayList<>();
char[] stringChars = encodedString.toCharArray();
StringBuffer sb = new StringBuffer();
int count = Integer.parseInt(stringChars[0]+"");
int j = 0;
for (int i = 1; i < encodedString.length(); i++) {
j = 0;
while (j++ < count) {
sb.append(stringChars[i++] + "");
}
list.add(sb.toString());
sb = new StringBuffer();
if (i < encodedString.length()) {
count = Integer.parseInt(stringChars[i]+"");
}
}
return list;
}
Considering 32 bit m/c
public static void main(String[] args) {
String text = "this is google!";
System.out.println("Actual text - " + text);
String encode = encode(text);
System.out.println("Encode - " + encode);
String decode = decode(encode);
System.out.println("Decode - " + decode);
}
public static String encode(String text) {
int n = text.length();
char[] carr = text.toCharArray();
int[] arr = new int[n / 4 +1];
int i = -1;
for (int k = 0; k < n; k++) {
if (k % 4 == 0)
i++;
int val = arr[i];
arr[i] = ((val << 8) | (int) (carr[k]));
}
String encoded = "";
for (int k = 0; k < arr.length; k++) {
int v = arr[k];
String tp = "";
while(v > 0){
tp = (char) (v%10 + 'a') + tp;
v = v/10;
}
encoded += tp + '#';
}
return encoded;
}
public static String decode(String text) {
int n = text.length();
char[] carr = text.toCharArray();
int[] arr = new int[n];
String s = "";
int ind = 0;
for (int i = 0; i < n; i++) {
if(carr[i] == '#'){
arr[ind] = Integer.parseInt(s);
s = "";
ind++;
}else{
s += String.valueOf((carr[i] - 'a'));
}
}
String decode = "";
int i = 0;
while (i < n) {
int k = 3;
while (k >= 0) {
int val = arr[i];
decode += (char) ((val & (255 << 8*k)) >> 8*k);
k--;
}
i++;
}
return decode;
}
//encoding static char SEPARATOR = ‘,’; public static String serialize(List<String> strs) { if(strs == null) return null; StringBuilder ret = new StringBuilder(); for(String str: strs) { ret.append(str.length()); ret.append(SEPARATOR); ret.append(str); } return ret.toString(); } //decoding public static List<String> deserialize(String s) { if(s == null) return null; List<String> strs = new ArrayList<String>(); int i = 0, n = s.length(); while(i < n) { int j = i; while(s.charAt(j) != SEPARATOR) { j++; } int len = Integer.parseInt(s.substring(i, j)); i = j + len + 1; if(len == 0) strs.add(“”); else strs.add(s.substring(j + 1, i)); } return strs; }Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
- aonecoding January 15, 2017We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.
@artur.ghandilyan:
Nope dude. The solution works with or without the character ',' in the strings. In fact the choice of SEPARATOR does NOT matter at all. Please read the code more carefully or at least provide one counter case.
Your method works exactly the same as mine, only with different parameter naming.
Replacing the while loop with find() won't make any difference other than shortening the code by one line.