Google Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
Uggh, where do the random ; come from after we click submit:
for(t=0,i = 0,count=0; i < str.length ; i++)
if( str[i] == alpha[t %M] ) count++;
else if( str[i] == alpha[++t %M] && count > 1) count=1;
else return false;
return ( count >;1 && t%M == M-1) ? true : false;
Someone report the >; bug to careercup please..
One more try:
for(t = 0, i = 0, count = 0; i < str.length ; i++)
if( str[i] == alpha[t %M] ) count++;
else if( str[i] == alpha[++t %M] && count > 1) count=1;
else return false;
return ( count > 1 && t%M == M-1) ? true : false;
The question says if W1 and W2 are valid words then W1W2 is also a valid word.
Consider HIRE & HHIIRREE both are valid words. Then HIREHHIIRREE should also be a valid word. Did you missed that scenario or am I making any mistake ?
It should handle W1W2, bit I read other posts and thought "hire" was invalid (because we needed more than 1 letter each).
Well if "hire" "hiiree" are valid, then it could be easier easier:
for(t = 0, i = 0; i < str.length ; i++)
if( str[i] == alpha[t %M] || str[i] == alpha[++t %M] ) continue;
return false;
return ( t%M == M-1) ? true : false;
char [] str = inputWord.toCharArray();
char[] alpha = {'h','i','r','e'};
int M = 4;int t=0, i=0, count=0, j=0;
int[] countArr = new int[M];
for(t = 0, i = 0, count = 0, j=0; i < str.length ; i++) {
if( str[i] == alpha[t % M]) count++;
else if(str[i] == alpha[++t %M] ) {countArr[j %M]=count; count=1; j++;}
else return false;
}
countArr[j%M]=count;
for (int k=0;k<M-1;k++) {
if (countArr[k]==countArr[k+1]) continue; else return false;
}
return (t%M == M-1) ? true : false;
The quesiton is meaningless.
What does "this is valid because n is blah blah"
This is invalid because n is not blah blah mean.
The inequalities are irrelevant if n is not defined lol
hugakakka (spelling) the original poster can "define n" first before using it to define a whole bunch of other things next time he/she posts a question.
Whatever version you want, the code should still be a few-liner.
Too many idiots posting questions. I don't care if I offend anyone.
Nowhere does the question define n.
AND even if n is defined, we need to know if it's
1) Fixed throughout the whole junk
2) Fixed within each word
3) Indepedent for each character
All are easy modifications from the same base code.
bool check_chars(char * word, int len, int i, int count, char ch) {
for (int j=i; j<i+count; j++)
if (j>=len || word[j] != ch)
return false;
return true;
}
bool is_valid_word(char * word) {
if (!word)
return false;
int len = strlen(word);
if (len==0 || len%4 != 0)
return false;
int i = 0;
while (i<len) {
if ((len-i)%4 != 0)
return false;
int count = 0;
while (word[i]=='h') {
count++;
i++;
}
if (count==0 ||
!check_chars(word, len, i, count, 'i') ||
!check_chars(word, len, i+count, count, 'r') ||
!check_chars(word, len, i+2*count, count, 'e'))
return false;
i += 3*count;
}
return true;
}
EDIT: I overlooked certain restrictions. My solution would be to design a simple Automata that handles this (In this case, a simple 5 state DFA can handle this). Here is a code. I think it works.
bool check(std::string str)
{
int state = 1;
bool fail = false;
for(int i=0;i<str.length();i++)
{
char x = str[i];
switch(x)
{
case 'h' :
if(state==1)
state =2;
else if(state==2)
state=2;
else if(state==5)
state = 2;
else
fail = true;
break;
case 'i' :
if(state==2)
state =3;
else if(state==3)
state = 3;
else
fail = true;
break;
case 'r':
if(state==3)
state =4;
else if(state==4)
state = 4;
else
fail = true;
break;
case 'e':
if(state==4)
state =5;
else if(state==5)
state = 5;
else
fail = true;
break;
default:
fail = true;
break;
}
if(fail)
break;
}
if(state==5)
return true;
else
return false;
}
n >= 1 is a given, so I don't know if I'd consider that a pitfall. Also, from what I understand, all letters need to have equal occurrence. What happens when you enter 'hhhhh'?
class Language
{
public void TestForValidLanguage()
{
string languageWord = "HHIIRREEHIREHHHIIIRRREEEE";
bool isValid = IsValidLanguage(languageWord, "HIRE");
}
public bool IsValidLanguage(string languageWords, string language)
{
int counter = 0;
int languageLength = -1;
int languageIndex = 0;
for (int i = 0; i < languageWords.Length; i++)
{
if (languageWords[i] == language[languageIndex]){}
else if (languageWords[i] == language[(languageIndex + 1)%language.Length])
{
if (languageLength == -1)
{
languageLength = counter;
}
if (counter != languageLength)
{
return false;
}
if ((languageIndex + 1) >= language.Length)
{
if (languageLength != counter)
{
return false;
}
//Reset the language length for the new word.
languageLength = -1;
}
languageIndex = (languageIndex + 1)%language.Length;
counter = 0;
}
else
{
return false;
}
counter++;
}
return counter == languageLength;
}
}
boolean isValid(String str) {
if (str == null || str.length < 4) {
return false;
}
Set<Char> set = new HashSet<Char>();
for (int i=0; i<str.length; i++) {
char c = str.charAt(i);
if (c != 'h' && c != 'i' && c != 'r' && c != 'e') {
return false;
}
set.add(c);
}
return (set.size() == 4);
}
# Runs in constant memory space, the check terminates ones it determines that an alien character not present in our language definition is found
# Runs in O(n) time
chars = ['h', 'i', 'r', 'e']
def check(string, adict = None):
if adict is None:
adict = {}
count = 0
previous = None
wordcomplete = 0
for letter in string:
if letter not in chars:
print 'Invalid for:',string
return
# first word, that is not a part of concatenated sequence, ignore checks
if letter == 'h' and wordcomplete == 0:
pass
# found last valid letter, now make the dict eligible for checking when we hit 'h' next time
if letter == 'e' and wordcomplete == 0:
wordcomplete = 1
if letter == 'h' and wordcomplete > 0:
# reset flag
wordcomplete = 0
result = verifypass(adict)
if result == -1:
print 'Invalid for:',string
else:
adict = {}
if letter not in adict:
adict[letter] = 1
else:
adict[letter] += 1
# check for last pass
result = verifypass(adict)
if result == -1:
print 'Invalid for:',string
else:
print 'Valid for:',string
def verifypass(adict):
# some char missing
if len(adict) < 4:
return -1
previouscount = -1
for key, val in adict.iteritems():
if previouscount != -1 and val != previouscount:
return -1
else:
previouscount = val
# successful pass, return 1
return 1
def main():
check('hhiirree')
check('hire')
check('hhiirreee')
check('hired')
check('hhiirrree')
check('hirehhiirree')
check('hiredhiirreeddhiree')
check('hie')
if __name__ == '__main__':
main()
A naive approach
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
bool check(char *str, int first,int last);
bool is_valid(char *str, int first, int last);
bool is_valid(char *str, int first, int last)
{
if(check(str,first,last) == true)
return true;
else
{
int i=0;
bool temp1=false,temp2=false;
for(i=first + 4;i<=last;i=i+4)
{
temp1 = is_valid(str,first,i-1);
if(temp1 == true)
{
temp2 = is_valid(str,i,last);
if(temp2 == true)
return true;
temp1 = false;
}
}
}
return false;
}
bool check(char *str, int first,int last)
{
int length,i=0,j=first;
length = last - first + 1;
if(last < first)
return true;
if(length%4 != 0)
return false;
else
{
while(i<length/4)
{
if(str[j] != 'h')
return false;
i++;
j++;
}
while(i<length/2)
{
if(str[j] != 'i')
return false;
i++;
j++;
}
while(i<(3*length)/4)
{
if(str[j] != 'r')
return false;
i++;
j++;
}
while(i<length)
{
if(str[j] != 'e')
return false;
i++;
j++;
}
}
return true;
}
int main()
{
char c[100]="hhiirreehhiirreehirehhhiiirrreeehirehire";
char b[100]="hhhhiiiirrrreeee";
int length;
length = strlen(c);
//cout << length << endl;
//cout << check(b,0, length-1) << endl;
cout << is_valid(c,0,length-1);
return 0;
}
This is an O(n) approach:
int IsValidString(string alphabet, string str)
{
if(alphabet.size()==0 || str.size()==0)
return 0;
int n=str.size();
transform(str.begin(),str.end(),str.begin(),tolower);
for(int i=0;i<(n/2)-1;i++)
{
if(str[i]==str[i+1] || str[i+1]==alphabet[0])
continue;
else if(alphabet.find(str.substr(i,2))!=string::npos)
continue;
else
return 0;
if(str[n/2+i]==str[n/2+i+1] || str[n/2+i+1]==alphabet[0])
continue;
else if(alphabet.find(str.substr(n/2+i,2))!=string::npos)
continue;
else
return 0;
}
return 1;
}
public static boolean isValidWord(final String word){
String alphabetStr = "hire";
char []alphabets = alphabetStr.toCharArray();
char []wordChar = word.toCharArray();
int []countArr = new int[4];
for(int i=0;i<4;i++){
countArr[i]=0;
}
boolean isValid = true;
int j=0;
for (int i = 0; i < wordChar.length; i++) {
if(wordChar[i]==alphabets[j=(j>3)?0:j]){
countArr[j]=countArr[j]+1;
}else if(wordChar[i] == alphabets[j=(j>=3)?0:(j+1)]){
countArr[j]=countArr[j]+1;
}else{
isValid=false;
break;
}
}
if(!isValid)
return isValid;
for (int i = 0; i < countArr.length-1; i++) {
if(countArr[i]!=countArr[i+1]){
isValid=false;
break;
}
}
return isValid;
}
private static boolean isvalidWord(String word) {
char [] wordChar = word.toCharArray();
int hCounter = 0, iCounter = 0, rCounter=0,eCounter=0;
boolean hVisitFlag=false,iVisitFlag=false,rVisitFlag=false,eVisitFlag=false ;
boolean wordMismatch = false;
for (int i=0; i< wordChar.length; i++) {
switch (wordChar[i]) {
case 'h':
if(!hVisitFlag)
if(hCounter != iCounter || hCounter != rCounter || hCounter != eCounter) {
wordMismatch = true; break;
}
hCounter++;
hVisitFlag=true; iVisitFlag=false;rVisitFlag=false;eVisitFlag=false; break;
case 'i':
iCounter++;
if(!iVisitFlag && !hVisitFlag) {
wordMismatch = true; break;
}
iVisitFlag=true; hVisitFlag=false;rVisitFlag=false;eVisitFlag=false; break;
case 'r':
rCounter++;
if(!rVisitFlag && !iVisitFlag) {
wordMismatch = true; break;
}
rVisitFlag=true; iVisitFlag=false;hVisitFlag=false;eVisitFlag=false; break;
case 'e':
eCounter++;
if(!eVisitFlag && !rVisitFlag){
wordMismatch = true; break;
}
eVisitFlag=true; iVisitFlag=false;rVisitFlag=false;hVisitFlag=false; break;
}
if(wordMismatch) return !wordMismatch;
}
return true;
}
static boolean isValidWord(char[] word) {
if (word == null || word.length == 0 || word.length % 4 != 0) {
return false;
}
if (word[0] != 'h' || word[word.length - 1] != 'e') {
return false;
}
int cnta = 1;
int cntb = 1;
char last_scan = 'h';
for (int i = 1; i < word.length; i++) {
switch (last_scan) {
case 'h':
if (word[i] == 'h') {
cnta++;
cntb++;
} else if (word[i] == 'i') {
cntb--;
last_scan = 'i';
} else {
return false;
}
break;
case 'i':
if (word[i] == 'i') {
cntb--;
} else if (word[i] == 'r' && cntb == 0) {
cntb = 1;
last_scan = 'r';
} else {
return false;
}
break;
case 'r':
if (word[i] == 'r') {
cntb++;
} else if (word[i] == 'e' && cntb == cnta) {
cntb--;
last_scan = 'e';
} else {
return false;
}
break;
case 'e':
if (word[i] == 'e') {
cntb--;
} else if (word[i] == 'h' && cntb == 0) {
cnta = 1;
cntb = 1;
last_scan = 'h';
} else {
return false;
}
break;
}
}
if (cntb == 0 && last_scan == 'e')
return true;
return false;
}
static boolean isValidWord(char[] word) {
if (word == null || word.length == 0 || word.length % 4 != 0) {
return false;
}
if (word[0] != 'h' || word[word.length - 1] != 'e') {
return false;
}
int cnta = 1;
int cntb = 1;
char last_scan = 'h';
for (int i = 1; i < word.length; i++) {
switch (last_scan) {
case 'h':
if (word[i] == 'h') {
cnta++;
cntb++;
} else if (word[i] == 'i') {
cntb--;
last_scan = 'i';
} else {
return false;
}
break;
case 'i':
if (word[i] == 'i') {
cntb--;
} else if (word[i] == 'r' && cntb == 0) {
cntb = 1;
last_scan = 'r';
} else {
return false;
}
break;
case 'r':
if (word[i] == 'r') {
cntb++;
} else if (word[i] == 'e' && cntb == cnta) {
cntb--;
last_scan = 'e';
} else {
return false;
}
break;
case 'e':
if (word[i] == 'e') {
cntb--;
} else if (word[i] == 'h' && cntb == 0) {
cnta = 1;
cntb = 1;
last_scan = 'h';
} else {
return false;
}
break;
}
}
if (cntb == 0 && last_scan == 'e')
return true;
return false;
}
public class WordValidator
{
private static char[] OrderedAcceptableCharacters = new char[] { 'h', 'i', 'r', 'e' };
public static bool ValidateWord(string word)
{
int currentIndex = 0;
int currentAcceptableCharacterIndex = 0;
while (currentIndex < word.Length)
{
if (word[currentIndex] == OrderedAcceptableCharacters[currentAcceptableCharacterIndex])
{
currentIndex++;
}
else
{
currentAcceptableCharacterIndex++;
if (currentAcceptableCharacterIndex >= OrderedAcceptableCharacters.Length)
{
if (word[currentIndex] == OrderedAcceptableCharacters[0])
{
return ValidateWord(word.Substring(currentIndex));
}
else
{
return false;
}
}
else if (word[currentIndex] == OrderedAcceptableCharacters[currentAcceptableCharacterIndex])
{
currentIndex++;
}
else
{
return false;
}
}
}
return true;
}
}
tried the following cases:
Console.WriteLine(WordValidator.ValidateWord("hhirre"));
Console.WriteLine(WordValidator.ValidateWord("hhirrehhhhhhhhhhhe"));
Console.WriteLine(WordValidator.ValidateWord("heirre"));
Console.WriteLine(WordValidator.ValidateWord("hire"));
Console.WriteLine(WordValidator.ValidateWord("hhhhhhhhhhhhhhire"));
Console.WriteLine(WordValidator.ValidateWord("hiiiiiiiiireeeeeeeeeee"));
Console.WriteLine(WordValidator.ValidateWord("hhhiiirrreeehhhiiirrree"));
String alphabetStr = "hire";
char []alphabets = alphabetStr.toCharArray();
char []wordChar = word.toCharArray();
int []countArr = new int[4];
for(int i=0;i<4;i++){
countArr[i]=0;
}
boolean isValid = true;
int j=0;
for (int i = 0; i < wordChar.length; i++) {
if(wordChar[i]==alphabets[j=(j>3)?0:j]){
countArr[j]=countArr[j]+1;
}else if(wordChar[i] == alphabets[j=(j>=3)?0:(j+1)]){
countArr[j]=countArr[j]+1;
}else{
isValid=false;
break;
}
}
if(!isValid)
return isValid;
for (int i = 0; i < countArr.length-1; i++) {
if(countArr[i]!=countArr[i+1]){
isValid=false;
break;
}
}
return isValid;
}
I have a solution:
public static boolean isValidWord(final String word){
String alphabetStr = "hire";
char []alphabets = alphabetStr.toCharArray();
char []wordChar = word.toCharArray();
int []countArr = new int[4];
for(int i=0;i<4;i++){
countArr[i]=0;
}
boolean isValid = true;
int j=0;
for (int i = 0; i < wordChar.length; i++) {
if(wordChar[i]==alphabets[j=(j>3)?0:j]){
countArr[j]=countArr[j]+1;
}else if(wordChar[i] == alphabets[j=(j>=3)?0:(j+1)]){
countArr[j]=countArr[j]+1;
}else{
isValid=false;
break;
}
}
if(!isValid)
return isValid;
for (int i = 0; i < countArr.length-1; i++) {
if(countArr[i]!=countArr[i+1]){
isValid=false;
break;
}
}
return isValid;
}
public static boolean isValidWord(final String word){
String alphabetStr = "hire";
char []alphabets = alphabetStr.toCharArray();
char []wordChar = word.toCharArray();
int []countArr = new int[4];
for(int i=0;i<4;i++){
countArr[i]=0;
}
boolean isValid = true;
int j=0;
for (int i = 0; i < wordChar.length; i++) {
if(wordChar[i]==alphabets[j=(j>3)?0:j]){
countArr[j]=countArr[j]+1;
}else if(wordChar[i] == alphabets[j=(j>=3)?0:(j+1)]){
countArr[j]=countArr[j]+1;
}else{
isValid=false;
break;
}
}
if(!isValid)
return isValid;
for (int i = 0; i < countArr.length-1; i++) {
if(countArr[i]!=countArr[i+1]){
isValid=false;
break;
}
}
return isValid;
}
bool validWord(char st[], char ch[4]){
int stlen = strlen(st);
int stindex = 0;
int n = 0;
for(int i =0; i<4; i++){
if(i==0){
while(stindex < stlen && st[stindex] == ch[i]){
n += 1;
stindex += 1;
}
}else{
int count = 0;
while( stindex < stlen && st[stindex] == ch[i]){
stindex += 1;
count += 1;
}
if(count != n)
return false;
}
}
if(stindex < stlen)
return validWord(&st[stindex], ch);
else
return true;
}
#!/usr/bin/env python
import re
import sys
index = 0
list1 = ['h','i','r','e']
length = 0
def checkValid(inputStr, i):
#print inputStr,i
if inputStr:
try:
match = re.search(list1[i]+'+',inputStr)
matchString = match.group(0)
if i == 0:
global length
length = len(matchString)
else:
if len(matchString) != length:
return False
except AttributeError,e:
return False
global index
if i == len(list1)-1:
index = 0
else:
index = i+1
return checkValid(inputStr[len(matchString):],index)
else:
if i == 0:
return True
else:
return False
if __name__ == '__main__':
inputStr = sys.argv[1]
if inputStr == "":
print False
else:
print checkValid(inputStr,index)
#!/usr/bin/env python
import re
import sys
index = 0
list1 = ['h','i','r','e']
length = 0
def checkValid(inputStr, i):
#print inputStr,i
if inputStr:
try:
match = re.search(list1[i]+'+',inputStr)
matchString = match.group(0)
if i == 0:
global length
length = len(matchString)
else:
if len(matchString) != length:
return False
except AttributeError,e:
return False
global index
if i == len(list1)-1:
index = 0
else:
index = i+1
return checkValid(inputStr[len(matchString):],index)
else:
if i == 0:
return True
else:
return False
if __name__ == '__main__':
inputStr = sys.argv[1]
if inputStr == "":
print False
else:
print checkValid(inputStr,index)
My solution:
bool isWordCorrect(const std::string word)
{
if (word.length() == 0) return false;
std::vector<char> allowedSigns = {'h', 'i', 'r', 'e'};
std::vector<unsigned int> countSigns(allowedSigns.size(), 0);
auto wordIt = begin(word);
// repeat till end of word
while (wordIt != end(word)) {
int count = 0; // counts signs per one word
auto counterIt = begin(countSigns);
// count signs in one word (from possible many w1w2..)
for (const auto &ch : allowedSigns) {
while (wordIt != end(word) && (*wordIt) == ch) {
++(*counterIt);
++wordIt;
++count;
}
++counterIt;
}
// verify it
for (auto &num : countSigns) {
if (num != count / allowedSigns.size()) return false;
else num = 0;
}
}
return true;
}
Example outputs:
isWordCorrect("hirehhhiiirrreee") => true
isWordCorrect("hiree") => false
isWordCorrect("") => false n=0
Assume that n is intended to be the same for every char in the dictionary and n>=1.
Main idea is borrowed from BrAiNleSs ÙƦІϏ. Thanks for your "ordered array".
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
bool isValid (string str, char *dict, int n) {
assert(n>0);
int cnt = 0, _cnt = 0; // ensure n is equal for every char in current “h^n i^n r^n e^n” word
int iStr = 0, iDict = 0;
while (iStr<str.size()) {
if (str[iStr] == dict[iDict%n]) {
if (iDict%n == 0) {
_cnt++;
} else {
cnt++;
if (cnt>_cnt) return false;
}
iStr++;
} else if (str[iStr] == dict[(iDict+1)%n]) {
if (iDict%n!=0 && cnt<_cnt) return false;
if ((iDict+1)%n == 0) _cnt = 0;
cnt = 0;
iDict++;
} else {
return false;
}
}
if (cnt < _cnt || iDict%n != n-1) return false;
return true;
}
int main() {
// your code goes here
char dict[4] = {'h', 'i', 'r', 'e'};
cout<<isValid("hire", dict, 4)<<endl;
cout<<isValid("hhirree", dict, 4)<<endl;
cout<<isValid("hhiirre", dict, 4)<<endl;
cout<<isValid("hhiirr", dict, 4)<<endl;
cout<<isValid("hhiirreehire", dict, 4)<<endl;
cout<<isValid("hhiirreehirehhh", dict, 4)<<endl;
cout<<isValid("hhiirreehrehire", dict, 4)<<endl;
cout<<isValid("hhiirreeabchire", dict, 4)<<endl;
return 0;
}
Check for two words. If both words are valid then concatenation is not needed to be checked. Substringing from 0 to N-1 remembering previous index of the substring.
public static boolean isValidWordN(String word1, String word2, int n){
return n>=1 && isValidWord(word1, n) && isValidWord(word2, n);
}
public static boolean isSubstringValid(String sub, int n){
HashSet<Character> validSet = new HashSet<Character>();
for(int i = 0 ; i < sub.length(); i++){
validSet.add(sub.charAt(i));
}
return validSet.size() == 1;
}
public static boolean isValidWord(String w, int n){
int last = 0;
StringBuffer sub = new StringBuffer();
for(int i = n-1; i < w.length(); i+=n){
System.out.println(w.substring(last, i+1));
sub.append(w.substring(last, i+1));
if(!isSubstringValid(w.substring(last, i+1),n)){
return false;
}
last = i+1;
}
return sub.length() == w.length();
}
Java Solution
Using Regex (Note you should compile the pattern once if possible):
public static boolean isWordRegex(String word) {
if (word == null || word.isEmpty())
return false;
word = word.toLowerCase();
String regex = "([h]+[i]+[r]+[e]+)+";
Pattern pattern = Pattern.compile(regex);
return pattern.matcher(word).matches();
}
Java Solution not using regex
public static boolean isWord(String word) {
if (word == null || word.isEmpty())
return false;
word = word.toLowerCase();
char[] cword = word.toCharArray();
for (int i = 0; i < cword.length; i++) {
char c = cword[i];
if (i == 0) {
if (c != 'h')
return false;
}
else if (i + 1 == cword.length && c != 'e')
return false;
else {
char prev = cword[i-1];
try {
if (prev != c && prev != expectedPrev(c))
return false;
}
catch (IllegalArgumentException e) {
return false;
}
}
}
return true;
}
private static char expectedPrev(char c) {
switch (c) {
case 'h': return 'e';
case 'i': return 'h';
case 'r': return 'i';
case 'e': return 'r';
default:
throw new IllegalArgumentException(c + " is not a valid character.");
}
}
#include<stdio.h>
#include<string.h>
void main()
{
int i,cnt=1,a[10],n=0;
char ch[20];
printf("\n Enter the Valid Word : ");
scanf("%s",ch);
for(i=0;ch[i]!='\0';i++)
{
if(ch[i]==ch[i+1])
{
cnt++;
}
else
{
a[n]=cnt;
cnt=1;
n=n+1;
}
}
cnt=0;
for(i=0;i<n-1;i++)
{
if(a[i]==a[i+1])
{
cnt=0;
}
else
{
cnt=1;
}
}
if(cnt==1)
printf("\nNot a Valid Word ");
else
printf("\nIt is a Valid Word ");
}
public class WordCheck {
public static boolean check(String input) {
if (input == null)
return false;
char[] chars = new char[] { 'h', 'i', 'r', 'e' };
int index = 0;
for (int i = 0; i < input.length(); i++) {
if (chars[index] == input.charAt(i))
continue;
int next = (index + 1) % 4;
if (chars[next] == input.charAt(i)){
index = next;
continue;
}
return false;
}
if (index != 3) {
return false;
}
return true;
}
public static void main(String[] argv) {
assert true == check("hire");
assert true == check("hirehire");
assert true == check("hhiiiirrrreeeee");
assert true == check("hhiiiirrrreeeeehirrree");
assert true == check("hhiiiirrrreeeeehirrreehirree");
assert false == check("hhiiiirrrreeeeehirr");
assert false == check("hhiiiirrhirr");
assert false == check("");
assert false == check(null);
}
}
There is a simple non-generic version for this specific case.
bool validWord(char *str) {
if (str == NULL || *str == '\0') {
return false;
}
bool flag;
int h,i,r,e;
while(1) {
h = 0;
i = 0;
r = 0;
e = 0;
while(*str == 'h') { h++; str++; }
while(*str == 'i') { i++; str++; }
while(*str == 'r') { r++; str++; }
while(*str == 'e') { e++; str++; }
flag = h & i & r & e;
if (*str == '\0' || !flag) {
return flag;
}
continue;
}
}
I wonder if this would be acceptable:
import re
def is_a_word(word):
return bool(re.match(r'^(h+i+r+e+)*$', word))
This question is practically begging to use already highly optimized automata that is available pretty much in any modern language. The way the language is expressed is similar how it was done in automata theory class. It feels as interviewer wanted to hint toward this direction.
bool isValid(const string& str) {
const string alphabet = "hire";
int curPos = 0;
int count = 0;
int tmpcount = 0;
for (int i = 0; i < str.length(); ++i) {
if (str[i] == 'h') ++count;
else {
// Indicates valid transition from 'h'
if (count && (curPos == 0)) { ++curPos; curPos %= alphabet.length(); tmpcount = 0; }
// Check if current char matches curPOs
if (str[i] != alphabet[curPos]) return false;
++tmpcount;
// Indicates (expected) transition from 'cur' to 'next'
if (tmpcount == count) {
tmpcount = 0;
++curPos; curPos %= alphabet.length();
if (curPos == 0) count = 0; // reset count if we are going to next cycle of 'h'
}
}
}
if (curPos != 0) return false;
if (str[str.length() - 1] != alphabet[alphabet.length() - 1]) return false;
return true;
}
Here's the C++ (11) solution with symbol table storing counts, it successfully validates concatenated words also:
bool validate(std::string &str) {
std::list<std::pair<std::string::value_type, int>>
symbolTable {{'h', 0}, {'i', 0}, {'r', 0}, {'e', 0}};
int strPos = 0;
auto symIt = symbolTable.begin();
auto symEnd = symbolTable.end();
auto currSym = symIt;
while(strPos <= str.size() - 1) {
if(currSym == symEnd) {
// reached sym table end, go to beginning
currSym = symIt;
} else {
if(currSym->first == str[strPos]) {
// matched symbol, inc counter
++strPos; // go to next char in the string
currSym->second++; // and increase counter
} else {
// current string char and sym table mismatch
if(currSym != symIt) {
// not 1st position in sym table
// compare current and previous counters
auto prev = currSym;
--prev;
if(currSym->second != prev->second) {
// counters at n and n - 1 not equal
return false;
}
}
// move to next position in sym table
++currSym;
}
}
}
// iterate over the map and check all counts match
int checkSum = symIt->second;
for(auto it = ++symIt; it != symEnd; ++it) {
if(checkSum != it->second) return false;
}
return true;
}
int getCode(char ch) {
switch(ch) {
case 'h': return(0);
case 'i': return(1);
case 'r': return(2);
case 'e': return(3);
default: return(-1);
}
}
int isValidWord(char str[], int n) {
int pre = 0;
int cur;
int i;
for(i = 0; i < n; i++) {
cur = getCode(str[i]);
if(cur == -1) {
return -1;
}
if (pre != 3 && cur < pre) {
return -1;
}
pre = cur;
}
if(pre == 3) {
return(1);
} else {
return(-1);
}
}
The definition of valid word are:
1. A given word is a valid word if it is of the form h^n i^n r^n e^n where n >=1. (eg: hhiirree)
2. Valid words has concatenation property i.e. if w1 and w2 are valid words w1w2 is also a valid word.
Since definition 1 says "h^n i^n r^n e^n where n >=1" each character has to appear in the word and the counts of each character have to be the same.
No assumption is made about the order of the characters!
Let's use some examples:
hire: valid
ire: not valid
ihre: valid
hhiirree: valid
eeiirrhh: valid
All the function needs to do is count each occurrence of the alphabet characters.
An equal count means pass.
Here is my code. Note I am not using 3rd party Java StringUtils lib. - all standard Java:
public class WordValidator {
static public String alphabet = "hire";
public WordValidator() {}
public static boolean ValidateWord(String str) {
if (str.length() == 0) return false;
char[] charset = alphabet.toCharArray();
str = str.toLowerCase();
int n = str.length() - str.replace(String.valueOf(charset[0]), "").length();
for (int i = 1; i < charset.length; i++) {
int count = str.length() - str.replace(String.valueOf(charset[i]), "").length();
if (count != n)
return false;
}
return true;
}
}
public static boolean wordBrute(String word, int index) {
if(index>=word.length())
return true;
int[] hist = new int[4];
int i;
outerLoop:
for(i=index;i<word.length();i++) {
char histChar = word.charAt(i);
switch(histChar) {
case 'h': {
hist[0]++;
break;
}
case 'i': {
if(check(hist,1))
return false;
hist[1]++;
break;
}
case 'r': {
if(check(hist,2))
return false;
hist[2]++;
break;
}
case 'e': {
if(check(hist,3))
return false;
while(i<word.length() && word.charAt(i) == 'e' ) {
i++;
hist[3]++;
}
break outerLoop;
}
default:
return false;
}
}
int prev = hist[0];
for(int j=1;j<hist.length;j++) {
if(hist[j] != prev)
return false;
prev = hist[j];
}
return true && (wordBrute(word,i));
}
public static boolean check(int[] hist,int index) {
return hist[index-1] == 0;
}
We know that there are four letters in the language and a correct word would have equal numbers of each character(as per question I am assuming)
Then we can just do following:
length = word.length;
if length %4 != 0 return false; // our word would always be of length multiple of four
else if {
int ind = length/4;
if(word.charAt(ind) != 'i') return false;
if(word.charAt(ind*2) !='r') return false;
if(word.charAt(ind*3) !='e') return false;
}
This example if for words starting with 'h' also I know I haven't checked other indexes in word...but I think you get the idea
just keep a count of the first char and compare to the others on the way through, reset the letters index when finish one check
public static boolean isValidWord(String word, char[] letters){
if(word==null || word.isEmpty() || letters==null || letters.length==0){
return false;
}
else{
int index = 0;
int count = 0;
int tmpCount = 0;
for(int i=0; i<word.length(); i++){
if(word.charAt(i)==letters[index]){
if(index==0){
count++;
}
tmpCount++;
}
else if(word.charAt(i)!=letters[index] && tmpCount!=count){
//not matching letters[index]
return false;
}
else if(word.charAt(i)!=letters[index] && index==letters.length-1){
//end of 1 valid word
index = 0;
i--;
tmpCount=0;
count = 0;
}
else if(word.charAt(i)!=letters[index]){
index++;
i--;
tmpCount=0;
}
}
if(index==letters.length-1 && tmpCount==count){
return true;
}
else{
return false;
}
}
}
public static void main(String[] args) {
System.out.println(isValidWord("HIREHHIIRREE", new char[]{'H','I','R','E'})); //true
System.out.println(isValidWord("HIREHHIIRRREE", new char[]{'H','I','R','E'})); //false
System.out.println(isValidWord("HIREHHIIRREEHIE", new char[]{'H','I','R','E'})); //false
}
This is another problem where using a state machine would be useful. We have 4 states. Depending on what’s being read at each state, we can either transition to the next state or we can simply return false (basically we reach an invalid state). If we have reached the end of the string and our state is the final state, we can simply return true; otherwise, we return false.
Following is the state machine. We need to consider the input h, i, r, e. The tricky part is that at each state, we should focus on what we are expecting and whatever we get is NOT what we are expecting, we return fasle. This corresponds to the invalid state. For example, in State 0, we expect either ‘h’ or ‘i'. If we don’t get either, we return false. In State 1, we expect either ‘i' or ‘r’. If we don’t get either, we return false.
We have the following states:
S0: initial state.
S1 and S2: intermediate states.
S3: state when pattern h^n i^n r^n e^n is achieved.
Here is the SM transition:
INPUT CURRENT_STATE NEXT_STATE
h S0 S0
i S0 S1
(!h && !i) S0 invalid
i S1 S1
r S1 S2
(!i && !r) S1 invalid
r S2 S2
e S2 S3
(!r && !e) S2 invalid
e S3 S3
h S3 S0
(!e && !h) S3 invalid
Here is the code:
bool isValidWord(std::string str)
{
int curState = 0;
for(int i = 0; i < str.length(); ++i) {
switch(curState) {
case 0:
if(str[i] == "i") {
curState = 1;
}
else if(str[i] != "h" && str[i] != "i") {
return false;
}
break;
case 1:
if(str[i] == "r") {
curState = 2;
}
else if(str[i] != "i") { // not i nor r. if it's "i", we just
// stay in the current state
return false;
}
break;
case 2:
if(str[i] == "e") {
curState = 3;
}
else if(str[i] != "r") { // not e nor r. if it's "r", we just
// stay in the current state
return false;
}
break;
case 3:
if(str[i] == "h") {
curState = 0; // concatenation of two strings
}
else if(str[i] != "e") { // not h nor e. if it's "e", we just stay
// in the current state
return false;
}
break;
default:
return false;
break;
}
}
// when we reach the end of the string and we are in the final state, we
// return true
if(state == 3)
return true;
return false;
}
public class GoogleHireProblem {
static boolean validWordInLanguage(String s){
if(s.length() == 0){
return false;
}
// check if concatenated by two valid words
char[] sChars = s.toCharArray();
int numOccurencesOfHInWord1=0;
boolean done=false;
int i = 0;
while(!done && i < sChars.length){
if(sChars[i] == 'h'){
i++;
numOccurencesOfHInWord1++;
} else if(sChars[i] == 'i') {
done = true;
break;
} else {
return false;
}
}
int numOccurencesOfIInWord1 = 0;
done = false;
while(!done && i < sChars.length){
if(sChars[i] == 'i'){
i++;
numOccurencesOfIInWord1++;
} else if(sChars[i] == 'r') {
done = true;
break;
} else {
return false;
}
}
if(numOccurencesOfHInWord1 != numOccurencesOfIInWord1){
return false;
}
int numOccurencesOfRInWord1 = 0;
done = false;
while(!done && i < sChars.length){
if(sChars[i] == 'r'){
i++;
numOccurencesOfRInWord1++;
} else if(sChars[i] == 'e'){
done = true;
break;
} else {
return false;
}
}
if(numOccurencesOfIInWord1 != numOccurencesOfRInWord1){
return false;
}
int numOccurencesOfEInWord1 = 0;
done = false;
while(!done && i < sChars.length){
if(sChars[i] == 'e'){
i++;
numOccurencesOfEInWord1++;
} else if(sChars[i] == 'h'){
done = true;
break;
} else {
return false;
}
}
if(numOccurencesOfRInWord1 != numOccurencesOfEInWord1){
return false;
}
if(i < sChars.length-1){
String word2 = s.substring(i);
//System.out.println(word2);
return(validWordInLanguage(word2));
} else {
return true;
}
}
public static void main(String[] args){
String[] testcases = {"hire" , "", "hhiirree" , "hhiirreehire"};
for(String s : testcases){
boolean isValidWord = validWordInLanguage(s);
System.out.println(s + "\t" + isValidWord);
}
}
}
In Ruby code, O(N)
def validate_hire( str )
alphabet = "hire".split("")
i = -1
prev_x = nil
str.split("").each do |x|
i += 1 unless prev_x == x
return false if alphabet[i % alphabet.size] != x
prev_x = x
end
(i+1) % alphabet.size == 0
end
def main()
p validate_hire("hire") # ==> true
p validate_hire("hhiirree") # ==> true
p validate_hire("hhiiiiirrreeeehire") # ==> true
p validate_hire("hireh") # ==> false
end
public class HireLanguage {
//hire, hhiirree
public boolean checkLanguage (String str) {
int n = 0, count = 0, i = 0;
char[] valid = new char [] {'h', 'i', 'r', 'e'};
int charPos = 0;
while(i < str.length()) {
char currChar = str.charAt(i);
if(currChar == valid[charPos]) {
++count;
}
else if((charPos + 1) < valid.length && currChar == valid[charPos + 1]) {
if(n == 0) {
n = count;
}
else if(count != n) {
return false;
}
count = 1;
++charPos;
if(charPos == -1) n = 0;
}
else {
if(charPos == 3) charPos = 0;
else {
return false;
}
}
if(i == (str.length() - 1) && charPos != 3) return false;
++i;
}
return true;
}
}
How about a recursive dynamic programming approach? For a word to conform to a language, all sub-words must also conform to the language. You can cut down on calls by calling isValidWord on substring from 1 - s.length()-1, but you dictionary won't fill as fast.
private static HashMap<String, Boolean> dictionary = new HashMap<String, Boolean>();
/**
* Returns whether a word is a valid "word", i.e. made up of characters
* in the character array
* @param c
* @return
*/
public static boolean isValidWord(String s, char [] c) {
if (dictionary.containsKey(s)) { //word found in dictionary
return true;
}
if (s.length() == 0) //empty words are in the language
return true;
boolean goLeft = false;
boolean goRight = false;
for (int i = 0; i < c.length; i++) { //if word not in dictionary, check ends
if (s.charAt(0) == c[i])
goLeft = true;
if (s.charAt(s.length()-1) == c[i])
goRight = true;
}
if (s.length() <= 1 && goLeft && goRight)
return true;
if (goLeft == false || goRight == false) {
return false;
}
boolean isValid = isValidWord(s.substring(1, s.length()), c) && isValidWord(s.substring(0, s.length()-1), c);
if (isValid) {
dictionary.put(s.substring(1, s.length()-1), true);
}
return isValid;
}
there's no need for dynamic programming. hashing strings will be much more expensive than performing a O(string_len) check.
1) There's no reason to use a Map. A set would be a better approach.
2) With this recursion algo, you're not saving any time because your map will always be empty until you get to the end of your string and start coming out of your recursion stack. Every word gets placed into the map and every existing word gets overwritten.
@Miguel - the O(string_len) only holds because the language is defined here as containing "hire". If it contained more characters, w/o dynamic programming you're looking at O(n^2).
@Nothing Special - I agree with your set comment. As for the second, with dynamic programming it's true that every permutation of the string has to be computed the first time, but subsequent calls are all cached so would be much faster.
Here is the approach
1. First reduce the string to non-repetitive characters like fors hhiirreee -> hire or hhiirreehhii->hirehi
2. Now in final reduced String check if its repettion of "hire". E.g. hir or hirehire wil be valid whereas hirehi is NOT
boolean isValid(String word){
//TODO:Check for null and empty
String reduced = new String(word.charAt(0));
for(int i=1;i<word.length;i++){
char c = word.charAt(i);
if(c==reduce.charAt(reduced.length-1))
continue;
else
reduced += c;
}
//Check if reduced is made up with only "hire"
for(int i=0;i<reduced.length;i=i+4){
if(reduced.length<i+4)
return false;
else{
if("hire".equals(reduced.substring(i,i+4))
return false;
}
}
return true;
}
private static final int STATE_INITIAL = 0;
private static final int STATE_H = 1;
private static final int STATE_I = 2;
private static final int STATE_R = 3;
private static final int STATE_E = 4;
public static boolean isWordValid(char[] word) {
int state = STATE_INITIAL;
for (int i = 0; i < word.length; i++) {
char letter = word[i];
switch (state) {
case STATE_INITIAL:
if(letter == 'H') state = STATE_H;
break;
case STATE_H:
if(letter == 'H') state = STATE_H;
else if(letter == 'I') state = STATE_I;
break;
case STATE_I:
if(letter == 'I') state = STATE_I;
else if(letter == 'R') state = STATE_R;
break;
case STATE_R:
if(letter == 'R') state = STATE_R;
else if(letter == 'E') state = STATE_E;
break;
case STATE_E:
if(letter == 'E') state = STATE_E;
else if(letter == 'H') state = STATE_H;
break;
default:
return false;
}
}
if(state == STATE_E || state== STATE_INITIAL) return true;
else return false;
}
private static final int STATE_INITIAL = 0;
private static final int STATE_H = 1;
private static final int STATE_I = 2;
private static final int STATE_R = 3;
private static final int STATE_E = 4;
public static boolean isWordValid(char[] word) {
int state = STATE_INITIAL;
for (int i = 0; i < word.length; i++) {
char letter = word[i];
switch (state) {
case STATE_INITIAL:
if(letter == 'H') state = STATE_H;
break;
case STATE_H:
if(letter == 'H') state = STATE_H;
else if(letter == 'I') state = STATE_I;
break;
case STATE_I:
if(letter == 'I') state = STATE_I;
else if(letter == 'R') state = STATE_R;
break;
case STATE_R:
if(letter == 'R') state = STATE_R;
else if(letter == 'E') state = STATE_E;
break;
case STATE_E:
if(letter == 'E') state = STATE_E;
else if(letter == 'H') state = STATE_H;
break;
default:
return false;
}
}
if(state == STATE_E || state== STATE_INITIAL) return true;
else return false;
}
A solution based on 4-state DFA. Python code:
def accept(s):
dic = {"h": 0, "i": 1, "r": 2, "e": 3}
s = map(lambda x: dic[x], s)
# q_0 is 0, A is {3}
dfa = [
[0, 1, None, None],
[None, 1, 2, None],
[None, None, 2, 3],
[0, None, None, 3],
]
q = 0
for a in s:
q = dfa[q][a]
if q == None:
return False
return a == 3
s = "hhirre"
print(accept(s))
s = "hirehhhirre"
print(accept(s))
s = "hir"
print(accept(s))
Small and simple (if regexp were allowed)
public static void main(String[] args)
{
Pattern p = Pattern.compile("(hh+ii+rr+ee+)+");
Matcher m = p.matcher("hhhhiirreehhiirree");
System.out.println(m.matches());
}
I have no idea who put negative points to your answer. I have a feeling that those people will fail an interview.
hugakkahuga, you are wrong. Pointing out that you can solve this with regex will give you extra points. Coding interviews test whether you can code, not whether you know algorithms. There is a big difference between these two.
This answer looks like a very good solution to me.
it is incorrect because the word "hiree" is invalid and the regular expression would accept it.
"A given word is a valid word if it is of the form h^n i^n r^n e^n where n >=1. (eg: hhiirree) "
That equal sign says that "hiree" is a valid word (letter must appear at least once), doesn't it?
Let's make it an "ordered" alphabet array
by letting (compile time fixed or get from somewhere at runtime):
alpha[]={ your ordered list of characters in your alphabet }
M be size of your ordered alphabet (i.e., size of alphabet array above)
idea:
for(t=0,i = 0,count=0; i < str.length ; i++) if( str[i] == alpha[t %M] ) count++; else if( str[i] == alpha[++t %M] && count > 1) count=1; else return false; return ( count >1 && t==M-1) ? true : false;Untested. Fix the bugs please.
- S O U N D W A V E October 24, 2013Maybe I'm missing something, but why do we need fancy stuff?