Amazon Interview Question
Software Engineer in TestsCountry: India
Interview Type: Phone Interview
I think here you are adding digits, you are not treating consecutive digits as number. [ not expecting 4+5+6...expected this number needs to treat as 456]
Manan is correct. Simply codes what Manan does
#include <stdio.h>
#include <ctype.h>
int main () {
char str[] = "PST456DA85M2A!!23++46" ;
int size = sizeof (str), i = 0, pDigit = 0, cur = 0, sum = 0 ;
while ( i < size ) {
if ( isdigit(str[i]) )
cur = (cur*10) + (str[i]-'0') ;
else {
if ( cur ) {
printf ("\nNumber is : %d", cur ) ;
sum += cur ;
cur = 0;
}
}
i ++ ;
}
printf ( "\nSum is : %d", sum ) ;
getchar () ;
return 0;
}
I guess, here you are missing one corner case, suppose last character of input string is digit, in that case you will miss the last integer of String.
int find_sum(char* s)
{
int sum=0;
int temp_sum=0;
while((*s)!='\0')
{
if((*s)>='0'&&(*s)<='9')
{
temp_sum=10*temp_sum+(*s)-'0';
}
else
{
sum=sum+temp_sum;
temp_sum=0;
}
++s;
}
sum=sum+temp_sum;
return sum;
}
@Anonymous on August 29, 2012 Code is working perfectly.
Since i m using char arr[] and sizeof operator it will return strlen(arr) + 1. So edge cases are covered.
But if i use char *arr for initialization and then use strlen then i have to cover the edge case. You can also try.
#include <iostream>
using namespace std;
int main () {
char str[] = "PST456DA85M2A!!23++46" ;
int size = strlen(str),prev=0, sum = 0 ;
printf ( "size is : %d\n", size) ;
for(int i=0;i<size;i++)
{
if(str[i]=='0'||str[i]=='1'||str[i]=='2'||str[i]=='3'||str[i]=='4'||str[i]=='5'||str[i]=='6'||str[i]=='7'||str[i]=='8'||str[i]=='9')
{
prev=prev*10+(str[i]-'0');
printf ( "prev is : %d\n", prev) ;
}
else
{
sum+=prev;
prev=0;
printf ( "sum is :%d %d\n",i, sum) ;
}
}
sum+=prev;
printf ( "\nSum is : %d", sum ) ;
system("pause");
}
#include<stdio.h>
int find_sum(char*s);
main()
{
char s[100];
scanf("%s",s);
printf("\nSum = %d",find_sum(s));
}
int find_sum(char* s)
{
int sum=0;
int temp_sum=0;
while((*s)!='\0')
{
if((*s)>='0'&&(*s)<='9')
{
temp_sum=10*temp_sum+(*s)-'0';
}
else
{
sum=sum+temp_sum;
temp_sum=0;
}
++s;
}
sum=sum+temp_sum;
return sum;
}
Make a char string to integer converter :
int convert( char *a, int offset )
{
int i, num;
num = 0;
for( i = 0; i <= offset; i++ ) {
num = num*10 + ( a[i]-'0' );
}
return num;
}
Parse the char array, if you find a digit ( base ) then find its offset ( number of consecutive digits after that ). Convert string from base to base+offset into integer using your function. Keep adding the sum of integers. For finding next integer, start search from base+offset in the char array.
I just gave hint, its OP's responsibility to complete it himself and learn the way of solving.
Thanks....but what I am really looking is it the optmized way of Programming....I know the solution...but looking at writing this program with minimum number of iterations..
void getTotalSum(char* pString)
{
if(!pString)
printf("\nNot valid");
int finalSum = 0;
int Sum = 0;
while(pString != '\0')
{
Sum = 0;
while((*pString <= 57) && (*pString <= 48))
{
Sum = Sum*10 + *pString - '0';
pString++;
}
finalSum = finalSum + Sum ;
}
printf("%d",finalSum );
}
this code won't work as the pointer is not increasing when it contains non-digit character...
#include <iostream>
using namespace std;
int main () {
char str[] = "PST456DA85M2A!!23++46" ;
int size = strlen(str),prev=0, sum = 0 ;
printf ( "size is : %d\n", size) ;
for(int i=0;i<size;i++)
{
if(str[i]=='0'||str[i]=='1'||str[i]=='2'||str[i]=='3'||str[i]=='4'||str[i]=='5'||str[i]=='6'||str[i]=='7'||str[i]=='8'||str[i]=='9')
{
prev=prev*10+(str[i]-'0');
printf ( "prev is : %d\n", prev) ;
}
else
{
sum+=prev;
prev=0;
printf ( "sum is :%d %d\n",i, sum) ;
}
}
sum+=prev;
printf ( "\nSum is : %d", sum ) ;
system("pause");
}
private static void countSum() {
String s = new String("PST456DA85M2A!!23++46");
String strDigit = "";
int sum = 0;
for (int i = 0; i < s.length(); i++) {
Character charAt = (Character)s.charAt(i);
if (Character.isDigit(charAt)) {
strDigit +=charAt;
} else {
if (strDigit.equals("") == false) {
sum = sum + new Integer(strDigit);
strDigit = "";
}
}
}
System.out.println(sum);
}
Java Code by using Pattern and matcher.
static int findSum(String inputStr){
int sum=0;
Pattern p = Pattern.compile("[0-9]+");
Matcher m =p.matcher(inputStr);
while(m.find()){
System.out.print("Start index: " + m.start());
System.out.print(" End index: " + m.end() + " ");
System.out.println(m.group());
sum=sum+ Integer.parseInt(m.group());
}
return sum;
}
#include<stdio.h>
#include<string.h>
int main()
{
char str[100000];
int k,i,j,a;
unsigned long long int sum=0,total_sum=0;
gets(str);
k=strlen(str);
for(i=0;i<k;i++)
{
sum=0;
a=str[i]-'0';
if(a>=0&&a<=9)
{
sum=a;
for(j=i+1;j<k;j++)
{
a=str[j]-'0';
if(a>=0&&a<=9){
sum=sum*10+a;
i=i+1;
}
else{
break;
}
}
}
total_sum+=sum;
}
printf("%llu\n",total_sum);
return 0;
}
int SumTheNumbers(char *in)
{
int sum = 0;
int i = 0;
while(in[i] != '\0')
{
if(in[i] >= '0' && in[i] <= '9') // it is digit
{
int num = (int)(in[i] - '0');
i++;
while(!(in[i] >= '0' && in[i] <= '9') && in[i] != '\0') // untill not a digit or not an end
{
int temp = (int)(in[i] - '0');
num = num*10 + temp;
i++;
}
sum = sum + num;
}
i++;
}
return sum;
}
I think this will go like this.
bit flgDigitFound=0;
int found=0;
int answer=0;
int i=0;
while (input != null)
{
if (input[i].char >=0 and input[i]<=9 )
{
flgDigitFound=1;
found=found*10+input[i].digit;
}
else
{
if (flgDightFound==1)
{
flgDigitFound=0;
answer=answer+found;
found=0;
}
}
i+=1;
}
string inputString = "PST456DA85M2A!!23++4600";
char[] inputChars = inputString.ToCharArray();
double sum = 0;
double tempnum = 0;
double powerCounter = 0;
double num;
for (int i = inputChars.Length - 1; i >= 0; i--)
{
if (inputChars[i] >= 48 && inputChars[i] <= 57)
{
num = inputChars[i] - 48;
tempnum = num * Math.Pow(10, powerCounter) + tempnum;
powerCounter = powerCounter + 1;
}
else
{
sum = sum + tempnum;
powerCounter = 0;
tempnum = 0;
}
}
Console.WriteLine();
Console.WriteLine(inputString);
Console.WriteLine(sum);
Console.ReadLine();
import java.io.*;
public class Add
{
boolean check_int(char a)
{
if(a>='0' && a<='9')
return true;
else
return false;
}
int add(String x)
{
x=x+'!';
double sum=0;
int count=1,mul=0;
for(int i=0;i<x.length();i++)
{
if(check_int(x.charAt(i)))
{
sum=(double) (sum+Integer.parseInt(String.valueOf((x.charAt(i))))*Math.pow(0.1, count));
count++;
}
else
{
mul+=(int)(sum*Math.pow(10, count-1));
count=1;
sum=0;
}
}
return mul;
}
public static void main(String arg[])
{
Add a=new Add();
int mul1;
String input="PST456DA85M2A!!23++46";
mul1=a.add(input);
System.out.println(mul1);
}
}
public static int sum(final String str) {
int sum = 0;
int base = 1;
for (int startIter = str.length() - 1; startIter >= 0; startIter--) {
if ((str.charAt(startIter) >= '0') &&
(str.charAt(startIter) <= '9')) {
sum += ((str.charAt(startIter) - '0') * base);
base *= 10;
} else {
base = 1;
}
}
return sum;
}
int Case(char a){
int temp=a;
if(temp>=48&&temp<=57)
return 1;
else
return 0;
}
int check(char A[],int n){
int sum=0;
int i=0;
int flag=0;
while(i<n){
int temp=0;
int tempo=Case(A[i]);
while(tempo){
int x=A[i]-48;
temp=x+temp*10;
flag=1;
i++;
tempo=Case(A[i]);
}
sum+=temp;
if(flag!=1)
i++;
flag=0;
}
return sum;
}
int Case(char a){
int temp=a;
if(temp>=48&&temp<=57)
return 1;
else
return 0;
}
int check(char A[],int n){
int sum=0;
int i=0;
int flag=0;
while(i<n){
int temp=0;
int tempo=Case(A[i]);
while(tempo){
int x=A[i]-48;
temp=x+temp*10;
flag=1;
i++;
tempo=Case(A[i]);
}
sum+=temp;
if(flag!=1)
i++;
flag=0;
}
return sum;
}
Here is a working C# code. Runtime O(n).
public static int AddNumbersOnly(char[] inp)
{
int len = inp.Length;
int curNum = 0, sum = 0;
for (int i = 0; i < len; i++)
{
if (inp[i] >= '0' && inp[i] <= '9')
{
curNum = (curNum * 10) + inp[i] - '0';
}
else
{
sum = sum + curNum;
curNum = 0;
}
}
if (curNum > 0)
sum = sum + curNum;
return sum;
}
amazon-interview-questions 43 Answers
If an array is having integers/Char/special Char... Ex: "PST456DA85M2A!!23++46", find out the sum of integers. ****Note: If we find consecutive digits in array we need to treat it as number, let say 456, we need to treat it as [ four hundread and fifty six]. Write a program to get the output by summing 456+85+2+23+46..also this needs to be done in lessnumber of iterations..
public int getSum(String input){
//String input = "PST456DA85M2A!!23AA4600";
int i = 0;
String number = "";
int total = 0;
while(i < input.length()){
if(input.charAt(i) >= '0' && input.charAt(i) <= '9'){
number += input.charAt(i);
i++;
continue;
}
if(!number.equals("")){
total = Integer.parseInt(number) + total;
}
number = "";
i++;
}
if(!number.equals("")){
total = Integer.parseInt(number) + total;
}
return total;
Java code that uses Regular Expression to replace non-digit characters with space. The resulting string contains only digits with space as delimitter. we can split the string using space and the resulting array can be iterated over to find the sum. Here s the code.
import java.util.regex.*;
public class SumIntegers {
public static void main(String a[]){
String s = "PST456DA85M2A!!23++46e";
Pattern pat = Pattern.compile("[^0-9]+");
Matcher mat = pat.matcher(s);
int sum = 0;
String str1 = mat.replaceAll(" ");
str1.trim();
System.out.println(str1);
String strArr[] = str1.split(" ");
for(int i=0;i<strArr.length;i++){
if(strArr[i].isEmpty()) strArr[i]="0";
sum += Integer.parseInt(strArr[i]);
}
System.out.println("sum is : "+sum);
}
}
C# Code
public int FindSum(String str)
{
Int32 sum = 0;
Int32 idx = 0;
Int32 number = 0;
Int32 numIdx = 0;
Char ch;
while (idx < str.Length)
{
ch = str[idx];
if (Char.IsDigit(ch))
{
numIdx = idx;
number = 0;
while (Char.IsDigit(str[numIdx]))
{
number = number * 10 + Int32.Parse(str[numIdx].ToString());
numIdx++;
if (numIdx == str.Length)
break;
}
sum += number;
idx = numIdx;
}
else
idx++;
}
/**
*
*/
package test;
import java.util.HashMap;
import java.util.List;
/**
* @author amal
*
*/
public class StringTest {
public static void main(String args[]) {
String str = "PST456DA85M2A!!23++46";
char str1[] = str.toCharArray();
int count = 0;
StringBuffer str2 = new StringBuffer();
for (char c : str1) {
int ascival = (int) c;
if (57 >= ascival && ascival >= 48 && !(ascival > 57)
&& !(ascival < 48)) {
str2.append(c);
}
else {
if (str2 != null && str2.length() > 0) {
count = count + Integer.valueOf(str2.toString());
str2 = new StringBuffer();
}
}
}
// for last number
if (str2 != null && str2.length() > 0) {
count = count + Integer.valueOf(str2.toString());
str2 = null;
}
System.out.println(count);
}
}
/**
*
*/
package test;
import java.util.HashMap;
import java.util.List;
/**
* @author amal
*
*/
public class StringTest {
public static void main(String args[]) {
String str = "PST456DA85M2A!!23++46";
char str1[] = str.toCharArray();
int count = 0;
StringBuffer str2 = new StringBuffer();
for (char c : str1) {
int ascival = (int) c;
if (57 >= ascival && ascival >= 48 && !(ascival > 57)
&& !(ascival < 48)) {
str2.append(c);
}
else {
if (str2 != null && str2.length() > 0) {
count = count + Integer.valueOf(str2.toString());
str2 = new StringBuffer();
}
}
}
// for last number
if (str2 != null && str2.length() > 0) {
count = count + Integer.valueOf(str2.toString());
str2 = null;
}
System.out.println(count);
}
}
private static int sumCharArray(char[] charArray) {
int sum = 0, num = 0;
for( int i = 0; i < charArray.length; i++ ) {
if( Character.isDigit( charArray[i] ) ) {
num = num * 10 + ( charArray[i] - '0' );
if( charArray.length - i == 1 ) {
sum += num;
}
}
else {
if( num > 0 ) {
sum += num;
num = 0;
}
}
}
return sum;
}
Use regex:
char[] c = new char[]{123dsd5455cf!!56};
String str = c.toString();
String newStr = str.replaceAll("[^0-9]", " ");
String[] out = newStr.split(" ");
int sum = 0;
for(int i = 0 ; i < out.length() ; i++){
sum += Integer.parseInt(out[i]);
}
System.Out.println(sum);
Works in O(n) time.
public class SumOfDigit {
public static void main(String[] args){
String str="PST456DA85M2A!!23++46";
String temp="";
int pos=0,sum=0;
boolean bFlag=false;
for(int i=0;i<str.length();i++){
if(str.charAt(i)>='0' && str.charAt(i)<='9'){
if(bFlag==true){
if((pos+1)==i){
temp=temp+str.charAt(i);
pos=i;
}
}
else{
temp="";
temp=temp+str.charAt(i);
bFlag=true;
pos=i;
}
}
else{
if(temp !=""){
sum=sum+Integer.valueOf(temp);
bFlag=false;
temp="";
}
}
}
if(temp !=""){
sum=sum+Integer.valueOf(temp);
bFlag=false;
temp="";
}
System.out.println("sum :"+sum);
}
}
public class SumOfDigit {
public static void main(String[] args){
String str="PST456DA85M2A!!23++46";
String temp="";
int pos=0,sum=0;
boolean bFlag=false;
for(int i=0;i<str.length();i++){
if(str.charAt(i)>='0' && str.charAt(i)<='9'){
if(bFlag==true){
if((pos+1)==i){
temp=temp+str.charAt(i);
pos=i;
}
}
else{
temp="";
temp=temp+str.charAt(i);
bFlag=true;
pos=i;
}
}
else{
if(temp !=""){
sum=sum+Integer.valueOf(temp);
bFlag=false;
temp="";
}
}
}
if(temp !=""){
sum=sum+Integer.valueOf(temp);
bFlag=false;
temp="";
}
System.out.println("sum :"+sum);
}
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void)
{
char str[] = "PST456DA85M2A!!23+46";
char *wkptr = str, *str_help, *str_help2;
int val = 0, i, flag = 0, trans; char arr[4];
while (*wkptr != '\0') {
if (*wkptr >= '0' && *wkptr <= '9') {
str_help = wkptr;
while (*str_help >= '0' && *str_help <= '9' && *str_help != '\0')
str_help2 = str_help++;
trans = str_help2 - wkptr;
for (i=0; (i <= trans) && (wkptr <= str_help2); )
arr[i++] = *wkptr++;
--wkptr; /* this is to get wkptr back to the last number char found, since it is incremented outside this loop anyway */
arr[i] = '\0';
val += atoi(arr);
}
++wkptr;
}
printf("Final val --> %d\n", val);
system("pause");
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void)
{
char str[] = "PST456DA85M2A!!23+46";
char *wkptr = str, *str_help, *str_help2;
int val = 0, i, flag = 0, trans; char arr[4];
while (*wkptr != '\0') {
if (*wkptr >= '0' && *wkptr <= '9') {
str_help = wkptr;
while (*str_help >= '0' && *str_help <= '9' && *str_help != '\0')
str_help2 = str_help++;
trans = str_help2 - wkptr;
for (i=0; (i <= trans) && (wkptr <= str_help2); )
arr[i++] = *wkptr++;
--wkptr; /* this is to get wkptr back to the last number char found, since it is incremented outside this loop anyway */
arr[i] = '\0';
val += atoi(arr);
}
++wkptr;
}
printf("Final val --> %d\n", val);
system("pause");
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void)
{
char str[] = "PST456DA85M2A!!23+46";
char *wkptr = str, *str_help, *str_help2;
int val = 0, i, flag = 0, trans; char arr[4];
while (*wkptr != '\0') {
if (*wkptr >= '0' && *wkptr <= '9') {
str_help = wkptr;
while (*str_help >= '0' && *str_help <= '9' && *str_help != '\0')
str_help2 = str_help++;
trans = str_help2 - wkptr;
for (i=0; (i <= trans) && (wkptr <= str_help2); )
arr[i++] = *wkptr++;
--wkptr; /* this is to get wkptr back to the last number char found, since it is incremented outside this loop anyway */
arr[i] = '\0';
val += atoi(arr);
}
++wkptr;
}
printf("Final val --> %d\n", val);
system("pause");
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void)
{
char str[] = "PST456DA85M2A!!23+46";
char *wkptr = str, *str_help, *str_help2;
int val = 0, i, flag = 0, trans; char arr[20];
while (*wkptr != '\0') {
if (*wkptr >= '0' && *wkptr <= '9') {
str_help = wkptr;
while (*str_help >= '0' && *str_help <= '9' && *str_help != '\0')
str_help2 = str_help++;
trans = str_help2 - wkptr;
for (i=0; (i <= trans) && (wkptr <= str_help2); )
arr[i++] = *wkptr++;
/* this is to get wkptr back to the last number char found, since it is incremented outside this loop anyway */
--wkptr;
arr[i] = '\0';
val += atoi(arr);
}
++wkptr;
}
printf("Final val --> %d\n", val);
}
Traverse right to left. If its first digit, add to sum, if second in a row, multiply by 10 and add to sum, if third in a row, multiply by 100 and add to sum. Well and so on. If not digit proceed until next digit and repeat.
Logic is clear ..but the thing is write program to make it in minimum number of iterations
#include<stdio.h>
#include<stdlib.h>
void sum(char *a)
{
int sum=0,i=0,final=0;
while(a[i]!='\0')
{
while(a[i]-'0'>=0 && a[i]-'0'<=9)
{
sum=sum *10+ (a[i]-'0');
i++;
}
final+=sum;
sum=0;
i++;
}
printf("%d\n",final);
}
int main()
{
//char a[20]="1$% 21+-98!!!??>76"; //Try for this input also
char a[50]="PST456DA85M2A!!23++46"; //Input
sum(a); //Function call
}
#include <iostream>
#include <ostream>
#include <string>
#include <sstream>
int main()
{
const char* digits = "0123456789";
std::string source = "PST456DA85M2A!!23++46";
int sum = 0;
for (std::string::size_type offset = 0; offset != std::string::npos;)
{
offset = source.find_first_of(digits, offset);
if (offset == std::string::npos)
{
break;
}
std::string:: size_type end = source.find_first_not_of(digits, offset);
std::string token = source.substr(offset, end - offset);
// Convert the string of digites to an integer
std::istringstream ist(token);
int temp;
ist >> temp;
sum += temp;
offset = end;
}
std::cout << sum << std::endl;
return 0;
}
/**
*
*/
package test;
import java.util.HashMap;
import java.util.List;
/**
* @author amal
*
*/
public class StringTest {
public static void main(String args[]) {
String str = "PST456DA85M2A!!23++46";
char str1[] = str.toCharArray();
int count = 0;
StringBuffer str2 = new StringBuffer();
for (char c : str1) {
int ascival = (int) c;
if (57 >= ascival && ascival >= 48 && !(ascival > 57)
&& !(ascival < 48)) {
str2.append(c);
}
else {
if (str2 != null && str2.length() > 0) {
count = count + Integer.valueOf(str2.toString());
str2 = new StringBuffer();
}
}
}
// for last number
if (str2 != null && str2.length() > 0) {
count = count + Integer.valueOf(str2.toString());
str2 = null;
}
System.out.println(count);
}
}
I think it is very simple
You just need to go though the string by char.
- loveCoding August 29, 20121 keep one String variable prev = 0 and sum = 0
2. Now go through string char by char say ch is the character
3. If ch is a digit -> prev = prev*10 + ch
4. if ch is NOT a digit or end of string -> sum = sum + prev AND set prev to 0
time complexity O(n) : 1 ITERATION