## Athena Health Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 5 vote

I guess using a stack this can be achieved.
Algo:
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.

Comment hidden because of low score. Click to expand.
0

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++) {
}
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);
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

How should it work?
abbc
cbc
ca
b

Or

abbc
cbc
ac
b

Comment hidden because of low score. Click to expand.
0

abbc
cbc
ac
b

Comment hidden because of low score. Click to expand.
0
of 0 vote

What is the output for 'cccccb'

Comment hidden because of low score. Click to expand.
0

cccccb
cccca
cccb
cca
cb
a
output - 1

Comment hidden because of low score. Click to expand.
0

But your question says the string has to be evaluated from left to right only. You are evaluating right to left here.

Comment hidden because of low score. Click to expand.
0

I am evaluating from left to right here. For this given string, unfortunately evaluation from right side also reduces the same way :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

just do it recursively, it will take O(n) since every time you reduce one char

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````s = "abccbabcba"
count = 0
while len(set(list(s))) != 1:
c1 = s[count]
c2 = s[count+1]
if c1 != c2:
if "a" and "b" in c1+c2:
s = "c"+s[2:]
count = 0
continue
elif "c" and "b" in c1+c2:
s = "a"+s[2:]
count = 0
continue
else:
s = "b"+s[2:]
count = 0
continue
else:
count = count +1
print s``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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){
char first = inputString.charAt(0);
char second = inputString.charAt(1);
Set<Character> set2 = new HashSet<Character>();
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);
}
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.