Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 5 vote

//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).
We 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.

- aonecoding January 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 January 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 January 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- aonecoding January 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 )

- NoOne January 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
}

- ZeroCool January 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- oscar.fimbres January 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

1. Pack string with a delimiter and escape the delimiter in the data.
2. Consider data compression including data dedupe
3. Consider data security to not let any decode the string easily.

- ankushbindlish January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

	}

- nimit444 January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
		}

- amaniitm.gupta26 January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- cmr January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use encodeURIComponent:

{{
function serialize (S) {
var s = []
for (var i = 0; i < S.length; ++i) {
s.push(encodeURIComponent(S[i])
}
return s.join(';')
}

function deserialize (s) {
var S = s.split(';')
for (var i = 0; i < S.length; ++i) {
S[i] = decodeURIComponent(S[i])
}
return S
}

}}}

- srterpe January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- getPDat January 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- sudip.innovates November 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is a wrong solution, what if the one or many original strings have ',' character in them?

- artur.ghandilyan January 15, 2017 | 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