Google Interview Question
Principal Software EngineersCountry: United States
Interview Type: In-Person
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);
}
}
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)?
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.
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;
}
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++;
}
}
}
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;
}
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;
}
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;
}
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;
}
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)
#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';
}
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);
}
BBBCCCAAAAUUUAAABBBDEF will be converted to B3C3A4U3A3B3DEF. Is this correct assumption?
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);
}
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();
}
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 + " ");
}
}
}
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.
- Bhaskar February 21, 2014