Athena Health Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
And the implementation:
public static void main(String[] args) {
String s = "abbc";
//String s = "aaac";
//String s = "aaaa";
Set<Character> uniqueChars = new HashSet<Character>();
for (int i = 0; i < s.length(); i++) {
uniqueChars.add(s.charAt(i));
}
Stack<Character> stack = new Stack<Character>();
int i = 1;
Character newChar = s.charAt(0);
while (i < s.length()) {
if (stack.isEmpty() || stack.peek().equals(newChar)) {
stack.push(newChar);
newChar = s.charAt(i++);
} else {
Character top = stack.pop();
for (Character unChar : uniqueChars) {
if (!unChar.equals(top) && !unChar.equals(newChar)) {
newChar = unChar;
break;
}
}
}
}
boolean change = true;
while (change) {
if (stack.isEmpty() || stack.peek().equals(newChar)) {
stack.push(newChar);
change = false;
} else {
Character top = stack.pop();
for (Character unChar : uniqueChars) {
if (!unChar.equals(top) && !unChar.equals(newChar)) {
newChar = unChar;
break;
}
}
}
}
System.out.println(stack.size() + " - " + stack);
}
I think the only catch here is, the shifting of characters-
Str = [a][b][b][c]
Pass 1 - [0][c][b][c]. now shift to left -> [c][b][c]
Pass 2 - [0][a][c]. now shift to left -> [a][c]
Pass 3 - [0][b]. shift to left -> [b]
return number of chars in the string - 1
But, this is an inefficient way of doing, since it will take O(n^2) time (traversing and shifting, both n).
There is a way to prevent the shift thing -
1. first reverse the string
2. start from right
Str = [c][b][b][a]
Pass 1 - [c][b][c]
Pass 2 - [c][a]
Pass 3 - [b]
return the number of chars left - 1
If it's strictly not allowed to start from right in any instances, then just do this (without any shifts) -
Str = [a][b][b][c]
Pass 1 - [0][c][b][c]
Pass 2 - [0][0][a][c]
Pass 3 - [0][0][0][b]
return the number of non 0 chars - 1
But your question says the string has to be evaluated from left to right only. You are evaluating right to left here.
import java.util.*;
class Main {
public static boolean checkSimilarChar(String test){
boolean flag = true;
for(int i =0; i< test.length();i++){
if(test.charAt(i)!=test.charAt(i+1)){
flag = false;
break;
}
}return flag;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
String inputString = s.nextLine();
Set<Character> set1 = new HashSet<Character>();
while(checkSimilarChar(inputString)!=true || inputString.length()>1){
set1.addAll(Arrays.asList(new Character[] {'a', 'b','c'}));
char first = inputString.charAt(0);
char second = inputString.charAt(1);
Set<Character> set2 = new HashSet<Character>();
set2.add(first);
set2.add(second);
if(first != second){
set1.removeAll(set2);
System.out.println(set1);
if(inputString.length()>=3){
inputString = set1.iterator().next()+inputString.substring(2);
}else{
inputString = set1.iterator().next()+"";
}
System.out.println(inputString);
}
}
}
}
I guess using a stack this can be achieved.
- Anonymous January 31, 2013Algo:
1. Start from the starting of the string till the end.
2. Take each character and perform these operations on stack:
a. if the stack is empty put that character into the stack.
b. else check the stack top element if the top element is different than the
element we are trying to insert, then pop that element out and
try the step b with the third element (e.g. char = a top = b then pop b out and try to
. push c onto the stack).
c. if the top element is same as the element we are trying to push just push the element and go to step 2.
After the step 2 is done take all the elements out of the stack. Number of elements poped out would be the answer.
As for the above case:
stack[ ]
input string = abbc
then stack would be changing like this
stack[a] -> stack[c] -> stack[a] ->stack[b]
now all the elements of the string are over so the final remaining elements are 1.