Amazon Interview Question
Software Engineer / DevelopersScan the given string and check each character if it is any of the given punctuation.
Hash can be used to store punctuation characters for faster search.
OR we can consider ascii values of characters and use binary search.
1) Use two pointers a and b.
2) Set both of them to the start of the text
3) While end is not reached, keep incrementing b until it hits a space/punctuation.
4) When it does hit a space or punctuation, set a = b and increment count by 1, and go back to step 3
The final value of count is our answer.
(Note that you might need to tweak it a little to support strings consequent punctuations)
I recently faced the same question.But the interviewer was not happy with the solution as given above.He wanted some CONTEXT-BASED solution !
What do you exactly mean by context-based?
Do you mean exact coding for the question asked
No, not code, but by context-based he said that for one particular character,there can be a set of another characters who would be defined as 'punctuation marks' for that character and would have to be skipped while counting the no of words in the sentence.
For eg- say for A, set of punctuation marks is {x,y,z}, so now whenever we encounter **Ax,this means the word has ended there.
/*
* File: main.cpp
* Author: Aaron
*
* Created on February 9, 2011, 6:21 PM
*/
#include <cstdlib>
#include <vector>
#include <ctype.h>
#define MAX_COUNT 10240
using namespace std;
/*
*
*/
void count_words(char* data,int* count);
int main(int argc, char** argv) {
int times=100;
int n=100;
vector<float> u;
char l[]="my test ; z";
while(true)
{
printf("input:");
char input[MAX_COUNT]={};
fgets(input, MAX_COUNT ,stdin);
input[strlen(input)-1]=0;
if(
strcasecmp((input), "quit") ==0
)
{
break;
}
int c=0;
count_words(input,&c);
printf("count :%d\n", c);
}
return 0;
}
bool is_invalid_in_word(char c)
{
bool v= !(
( (c>='a') && (c<='z') )
||
( (c>='A') && (c<='Z') )
);
return v;
//in your case,just change this function
//as below:
/**
if(c=='x')
{
return true;
}
if(c=='y')
{
return true;
}
if(c=='z')
{
return true;
}
return false;
*/
}
void count_words(char* data,int* count)
{
if(data==NULL)
{
*count=0;
return ;
}
int len=strlen(data);
bool inWord=false;
for(int i=0;i<len;i++)
{
char c=data[i];
bool invalid=is_invalid_in_word(c)
;
if(inWord)
{
if(invalid)
{
//*count=*count+1;
inWord=false;
}else
{
//skip
}
}else
{
if(invalid)
{
//skip
}else
{
*count=*count+1;
inWord=true;
}
}
}
printf("str:%s len :%d\n",data, len);
}
Why cant we just count the number of white spaces/punctuations/end of string in the string to get the number of words?
No. If you were to have the following string: "Hello World!!", you would end up counting three words due to the extra exclamation mark when there are only two words to begin with.
a solution in C++:
#include <iostream>
bool iswordchar(char c)
{
return(c>='A' && c<='z');
}
int wordcount(char *p)
{
int count = 0;
int i = 0;
int word = 0;
while (p[i] != '\0')
{
while (p[i] != '\0' && !iswordchar(p[i])) {
i++;
word = 0;
}
while (p[i] != '\0' && iswordchar(p[i]) ) {
i++;
word = 1;
}
count += word;
}
return count;
}
int wordcount_main() {
char *p = "oh, it is a rainy day again!";
std::cout << wordcount(p);
return 0;
}
public static int WordCount(String str)
{
if(str == null) {return 0;}
str = str.Trim();
int wordCount = 0, index =0;
while (index < str.Length)
{
// check if the current character is part of a word
while (index < str.Length && !char.IsWhiteSpace(str[index]))
{
index++;
}
wordCount++;
// skip whitespace until next word
while (index < str.Length && char.IsWhiteSpace(str[index]))
{
index++;
}
}
return wordCount;
}
strtok(mystring, " ")
- Mat February 14, 2011