Google Interview Question for Principal Software Engineers


Country: United States
Interview Type: In-Person




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

ASCII code uses only 8 bits of the available 32 bits of word size. I have tried using the remaining 24 bits to store additional characters.

public static void compress(String[] args) {
		String s="FOOFIGHTERS";
		char[]array= s.toCharArray();
		int z=24,t=0;
		for(int i=0;i<s.length();i++){
			int c = s.charAt(i);
			t |= c << z;
			z-=8;
			
			if (z==-8 || i == s.length()-1){
				z=24;
				System.out.println("t="+t);
				uncompress(t);
				t=0;
			}
		}
		
	public static void uncompress(int t){
		int a,z=24;
		int mask=1;
		mask = (mask << 8)-1;
		while(z != -8){
			a=t;
			a = a >> z & mask;
			z-=8;
			System.out.println((char)a);
		}
	}

- Bhaskar February 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Below is the code to represent string such as FOOFIGHTERS --> FO2FIGHTERS
Complexity: O(n)

public static void compressToNumbers(String str){
		int i=1,count=1;
		char next,prev;
		String s="";

		if (str.length()==0)
			return;

		prev=str.charAt(0);

		while(i < str.length()){
			next=str.charAt(i);

			if(prev==next){
				count++;
			}else{
				if (count==1)
					s="";
				else
					s = String.valueOf(count);
				System.out.print(prev+s);
				count=1;
			}

			prev = next;
			i++;
		}
		if (count==1)
			s="";
		else
			s = String.valueOf(count);
		System.out.print(prev+s);
	}
}

- Bhaskar February 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about regular expressions, wouldn't that be easier?

- Anonymous February 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Perl regex: s/((.)\2+)/$2 . length($1)/ge;

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

they said that no extra memory is needed:

1) scan through left to right
2) find max contiguous same characters substring, assume the start/end indices are i and j respectively for current character c.
3) write (j-i+1) integer as string from position i+1, assume the end of integer string is k.
move all the rest of original string forward to position k+1.

Only O(1) extra space is needed. and the time complexity is O(n^2)?

- samuel February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the string's alphabets are only a-z, we can use a special character to fill the holes, and compact the resulting string at the end of counting, the time complexity will be O(n) then.

- samuel February 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We share the same thought but O(1) space is not accurate, it is actually O(c) since it might need a char array to hold the count.

- soysauce February 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

string int2str(int i){
	string res;
	while(i > 0){
		res.push_back('0'+i%10); i/=10;
	}
	reverse(res.begin(), res.end());
	if(res.length() == 0) return "0";
	return res;
}
string compress(string s){
	if(s.length() < 2) return s;
	string res;
	int i = 0, j = 0;
	while(j < s.length())
	{
		if(s[i] == s[j]){
			j++; continue;
		}
		res.push_back(s[i]);
		if(j-i>1) res += int2str(j-i);
		i = j;
	}
	res.push_back(s[i]); 
	if(j-i>1) res += int2str(j-i);
	return res;
}

- Anonymous February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming, that we basically want collapse repetitions to <character><count> format. E.g. "HHHHHHHHHHELLLLLLLLLLLLPPPP ME BOBBBBBB" becomes "H10EL12P4 ME BOB6"
Also, assuming numbers are not allowed in the input.

int msd(int& k)
{
    int d=1;
    while (k>=d*10) d *= 10;
    int r = k/d;
    k %= d;
    return r;
}

void compress(char *str)
{
    if (str[0]==0) return;
    size_t i=0, j=1;
    while (str[j]) {
        while (str[i] == str[j]) j++;
        if (j-i>1) {
            int cnt = j-i;
            while (cnt>=10)
                str[++i] = '0'+msd(cnt);
            str[++i] = '0'+msd(cnt);
            int ii = i+1;
            while ((str[ii++]=str[j++]));
            j = ++i+1;
        } else {
            i = j++;
        }
    }
}

- shinjin February 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a clean c++ code. Although I have used string class from c++, the same can be done with c style pointers. I just feel lazy to do with c-style string.

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

string to_string(int num)
{
	stringstream s;
	s << num;
	return s.str();
}

void copy(string &str, int i, int j, char c, int &next_pos)
{
	int count = j-i;
	if(count == 1) {
		str[next_pos++] = c;
		return;
	}
	string count_str = to_string(count);
	str[next_pos++] = c;
	for(int k=0; k<count_str.length(); ++k) {
		str[next_pos++] = count_str[k];
	}
	
}

void compress(string &str)
{
	int i = 0;
	int next_pos = 0;
	while(i<str.length()) {
		char current = str[i];
		int j = i+1;
		while(j < str.length() && str[i] == str[j])
			++j;
		copy(str, i, j, current, next_pos);
		//cout << "i " << i << " j " <<j << " next_pos " << next_pos << endl;
		i = j;
	}
	str.resize(next_pos);
}
int main()
{
	string str = "abbbbbbbbbbbbbbbbccccccdddddd";
	compress(str);
	cout << str << endl;
}

- aj February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my java solution

public String compress(String word) {
char lastLetter = 0;
int lastLetterCounter = 0;
for (int i = 0; i < word.length() ; i++) {
char tempLetter = word.charAt(i);
if (tempLetter == lastLetter) {
if (++lastLetterCounter >= 2) {
word = word.substring(0, lastLetterCounter == 2 ? i : i - 1) + lastLetterCounter + word.substring(i+1);
}
} else {
lastLetterCounter = 1;
}
lastLetter = tempLetter;
}
return word;
}

- Andres February 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

public String compress(String word) {
		char lastLetter = 0;
		int lastLetterCounter = 0;
		for (int i = 0; i < word.length() ; i++) {
			char tempLetter = word.charAt(i);
			if (tempLetter == lastLetter) {
				if (++lastLetterCounter >= 2) {
					word = word.substring(0, lastLetterCounter == 2 ? i : i - 1) + lastLetterCounter + word.substring(i+1);
				}
			} else {
				lastLetterCounter = 1;
			}
			lastLetter = tempLetter;
		}
		return word;
	}

- Andres February 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public char[] compress(char[] A)
{
	int k = 0;
	for(int i = 0; i < A.length(); )
	{
		A[k] = A[i];
		int j = i + 1;

		while ((j < A.length()) && (A[i] == A[j]))
		{
			j++;
		}

		if(i < (j-1))
		{
			A[k+1] = j - i;
			k = k + 2;
			i = j;
		}
		else
		{
			i++;
			k++;

			if(i == A.length())
			{
				while(k < A.length())
				{
					A[k] = null;
					k++;
				}
			}
		}
	}

	return A;
}

- KunalP March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

input = list("FOOFFFIGHTERS")

def compress(input):
    print input
    if not input or len(input) < 1:
        return input
    cur_char = input[0]
    start_index = 0
    for index in range(1, len(input)):
        if cur_char != input[index]:
            if start_index + 1 == index:
                pass
            else:
                input[start_index + 1] = chr(index - start_index + ord('0'))
            cur_char = input[index]
            start_index = index
        else:
            input[index] = '$'
    last_good_index = 0
    for index in range(1, len(input)):
        if input[index] != '$':
            input[last_good_index + 1] = input[index]
            last_good_index = last_good_index + 1
    for index in range(len(input)-1, last_good_index, -1):
        del input[index]
    
    return input

compress(input)
print input

Output:

['F', 'O', 'O', 'F', 'F', 'F', 'I', 'G', 'H', 'T', 'E', 'R', 'S']
['F', 'O', '2', 'F', '3', 'I', 'G', 'H', 'T', 'E', 'R', 'S']

Complexity O(N), Space: O(1)

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

#include<stdio.h>

void compressString(char *string1);

int main(void)
{

	char a[30] = "nno";
	
	printf("%s\n", a);
	compressString(a);
	printf("%s\n", a);

	return 0;

}

void compressString(char *string1)
{

	int count;

	int buffer;
	int prev;
	int curr;

	buffer = 0;
	prev = 0;
	curr = 1;

	count = 0;

	while(string1[curr] != '\0')
	{

		if(string1[curr] == string1[prev])
		{
			count += 1;
		}
		else
		{
			string1[buffer++] = string1[prev];
			if(count)
			{
				string1[buffer++] = (count+1) + '0';
			}

			count = 0;
			prev = curr;
		}

		curr += 1;

	}

	// Flush

	string1[buffer++] = string1[prev];
	if(count)
	{
		string1[buffer++] = (count+1) + '0';
	}
	string1[buffer++] = '\0';

}

- Alejandro Gonzalez P April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(1) Space, O(n) time complexity

public String getCompressedString(String stringToCompress){
		StringBuilder sb = new StringBuilder(stringToCompress);
		char prev = sb.charAt(0);
		int count = 0;
		int j = 0;
		for(int i = 0; i < sb.length(); i++){
			if(prev == sb.charAt(i)){
				count++;
			} else {
				if(count == 1){
					sb.replace(j, j+1, String.valueOf(prev));
					j++;
				} else {
					sb.replace(j, j+2, String.valueOf(prev) + String.valueOf(count));
					j = j + 2;
				}
				prev = sb.charAt(i);
				count = 1;
			}
		}
		if(count > 1){
			sb.replace(j, j+2, String.valueOf(prev) + String.valueOf(count));
			j = j + 2;
		} else {
			sb.replace(j, j+1, String.valueOf(prev));
			j++;
		}
		return sb.substring(0,j);
	}

- Abhishek Kothari May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

BBBCCCAAAAUUUAAABBBDEF will be converted to B3C3A4U3A3B3DEF. Is this correct assumption?

- Victor February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think that's what they asked.

- samuel February 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here is one solution
Read the string (Char[]) from the end to the front and modified the char[] in place from the end to front.

public static String compressString(String in){
	    char[] inChars = in.toCharArray();
	    int index = inChars.length - 2;
	    char last = inChars[index+1];
	    int indexEnd = index+1;
	    int count = 1;
	    
	    while(index >= 0)
	    {
	        if (inChars[index]==last)
	        {
	            count++;
	        }
	        else
	        {
	            if(count > 1)
	            {
	                char[] countChars = Integer.toString(count).toCharArray();
	                System.arraycopy(countChars, 0, inChars, indexEnd-countChars.length+1, countChars.length);
	                inChars[indexEnd-countChars.length] = last;
	                indexEnd = indexEnd-countChars.length-1;
	            }
	            else
	            {
	                if(inChars[indexEnd] != last)
	                {
	                    inChars[indexEnd] = last;
	                }
	                indexEnd--;   
	            }
	            last = inChars[index];
	            count = 1;
	        }
	        index--;
	    }
	    if(count > 1)
	    {
            char[] countChars = Integer.toString(count).toCharArray();
            System.arraycopy(countChars, 0, inChars, indexEnd-countChars.length+1, countChars.length);
            inChars[indexEnd-countChars.length] = last;
            indexEnd = indexEnd-countChars.length;
	    }
	    else
	    {
	        if(inChars[indexEnd] != last)
	        {
	            inChars[indexEnd] = last;
	        }
	        
	    }
	    char[] resArray = new char[inChars.length - indexEnd];
	    System.arraycopy(inChars, indexEnd, resArray,0, resArray.length);
	    return new String(resArray);
	}

- Anonymous February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

private static String compress(char[] input) {
		if (input == null )  return null;
		if (input.length == 1) return String.valueOf(input);
		StringBuilder result = new StringBuilder();
		int p = 0;
		for ( int i = 1; i < input.length; ++ i) {
			if ( input[i] != input[p] ) {				
				result.append(input[p]);
				if (i-p > 1) {	
					result.append(String.valueOf(i-p));
					p+=(i-p);
				} else {
					p++;
				}
			}
		}
		result.append(input[input.length-1]);
		if (p < input.length-1) {
			result.append(String.valueOf(input.length-p));
		}
	return result.toString();
	}

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

Not good. OP calls for "You also have to make sure that you are not using extra memory."

With the StringBuilder you'd end up using as much extra memory as the original string in worst case. Plus overhead.

- shinjin February 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class CompressString {

	/**
	 * @param args
	 * You are given a string FOOFIGHTERS.
	 *  You have to come up with an algorithm that will compress this string.
	 *  You also have to make sure that you are not using extra memory. 
	 *  For example: FOOFIGHTERS will be compressed as FO2FIGHTERS. 
	 *  You should not use another array or bitfield to keep a frequency count for the individual letters.
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CompressString cs = new CompressString();
		cs.compress();
	}

	private void compress() {
		String s = "ffreesourrrrrrcecooomkhhhggggyutttkkkkkk";
		char arr[] = s.toCharArray();

		int arrayLength = arr.length;
		int pointer1 = 0;
		int pointer2 = 0;
		char element = '\0';
		int count = 1;
		for (int i = 0; i < arrayLength; i++) {
			if (i > 0) {
				if (arr[i] == arr[i - 1]) {
					if (pointer1 == 0) {
						if (pointer2 > 0) {
							pointer1 = pointer2 + 1;
						} else {
							pointer1 = i;
						}
					}
					count++;
				} else {
					if (count > 2) {
						pointer2 = pointer1;
						arr[pointer1] = (char) ('0' + count);
						pointer1 = 0;
						count = 1;
					} else if (count == 2) {
						if (pointer2 > 0) {
							pointer2 = pointer1;
						}
						arr[pointer1] = (char) ('0' + count);
						pointer1 = 0;
						count = 1;
					}
				}

				if (pointer2 > 0 && count == 1) {
					pointer2++;
					arr[pointer2] = arr[i];
				}

			}
		}

		if (pointer2 > 0) {
			if (count > 1) {
				arr[++pointer2] = (char) ('0' + count);
			}
			for (int i = (pointer2 + 1); i < arrayLength; i++) {
				arr[i] = '\0';
			}
		}

		for (char c : arr) {
			System.out.print(c + " ");
		}
	}

}

- Ankit Garg February 23, 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