Sapient Corporation Interview Question Developer Program Engineers
Country: India
Interview Type: In-Person
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
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.
implementation in Java
public class TidyCharacters {
public static String tidy(String s){
int[] lettersFrequency = new int[26];
int digitsSum = 0;
StringBuilder specialChars = new StringBuilder();
for(char c:s.toCharArray()){
if( '0' <= c && c <= '9' ){
digitsSum += ( c - '0' );
} else if ( 'A' <= c && c <= 'Z' ){
lettersFrequency[c - 'A']++;
} else {
specialChars.append(c);
}
}
StringBuilder result = new StringBuilder();
for( int i=0;i<lettersFrequency.length;i++){
int count = lettersFrequency[i];
for( int j=0;j<count;j++){
result.append((char)('A'+i));
}
}
result.append(digitsSum);
result.append(specialChars);
return result.toString();
}
public static void main(String[] args){
System.out.println("<< "+args[0]);
System.out.println(">> "+tidy(args[0]));
}
}
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);
}
}
package interview.sort;
import java.util.Arrays;
public class sortAlphaNumberCharacter {
public static void main(String[] args) {
String input="CAE2W3@D#";
int len=input.length();
char [] arr=new char[len];
String output="";
int sum=0;
boolean digitPresent=false;
String specialOutput="";
for(int i=0;i<len;i++){
char c=input.charAt(i);
if(Character.isAlphabetic(c)){
arr[i]=c;
}else if(Character.isDigit(c)){
digitPresent=true;
sum=sum+Integer.parseInt(String.valueOf(c));
}else{
specialOutput=specialOutput.concat(String.valueOf(c));
}
}
Arrays.sort(arr);
for (char c : arr) {
output=output.concat(String.valueOf(c));
}
if(digitPresent)
output=output.concat(String.valueOf(sum)).concat(specialOutput);
else
output=output.concat(specialOutput);
System.out.println("output is "+output);
}
}
package interview.sort;
import java.util.Arrays;
public class sortAlphaNumberCharacter {
public static void main(String[] args) {
String input="CAE2W3@D#";
int len=input.length();
char [] arr=new char[len];
String output="";
int sum=0;
boolean digitPresent=false;
String specialOutput="";
for(int i=0;i<len;i++){
char c=input.charAt(i);
if(Character.isAlphabetic(c)){
arr[i]=c;
}else if(Character.isDigit(c)){
digitPresent=true;
sum=sum+Integer.parseInt(String.valueOf(c));
}else{
specialOutput=specialOutput.concat(String.valueOf(c));
}
}
Arrays.sort(arr);
for (char c : arr) {
output=output.concat(String.valueOf(c));
}
if(digitPresent)
output=output.concat(String.valueOf(sum)).concat(specialOutput);
else
output=output.concat(specialOutput);
System.out.println("output is "+output);
}
}
import java.util.*;
import java.lang.Character;
public class sortString {
public static void main(String[] args){
String inputStr;
Scanner in=new Scanner(System.in);
System.out.println("Enter String");
inputStr=in.nextLine();
char[] charArr=inputStr.toCharArray();
Arrays.sort(charArr);
String sorted= new String(charArr);
System.out.println("Entered String is::"+sorted);
int len =sorted.length();
System.out.println("Entered String length is::"+len);
String sC=new String();
String num=new String();
String alp=new String();
for(int i=0;i<len;i++){
char val=sorted.charAt(i);
//System.out.println("Entered String val is::"+val);
if(Character.isLetter(val)){
alp=alp+val;
System.out.println("Entered alp val is::"+alp);
}
else if(Character.isDigit(val)){
num=num+val;
System.out.println("Entered num val is::"+num);
}
else
{
sC=sC+val;
System.out.println("Entered sC val is::"+sC);
}
}
System.out.println("Final String is::"+alp+num+sC);
}
}
public class StringManipulation {
public static void main(String[] args) {
String a = "AB@CD^1AS^%HYUIO98@()(!@#";
StringBuffer sb_alpha = new StringBuffer();
StringBuffer sb_number = new StringBuffer();
StringBuffer sb_extra = new StringBuffer();
for (int i = 0; i <= a.length() - 1; i++) {
char b = a.charAt(i);
if (Character.isAlphabetic(b)) {
sb_alpha.append(b);
} else if (Character.isDigit(b)) {
sb_number.append(b);
} else {
sb_extra.append(b);
}
}
sb_alpha.append(sb_number).append(sb_extra);
System.out.println(sb_alpha);
}
}
package com;
import java.util.Arrays;
public class OrderString {
public static void main(String[] args) {
String input = "CAE2W3@D#";
String output = "";
String splOutput = "";
int sum = 0;
boolean isDigit = false;
for (char c : input.toCharArray()) {
if (Character.isDigit(c)) {
isDigit = true;
sum = sum + Integer.parseInt(String.valueOf(c));
} else if (Character.isLetter(c)) {
output = output.concat(String.valueOf(c));
} else {
splOutput = splOutput.concat(String.valueOf(c));
}
}
if (isDigit)
output = output + String.valueOf(sum);
output = output + splOutput;
char[] charArray = output.toCharArray();
Arrays.sort(charArray);
System.out.println("Sorted String " + output);
}
}
public class TidyCharaters1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("please enter string");
String s = sc.nextLine();
System.out.println(tidyCal(s));
}
public static StringBuilder tidyCal(String s){
Map<Character, Integer> charMap = new TreeMap<Character, Integer>();
int sum = 0;
StringBuilder specialChar = new StringBuilder();
for(char c : s.toCharArray()){
if(c >= '0' && c <= '9' ){
sum = sum + Character.getNumericValue(c);
}else if(c >='A' && c<='Z'){
charMap.put(c, (charMap.containsKey(c) ? charMap.get(c) + 1 : 1));
; }else{
specialChar.append(c);
}
}
Set<Character> set = new HashSet<Character>();
StringBuilder result = new StringBuilder();
// List<Character> charList = new ArrayList<Character>();
int i = 0;
set = charMap.keySet();
for(char c : set){
i = charMap.get(c);
for(int j = 0 ; j<i; j++){
result.append(c);
}
}
result.append(sum);
result.append(specialChar);
return result;
}
}
public class TidyCharaters1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("please enter string");
String s = sc.nextLine();
System.out.println(tidyCal(s));
}
public static StringBuilder tidyCal(String s){
Map<Character, Integer> charMap = new TreeMap<Character, Integer>();
int sum = 0;
StringBuilder specialChar = new StringBuilder();
for(char c : s.toCharArray()){
if(c >= '0' && c <= '9' ){
sum = sum + Character.getNumericValue(c);
}else if(c >='A' && c<='Z'){
charMap.put(c, (charMap.containsKey(c) ? charMap.get(c) + 1 : 1));
; }else{
specialChar.append(c);
}
}
Set<Character> set = new HashSet<Character>();
StringBuilder result = new StringBuilder();
// List<Character> charList = new ArrayList<Character>();
int i = 0;
set = charMap.keySet();
for(char c : set){
i = charMap.get(c);
for(int j = 0 ; j<i; j++){
result.append(c);
}
}
result.append(sum);
result.append(specialChar);
return result;
}
}
public class TidyCharaters1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("please enter string");
String s = sc.nextLine();
System.out.println(tidyCal(s));
}
public static StringBuilder tidyCal(String s){
Map<Character, Integer> charMap = new TreeMap<Character, Integer>();
int sum = 0;
StringBuilder specialChar = new StringBuilder();
for(char c : s.toCharArray()){
if(c >= '0' && c <= '9' ){
sum = sum + Character.getNumericValue(c);
}else if(c >='A' && c<='Z'){
charMap.put(c, (charMap.containsKey(c) ? charMap.get(c) + 1 : 1));
; }else{
specialChar.append(c);
}
}
Set<Character> set = new HashSet<Character>();
StringBuilder result = new StringBuilder();
// List<Character> charList = new ArrayList<Character>();
int i = 0;
set = charMap.keySet();
for(char c : set){
i = charMap.get(c);
for(int j = 0 ; j<i; j++){
result.append(c);
}
}
result.append(sum);
result.append(specialChar);
return result;
}
}
String alphanumeric = "CAE2W3@D#";
Pattern p = Pattern.compile("-?\\d+");
Matcher m = p.matcher(alphanumeric);
String alpha = alphanumeric.replaceAll("[^A-Za-z]", "");
String s = alphanumeric.replaceAll("[A-Za-z0-9]", "");
char[] alphaArry = alpha.toCharArray();
Arrays.sort(alphaArry);
int sum = 0;
while (m.find()) {
sum +=Integer.parseInt( m.group());
}
System.out.println(new String(alphaArry)+sum+s);
}
function sequenceString(input) {
let alphabet = [];
let intVal = 0;
let specialChar = [];
for (let i in input) {
if (parseInt(input[i], 10)) {
intVal += parseInt(input[i], 10);
} else if (input[i].toLowerCase().charCodeAt() >= 97 && input[i].toLowerCase().charCodeAt() <= 122) {
alphabet.push(input[i]);
} else {
specialChar.push(input[i]);
}
}
alphabet.sort((a, b) => {
if(a > b) {
return 1;
}
if(b > a) {
return -1;
}
return 0;
});
return `${alphabet.join('')}${intVal}${specialChar.join('')}`;
}
function sequenceString(input) {
let alphabet = [];
let intVal = 0;
let specialChar = [];
for (let i in input) {
if (parseInt(input[i], 10)) {
intVal += parseInt(input[i], 10);
} else if (input[i].toLowerCase().charCodeAt() >= 97 && input[i].toLowerCase().charCodeAt() <= 122) {
alphabet.push(input[i]);
} else {
specialChar.push(input[i]);
}
}
alphabet.sort((a, b) => {
if(a > b) {
return 1;
}
if(b > a) {
return -1;
}
return 0;
});
return `${alphabet.join('')}${intVal}${specialChar.join('')}`;
}
Javascript
function sequenceString(input) {
let alphabet = [];
let intVal = 0;
let specialChar = [];
for (let i in input) {
if (parseInt(input[i], 10)) {
intVal += parseInt(input[i], 10);
} else if (input[i].toLowerCase().charCodeAt() >= 97 && input[i].toLowerCase().charCodeAt() <= 122) {
alphabet.push(input[i]);
} else {
specialChar.push(input[i]);
}
}
alphabet.sort((a, b) => {
if(a > b) {
return 1;
}
if(b > a) {
return -1;
}
return 0;
});
return `${alphabet.join('')}${intVal}${specialChar.join('')}`;
}
function sequenceString(input) {
let alphabet = [];
let intVal = 0;
let specialChar = [];
for (let i in input) {
if (parseInt(input[i], 10)) {
intVal += parseInt(input[i], 10);
} else if (input[i].toLowerCase().charCodeAt() >= 97 && input[i].toLowerCase().charCodeAt() <= 122) {
alphabet.push(input[i]);
} else {
specialChar.push(input[i]);
}
}
alphabet.sort((a, b) => {
if(a > b) {
return 1;
}
if(b > a) {
return -1;
}
return 0;
});
return `${alphabet.join('')}${intVal}${specialChar.join('')}`;
}
1) seperate alphabet /number/others
- anonymous February 29, 2012like dutch flags problem
2) sort alphabets part