Adobe Interview Question
SDE1sCountry: India
/**
* Created by kr.abhishek on 10/12/2016.
*/
import java.util.Arrays;
import java.util.Scanner;
public class ArrayTest {
public static void main (String [] args)
{
int a[][] = {{1,92,43,4,5},{234,341,56}};
int b=a.length;
for (int i=0;i<a.length; i++)
{
Arrays.sort(a[i]);
for (int j=0;j<a[i].length;j++)
{
System.out.println(a[i][j]);
}
}
System.out.println("value of legth of a is:"+b);
Scanner scanner = new Scanner(System.in);
System.out.println("enter any string to know its type or enter Q to quit");
String str=null;
do {
str = scanner.nextLine();
System.out.println("the string "+str+"type is "+ stringtest(str));
}
while (!"Q".equals(str));
}
public static String stringtest(String s)
{
int vowelcnt=0;
int conscnt=0;
int qvcnt =0;
int qccnt=0;
String strtype;
for(int i=0;i<s.length();i++) {
if (checkvowel(s.charAt(i)) && s.charAt(i) != '?') {
vowelcnt++;
conscnt = 0;
if (vowelcnt == 3)
break;
}
if (checkconsonant(s.charAt(i)) && s.charAt(i) != '?') {
conscnt++;
vowelcnt = 0;
if (conscnt == 5)
break;
}
if (s.charAt(i) == '?') {
if (vowelcnt == 0 && conscnt == 0) {
while (s.charAt(++i) == '?' && i < s.length() - 1) {
System.out.println("inside while");
}
System.out.println("value of i at exit:" + i);
if (i >= 2) {
return "Mixed";
}
if (checkconsonant(s.charAt(i))) {
qccnt++;
conscnt++;
}
if (checkvowel(s.charAt(i))) {
qvcnt++;
vowelcnt++;
}
}
if (vowelcnt > 0) {
qvcnt++;
vowelcnt++;
if (i < s.length() - 1) {
i++;
if (checkvowel(s.charAt(i))||s.charAt(i)=='?') {
qvcnt++;
vowelcnt++;
}
if (checkconsonant(s.charAt(i))) {
qccnt++;
conscnt++;
}
}
}
if (conscnt > 0) {
qccnt++;
conscnt++;
if (i < s.length() - 1) {
i++;
if (checkconsonant(s.charAt(i))||s.charAt(i)=='?') {
qccnt++;
conscnt++;
}
if (checkvowel(s.charAt(i))) {
qvcnt++;
vowelcnt++;
}
}
}
}
if (conscnt == 5) {
if (qccnt > 0)
strtype = "MIxed";
else
strtype = "Bad";
return strtype;
}
if (vowelcnt == 3) {
if (qvcnt > 0)
strtype = "MIxed";
else
strtype = "Bad";
return strtype;
}
}
strtype="Good";
return strtype;}
public static boolean checkvowel(char c)
{
return (c=='a'||c=='e'||c=='i'||c=='o'||c=='u');
}
public static boolean checkconsonant(char c)
{
return (c=='b'||c=='c'||c=='d'||c=='f'||c=='g'||c=='h'||c=='j'||c=='k'||c=='l'||c=='m'||c=='n'||c=='p'||c=='q'||c=='r'||c=='s'||c=='t'||c=='v'||c=='w'||c=='x'||c=='y'||c=='z');
}
}
/**
* Created by kr.abhishek on 10/12/2016.
*/
import java.util.Arrays;
import java.util.Scanner;
public class ArrayTest {
public static void main (String [] args)
{
int a[][] = {{1,92,43,4,5},{234,341,56}};
int b=a.length;
for (int i=0;i<a.length; i++)
{
Arrays.sort(a[i]);
for (int j=0;j<a[i].length;j++)
{
System.out.println(a[i][j]);
}
}
System.out.println("value of legth of a is:"+b);
Scanner scanner = new Scanner(System.in);
System.out.println("enter any string to know its type or enter Q to quit");
String str=null;
do {
str = scanner.nextLine();
System.out.println("the string "+str+"type is "+ stringtest(str));
}
while (!"Q".equals(str));
}
public static String stringtest(String s)
{
int vowelcnt=0;
int conscnt=0;
int qvcnt =0;
int qccnt=0;
String strtype;
for(int i=0;i<s.length();i++) {
if (checkvowel(s.charAt(i)) && s.charAt(i) != '?') {
vowelcnt++;
conscnt = 0;
if (vowelcnt == 3)
break;
}
if (checkconsonant(s.charAt(i)) && s.charAt(i) != '?') {
conscnt++;
vowelcnt = 0;
if (conscnt == 5)
break;
}
if (s.charAt(i) == '?') {
if (vowelcnt == 0 && conscnt == 0) {
while (s.charAt(++i) == '?' && i < s.length() - 1) {
System.out.println("inside while");
}
System.out.println("value of i at exit:" + i);
if (i >= 2) {
return "Mixed";
}
if (checkconsonant(s.charAt(i))) {
qccnt++;
conscnt++;
}
if (checkvowel(s.charAt(i))) {
qvcnt++;
vowelcnt++;
}
}
if (vowelcnt > 0) {
qvcnt++;
vowelcnt++;
if (i < s.length() - 1) {
i++;
if (checkvowel(s.charAt(i))||s.charAt(i)=='?') {
qvcnt++;
vowelcnt++;
}
if (checkconsonant(s.charAt(i))) {
qccnt++;
conscnt++;
}
}
}
if (conscnt > 0) {
qccnt++;
conscnt++;
if (i < s.length() - 1) {
i++;
if (checkconsonant(s.charAt(i))||s.charAt(i)=='?') {
qccnt++;
conscnt++;
}
if (checkvowel(s.charAt(i))) {
qvcnt++;
vowelcnt++;
}
}
}
}
if (conscnt == 5) {
if (qccnt > 0)
strtype = "MIxed";
else
strtype = "Bad";
return strtype;
}
if (vowelcnt == 3) {
if (qvcnt > 0)
strtype = "MIxed";
else
strtype = "Bad";
return strtype;
}
}
strtype="Good";
return strtype;}
public static boolean checkvowel(char c)
{
return (c=='a'||c=='e'||c=='i'||c=='o'||c=='u');
}
public static boolean checkconsonant(char c)
{
return (c=='b'||c=='c'||c=='d'||c=='f'||c=='g'||c=='h'||c=='j'||c=='k'||c=='l'||c=='m'||c=='n'||c=='p'||c=='q'||c=='r'||c=='s'||c=='t'||c=='v'||c=='w'||c=='x'||c=='y'||c=='z');
}
}
Below is the implementation in C++
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <locale>
using namespace std;
enum StrType { GOOD, BAD, MIXED };
bool isChar(char c)
{
if(c >= 'a' && c <= 'z')
return true;
return false;
}
bool isVowel(char c)
{
if(c == 'a' || c == 'e' || c == 'i'
|| c == 'o' || c == 'u')
return true;
return false;
}
StrType checkStrType(string str)
{
int vcnt = 0, vcnt_mixed = 0;
int ccnt = 0, ccnt_mixed = 0;
bool mixed = false;
for_each(str.begin(), str.end(), [](char &x){x = tolower(x);});
for(int i = 0; i < str.size(); i++){
if(isChar(str[i])){
if(isVowel(str[i])){
vcnt++;
if(vcnt_mixed > 0)
vcnt_mixed++;
ccnt = ccnt_mixed = 0;
}
else {
ccnt++;
if(ccnt_mixed > 0)
ccnt_mixed++;
vcnt = vcnt_mixed = 0;
}
}
else if(str[i] == '?'){
vcnt_mixed += vcnt + 1;
ccnt_mixed += ccnt + 1;
vcnt = ccnt = 0;
}
if(vcnt >= 3 || ccnt >= 5)
return BAD;
if(vcnt_mixed >= 3 || ccnt_mixed >= 5)
mixed = true;
}
return mixed ? MIXED : GOOD;
}
Here are some test results.
abc : GOOD
abcdefghjkl : BAD
abcd?eg : GOOD
abcd?eij : MIXED
abcd?keij : MIXED
abcd??eij : MIXED
kbd??ej : MIXED
kbd?e? : MIXED
?aa : MIXED
: GOOD
jk : GOOD
class test
{
public static void main(String ar[])
{
String s="dsjg?uoaerfgkahe";
String v="aeiou";
int vo=0,cons=0,flag1=0,flag2=0;
char ch[]=s.toCharArray();
for(int i=0;i<s.length();i++)
{
if((v.contains(""+ch[i]) || ch[i]=='?')&&i<s.length()-3)
{
if((v.contains(""+ch[i+1]) || ch[i+1]=='?') && (v.contains(""+ch[i+2]) || ch[i+2]=='?'))vo=1;
if(ch[i]=='?'|| ch[i+1]=='?'|| ch[i+2]=='?')flag1=1;
}
if((!v.contains(""+ch[i])||ch[i]=='?')&&i<s.length()-5)
{
if((!v.contains(""+ch[i+1])||ch[i+1]=='?')&&(!v.contains(""+ch[i+2])||ch[i+2]=='?')&&(!v.contains(""+ch[i+3])||ch[i+3]=='?')&&(!v.contains(""+ch[i+4])||ch[i+4]=='?'))
cons=1;
if(ch[i]=='?'||ch[i+1]=='?'||ch[i+2]=='?'|| ch[i+3]=='?'||ch[i+4]=='?')flag2=2;
}
}
if(flag1!=0 && flag2!=0)
System.out.println("MIXED");
else if(vo!=0||cons!=0)
System.out.println("BAD");
else
System.out.println("GOOD");
}
}
class test
{
public static void main(String ar[])
{
String s="dsjg?uoaerfgkahe";
String v="aeiou";
int vo=0,cons=0,flag1=0,flag2=0;
char ch[]=s.toCharArray();
for(int i=0;i<s.length();i++)
{
if((v.contains(""+ch[i]) || ch[i]=='?')&&i<s.length()-3)
{
if((v.contains(""+ch[i+1]) || ch[i+1]=='?') && (v.contains(""+ch[i+2]) || ch[i+2]=='?'))vo=1;
if(ch[i]=='?'|| ch[i+1]=='?'|| ch[i+2]=='?')flag1=1;
}
if((!v.contains(""+ch[i])||ch[i]=='?')&&i<s.length()-5)
{
if((!v.contains(""+ch[i+1])||ch[i+1]=='?')&&(!v.contains(""+ch[i+2])||ch[i+2]=='?')&&(!v.contains(""+ch[i+3])||ch[i+3]=='?')&&(!v.contains(""+ch[i+4])||ch[i+4]=='?'))
cons=1;
if(ch[i]=='?'||ch[i+1]=='?'||ch[i+2]=='?'|| ch[i+3]=='?'||ch[i+4]=='?')flag2=2;
}
}
if(flag1!=0 && flag2!=0)
System.out.println("MIXED");
else if(vo!=0||cons!=0)
System.out.println("BAD");
else
System.out.println("GOOD");
}
}
Here's an O(n) time, O(n) space solution.
Basic approach :
Dynamic programming.
For every '?' , we got two options : either fill a consonant , or a vowel and move forward. According to your previous choice, your prefix will change, i.e .
if you fill a consonant, your new function call will have c+1 consonants , and 0 vowels in the last streak.
so the recurrence boils down to two cases.
1. when its not a '?'
classify(startindex, consonants , vowels ) = classify(startindex + 1, consonants +1 , 0)
OR
classify(startindex, consonants , vowels ) = classify(startindex + 1, 0 , vowels + 1)
depending on whether the character at startindex is a consonant or a vowel.
2. when its a '?'
in this case , you need to check both cases, consonant and vowel
let c_val = classify(startindex+1 , consonant+1 , 0)
let v_val = classify(startindex+1 , 0 , vowel+1)
now the answer will be :
- if both c_val and v_val are good, then answer is good
- if both c_val and v_val are bad, then answer is bad
- the answer is mixed in all other cases
Here's the code(C++) :
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long int lli;
typedef vector<lli> vli;
#define GOOD 1
#define BAD -1
#define MIXED 0
bool isvowel(char c)
{
string s = "aeiou";
for(char x : s)
{
if(c == x)
return true;
}
return false;
}
int substringtype[10000][6][4];
int classify(const string &s , int start = 0 , int c = 0 , int v = 0)
{
if(c==5 || v==3)
return BAD;
if(start == s.size())
return GOOD;
if(substringtype[start][c][v] != -1)
{
return substringtype[start][c][v];
}
if(s[start] != '?')
{
if(isvowel(s[start]))
{
substringtype[start][c][v] = classify(s , start+1 , 0 ,v+1);
return substringtype[start][c][v];
}
substringtype[start][c][v] = classify(s, start + 1, c+1 , 0);
return substringtype[start][c][v];
}
int c_opt = classify(s, start + 1, c+1 , 0);
int v_opt = classify(s, start + 1, 0 , v+1);
if(v_opt == c_opt)
{
substringtype[start][c][v] = v_opt;
}
else
substringtype[start][c][v] = MIXED;
return substringtype[start][c][v];
}
int main()
{
int i, j, k;
for(i=0;i<10000;i++)
{
for(j=0;j<6;j++)
{
for(k=0;k<4;k++)
{
substringtype[i][j][k] = -1;
}
}
}
cout<<classify("ab??bbb")<<endl;
}
public static string CategorizedString(string s)
{
// if three consecutive Vowels - or five consecutive consonants (alphabets-aeiou - 21 symbols) - bad
// if a?i - sounds bad , aeio? sounds bad
// else good
int vcount = 0;
int ccount = 0;
int vmixed = 0;
int cmixed = 0;
int i = 0;
while (i < s.Length)
{
if (IsVowel(s[i]) || s[i]=='?')
{
if (i == 0)
{
vcount++;
if (s[i] == '?')
vmixed++;
}
if (i > 0)
{
if ((IsVowel(s[i - 1]) || s[i - 1] == '?') && s[i] != '?')
{
vcount++;
ccount = 0;cmixed = 0;
}
if (s[i] == '?')
{
vmixed++;vcount++;
}
}
}
if (IsConsonants(s[i]))
{
if (i == 0)
{
ccount++;
if (s[i] == '?')
cmixed++;
}
if (i > 0)
{
if (IsConsonants(s[i - 1]) && s[i] != '?')
{
ccount++;
vcount = 0;vmixed = 0;
}
if (s[i ] == '?')
{
cmixed++; ccount++;
}
}
}
if ((ccount == 5 && cmixed == 0) || (vcount == 3 && vmixed == 0))
return "bad";
else if ((ccount == 5 && cmixed > 0) || (vcount == 3 && vmixed > 0)) return "mixed";
if (s[i]=='?')
{
// do nothing as we checking it in above scenarios
//continue;
}
i++;
}
return "good";
}
static bool IsVowel(char c)
{
HashSet<char> vowels = new HashSet<char>() { 'a', 'e', 'i', 'o', 'u' };
return vowels.Contains(c);
}
static bool IsConsonants(char c)
{
return !IsVowel(c) ;
}
import java.io.*;
public class String_GOOD_MIXED_BAD
{
public static void main(String[] args)throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String str=br.readLine();
char[] ch=str.toCharArray();
if(isBad(str)==1)
{
System.out.println("BAD");
}
else if(isMixed(str)==1)
{
System.out.println("MIXED");
}
else
{
System.out.println("GOOD");
}
}
public static int isMixed(String s)
{
for(int i=0;i<=s.length()-3;i++)
{
int v=0;
int q=0;
String sub=s.substring(i,i+3);
char[] t=sub.toCharArray();
for(char ch:t)
{
if(ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')
{
v++;
}
else if(ch=='?')
{
q++;
}
}
if((v==0&&q==3)||(v==1&&q==2)||(v==2&&q==1))
{
return 1;
}
}
for(int i=0;i<=s.length()-3;i++)
{
int c=0;
int q=0;
String sub=s.substring(i,i+3);
char[] t=sub.toCharArray();
for(char ch:t)
{
if(c>='a'&&c<='z'&&c!='a'&&c!='e'&&c!='i'&&c!='o'&&c!='u')
{
c++;
}
else if(ch=='?')
{
q++;
}
}
if((c==0&&q==5)||(c==1&&q==4)||(c==2&&q==3)||(c==3&&q==2)||(c==4&&q==1))
{
return 1;
}
}
return -1;
}
public static int isBad(String s)
{
for(int i=0;i<=s.length()-3;i++)
{
int vws=0;
String sub=s.substring(i,i+3);
char[] t=sub.toCharArray();
for(char ch:t)
{
if(isVowel(ch)==1)
{
vws++;
}
}
if(vws==3)
{
return 1;
}
}
for(int j=0;j<=s.length()-5;j++)
{
int con=0;
String sub=s.substring(j,j+5);
char[] t=sub.toCharArray();
for(char ch:t)
{
if(isConso(ch)==1)
{
con++;
}
}
if(con==5)
{
return 1;
}
}
return -1;
}
public static int isVowel(char c)
{
if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')
{
return 1;
}
else
{
return -1;
}
}
public static int isConso(char c)
{
if(c>='a'&&c<='z'&&c!='a'&&c!='e'&&c!='i'&&c!='o'&&c!='u')
{
return 1;
}
else
{
return -1;
}
}
}
This is very lazy, using regex, and bad matching on them. But generally gives you the idea.
- NoOne October 12, 2016The fall back *order* is essential.