Epic Systems Interview Question Software Engineer / Developers
lets say the security code is 12646 the user can either enter the correct code or can enter code missing only 1 digit from correct code like 124(6 is missing) abd the rest all digits must be in squence to correct code(like 124 is in seq but not 142). in short only one digit can be missed by preserving the seq. for above 2646,1646 and 124 are valid but not 1264,1246 646 etc. hope iam clear with my question
Algorithm
step1 : declare one variable "int only_missing_element;"
step2: start comparing standard String1 and our input String2
step3: only linear scanning, if one integer misses, then set that in only_missing_element
step4: if till the end of scan, int only_missing_element misses in string2, then condition passed;else failed
Time Complexity : O(n)
Space Complexity: O(1)
I think the above algo isn't correct. With this algo, how can u handle the case like, correct is 12646, but input is 1264 or 1246. Both of these 2 are supposed to be incorrect. However, with ur algo, they are going to be considered as correct.
My algo is that, we can use 2 set. One stores all missed chars, the other stores all matched chars. We compare all chars in 2 strings linearly. Whenever a miss or match happens, compare the current char with these 2 sets. There are 2 cases.
A. Miss:
1. If this char isn't in the missed set
(1) missed set is empty, then put it in and continue
(2) missed set isn't empty, then return false
2. After 1, check it with the matched set
(1) if it is in the matched set, it means this char was considered to be "matched" something before, so we should return false.
(2) if it isn't in the matched set, then this one is good and we can go ahead check the next one
B. Matched
1. If this char isn't in the matched set, put it in.
2. If this char is in the missed set, return false, since it was considered to be "missed" before. If it is already inside, then go on.
Another corner case I can come up with is that the correct password is running out before the correct one. For example, consider that the correct password is 12646, and the input one is 12645.
yy made a good point. All are perfect except one fault I think. When A.Miss: 1.(2) missed set isn't empty, we should further check if the current char in correct is equal to the missing char. if yes, we continue; o/w we return false.
In fact, the missing set should only contain one char.
Can anyone tell is this correct or wrong..plzz provide comments if there is best way to do it
/////////////
import java.util.*;
public class Sequence
{
public static void main(String[] args)
{
String secureCode = args[0];
String enteredCode = args[1];
Sequence s = new Sequence();
s.validateCode(secureCode,enteredCode);
}
public void validateCode(String secureCode,String enteredCode)
{
char missingChar = 'a';
for(int i=0;i<secureCode.length();i++)
{
if(i<enteredCode.length())
{
if(secureCode.charAt(i) != enteredCode.charAt(i))
{
missingChar = secureCode.charAt(i);
break;
}
}
else
{
missingChar = secureCode.charAt(i);
break;
}
}
if(missingChar == 'a')
{
System.out.println("valid");
}
else
{
String newString = "";
for(int i=0;i<secureCode.length();i++)
{
if(secureCode.charAt(i) != missingChar)
{
newString = newString+secureCode.charAt(i);
}
}
if(newString.equals(enteredCode))
{
System.out.println("valid");
}
else
{
System.out.println("invalid");
}
}
}
}
Determine what could be the character that is missing. Then call a function to see if that is the only character missing.
#include<stdio.h>
#include<string.h>
void verifyCode(char secureCode[], char enteredCode[], char missingChar)
{
int i = 0, j = 0;
for(i=0, j=i; i<strlen(secureCode); i++, j++)
{
if(secureCode[i] == missingChar) {j--;continue;}
else if(secureCode[i] != enteredCode[j])
{
printf("Error\n"); return;
}
}
printf("Correct\n");
return;
}
int main()
{
int i = 1;
char missingChar = 'a';
char secureCode[] = "678349286886";
char enteredCode[] = "67349266";
for(i=0; i<strlen(secureCode); i++)
if(secureCode[i] != enteredCode[i])
{
missingChar = secureCode[i];
break;
}
verifyCode(secureCode, enteredCode, missingChar);
}
import java.io.*;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Gagan
*/
public class NumLockDemo {
public static void validate(char o[],char i[], char m){
int k,j;
for(k = 0, j=0; k < o.length; k++,j++){
if(o[k] == m){
j--;
continue;
}
else{
if(o[k] != i[j]){
System.out.println("Invalid");
return;
}
}
}
System.out.println("valid");
}
public static void main(String args[]){
String org = "1266";
String inp = "";
System.out.println("Enter the code: ");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try{
inp = br.readLine();
}
catch(IOException e){
System.out.println(e);
}
char missing = 'a';
char orignal[] = org.toCharArray();
char input[] = inp.toCharArray();
for(int i=0; i<orignal.length; i++){
try{
if(orignal[i]!=input[i]){
missing = orignal[i];
break;
}
}
catch(ArrayIndexOutOfBoundsException e){
missing = orignal[i];
}
}
validate(orignal, input, missing);
}
}
Haven't seen the previously posted soln's whether they work in all cases.
Consider for example:-
a) if Correct password is 12666646 and input is 124 then the password is correct
b) if cp is 12666645 and input is 124 then password is INCORRECT since 6 & 5 are missing. Long story short only one value can be the missing value and missing value can repeat several times.
My solution is
public class MissingNumberProblem {
public static void main(String[] args){
String input = "124";
if(checkPass(input)){
System.out.println("correct password");
}else{
System.out.println("incorrect Password");
}
}
public static boolean checkPass(String pass){
String correctPass = "12666646";
// Input Password can't be greater than correct password so return false
if(pass.length() > correctPass.length()){
return false;
}
char missingVal = '$'; //Initialize to some value
boolean correct = true;
int i=0, j=0;
while( j < pass.length()){
if(correctPass.charAt(i) == pass.charAt(j)){
i++;j++;
}
else if(missingVal == '$'){
missingVal = correctPass.charAt(i);
}else if(correctPass.charAt(i+1) == pass.charAt(j)){
missingVal = correctPass.charAt(i);
i += 2;
j++;
}else if (correctPass.charAt(i) == missingVal){
i++;
}
else {
correct = false;
break;
}
}
/* Above while loop checks remaining values in correctPassword that we not compaired in
the previous while loop.
Note : remaining values/ chars can only be equal to the missingVal otherwise the
input password is incorrect
eg: correctPass = "12645"; inputPass = "124"
*/
while(i < correctPass.length()){
if(correctPass.charAt(i) == missingVal){
i++;
}else{
correct = false;
break;
}
}
return correct;
}
}
import java.io.*;
import java.util.Scanner;
class keypad
{
public static void main(String []args)
{
String password="18518";
String passwd;
int []unique= new int [password.length()];
int len,len1=0;
String [] possiblepasswd=new String[10];
System.out.println( "Enter password" );
for(int i=0;i<password.length();i++)
{
len1=len1+i;
}
System.out.println( "length="+len1);
String [] access= new String [len1];
Scanner sc= new Scanner(System.in);
passwd=sc.next();
if(passwd.compareTo(password)==0)
{
System.out.println("Welcome");
System.exit(1);
}
if(passwd.length()>password.length())
{
System.out.println("DENIED");
}
int [] distinct= new int [password.length()];
for (int i=0;i<password.length();i++)
{
distinct[i]= Integer.parseInt(String.valueOf(password.charAt(i)));
//System.out.println(distinct[i]);
}
int k=0;
int flag=0;
// unique[0]=distinct[0];
for (int i=0;i<distinct.length;i++)
{
flag=0;
//System.out.println("flag= "+flag);
for(int j=0 ;j<unique.length;j++)
{
if(distinct[i]==unique[j])
{
//System.out.println("Entered "+unique[j]+" "+distinct[i]);
flag=1;
}
//System.out.println("flag= "+flag);
}
if(flag==0)
unique[k++]=distinct[i];
}
for(int i=0;i<k;i++)
System.out.println(unique[i]);
int l=0;
for(int i=0;i<unique.length;i++)
{
access[l]="";
for(int j=0;j<distinct.length;j++)
{
if(unique[i]!=distinct[j])
{
//System.out.println("Entered "+unique[j]+" "+distinct[i]+ " \tl= "+l);
access[l]=access[l]+distinct[j];
}
}
++l;
}
for(int j=0;j<l;j++)
{
//System.out.println(passwd +" "+access[j]);
if(passwd.compareTo(access[j])==0)
{
System.out.println("welcome");
break;
}
}
}
}
<pre lang="java" line="1" title="CodeMonkey85822" class="run-this">Can we do like this?
1. Compare the input code and security code, find the first different letter;
2. Delete all appearance of that letter in input string;
3. Compare the left string with the security, if identical, then they are the same, otherwise it's incorrect.
</pre><pre title="CodeMonkey85822" input="yes">
</pre>
int correct(int orig, int input)
{
int missing,flag=0;
while(input>0)
{
if(input%10!=orig%10&&flag==0)
{
missing=orig%10;
flag=1;
orig/=10;
while(orig%10==missing)orig/=10;
}
else if(orig%10!=input%10&&flag==1&&orig%10!=missing)
return 0;
else if(orig%10==input%10)
{
orig/=10;
input/=10;
}
}
return 1;
}
int correct(int orig, int input)
{
int missing,flag=0;
while(input>0)
{
if(input%10!=orig%10&&flag==0)
{
missing=orig%10;
flag=1;
orig/=10;
while(orig%10==missing)orig/=10;
}
else if(orig%10!=input%10&&flag==1&&orig%10!=missing)
return 0;
else if(orig%10==input%10)
{
orig/=10;
input/=10;
}
}
return 1;
}
its a security code problem .. I am assuming that only one digit can be misplaced (does not count repeated digits). what i mean is the input security code must have a minimum length of original code length - 1. if this assumption is correct then this simple if else code will work fine..
(code in c#)
static void Main (string[] args)
{
string correctCode = "556644";
Console.WriteLine("Please enter the security code: ");
string inputCode = Console.ReadLine();
if (correctCode.Length - inputCode.Length<=1)
{
int count = 0;
char[] input = inputCode.ToCharArray();
char[] correct = correctCode.ToCharArray();
for ( int i = 0; i<correct.Length; i ++ )
{
if (count > 0)
{
if (i < input.Length)
{
if ((!input[i - count].Equals(correct[i])))
{
count++;
}
}
else
{
count++;
break;
}
}
else
{
if (i < input.Length)
{
if ((!input[i].Equals(correct[i])))
{
count++;
}
}
else
{
count++;
break;
}
}
if (count > 1)
break;
}
if (count >= 0)
{
Console.WriteLine("correct code: {0}", correctCode);
Console.WriteLine("input code: {0}", inputCode);
Console.WriteLine("WELCUM!!!!");
}
else
{
Console.WriteLine("You are not allowed");
Console.WriteLine("correct code: {0}", correctCode);
Console.WriteLine("input code: {0}", inputCode);
}
}
else Console.WriteLine("code not valid , INTRUDER !!! ");
Console.ReadLine();
}
using System;
namespace ConsoleApplication
{
class SecurityCode
{
public static void Show( )
{
string securityCode = "12646";
string temp;
//124
string code = Console.ReadLine( );
string missing = "";
int j = 0;
int i = 0;
while( j < code.Length )
{
if( code[ j ] == securityCode[ i ] )
{
j++;
i++;
continue;
}
if( code[ j ] != securityCode[ i ] )
{
missing = securityCode[ i ].ToString( );
temp = securityCode.Replace( securityCode[ i ].ToString( ), "" );
if( temp != code )
{
Console.WriteLine( "WRONG" );
break;
}
else
{
Console.WriteLine( "RIGHT" );
break;
}
}
}
if( i < securityCode.Length )
{
missing = securityCode[ i ].ToString( );
temp = securityCode.Replace( securityCode[ i ].ToString( ), "" );
if( temp != code )
{
Console.WriteLine( "WRONG" );
}
else
{
Console.WriteLine( "RIGHT" );
}
}
}
}
}
bool CheckSecurity(int* input, int n, int* password, int m) {
int cur1[10] = {0};
int cur2[10] = {0};
int i;
int missing = -1;
for(i = 0; i < m; i++ )
cur1[ password[i] ]++;
for(i = 0; i < n; i++ )
cur2[ input[i] ] ++;
for(i = 0; i < 10; i++) {
if( cur1[i] != cur2[i] ) {
if( cur2[i] == 0 ) {
if( missing == -1 )
missing = i;
else
return false;
} else
return false;
}
}
int *tmp = new int[n];
int j = 0;
for( i = 0; i < m; i++) {
if( password[i] == missing )
continue;
else
tmp[j++] = password[i];
}
for( i = 0; i < n; i++) {
if( input[i] != tmp[i]) {
delete tmp;
return false;
}
}
delete tmp;
return true;
}
<pre lang="" line="1" title="CodeMonkey91465" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main {
public static void main (String[] args) throws java.lang.Exception {
System.out.println("Please enter the correct security code");
Scanner scan = new Scanner(System.in);
String security_code = "";
try {
security_code = scan.next();
} catch (FormatException ex) {
System.out.println(ex.message);
}
System.out.println("Please enter user's code");
String entered_code = "";
try {
entered_code = scan.next();
} catch (FormatException ex) {
System.out.println(ex.message);
}
String temp_code = security_code;
int i = 0;
while (i<entered_code.length()) {
if(entered_code[i] == temp_code[i]) {
i++
} //end if
else if (entered_code[i] != temp_code[i]) {
temp_code = temp_code.ReplaceAll(temp_code[i], "");
break;
} // end else if
} // end while
if(temp_code.equals(entered_code))
System.out.println("Code is correct, give access");
else
System.out.println("Incorrect code, access denied");
}
}
</pre><pre title="CodeMonkey91465" input="yes">
</pre>
static void validate()
{
int valid[]={1,2,6,4,6};
int check[]={2,6};
int flag=0;
int no=-1;
int count=0;
int j=0;
int k=0;
for(j=0;j<check.length;)
{
System.out.println("Current check element "+check[j]+" Valid Element "+valid[k]);
if(no!=-1 && no!=valid[k] && valid[k]!=check[j])
{
flag=1;
break;
}
else if(valid[k]!=check[j] && no == -1)
{
no=valid[k];
k++;
}
else
{
j++;
k++;
}
System.out.println(" No "+no);
}
for(j=k;j<valid.length;j++)
{
if(valid[j]!=no)
{
flag=1;
break;
}
}
if(flag==1)
{
System.out.println("Invalid");
}
if(flag==0)
{
System.out.println("valid");
}
}
Can you explain the question?
- sdm February 23, 2010