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()) {

            str.add(c);
        }

    }

    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);
                str.add(i + 1, next);

            }

        }

        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';

    }

}

- aonecoding May 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

onecoding - Is it possible to provide solution in Python?

- @TryHard May 10, 2017 | Flag Reply
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()
  }
}

- guilhebl May 10, 2017 | Flag Reply
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

- Fernando May 11, 2017 | Flag Reply
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++){
	        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;
	}
}

- NinjaCoder July 27, 2017 | Flag Reply
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

- pointzz.ki August 15, 2017 | Flag Reply
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));
	}
}

- Mayank Jain August 21, 2017 | Flag Reply
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)
    if not found and len(seq) > 1:
        return -1

- petrice August 26, 2017 | Flag Reply
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;
}

- sue April 28, 2018 | Flag Reply
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)))

- Anonymous May 05, 2019 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More