Apple Interview Question
SDE-3sCountry: United States
Interview Type: In-Person
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()
}
}
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
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++){
backTrack.add(input.charAt(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);
backTrack.add(i+1,ch2);
}
}
}
return -1;
}
}
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
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));
}
}
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)
if not found and len(seq) > 1:
return -1
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;
}
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)))
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.
- aonecoding May 10, 2017