Facebook Interview Question
Developer Program EngineersCountry: India
Considering how poor the question was formulated with all those typos I assume the last 'A' is a typo and it should be 'CAE2W3D'. Btw, it can be solved in linear time: assume only upper-case characters and numbers. Iterate over input and count occurrences of letters (~ bucket sort); plus maintain a sum variable for cases a number is encountered. At the end go over occurrences array and at the end append sum.
public static void main(String[] args) {
assert "ACDEW5".equals(sort("CAE2W3D"));
}
private static String sort(String str) {
if (str.length() == 0) {
return str;
}
int[] occs = new int[26];
int sum = 0;
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch >= 'A' && ch <= 'Z') {
occs[ch - 'A']++;
} else {
sum += ch - '0';
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < occs.length; i++) {
char ch = (char) ('A' + i);
while (occs[i] > 0) {
sb.append(ch);
occs[i]--;
}
}
if (sum > 0) {
sb.append(sum);
}
return sb.toString();
}
howz this ?
import java.util.*;
import java.io.*;
public class prac
{
public static void main(String[] args)
{
String s = "CAE2W3D";
char[] arr = s.toCharArray();
Arrays.sort(arr);
int sum = 0;
for (int i=0;i<arr.length ;i++ )
{
if(Character.isLetter(arr[i]))
{
System.out.print(arr[i]);
}
else
{
sum = sum + Character.getNumericValue(arr[i]);
}
}
System.out.print(sum);
System.out.println();
}
}
Or may be this ?
import java.util.*;
import java.io.*;
public class prac
{
public static void main(String[] args)
{
String s = "CAE2W3D";
char[] arr = s.toCharArray();
Arrays.sort(arr);
int sum = 0;
int pos = 0;
for (int i=0;i<arr.length ;i++ )
{
if(Character.isLetter(arr[i]))
{
arr[pos] = arr[i];
pos++;
}
else
{
sum = sum + Character.getNumericValue(arr[i]);
}
}
for (int i=0;i<pos ;i++)
{
System.out.print(arr[i]);
}
System.out.print(sum);
System.out.println();
}
}
Use an integer array of size 26 for 26 alphabets (whichever is required)
Keep marking (or adding for repititions) the characters at the right position as you visit them. (Neglect non-alphabets)
Print the characters in the array by iterating through its index while you also count for the number of set bits. Append with the counter.
public class StringAsAlphabetFB {
void sortAndSum(String str) {
int[] array = new int[26];
int sum = 0;
for (int i=0; i<26;i++)
array[i] = 0;
for (int i=0; i<str.length(); i++) {
str = str.toLowerCase();
char c = str.charAt(i);
if (c>='a' && c<='z') {
array[c-'a']++;
}
else if (c>='0' && c<='9') {
sum += Integer.parseInt(c+"");
}
}
for (int i=0; i<26; i++) {
while(array[i]-- > 0)
System.out.print((char) ('a' + i));
}
System.out.println(sum);
}
public static void main(String[] args) {
StringAsAlphabetFB s = new StringAsAlphabetFB();
s.sortAndSum("zertyAB4ER69");
}
}
Considering the input CAE2W3D, the following code gives the output as expected. This code works for any ASCII character other than alphabet.
private static void sortStringAndSumInt(String str) {
int[] charSet = new int[256];
int sum = 0;
for(int i=0; i<charSet.length; i++) {
charSet[i] = 0;
}
for(int i=0; i<str.length(); i++) {
int val = str.charAt(i);
if(!(val >= '0' && val <= '9')) {
charSet[val]++;
}
else {
sum = sum + (val-'0');
}
}
for(int i=0; i<charSet.length; i++) {
if(charSet[i] != 0) {
System.out.print((char)i);
}
}
System.out.print(sum);
}
Considering the input CAE2W3D, the following code gives the output as expected. This code works for any ASCII character other than alphabet.
private static void sortStringAndSumInt(String str) {
int[] charSet = new int[256];
int sum = 0;
for(int i=0; i<charSet.length; i++) {
charSet[i] = 0;
}
for(int i=0; i<str.length(); i++) {
int val = str.charAt(i);
if(!(val >= '0' && val <= '9')) {
charSet[val]++;
}
else {
sum = sum + (val-'0');
}
}
for(int i=0; i<charSet.length; i++) {
if(charSet[i] != 0) {
System.out.print((char)i);
}
}
System.out.print(sum);
}
{{
write a program to print the given string as alphabets in order next integres fallowed by sum
example: CAE2W3D is input and output should be
ACDEW5
void PrintStrAndNumSum(char *str)
{
int n = A.Length;
int offset = (int)'A';
int map[27];
for(int i = 0 ; i<27 ;i++)
map[i] = 0;
while(*str != '/0')
{
if(*str >= 'A' && *str <= 'Z')
map[(int)(*str - 'A')]++;
else
if(*str >='0' && *str <= '9')
map[26] += (int) (*str - '0');
else
{
// Charset is out of range
return -1;
}
}
for(int i = 0 ; i<26 ;i++)
{
while(map[i] > 0)
{
print('%c' , i + 'A');
map[i]--;
}
}
print("%d",map[26]);
}
}
}}
{{
write a program to print the given string as alphabets in order next integres fallowed by sum
example: CAE2W3D is input and output should be
ACDEW5
void PrintStrAndNumSum(char *str)
{
int n = A.Length;
int offset = (int)'A';
int map[27];
for(int i = 0 ; i<27 ;i++)
map[i] = 0;
while(*str != '/0')
{
if(*str >= 'A' && *str <= 'Z')
map[(int)(*str - 'A')]++;
else
if(*str >='0' && *str <= '9')
map[26] += (int) (*str - '0');
else
{
// Charset is out of range
return -1;
}
}
for(int i = 0 ; i<26 ;i++)
{
while(map[i] > 0)
{
print('%c' , i + 'A');
map[i]--;
}
}
print("%d",map[26]);
}
}
}}
void FacebookTest1()
{
const char const szInput[] = "CAE2W3A";
char tmp[26] = {0x00};
size_t sum = 0;
for( size_t i = 0; i < sizeof(szInput); i++ )
{
char chr = szInput[i];
size_t index = chr - 'A';
if( '0' <= chr && chr <= '9' )
{
sum += chr - '0';
}
else
{
if( 0x00 == tmp[index] )
{
tmp[index] = szInput[i];
}
}
}
for( size_t i = 0; i < 26; i++ )
{
if( tmp[ i ] )
{
cout << tmp[ i ];
}
}
cout << sum << endl;
}
First partition on 'A', based on ascii value of these characters.. that should return the index of 'A'.
and then right side will be alphabet, left would be numerics.. quick_sort the alphabet part (index of 'A' ...end)...and add the numerics (0.. index of 'A') and move to the end.
char a[] = {'C','D','E','2','W','3','A' };
char pivot = 'A',tmp;
int idx = 0, val = 0;
for(int i = 0;i<a.length;i++){
if(a[i]<pivot){
tmp = a[i];
a[i] = a[idx];
a[idx] = tmp;
idx++;
}
}
Arrays.sort(a, idx, a.length);
for(int i=0;i<idx;i++) val+=(a[i]-'0');
String ans = new String(a,idx,a.length-idx)+val;
System.out.println(" "+ ans);
#include "stdio.h"
#include "string.h"
#include "malloc.h"
#define NUMBER_OF_ALPHABET 27
char * reorder(char * str) {
int i,j =0;
int * a =(int *) calloc(sizeof(int), NUMBER_OF_ALPHABET + 1);
char * s = (char *) calloc(sizeof(char), strlen(str));
for(i = 0; i < strlen(str); i ++) {
if ((int)str[i] <= 'Z' & (int)str[i] >='A'){
int index = (int) str[i] - 'A';
if (index >=0 && index <= NUMBER_OF_ALPHABET)
a[index]++;
}
else if(str[i]>='0' && str[i]<='9')
a[NUMBER_OF_ALPHABET] += (int)str[i] - '0';
}
for(i = 0; i< NUMBER_OF_ALPHABET; i++) {
while (a[i] > 0) {
s[j] = (char) (i + 'A');
j++;
i++;
}
}
if(a[NUMBER_OF_ALPHABET] > 0)
s[j] = (char) (a[NUMBER_OF_ALPHABET] + '0');
return s;
}
int main () {
char * test_string = "RADOE3F2";
printf("The original string is %s.\nThe ordered string is %s\n",
test_string,reorder(test_string));
return 0;
}
#include<iostream>
#include<conio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iterator>
#include<cstdlib>
#include<map>
#include<numeric>
using namespace std;
bool palindrome(string s)
{
return equal(s.begin(),s.end(),s.rbegin());
}
int main()
{
string kratos;
vector<int> vec;
kratos="nare12sh";
string::const_iterator iter;
for(iter=kratos.begin();iter!=kratos.end();iter++)
{
char p;
p=*iter;
char* g=&p;
int f=atoi(g);
if(f!=0)
vec.push_back(f);
}
int d=accumulate(vec.begin(),vec.end(),0);
cout<<d;
getch();
return 0;
}
#include <iostream>
#include <string>
using namespace std;
int main()
{
string inputStr;
string numericStr;
string alphaStr;
int numericStrLen = 0;
int alphaStrLen = 0;
cout << "Enter your string " << endl;
cin >> inputStr;
for (int i=0; i<inputStr.length(); i++)
{
if( toascii(inputStr.at(i)) < 58)
{
int j=0;
while(j<numericStr.length() && numericStr.at(j)<inputStr.at(i))
{
j++;
}
numericStr.insert(j,1,inputStr.at(i));
}
else
{
int j=0;
while(j<alphaStr.length() && alphaStr.at(j)<inputStr.at(i))
{
j++;
}
alphaStr.insert(j,1,inputStr.at(i));
}
}
cout << endl << alphaStr << numericStr << endl;
return 1;
}
void sort_alpha_sum_int(const char *str)
{
int ref_counts[256];
int sum;
int i;
memset(ref_counts, 0, sizeof(ref_counts));
while (*str != '\0') {
if (*str >= '0' && *str <= '9') {
sum += (int)(*str - '0');
} else {
ref_counts[(unsigned char)*str]++;
}
}
for (i = 0; i < 256; ++i) {
while(ref_counts[i]--) {
printf("%c", (char)i);
}
}
printf("%d\n", sum);
}
Give the order of letters and sum integers up followed, right? But how come the 'D' is here?
- xiaojian@buffalo.edu April 21, 2012