CareerCup

C++ solution using the STL's output string stream class. You didn't specify what to do when there is a single letter. I think the common way is to make it "1a" (it gets bigger).

string Compress(const string& s) {
	ostringstream oss;
	for (size_t j, i = 0; i < s.size(); i = j) {
		for (j = i+1; j < s.size() && s[j]==s[i]; j++)
			; // all the work is done in the previous line
		oss << j-i << s[i]; // add the count and letter
	}
	return oss.str(); // return the string representation
}

public String countCharecter(String str)
	{
		
		HashMap<Character, Integer> map= new HashMap<Character,Integer>();
		ArrayList<Character> arryList=new ArrayList<Character>();
		for(char c:str.toCharArray())
		{
			if(!arryList.contains(c))
				arryList.add(c);
			
			if(map.containsKey(c))
			{
				int i=map.get(c);
				map.put(c, ++i);				
			}
			else
				map.put(c, 1);
		}
		str="";
		for(int i=0;i<arryList.size();i++)
		{
			
			str=str+map.get(arryList.get(i))+arryList.get(i);
			
		}
		return str;

	}

String s="aaabbccc";
        StringBuilder sb=new StringBuilder();
        int count=1;
        for(int i=0,j=1;j<=s.length()-1;i++,j++){
            if(s.charAt(i)==s.charAt(j)){
                count++;
            }
            else{
                sb.append(count);
                sb.append(s.charAt(i));
                //sb.append(count+s.charAt(i));
                count=1;
            }
        }
        System.out.println(sb.toString());
    }

I think binary search (if the strings are sorted) can be done on this string to count one type of character.
If the string is like this
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbcccccccccccccccddddddddddddddddddddddddd
Here n=70
there are 4 types of characters(next character can be found as the neighbor of previous character counted)
4*log(70) = 7.38
This might be one of the solutions that interviewer was expecting.

A linear time solution is easy. What complexity class was the interviewer looking for?

+1 Myth. Please tell us what complexity you are looking for...

/// Single traverse with two itrs.
#include <iostream>

using namespace std;

int main()
{
std::string str = "aaabbcccddddd";

std::string::iterator itr1=str.begin();
std::string::iterator itr2=str.begin();

unsigned int repeateCnt = 0;
for(; itr2 != str.end(); ++itr2)
{
if(*itr1 == *itr2)
{
repeateCnt = repeateCnt + 1;
}
else
{
cout << repeateCnt << *itr1;
itr1 = itr2;
repeateCnt = 1;
}
}
cout << repeateCnt << *itr1;
}

Using map for chars and corresponding counts wont work, e.g input - aaabbaaabb ( 3a2b3a2b). Queue will suffice for this use-case.

Is there a condition where all a's, b's and c's are not in the same group. For example, one condition to this problem might as well be "aaabbccabbbc", which then amounts to "3a2b2c1a3b1c"?

If that is the case, the HashMap implementation will not work.

Here's an implementation based on that assumption:

/**
 * Use SIMPLE LOGIC for Converting this string str="aaabbccc" into str="3a2b3c".
 * ###Note:###
 * I gave 3 diff solutions to interviewer with loops,conditions etc.,But he
 * wanted a real OPTIMAL SOLUTION..lets see who'll write!!!!!
 *
 * Taken from careercup question 6074182194429952
 *
 */
package org.k0r0pt.prep.interview.amazon;

import java.util.HashMap;

/**
 * @author Xtreme
 *
 */
public class StringOp1 {
	
	/**
	 * Does the operation on the input String as is asked in the problem Statement.
	 * @param inputStr The input string to do the operation on.
	 * @return The result String after doing the operation on it.
	 */
	public String doTheOperation(String inputStr) {
		HashMap<Character, Integer> charCountMap = new HashMap<Character, Integer>();
		StringBuilder finalString = new StringBuilder();
		char[] charactersInInputStr = inputStr.toCharArray();
		char previousCharacter = 0;
		int i = 0;
		for(char character:charactersInInputStr) {
			if(previousCharacter == 0) {
				// This is the first iteration of this loop.
				charCountMap.put(character, ++i);
				previousCharacter = character;
				continue;
			}
			if(previousCharacter != character) {
				// Consolidate data for the character seen so far and start adding for the new one.
				finalString.append(charCountMap.get(previousCharacter));
				finalString.append(previousCharacter);
				// System.out.print(charCountMap.get(previousCharacter) + previousCharacter);
				charCountMap.remove(previousCharacter);
				i = 0;
				charCountMap.put(character, ++i);
				previousCharacter = character;
			} else {
				charCountMap.put(character, ++i);
			}
		}
		finalString.append(charCountMap.get(previousCharacter));
		finalString.append(previousCharacter);
		return finalString.toString();
	}
	
	/**
	 * Driver for our method. Typically, this would be in another class altogether.
	 * 
	 * @param args Y'know, command line arguments.
	 */
	public static void main(String[] args) {
		StringOp1 strOp1 = new StringOp1();
		String outputStr = strOp1.doTheOperation("aaabbcdddeefffaaabbdddccc");
		System.out.println(outputStr);
	}
}

static String convert(String s){
        char c;
        int count =0;
        StringBuilder sb = new StringBuilder();
        
        c = s.charAt(0);
        for(int i=1; i < s.length(); i++){
            count++;
            if(c != s.charAt(i)){
                sb.append(count + "" + c);
                c = s.charAt(i);
                count=0;
            }
        }
        sb.append(++count + "" + c);
        return sb.toString();
    }

I doubt if this can be done less than O(n) as in any case we would traverse entire array atleast once. O(n) solution seems preety straight forward.

Assume the characters in the string are not ordered, this code compact consecutive chars.

def transform(input):
	charFreq = [0]*26
	offsetSeq = []
	lo = None
	
	for char in input:
		offset = ord(char) - ord('a')
		charFreq[offset] += 1
		if(offset != lo):
			offsetSeq.append(offset)
			lo = offset
	
	result = ''
	for offset in offsetSeq:
		result += str(charFreq[offset]) + chr(ord('a') + offset)
		
	return result

public class 
Practice 
{
	/* In-place using a StringBuffer, single pass O(n) */
	public static String
	P
	(StringBuffer sb)
	{
		int  k = 0;
		for (int i = 0; i < sb.length();) {
			int length = 1;
			for (; length + i < sb.length() 
					&& sb.charAt(length + i) == sb.charAt(length+i-1); ++length);
			sb.setCharAt(k++, sb.charAt(i));
			if (length > 1) {
				String sub = Integer.toString(length);
				for (int j = 0; j < sub.length(); j++,k++)
					sb.setCharAt(k, sub.charAt(j));
			}
			
			i += length;
		}
		
		return sb.substring(0, k);
	}
}

count=1;
conv(char *str,char *str2){

int i=0;
int j=1;
int k=0;
loop:
while(str[i]==str[j]){
count++;
str++;
}
str2[k]=count;
count++;
k++;
str2[k]=str[i];
str++;
if(str[i]!='\0')
{
goto loop;
}


}

public class StringConverting {

	public static String encodeStr(String str) {
		int charposition = 0;
		int cursor = 0;
		StringBuilder result = new StringBuilder();
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(charposition) != str.charAt(cursor)) {
				result.append(cursor - charposition);
				result.append(str.charAt(charposition));
				charposition = cursor;
			}
			cursor++;
		}
		result.append(cursor - charposition);
		result.append(str.charAt(charposition));
		return result.toString();
	}

	public static void main(String[] args) {

		String str = "aaaabbcdddddddddzzzooo";
		System.out.println(encodeStr(str));

		str = "aaaa";
		System.out.println(encodeStr(str));
		
		str = "abcdefg";
		System.out.println(encodeStr(str));
	}
 
4a2b1c9d3z3o
4a
1a1b1c1d1e1f1g

string str = "vaaabbcccdmmmmm";
int charCount = 0;
string outputStr = "";
//0
if (str[0] != str[1])
{
outputStr += "1" + str[0];
}
for (int i = 1; i < str.Length-1; i++)
{
++charCount;
if (str[i] != str[i + 1])
{
outputStr += Convert.ToString(charCount) + str[i];
charCount = 0;
}
else
continue;
}
if (str[str.Length - 1] == str[str.Length - 2])
{
outputStr += Convert.ToString(++charCount) + str[str.Length - 1];
}
else
{
outputStr +="1" + str[str.Length - 1];
}

//code laguage C#
//string str = "3a2b3c";
private void computString()
{
string str = "vaaabbcccdmmmmm";
int charCount = 0;
string outputStr = "";
//0
if (str[0] != str[1])
{
outputStr += "1" + str[0];
}
for (int i = 1; i < str.Length-1; i++)
{
++charCount;
if (str[i] != str[i + 1])
{
outputStr += Convert.ToString(charCount) + str[i];
charCount = 0;
}
else
continue;
}
if (str[str.Length - 1] == str[str.Length - 2])
{
outputStr += Convert.ToString(++charCount) + str[str.Length - 1];
}
else
{
outputStr +="1" + str[str.Length - 1];
}
MessageBox.Show(outputStr);
}

private void computString()
{
string str = "vaaabbcccdmmmmm";
int charCount = 0;
string outputStr = "";
//0
if (str[0] != str[1])
{
outputStr += "1" + str[0];
}
for (int i = 1; i < str.Length-1; i++)
{
++charCount;
if (str[i] != str[i + 1])
{
outputStr += Convert.ToString(charCount) + str[i];
charCount = 0;
}
else
continue;
}
if (str[str.Length - 1] == str[str.Length - 2])
{
outputStr += Convert.ToString(++charCount) + str[str.Length - 1];
}
else
{
outputStr +="1" + str[str.Length - 1];
}
MessageBox.Show(outputStr);
}

{
string str = "vaaabbcccdmmmmm";
int charCount = 0;
string outputStr = "";
//0
if (str[0] != str[1])
{
outputStr += "1" + str[0];
}
for (int i = 1; i < str.Length-1; i++)
{
++charCount;
if (str[i] != str[i + 1])
{
outputStr += Convert.ToString(charCount) + str[i];
charCount = 0;
}
else
continue;
}
if (str[str.Length - 1] == str[str.Length - 2])
{
outputStr += Convert.ToString(++charCount) + str[str.Length - 1];
}
else
{
outputStr +="1" + str[str.Length - 1];
}
MessageBox.Show(outputStr);
}

{
string str = "vaaabbcccdmmmmm";
int charCount = 0;
string outputStr = "";
//0
if (str[0] != str[1])
{
outputStr += "1" + str[0];
}
for (int i = 1; i < str.Length-1; i++)
{
++charCount;
if (str[i] != str[i + 1])
{
outputStr += Convert.ToString(charCount) + str[i];
charCount = 0;
}
else
continue;
}
if (str[str.Length - 1] == str[str.Length - 2])
{
outputStr += Convert.ToString(++charCount) + str[str.Length - 1];
}
else
{
outputStr +="1" + str[str.Length - 1];
}
MessageBox.Show(outputStr);
}

private void computString()
{
string str = "vaaabbcccdmmmmm";
int charCount = 0;
string outputStr = "";
//0
if (str[0] != str[1])
{
outputStr += "1" + str[0];
}
for (int i = 1; i < str.Length-1; i++)
{
++charCount;
if (str[i] != str[i + 1])
{
outputStr += Convert.ToString(charCount) + str[i];
charCount = 0;
}
else
continue;
}
if (str[str.Length - 1] == str[str.Length - 2])
{
outputStr += Convert.ToString(++charCount) + str[str.Length - 1];
}
else
{
outputStr +="1" + str[str.Length - 1];
}
MessageBox.Show(outputStr);
}
}

private void computString()
{
string str = "vaaabbcccdmmmmm";
int charCount = 0;
string outputStr = "";
//0
if (str[0] != str[1])
{
outputStr += "1" + str[0];
}
for (int i = 1; i < str.Length-1; i++)
{
++charCount;
if (str[i] != str[i + 1])
{
outputStr += Convert.ToString(charCount) + str[i];
charCount = 0;
}
else
continue;
}
if (str[str.Length - 1] == str[str.Length - 2])
{
outputStr += Convert.ToString(++charCount) + str[str.Length - 1];
}
else
{
outputStr +="1" + str[str.Length - 1];
}
MessageBox.Show(outputStr);
}
}

void Replace(char *s)
{
 char *q=s;
 int cnt=1;
 int i=0;
 while(*q)
 {
  if(*q==*(q+1))
  {
    q++;
    cnt++;
  }
  else
  {
    s[i++]=cnt+'0';
    s[i++]=*q;
    q++;
    cnt=1;
  }
 }
 s[i]='\0';
}
int main()
{
  char *s="aaabbccc";
   Replace(s);
  puts(s);
   return 1;
}

public static void main(String[] args) {


        String input="aaaabbbbcccceeee";
        char[] charArr= input.toCharArray();

        int counter=1;

        int charCounter=1;

        int loopCount=0;
       // System.out.print("charArr.length : "+charArr.length);
         while(counter<charArr.length)
         {
             loopCount++;

            try
            {
                if(charArr[counter-1]!=charArr[counter])
                {
                    System.out.print(charCounter+""+charArr[counter-1]);
                    counter++;
                    charCounter=1;
                   // System.out.println("counter2 : "+counter);
                }

                if(charArr[counter-1]==charArr[counter]&& charArr[counter]==charArr[counter+1]&&charArr[counter]==charArr[counter+2])
                {

                   // System.out.println("charArr[counter] : "+charArr[counter]);
                   // System.out.println("charArr[counter++] : "+charArr[counter++]);
                    charCounter++;
                    charCounter++;
                    charCounter++;
                    counter++;
                    counter++;
                    counter++;

                    if(counter==charArr.length)
                    {
                        System.out.print(charCounter+""+charArr[counter-1]);
                    }
                   // System.out.println("counter1 : "+counter);
                }
                else if(charArr[counter-1]==charArr[counter]&& charArr[counter]==charArr[counter+1])
             {

                // System.out.println("charArr[counter] : "+charArr[counter]);
                // System.out.println("charArr[counter++] : "+charArr[counter++]);
                 charCounter++;
                 charCounter++;
                 counter++;
                 counter++;
                // System.out.println("counter1 : "+counter);
                 if(counter==charArr.length)
                 {
                     System.out.print(charCounter+""+charArr[counter-1]);
                 }
             }
             else if(charArr[counter-1]==charArr[counter])
             {

                // System.out.println("charArr[counter] : "+charArr[counter]);
                // System.out.println("charArr[counter++] : "+charArr[counter++]);
                 charCounter++;
                 counter++;
                // System.out.println("counter1 : "+counter);
                 if(counter==charArr.length)
                 {
                     System.out.print(charCounter+""+charArr[counter-1]);
                 }
             }


         }
            catch(Exception e)
            {
                if(e instanceof  java.lang.ArrayIndexOutOfBoundsException)
                {
                    System.out.print(charCounter+""+charArr[counter-1]);
                    counter=charArr.length;
                }

            }
         }





    }

Eff: o(n) < n

}

String str = "abbddccdc";
		String result = "";
		int index;
		boolean[] visitedIndexs = new boolean[str.length()];
		result = "";
		char current;
		int count = 1;
		for (int i = 0; i < str.length(); i++) {
			current = str.charAt(i);
			index = i;
			count = 1;
			if (visitedIndexs[i] == true)
				continue;
			while (true) {
				visitedIndexs[index] = true;
				index = str.indexOf(current, index + 1);
				if (index == -1)
					break;
				count++;
			}
			result = result + current + count;

		}

will this work?

public class SequenceCount{
	public static void main(String[] args){
		String s = "aaabbccc";
		int len = s.length();
		for(int i=0, count=1; i<len; i++){
			if(s.charAt(i) == ((i == len - 1) ? '\0' : s.charAt(i+1))){
				count++;
			}else{
				System.out.print(String.format("%d%c", count, s.charAt(i)));
				count = 1;
			}
		} 
	}
}

Using Array:

//conversion of string
//Use SIMPLE LOGIC for Converting this string str="aaabbccc" into str="3a2b3c".

public class Compression{
public static void main(String[] args){
char a[] = {'a','a','a','b','b','b','b','c','c','d','d','d','d','d','d','e','e'} ;
int sum = 1;
for(int i =0; i<(a.length-1); i++){

if(a[i+1]==a[i])
{
sum = sum +1;

if(i==a.length-1)
System.out.print(sum+""+a[i]);
}
else
{
System.out.print(sum+""+a[i]);
sum = 1;
}
}
}
}

public static String CmpString(String s)
{
	char[] set = s.toCharArray();
	char value = set[0];
	int count = 1;
	StringBuffer result = new StringBuffer();
	for(int i = 1; i < set.length; i++)
	{
		if(set[i] == value)
		{
			count++;
		}
		else
		{
			result.Append(count);
			result.Append(value);
			value = set[i];
			count = 1;	
		}
	}
	result.Append(count);
	result.Append(value);
	
	String = result.toString();

}

public string alphcount(String s){

char[] ch = s.toCharArray();
String sb = new String();

for(int i=0;i<ch.length;i++){
int j =((str.lastIndexOf(ch[i]))-i)-1;
sb=sb+j+Character.toString(ch[i]);
i=j;
}

return sb;
}

public static String compressStr(String s) {
int start = 0, end = 1;
int count = 1;
if (s.length() < 2)
return s;
StringBuilder sb = new StringBuilder();
while (start < s.length() && end < s.length()) {
while (end < s.length() && s.charAt(end) == s.charAt(start)) {
end++;
count++;
}
sb.append(new Integer(count).toString());
sb.append(s.charAt(start));
start = end;
end = start + 1;
count = 1;
}
return sb.toString();
}

A simple implementation using strings:

public class Dump 
{
	public static void main(String[] args) 
	{
		String str1 = "aaabbccc";
		char start;
		int count = 1;
		start = str1.charAt(0);
		for(int i=0; i<str1.length()-1; i++)
		{
			if(str1.charAt(i+1) == start)
			{
				count = count + 1;
			}
			else
			{
				System.out.print(count);
				System.out.print(start);
				start = str1.charAt(i+1);
				count = 1;
				
			}
		}
		System.out.print(count);
		System.out.print(start);
	}
	
}

This is my resolution and I shall explain why i use nextChar to solve this situation: abc, when I use sprintf, the point b will be replaced by '\0', so the while will terminated, so I need record this char.

#include<string>
#include<iostream>
using namespace std;

void compressStr(char* pStr) {
	int count;
	char* p = pStr;
	char* pNewStr = pStr;
	char temp, nextChar;
	while (*p) {
		count = 0;
		temp = *p;
		while (*p == temp) {
			count++;
			p++;
		}
		nextChar = *p;
		if (count > 1) {
			sprintf(pNewStr, "%d%c", count, temp);
		} else {
			sprintf(pNewStr, "%c", temp);
		}	
		pNewStr += strlen(pNewStr);
		*pNewStr = nextChar;
	}
}

int main(int argc, char* argv[]) {
	char str[] = "aaabbbcccd";
	compressStr(str);
	cout << str << endl;
	cin.get();
	return 0;
}

That's a regexp task:

perl -le '$_="aaabbccc"; s/((.)\2*)/length($1).$2/ge ; print'                             
3a2b3c

Enjoy,

Assuming that its a char array -- aaabbccc to 3a2b3c

keep a counter for the current item ('a') .. convert this into equivalent string
Here for a it will be 3 numerical converted to '3' .
Now you know the index_1 you are in and the space required to put '3a' and keep another counter for the real index_2 in the original string. [I meant in place changing]

Now the problem comes when the integer bound is crossed and when a single alphabet happens to be appearing 20 or 100 times... you need to calculate the space correctly, by dividing the number by 10, till it becomes zero... to find the space required..

keep going till you hit '\0' and when you hit, mark the index_2 position as '\0' in place, No extra memory needed.

By using Regular expression and recursion you can solve this problem easily. My answer is:
You can call the GetResult("pqaaaaabbbcccc", 0, result); from any method :)


static void GetResult(string InputData, int StartAt, StringBuilder Result)
{
if (StartAt >= InputData.Length)
return;

string matchResult = new Regex(@"((.)\2*)").Match(InputData, StartAt).Value;

GetResult(InputData, StartAt + matchResult.Length, Result.Append(string.Format("{0}{1}", matchResult.Length, matchResult.ToCharArray()[0])));
}

By using Regular expression and recursion you can solve this problem easily. My answer is:
You can call the GetResult("pqaaaaabbbcccc", 0, result); from any method :)


static void GetResult(string InputData, int StartAt, StringBuilder Result)
{
if (StartAt >= InputData.Length)
return;

string matchResult = new Regex(@"((.)\2*)").Match(InputData, StartAt).Value;

GetResult(InputData, StartAt + matchResult.Length, Result.Append(string.Format("{0}{1}", matchResult.Length, matchResult.ToCharArray()[0])));
}

static void GetResult(string InputData, int StartAt, StringBuilder Result)
        {
            if (StartAt >= InputData.Length)
                return;
            
            string matchResult = new Regex(@"((.)\2*)").Match(InputData, StartAt).Value;

            GetResult(InputData, StartAt + matchResult.Length, Result.Append(string.Format("{0}{1}", matchResult.Length, matchResult.ToCharArray()[0])));
        }

static void GetResult(string InputData, int StartAt, StringBuilder Result)
        {
            if (StartAt >= InputData.Length)
                return;
            
            string matchResult = new Regex(@"((.)\2*)").Match(InputData, StartAt).Value;

            GetResult(InputData, StartAt + matchResult.Length, Result.Append(string.Format("{0}{1}", matchResult.Length, matchResult.ToCharArray()[0])));
        }

THIS IS ALL I HAVE NOW..HELP ME..

initially i counted from str..

char x='a';
char y='b';
char z='c';

1)first count the chars in str
for(i=0;i<n;i++){
if(str[i]==x)
{
ct++;
}
}
//same fr next 2 letters..
for(i=0;i<n;i++){
if(str[i]==y)
{
ct++;
}
}//next
for(i=0;i<n;i++){
if(str[i]==z)
{
ct++;
}
}

counts: a=3,b=2,c=3(chk ques)

2)next i wrote like ,

if(count==3)
{
printf("the count is %d%c:"countof(x),char);//shld return an err;i dnt knw 2 hw 2 declare..and get 3.a(count of a.char)
}

so on..Any better soln??SRY FR ANY BUGS I explained him concept only...

1) Use a map of <char,int>
2) Traverse the array. Add the char and occurrence count to the map.
3) Again traverse the array . Using the map,modify the array.

struct table
{
	int cnt;
	char c;
	table(int i,char j):cnt(i),c(j) {};
};

void EditString(char *s)
{
	try
	{
		if(!*s) throw "\nNull String\n";
	}catch(const char *p)
	{
		puts(p);
		return;
	}
	int count=1;
	int i,j;

	queue<table>q;

	for(i=0;i<n;i++)
	{
		if(s[i]==s[i+1])
			count++;
		else
		{
			table t(count,s[i-1]);
			q.push(t);
			count=1;
		}
	}
	i=0;

	while(!q.empty())
	{
		table t=q.front();
		q.pop();
		s[i++]=(char)t.cnt;
		s[i++]=t.c;
	}
	for(j=i;j<n;j++)
		s[j]=(char)0;
	s[j]='\0';
}

what that single letter case..
Ex: abc what is the output expected in that case i guess output should be "abc".I have taken this assumption into consideration.
void Convert(char str[],int len)
{
char check=str[0];
int count=1;
int i=0,start=0;
for(i=1,start=0;i<len;i++)
{
if(str[i]==str[i-1])
count++;
else
{
if(count!=1)
str[start++]='0'+count;
str[start++]=str[i-1];
count=1;
}
}
if(count!=1)
str[start++]='0'+count;
str[start++]=str[i-1];
memset(str+start,0,len-start);
}

Wow. 3 different, using LOOPS and CONDITIONS!!!!!!!!!!!!!!!!!
AWESOME!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

You just need to convert the string str="aaabbccc" into str="3a2b3c"? Using simple logic?

String str="aaabbccc"
String str="3a2b3c"

:D