CareerCup

1) seperate alphabet /number/others
like dutch flags problem
2) sort alphabets part

void partition(int a[], int n)
{
int low==0,mid=0,high=n-1;
while(mid<high)
{
switch(a[mid])
{
case 0:
swap(&a[low++],a[mid]);
break;
case 1:
mid++;
break;
case 2:
swap(&a[high--],&a[mid]);
break;
}
}
}

i would have 3 empty strings at the beginning one for storing letters, one for numbers and one for symbols.

then loop on the input string, append each character to its corresponding string. then sort each of the 3 strings. and concatenate them in the required order.

it will be in O(n log n) time and O(n) space

Since when they started asking such questions. Did you tag the company name correctly?

we can use hashing for the alphabets then it will be a O(n) algo simply

1.
i) Create a char array of size 26 for hashing the occurences of the letters.
ii) Create an array ( depends upon the number of special characters ) for storing the special
characters. ( I assume that there is no sorted order for them, though even if there was one, it
could be handled ).
iii) A temporary int variable would hold the sum.

2. Traverse the given array.
i) Hash the occurences of the alphabets by maintaining a count.
ii) Append the special characters to the array allocated for them.
iii) Keep updating the sum as and when you encounter a number.

3. Printing remains.
i) Traverse the alphabet array in order printing the occurences of the letters.
ii) Print the sum.
iii) The special character string may now be printed as well.

O(N) time and constant space.

1.
i) Create a char array of size 26 for hashing the occurences of the letters.
ii) Create an array ( depends upon the number of special characters ) for storing the special
characters. ( I assume that there is no sorted order for them, though even if there was one, it
could be handled ).
iii) A temporary int variable would hold the sum.

2. Traverse the given array.
i) Hash the occurences of the alphabets by maintaining a count.
ii) Append the special characters to the array allocated for them.
iii) Keep updating the sum as and when you encounter a number.

3. Printing remains.
i) Traverse the alphabet array in order printing the occurences of the letters.
ii) Print the sum.
iii) The special character string may now be printed as well.

O(N) time and constant space.

Scala version

def printSpecial(s:String)= {
    val charRange = ('a' to 'z') ++ ('A' to 'Z')
    val numberRange = ('0' to '9')
    def _group(todo:List[Char], chars:List[Char], specialChars:List[Char], sum:Int, fOnFinish:(List[Char], List[Char], Int)=>Unit):Unit = {
      todo match {
        case head::tail=>
          if (charRange contains head) {
            _group(tail, chars :+ head, specialChars, sum, fOnFinish)
          } else if (numberRange contains head) {
            _group(tail, chars, specialChars, sum + head.asDigit, fOnFinish)
          } else {
            _group(tail, chars, specialChars :+ head, sum, fOnFinish)
          }
        case _ => fOnFinish(chars,specialChars,sum)
      }
    }
    _group(s.toList, Nil, Nil, 0, (chars, special, sum) => {
        print(chars.sortBy(_.asDigit).foldLeft("")(_+_))
        print(sum)
        println(special.foldLeft("")(_+_))
      })
  }

import java.util.Arrays;

public class Example {
/*public static void main(String... args) {
String pratp="";

pratp.getChars(0,pratp.length(), char[] dst, 0);
System.out.println();
//for(){
//System.out.println(x + " " + y + " ");
}*/
public static void main(String[] args){
String str = "CAE2W3@D#";
int sum=0;
char[] arr = new char[str.length()];
char[] arr1 = new char[str.length()];
char[] arr2 = new char[str.length()];
str.getChars(0, str.length(), arr, 0);
System.out.print("The Character array equals: ");
System.out.println(arr);
int st1 = 0;
int st2 = 0;
for(int i=0;i<arr.length;i++){
char temp=arr[i];
if(Character.isLetter(temp)){
System.out.println(temp +"is Letter on index" +i);
arr1[st1]=temp;
st1++;
//st1.append(arr[i]);
}
else if(Character.isDigit(temp)){
System.out.println(arr[i] +"is digit on index" +i);
int n=Integer.valueOf(temp+"");
System.out.println("int value is :"+n);
sum=sum+n;
}
else{
System.out.println(temp] +"is SPL Char on index" +i);
//arr2.add(arr[i]);
arr2[st2]=temp;
st2++;
//st2.append(arr[i]);
}
}
Arrays.sort(arr1);
System.out.print(arr1);
System.out.print(sum);
System.out.print(arr2);
}
}