## Apple Interview Question for SDE-3s

Country: United States
Interview Type: In-Person

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

Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.

Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.

Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.

Backtracking for all the combinations to solve this problem.

``````public class StringToSingleChar {

public static void main(String[] args) {

StringToSingleChar t = new StringToSingleChar("ABACABB");
System.out.println(t.pathLen());

}

List<Character> str;

public StringToSingleChar(String s) {

str = new ArrayList<>();

for(char c: s.toCharArray()) {

}

}

public int pathLen() {

if(str.size() == 0) return -1;

if(str.size() == 1) return 0;

if(invalidToConvert()) return -1;

for(int i = 0; i < str.size() - 1; i++) {

char curr = str.get(i), next = str.get(i + 1);

if(curr != next) {

//backtracking, try to convert any two adjacent chars in str
str.set(i, convert(curr, next));
str.remove(i + 1);

int steps = pathLen();

if(steps >= 0) return steps + 1;

//recover the str after the recursive calls
str.set(i, curr);

}

}

return -1;

}

//check if given string is invalid like "AAAAA..." or "BBBBB..." or "CCCCC..."
private boolean invalidToConvert() {

for(int i = 0; i < str.size() - 1; i++) {

if(str.get(i) != str.get(i + 1)) return false;

}

return true;

}

private char convert(char a, char b) {

if(a != 'C' && b != 'C') return 'C';

if(a != 'B' && b != 'B') return 'B';

return 'A';

}

}``````

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

onecoding - Is it possible to provide solution in Python?

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

Scala version using backtracking:

``````object StringToCharMapping {

val mappings = Map("AB" -> 'C', "BA" -> 'C', "AC" -> 'B', "CA" -> 'B', "BC" -> 'A', "CB" -> 'A')

def main(args: Array[String]): Unit = {
println(toSingleCharNumChanges("ABACB"))
println(toSingleCharNumChanges("ABACABB"))
}

def toSingleCharNumChanges(s:String) : Int = {
var str = new StringBuilder(s)

def f() : Int = {
if (str.size == 0) return -1
if (str.size == 1) return 0
if (str.sliding(2).map(a => a(0) == a(1)).count(identity) > 0) return -1

for (i <- 0 to str.size - 2) {
val c = str(i)
val n = str(i+1)
if (c != n) {

// backtracking
str(i) = mappings(c+""+n)
str.deleteCharAt(i+1)

val steps = f()

if (steps >= 0) return steps + 1

// place chars back to original spots
str(i) = c
str(i + 1) = n
}
}
return -1
}
f()
}
}``````

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

Here is a python answer for the question, no backtracking though

``````def invalid(s):
for x in xrange(len(s)-1):
if s[x] != s[x+1]: return False
return True

def convert(a, b):
if (a == 'A' and b == 'B') or (a == 'B' and b == 'A'):
return 'C'
elif (a == 'A' and b == 'C') or (a == 'C' and b == 'A'):
return 'B'
else:
return 'A'

def pathlen(initial_string):
frontier = [(initial_string, 0)]

for (s, l) in frontier:
if len(s) == 1: return l
if len(s) == 0 or invalid(s): continue

for x in xrange(len(s)-1):
a = s[x]; b = s[x+1]
new_string = s[:x] + convert(a, b) + s[x+2:]
frontier.append((new_string, l+1))

return -1``````

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

this is a backTracking algo. Maintain an arrayList and keep replacing pairs with the character.
If you dont get the solution, loop for the next element pair.
If nothing happens, then return -1.

``````import java.io.*;
import java.util.*;

class GFG {
public static void main (String[] args) {
String input = "ABACB";
//String dict[] = {"AB,C","AC,B","BC,A"};
String dict[] = {"AB,C","CC,B","BB,B"};
System.out.println(findLen(input,dict));
}

static int findLen(String input, String dictionary[]) {
HashMap<String,Character> map = new HashMap<>();

for(String dict : dictionary) {
String str = dict.substring(0,2);
String revStr = "" + dict.charAt(1) + dict.charAt(0);
map.put(str,dict.charAt(3));
map.put(revStr,dict.charAt(3));
//System.out.println(str + " " + revStr);
}

ArrayList<Character> backTrack = new ArrayList<>();
for(int i=0; i<input.length(); i++){
}

int len = findLenUtil(map,backTrack);

return len;

}

static int findLenUtil(HashMap<String,Character> map, ArrayList<Character> backTrack) {

for(Character ch : backTrack) {
System.out.print(ch + " ");
}
System.out.println();

if(backTrack.size() == 1)
return 0;

for(int i=0; i<backTrack.size()-1; i++) {
char ch1 = backTrack.get(i);
char ch2 = backTrack.get(i+1);
//System.out.println(ch1 + " " + ch2);

String str = "" + ch1 + ch2;
if(map.containsKey(str)) {
char replace = map.get(str);
backTrack.set(i,replace);
backTrack.remove(i+1);

int len = findLenUtil(map,backTrack);
if(len != -1) {
return len + 1;
}
else {
backTrack.set(i,ch1);
}
}
}
return -1;
}
}``````

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

``````import sys

def search(current_str, candidate_map, steps):
print current_str, steps

if len(current_str) == 1:
return steps

min_steps = sys.maxint
for key in candidate_map.keys():
if key in current_str:
index = current_str.index(key)
tmp_steps = search(current_str[:index] + candidate_map[key] + current_str[index + len(key):], candidate_map, steps + 1)
min_steps = min(min_steps, tmp_steps)

return min_steps

if __name__ == '__main__':
input_str = 'AABCB'
candidate_map = {'AB': 'C', 'AC': 'B', 'BC': 'A'}

if len(input_str) <= 1:
print 0

print input_str, candidate_map

steps = search(input_str, candidate_map, 1)
print steps if steps < sys.maxint else -1``````

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

1. Keep a counter i which tells the position from where we should look for two character and find their conversion. Eg; ABCB, i=0 means we will loop for (i)th and (i+1)th chars i.e AB and get the movement as AB->C , so result is "C"CB.
2. When we cannot convert from current ith posistion i.e in CCB if i=0, "CC" cannot to converted to a valid move , so call recursively for i+1 i.e i=1 and now we can convert 1th and 2th chars (CB) to A, hence result is C"A" and so on.
3. keep checking in every step if str does not contains all same chars, here is string is invalid now and cannot be further reduced like .. AAA , BB , CCC etc.

``````import java.util.*;
public class StringSequenceToChar {

static HashMap<String,String> map = new HashMap<String,String>();
static {
map.put("AB","C");
map.put("BA","C");
map.put("AC","B");
map.put("CA","B");
map.put("BC","A");
map.put("CB","A");
}

public static String convert(String str){
if(map.containsKey(str)){
return map.get(str);
}else{
return null;
}
}

public static int getPath(String str, int i , int steps){

//Conversion done
if(str.length()==1){
return steps;
}

//Check if all chars are same, cannot convert // Imp
int ctr=0;
for(int k=1;k<=str.length()-1;k++){
if(str.charAt(k-1) != str.charAt(k)){
break; // Optimization
}else{
ctr++;
}
}
if(ctr==str.length()-1){
return -1;
}

//we kept increasing i and it is beyond length-1
if(i> (str.length()-1)-1){
i=0;
}

String result = convert(str.substring(i, i+2));

int res=0;
if(result!=null){
res = getPath(str.substring(0,i)+result+str.substring(i+2,str.length()) ,i,steps+1);
}else{
res = getPath(str ,i+1,steps);
}

if(res < 0){
return -1;
}else{
return res;
}
}

public static void main(String[] args) {

System.out.println(getPath("ABACB",0,0));
System.out.println(getPath("AAA",0,0));
System.out.println(getPath("AAC",0,0));
System.out.println(getPath("BB",0,0));
}
}``````

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

I am not sure about the complexity though

``````dic = {"ab":"c","ca":"b","ba":"c","ac":"b","bc":"a","cb":"a"}
def getPath(seq):
path = 0
if len(seq) == 1:
return path
return pathnum(seq,path)

def pathnum(seq,path):
found = False
for key,val in dic.items():
while key in seq:
found = True
seq = seq.replace(key,val)
path = path + 1
if len(seq) == 1:
break
if len(seq) == 1:
return path
if found and len(seq) > 1:
return pathnum(seq,path)
return -1``````

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

``````int bfsShortest() {
string input = "ABACB";
map<string, char> lookup;
lookup["AB"] = 'C';
lookup["AC"] = 'B';
lookup["BC"] = 'A';

lookup["BA"] = 'C';
lookup["CA"] = 'B';
lookup["CB"] = 'A';

set<string> visited;
struct info {
string input;
int steps;
};

queue<info> q;

info i;
i.input = input;
i.steps = 0;
q.push(i);

int minSteps = INT_MAX;

while (!q.empty()) {
info curr = q.front();
q.pop();
if (curr.input.length() == 1) {
minSteps = min(minSteps, curr.steps);
}
visited.insert(curr.input);

for (int i = 0; i < curr.input.length(); i++) {
if (i > curr.input.length() - 2) break;
string temp = curr.input.substr(i, 2);
if (lookup.find(temp) != lookup.end()) {
string modified = curr.input.substr(0, i) + lookup[temp] + curr.input.substr(i + 2);
info m;
m.input = modified;
m.steps = curr.steps + 1;
if (visited.find(modified) == visited.end())
q.push(m);
}
}
}
return (minSteps == INT_MAX) ? -1 : minSteps;
}``````

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

``````def reduce_string(x: str) -> int:
count = 0
while len(x) != 1:
length = len(x)
for i in range(length):
one_two = x[i:i+2]
if one_two in ('AB', 'BA'):
x = x[:i] + 'C' + x[i+2:]
count += 1
elif one_two in ('AC', 'CA'):
x = x[:i] + 'B' + x[i+2:]
count += 1
elif one_two in ('BC', 'CB'):
x = x[:i] + 'A' + x[i+2:]
count += 1
if length > 1 and x in (length*'A', length*'B', length*'C'):
count = -1
break
return count

for string in ('ABACB', 'ABACABB', 'ABCBACBBC', 'AAA'):
print("%s: %d" % (string, reduce_string(string)))``````

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.