Epic Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
Can you please explain why we required hash table.? Because we have to check the same sequence is followed immediately or not?
Java code according to the above idea:
import java.util.HashMap;
public class ValidString {
public static void main(String[] args) {
String str = "123d123";
boolean cond3 = isseqValid(str);
boolean cond2 = ischarValid(str);
boolean cond1 = islenValid(str);
System.out.println(cond3&&cond2&&cond1);
}
private static boolean islenValid(String string) {
if(string.length()>=5 && string.length()<=12) return true;
return false;
}
private static boolean ischarValid(String string) {
char[] crs = string.toCharArray();
boolean num_flag = false;
boolean char_flag = false;
for(int i =0;i<string.length();i++){
if(crs[i] >= '0' && crs[i] <= '9'){
num_flag = true;
}
if(crs[i] >= 'a' && crs[i] <= 'z'){
char_flag = true;
}
}
return num_flag && char_flag;
}
public static boolean isseqValid(String str){
/**
* HashMap store the substring as a key and its ending index as a value.
* Before putting value into the hashmap, it checks if the substring already exists.
* If yes, retrieve the value and compare value + 1 with the starting index of the new substring.
* If they are equal, it means there are consecutive substrings.
*/
HashMap<String,Integer> stringindexMap = null;
int len = str.length();
for(int i = 1; i< len ; i++){
stringindexMap = new HashMap<String,Integer>();
for(int j = 0; j+i <= len;j++){
String sub = str.substring(j,j+i);
if(stringindexMap.get(sub) == null){
stringindexMap.put(sub, j + i -1);
}
else{
int prevlastIndex = stringindexMap.get(sub);
if(prevlastIndex == j - 1) return false;
}
}
}
return true;
}
}
public class VerifyPasswd {
public static void verifyPasswd(String passwd) {
if (!checkLen(passwd))
return;
if (!checkChar(passwd))
return;
if (!checkSeq(passwd))
return;
System.out.println("Valid Passwd");
}
private static boolean checkSeq(String passwd) {
for (int index = 0; index < passwd.length(); index++) {
char c1 = passwd.charAt(index);
int index2 = passwd.indexOf(c1, index + 1);
if (index2 != -1) {
String str1 = passwd.substring(index, index2);
String str2 = passwd.substring(index2, 2 * index2 - index);
if(str1.equals(str2)){
return false;
}
}
}
return true;
}
private static boolean checkChar(String passwd) {
char[] chars = passwd.toCharArray();
boolean num_flag = false;
boolean lowercase_flag = false;
for (int i = 0; i < chars.length; i++) {
if (chars[i] >= '0' && chars[i] <= '9') {
num_flag = true;
}
if (chars[i] >= 'a' && chars[i] <= 'z') {
lowercase_flag = true;
}
}
if (num_flag && lowercase_flag) {
return true;
}
return false;
}
private static boolean checkLen(String passwd) {
if (passwd.length() < 5 || passwd.length() > 12) {
return false;
}
return true;
}
public static void main(String[] args) {
verifyPasswd("1123123qs");
}
}
I change a little bit in your method checkSeq(), so it can check case like:"1310213102a"
public static boolean checkSeq(String pw) {
for (int i = 0; i < pw.length(); i++) {
char c1 = pw.charAt(i);
int nextIndex = pw.indexOf(c1, i + 1);
while (nextIndex != -1) {
String s1 = pw.substring(i, nextIndex);
if (2 * nextIndex - i <= pw.length()) {
String s2 = pw.substring(nextIndex, 2 * nextIndex - i);
if (s1.equals(s2)) {
return false;
}
}
nextIndex = pw.indexOf(c1, nextIndex + 1);
}
}
return true;
}
public static void invalidPassword(String str)
{
for(int i=1;i<=str.length();i++)
{
Map<String,Integer[]> strMap = new HashMap<String, Integer[]>();
for(int j=0; j+i<=str.length();j++)
{
String key = str.substring(j, j+i);
System.out.println(" "+str.substring(j, j+i)+" "+j+" "+(j+i-1));
if(strMap.get(key)==null)
{
Integer indices[] = {j,(j+i-1)};
strMap.put(key,indices);
}
else
{
Integer indices[] = strMap.get(key);
if(j==indices[1]+1)
{
System.out.println("Repeat");
return;
}
}
}
System.out.println("");
}
}
1)Just count the no of characters and see if it lies between 5 and 12.
2)Keep the count of vowel and number encountered ,it should be greater than 1
3)Create a hash table with substring as key and its end index as value.Before inserting a pair <substring,ending index> in hash table ,check if substring is already present in hashtable, if present then ,its (ending index+1) should not be equal to starting index of this repeated substring.
I think it should work for this case too.Please correct if I am not able to see your point.
Hey S.A.M Please find the code for the question you posted and checks if it works properly and suites your requirements:
public class DubleSeqString
{
public static void main(String[] args)
{
DubleSeqString db = new DubleSeqString();
String pwd="azaasdasd";
if(pwd.length()>=5 && pwd.length()<= 12)
{
System.out.println("Password is between 5 and 12 !! Hence valid");
if(db.PasswordStringContains(pwd) == true)
{
System.out.println("Password contains number and lower case letters !! Hence Valid");
if(db.DoubleSeqExist(pwd)==true)
{
System.out.println("Password contains Double Seq characters Continously Hence Invalid");
}
else
{
System.out.println("Password Is valid");
}
}
else
{
System.out.println("Password does not contain numbers or lower case letters does not exist");
}
}
else
{
System.out.println("String Characters length does not match");
}
}
// Code to Check the Password contains small Characters and Number exists
public boolean PasswordStringContains(String pwd)
{
boolean numberexist=false,lowercaseexist=false;
for(int i=0;i<pwd.length();i++)
{
if(((int)pwd.charAt(i)) >= 48 && ((int)pwd.charAt(i)) <= 57)
{
numberexist=true;
}
if(((int)pwd.charAt(i)) >= 97 && ((int)pwd.charAt(i)) <= 122)
{
lowercaseexist=true;
}
}
if(numberexist==true && lowercaseexist==true)
{
return true;
}
else
{
return false;
}
}
/// Code to Check the Double Sequence String is not allowed
public boolean DoubleSeqExist(String pwd)
{
boolean SeqStringAllowed=false;
for(int i=0;i<pwd.length();i++)
{
int value = pwd.substring(i+1,pwd.length()).indexOf(pwd.charAt(i));
if(value > 0)
{
if((i+1+value+1+value) <= pwd.length()) // if(i+2*(value+1) <= pwd.lenght())
{
if(pwd.substring(i,i+1+value).equals(pwd.substring(i+1+value,i+2*(1+value))))
{
SeqStringAllowed=true;
break;
}
}
}
}
if(SeqStringAllowed==true)
{
return true;
}
else
{
return false;
}
}
}
Hello, Rewriting the DoubleSeqExist Method to check the String contains Double Seq Characters, Verified for Input "1310213102a". It allows repeated single character but not Double Sequence Characters.
public boolean DoubleSeqExist(String pwd)
{
boolean SeqStringAllowed=false;
int value=0;
int i=0,length=pwd.length();;
for(int j=0;j<pwd.length();j++)
{
do
{
value = pwd.substring(i,length).lastIndexOf(pwd.charAt(j));
if(value > 0 && value > (j+1))
{
if((j+2*(value-j)) <= pwd.length()) // if(i+2*(value+1) <= pwd.lenght())
{
if(pwd.substring(j,value).equals(pwd.substring(value,j+2*(value-j))))
{
SeqStringAllowed=true;
break;
}
}
}
length=value;
}
while(value>0);
if(SeqStringAllowed==true)
{
break;
}
length=pwd.length();
}
if(SeqStringAllowed==true)
{
return true;
}
else
{
return false;
}
}
}
/* Verify if the given password is valid/invalid;
1. must be 5-12 characters long
2. must contain atleast one number and one lowercase character
3. a sequence must not be followed by the same sequence (like 123123qs is invalid, 123qs123 is valid)
*/
import java.util.regex.*;
public class PasswordRejex{
public static void main(String abc[])
{
String password="123l123q";
// char [] pass = password.toCharArray();
char checkChar;
boolean check;
int indexOfRepeat=0;
String PASSWORD_PATTERN = "((?=.*\\d)(?=.*[a-z]).{5,12})";
Pattern p = Pattern.compile(PASSWORD_PATTERN);
Matcher m = p.matcher(password);
// System.out.println(m.matches());
check=m.matches();
if(m.matches()){
for(int i=0;i<password.length();i++)
{
indexOfRepeat=password.indexOf(password.substring(i,i+1),i+1);
if(indexOfRepeat>=0)
{
String patternOne = password.substring(i,indexOfRepeat);
char[] p1 =patternOne.toCharArray();
// System.out.print(patternOne+" and ");
String patternTwo = password.substring(indexOfRepeat);
char[] p2 =patternTwo.toCharArray();
// System.out.print(patternTwo+"\n");
// System.out.println("compare for length = "+patternOne.length());
for(int k=0;k<patternOne.length();k++){
if(p1[k]==p2[k])
{
// System.out.println("comparing "+p1[k]+" and "+p2[k]);
check=false;
}
else
{
// System.out.println("comparing "+p1[k]+" and "+p2[k]+" which obviousy does not match");
check=true;
break;
}
}
}
if(!check) break;
}
}
if(check)
System.out.println(" password "+password+" is valid");
else
System.out.println(" password "+password+" is invalid");
}
}
The following piece of code, generates all possible substrings and checks for a sequence. For example:
From "123123qs",
during the first round, the substrings "1", "12", "123", "1231" are generated and compared.
int main () {
char a[] = "123123qs";
char buff[256];
int a_lenth = strlen(a);
int i, j, match_found = 0;
for (i = 0; i < a_lenth; i++) {
for (j = i; j < i+(a_lenth-i)/2; j++) {
memset (buff, 0, sizeof (buff));
memcpy (buff, a+i, j-i+1);
if (memcmp (buff, a+j+1, j-i+1)) {
continue;
} else {
match_found = 1;
printf ("Not a valid password\n");
break;
}
}
if (match_found) {
break;
}
}
return 0;
}
No String specific functions in java are used(except for length() function)
public class ValidatePassword {
String str;
int length;
public ValidatePassword(String str){
this.str=str;
this.length=str.length();
}
public boolean validatePassword(){
if(!checkLength()){
System.out.println("check the length of the password");
return false;
}
if(!checkConstraint()){
System.out.println("include atleast one digit and one lower case character");
return false;
}
if(!checkSequence()){
System.out.println("avoid the sequences in the password");
return false;
}
return true;
}
public boolean checkLength(){
if(length>=5 && length<=12)
return true;
return false;
}
public boolean checkConstraint(){
int count1=0;
int count2=0;
for (int i = 0; i < length; i++) {
if(str.charAt(i)>='1' && str.charAt(i)<= '9')
count1++;
else if(str.charAt(i)>= 'a' && str.charAt(i)<= 'z')
count2++;
}
if(count1>=1 && count2>=1)
return true;
return false;
}
public boolean checkSequence(){
for (int k = 0; k < length; k++) {
int i=0;
int j=i+k;
while(i<j && j< length){
if(str.charAt(i)==str.charAt(j)){
int a=i+1;
int b=j+1;
boolean sequence=true;
for (int l = 1; l < k ; l++) {
if(a<b && b<length){
if(sequence){
if(str.charAt(a)!=str.charAt(b)){
sequence=false;
}
else{
a++;
b++;
}
}
else{
break;
}
}
else{
sequence=false;
}
}
if(sequence)
return false;
}
i++;
j++;
}//end of while loop
}//end of k for loop
return true;
}//end of checkSequence method
}
public class verifyPhone {
public static void main(String[] args) {
String phone="123qs123" ;
boolean len=false;
boolean num=false;
boolean seq=false;
len=checklen(phone);
num=checknum(phone);
seq=checkseq(phone);
System.out.println(len);
System.out.println(num);
System.out.println(seq);
if(len&&num&&seq){
System.out.println("this is a valid password");
}else{System.out.println("this is invalid password"); }
}
private static boolean checkseq(String phone) {
boolean seq=true;
char[] pass=phone.toCharArray();
for(int i=0;i<pass.length-1;i++){
for(int j=i+1;j<pass.length/2;j++){
if(pass[i]==pass[j]){
int count=0;
for(int k=i;k<j;k++){
if(pass[k]==pass[k+j-i]){
count++;
}
}
if(count==j-i){
seq=false;
}
}
}
}
return seq;
}
private static boolean checknum(String phone) {
boolean num=false;
if(containsLowerCase(phone)&&containsDigit(phone)){
num=true;
}
return num;
}
private static boolean containsLowerCase(String phone) {
boolean containslc=false;
if(phone!=null){
for(char c:phone.toCharArray()){
if(Character.isLowerCase(c)){
containslc=true;
}
}
}
return containslc;
}
public static boolean containsDigit(final String s){
boolean containsDigit = false;
if(s != null){
for(char c : s.toCharArray()){
if(Character.isDigit(c)){
containsDigit = true;
break;
}
}
}
return containsDigit;
}
private static boolean checklen(String phone) {
boolean len=false;
if(phone.length()>=5&&phone.length()<=12){len=true;}
return len;
}
}
Python version, use Hash table and store subset as key, index as value.
"""
5:03
@Python 2.7
Verify if the given password is valid/invalid;
1. must be 5-12 characters long
2. must contain atleast one number and one lowercase character
3. a sequence must not be followed by the same sequence (like 123123qs is invalid, 123qs123 is valid)
- S.A.M on March 10, 2012 in United States Report Duplicate | Flag
"""
class VeriPwd(object):
def __init__(self, pwd):
if pwd is None:
print 'Invalid Passwod'
raise SystemExit
self._pwd = pwd
self._seq = {}
def validate(self):
lenFlag = False
numFlag = False
lowFlag = False
seqFlag = True
if 5 <= len(self._pwd) <= 12:
lenFlag = True
for c in self._pwd:
if '0' <= c <= '9':
numFlag = True
if 'a' <= c <= 'z':
lowFlag = True
seqFlag = self.checkSeq()
# print lenFlag, numFlag, lowFlag, seqFlag
return (lenFlag and numFlag and lowFlag and seqFlag)
def checkSeq(self, seqLen = 2):
if seqLen >= len(self._pwd) / 2 + 1:
return True
for i in range(len(self._pwd) - seqLen + 1):
if self._pwd[i:i+seqLen] not in self._seq:
self._seq[self._pwd[i:i+seqLen]] = [i+seqLen]
print 'excuted',self._pwd[i:i+seqLen], str(i+seqLen)
else:
if i in self._seq[self._pwd[i:i+seqLen]]:
return False
# print 'XXX at', self._seq[self._pwd[i:i+seqLen]]
else:
self._seq[self._pwd[i:i+seqLen]].append(i+seqLen)
# print 'insert at', self._seq[self._pwd[i:i+seqLen]]
return self.checkSeq(seqLen+1)
if __name__ == '__main__':
vp = VeriPwd('12qs12ad12')
print vp.validate()
print '--------------'
vp = VeriPwd('123123qs')
print vp.validate()
public static void isPasswordValid()
{
String pass = "w8rtytrt";
boolean isPassword = true;
if (pass.matches("(?=.*\\d)(?=.*[a-z]).{5,12}"))
{
for (int i = 0; i < pass.length(); i++)
{
for (int j = 1 + i; j - i <= pass.substring(i).length() / 2; j++)
{
if (pass.substring(i, j)
.equals(pass.substring(j, j
+ pass.substring(i, j).length())))
{
isPassword = false;
break;
}
}
if (!isPassword)
break;
}
}
else
{
isPassword = false;
}
if (isPassword)
System.out.println("Valid password");
else
System.out.println("Invalid password");
}
//Verify if the given password is valid/invalid;
//1. must be 5-12 characters long
//2. must contain atleast one number and one lowercase character
//3. a sequence must not be followed by the same sequence (like 123123qs is invalid, 123qs123 is valid)
#include<conio.h>
#include<cstdlib>
#include<iostream>
#include<string.h>
bool flag=0;
using namespace std;
bool lenCheck(string in)
{ //flag=0;
if(in.length()>=5&&in.length()<=12) //strlen should be used with char array it can take spaces as well
//flag=1;
return true;
}
bool numCheck(string in)
{//flag=0;
const char *chars=in.c_str(); //always convert the string to char if u want to compare anthing like here
for(int i=0;i<in.length();i++)
if(chars[i]>='0' && chars[i]<='9')
// flag=1;
return true;
}
bool charCheck(string in)
{// flag=0;
const char *chars=in.c_str();
for(int i=0;i<in.length();i++)
if(chars[i]>='a'&& chars[i]<='z')
// flag=1;
return true;
}
bool seqCheck(string in)
{// flag=0;
int seqCount=0;
const char *chars=in.c_str();
for(int i=0;i<in.length();i++)
for(int j=i+1;j<in.length();j++)
if (chars[i]==chars[j])
seqCount++;
if(seqCount>1)
// flag=1;
return true;
}
int main()
{
string in;
cout<< "Enter password: ";
cin>>in;
cout<< in<<endl;
cout<<"len"<<lenCheck(in)<<endl;
cout<<"num"<<numCheck(in)<<endl;
cout<<"char"<<charCheck(in)<<endl;
cout<<"seq"<<seqCheck(in);
getch();
return 0;
}
The duplicate subsequence code is the trickiest bit. A simple solution is:
Loop through the password string character by character. For each character,
- Search for the next occurrence of the character in the string.
- Note the length between the next occurrence and the current position.
- Check if the string from the current position to the next occurrence is duplicated from the next occurrence onward; if so, a duplicate exists.
Note that this solution is O(n), and does not require any external storage other than the single substring examined.
#include <stdio.h>
void pwdcheck2(char *c)
{
int i , len= strlen(c);
int ret1 = 0, ret2 = 0;
for(i=0;i<len;i++)
{
char ch = c[i];
if (ch >= 'a' && ch <= 'z')
ret1 = 1;
if (ch >= '0' && ch <= '9')
ret2 = 1;
}
if (ret1)
printf("contains lower\n");
if (ret2)
printf("contians number\n");
}
void pwdcheck3(char *c)
{
int len = strlen(c);
int ret = 0,i,j;
for(i=0;i<len;i++)
{
for (j=i+1;j<len;j++)
{
if (c[i] == c[j])
{
if (!strncmp(c+i, c+j, j-i))
ret = 1;
}
}
}
if (ret==1)
printf("contains repetition\n");
}
int main()
{
char c[] = "xyabcabc2kl";
pwdcheck3(c);
pwdcheck2(c);
}
package p1;
public class validpassword {
public static void main(String args[])
{
String pass="12312312345a";
ifvalid(pass);
}
static void ifvalid(String pass)
{
if(is_len(pass)&&is_lowercase(pass)&& is_sequence(pass))
{
System.out.println(pass+" is valid password");
}
else{System.out.println(pass+" is invalid password");}
}
static boolean is_len(String pass1)
{
if(pass1.length()<5 ||pass1.length()>12)
{return false;}
return true;
}
static boolean is_lowercase(String pass1)
{ String ar="1234567890";
String ar1="A";
for(int i=0;i<pass1.length();i++)
{ for(int j=0;j<ar.length();j++)
{
pass1 =pass1.replaceAll(ar.substring(j,j+1),ar1);
}
}
// System.out.print(pass1);
for(int i=0;i<pass1.length();i++)
{
int n = (int)pass1.charAt(i);
if(n>=97)
{
return true;
}
}
return false;
}
static boolean is_sequence(String pass1)
{
int n=pass1.length()/2;
for(int j=2;j<=n;j++){
for(int i=j;i<=pass1.length()-j;i++)
{
if(pass1.regionMatches(i-j,pass1.substring(i, i+j),0, j))
{
return false;
}
}
}
return true;
}
}
C++ Version of mine
bool searchSuspect(std::pair< size_t, size_t >& in)
{
if (in.second == in.first)
return true;
return false;
}
bool sanityCheck (const std::string& in)
{
if (in.size() > 12 || in.size() < 5)
{
return false;
}
bool isNumberExist = false;
bool isLowerCaseExist = false;
std::pair< size_t, size_t > suspect;
for (size_t i = 0; i < in.size(); i++)
{
if ( islower(in[i]) )
isLowerCaseExist = true;
if ( isdigit(in[i]) )
isNumberExist = true;
size_t found = in.find( in[i], i+1 );
if (found != std::string::npos)
{
size_t dist = found - i;
if (suspect.second == 0 || dist == suspect.first)
{
suspect.first = dist;
suspect.second++;
}
else
{
if (searchSuspect(suspect))
return false;
suspect.first = dist;
suspect.second = 1;
}
continue;
}
if (searchSuspect(suspect))
return false;
suspect.second = 0;
}
if (isLowerCaseExist && isNumberExist)
return true;
else
return false;
}
int main()
{
std::string in1 = "123q123";
std::cout << std::boolalpha << sanityCheck(in1);
}
My solution using PHP:
<?php
function validatePassword($password)
{
if(strlen($password)<5 || strlen($password)>12)
return false;
$letExist=$numExist=false;
for($i=0;$i<strlen($password);$i++)
{
$chr=$password[$i];
if(is_numeric($chr))
$numExist=true;
else if(ord($chr)>=97 && ord($chr)<=122)
$letExist=true;
if($letExist && $numExist)
break;
}
if(!$letExist || !$numExist)
return false;
for($i=0;$i<strlen($password);$i++)
{
for($k=0;$k<strlen($password);$k++)
{
$cur=substr($password,$k,$i+1);
$len=strlen($cur);
$nxt=substr($password,$k+$len,$i+1);
if($cur==$nxt)
false;
}
}
return true;
}
?>
Naive methods are easy to come up with. You can either store all possible substrings (n^2) and then do string compare to search consecutive duplicate substrings, or use hash map to store all possible start locations. Refer to the top post for the first method. For the second method:
bool validPassword(string password) {
/* Check string length and upper lower case stuff... omitted */
unordered_multimap<char, int> umm;
for (int i = 0; i < password.size(); ++i) {
if (i != 0 && password[i] == password[i - 1]) return false;
if (umm.count(password[i])) {
auto range = umm.equal_range(password[i]);
for (auto it = range.first; it != range.second; ++it) {
int candstart = 2 * (*it).second - i + 1;
if (candstart < 0 || password[candstart] !=\
password[(*it).second + 1])
continue;
int candlen = i - (*it).second;
if (password.substr(candstart, candlen) == \
password.substr((*it).second + 1, candlen))
return false;
}
}
umm.insert(make_pair(password[i], i));
}
return true;
}
Admit it, both methods have complexity O(n^3).
I really think we can do better than O(n^3).
I am referring to longest repeated substring problem. If we construct the suffix tree (in O(N) by Ukkomen algorithm, or O(N^2) naive method), then for all N^2 suffix substring pairs, with O(N) preprocess time, we can do longest common prefix inqury in O(1) time for one pair of suffix substring (by Harel and Tarjan's algorithm, refer to
community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Introduction
), thus achieving O(N^2) time complexity.
This is a very interesting problem. Any thoughts and ideas, fellow CCers?
public boolean isValidPwd(String pwd){
return checkLength(pwd)&&checkSequence(pwd)&&checkChar(pwd);
}
public boolean checkLength(String pwd){
int len = pwd.length();
if(len<5||len>12) return false;
else return true;
}
public boolean checkChar(String pwd){
int alpha = 0, num=0;
for(int i=0;i<pwd.length();i++){
if(pwd.charAt(i)>='0'&&pwd.charAt(i)<='9') num++;
if(pwd.charAt(i)>='a'&&pwd.charAt(i)<='z') alpha++;
}
if(num>=1&&alpha>=1) return true;
else return false;
}
public boolean checkSequence(String pwd){
HashSet<String> hs = new HashSet<String>();
int len = pwd.length();
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
String str = pwd.substring(i,j);
if(!hs.contains(str)){
hs.add(str);
}else return false;
}
}
return true;
}
I wrote my code as below its working for checked one , please let me know if it is working for all cases.
public static void main(String[] args) {
String password = "1310213102a";//"aA1aA";
int len = password.length();
int i,j;
boolean repeated = false;
for(i=0;i<len;i++)
{
for (j=i+1;j<len;j++)
{
if (password.charAt(i) == password.charAt(j))
{
String sub1 = password.substring(i,j);
int subLen = sub1.length();
if( subLen > 1){
String sub2 = password.substring(j, ( j+subLen < len) ? j+subLen : len );
if( sub1.equals(sub2) ){
System.out.println(" sub1 = " + sub1 + " sub2 = " + sub2);
repeated = true;
}
}
}
}
}
if (repeated == true )
System.out.println("contains repetition\n");
}
public class PassValidator {
static Predicate<String> isGoodString = (String s) -> {
if (s.length() < 5 || s.length() > 12) return false;
boolean hasNumber = false;
boolean hasLowerCase = false;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!hasNumber && c >= '0' && c <= '9') hasNumber = true;
if (!hasLowerCase && c >= 'a' && c <= 'z') hasLowerCase = true;
HashSet<String> seqs = new HashSet<>();
int cap = Math.min(i, s.length() - i); // optimization
for (int j = i - 1; j >= 0 && j >= i - cap; j--) seqs.add(s.substring(j, i)); // filling hashmap with prev strings
for (int j = i + 1; j <= s.length() && j <= i + cap; j++) { // checking forward
if (seqs.contains(s.substring(i, j)))
return false;
}
}
if (hasNumber && hasLowerCase) return true;
return false;
};
public static void main(String[] args) {
List<String> test = Arrays.asList("123123qs", "123qs123","abcd9abab","abab9494", "ZAOEII");
System.out.println("printing only good strings");
test.stream().filter(isGoodString).forEach(s -> System.out.println(s));
}
}
boolean isValidPass(String pwd){
int len=pwd.length();
if(len>4 && len<13){
for(int i=0;i<len;i++){
int j = pwd.indexOf(pwd.charAt(i),i+1);
if(j != -1 && 2*j-i < len){
String patrn1 = pwd.substring(i,j);
String patrn2 = pwd.substring(j,j+(j-i));
if(patrn1.compareTo(patrn2) == 0){
return false;
}
}
}
if(chrNumCheck(pwd)==true) return true;
}
return false;
}
public static boolean hasDoubleSequence(String pwd)
{
for (int end1 = 0; end1 < pwd.length(); end1++)
{
int end2 = pwd.indexOf(pwd.charAt(end1),end1+1);
int len = end2 - end1;
System.out.println(end1+" "+end2);
if(end2 > -1 && len <= end1+1)
{
String s1 = pwd.substring(end1-len+1, end1+1);
String s2 = pwd.substring(end1+1, end2+1);
if(s1.equals(s2))
return true;
}
}
return false;
}
First two conditions are simple so here is the implementation of the last condition which checks if there are neighboring sequences in the string. Algo is follows:
1) In array are kept the latest indexes of each character in the string.
2) If the character occurred first time we add it to the array.
3) If the character occurred second time we check if the sequence is created by checking contiguous character from the previous occurrence and current
Code:
public static void main(String[] args) {
// char[] s = "123123qs".toCharArray();
//char[] s = "123qs123qs".toCharArray();
char[] s = "1w23qs1a2323qs".toCharArray();
int[] latestIndex = new int[256];
Arrays.fill(latestIndex, -1);
int startOfSeq = -1;
int startOfPrevSeq = -1;
int seqLength = 0;
for (int i = 0; i < s.length; i++) {
if (latestIndex[s[i]] == -1) {
latestIndex[s[i]] = i;
if (startOfSeq != -1) {
if (startOfPrevSeq + seqLength == startOfSeq) {
System.out.println("Not valid");
return;
} else {
for (int j = startOfSeq; j < i; j++) {
latestIndex[s[j]] = j;
}
}
}
startOfSeq = -1;
startOfPrevSeq = -1;
seqLength = 0;
} else {
if (startOfSeq == -1) {
startOfPrevSeq = latestIndex[s[i]];
startOfSeq = i;
seqLength = 1;
} else if (s[startOfPrevSeq + seqLength] == s[i]) {
seqLength++;
} else {
if (startOfPrevSeq + seqLength == startOfSeq) {
System.out.println("Not valid");
return;
} else {
for (int j = startOfSeq; j < i; j++) {
latestIndex[s[j]] = j;
}
startOfSeq = -1;
startOfPrevSeq = -1;
seqLength = 0;
i--;
}
}
}
}
if (startOfSeq != -1) {
if (startOfPrevSeq + seqLength == startOfSeq) {
System.out.println("Not valid");
return;
}
}
System.out.println("Valid");
}
1)Just count the no of characters and see if it lies between 5 and 12.
- Anonymous March 12, 20122)Keep the count of vowel and number encountered ,it should be greater than 1
3)Create a hash table with substring as key and its end index as value.Before inserting a pair <substring,ending index> in hash table ,check if substring is already present in hashtable, if present then ,its (ending index+1) should not be equal to starting index of this repeated substring.