Google Interview Question for SDE1s


Country: United States




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

"flips of characters" is ambiguous. The implementation will vary depending on how the interviewer defines a "flip of characters".

For example, given a = "ate" and b ="eat"

Is turning a.charAt(0) from an 'a' to an 'e' considered a flip?
If so then this results in 'a' being flipped, 't' being flipped and 'e' being flipped which would result in 3 flips.

Or alternatively is a flip a sort of a swap between the 'e' and 'a' in "ate" so that way e is put in place and string a becomes "eta"
Which means 'e' and 'a' are flipped and then 't' and 'a' are flipped resulting in 2 flips or swaps?

So did you ask the interviewer what they meant? If so can you please give some examples or more explanation on what this means in your question.

- fgharo91 December 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

"flips of characters" is ambiguous. The implementation will vary depending on how the interviewer defines a "flip of characters".

For example, given a = "ate" and b ="eat"

Is turning a.charAt(0) from an 'a' to an 'e' considered a flip?
If so then this results in 'a' being flipped, 't' being flipped and 'e' being flipped which would result in 3 flips.

Or alternatively is a flip a sort of a swap between the 'e' and 'a' in "ate" so that way e is put in place and string a becomes "eta"
Which means 'e' and 'a' are flipped and then 't' and 'a' are flipped resulting in 2 flips or swaps?

So did you ask the interviewer what they meant? If so can you please give some examples or more explanation on what this means in your question.

- gfhd760 December 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

o(n) with two dicts space o(1). suggestions welcome

def anagrams(a,b):
    hist_a = dict()
    hist_b = dict()
    if len(a) != len(b):
        return -1
    for i in range(len(a)):
        if a[i] in hist_a:
            hist_a[a[i]] += 1
        else:
            hist_a[a[i]] = 1
        if b[i] in hist_b:
            hist_b[b[i]] += 1
        else:
            hist_b[b[i]] = 1    
    
    count = 0
    print(hist_a, hist_b)
    for i in hist_b:
        if i in hist_a:
            count += hist_b[i] - hist_a[i]
        else:
            count += hist_b[i]
    return count

- marc.torsoc December 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm pretty certain that the idea of a "flip" is what we might more naturally call a "swap" or an "exchange". So, the easy case is where the swaps do not chain together. For example,
abcd ==> badc takes two swaps: a<>b and c<>d

The trick comes in when the swaps chain together into cycles. For example:
abcd ==> bcda takes three swaps:
a<>b (bacd)
a<>c (bcad)
a<>d (bcda)

My code does two quick checks at the beginning: check if the strings at least have the same length. Then check if they contain the same counts of every letter (are anagrams).

If they are, then it basically becomes a directed graph, where every mismatch between string a and string b is an edge. I make an adjacency list in the form of a hashmap, and also keep a list of edges. The key method is loop_finder, which pops an edge, then follows the edges until it returns to the starting point. One thing to notice is that if the cycle has n edges, then that corresponds to n-1 swaps, NOT n.

TESTS:
input: ab ba
output: 1

input: abcd bcda
output: 3

input: aaabbcd dcaabab
output: 3

import java.util.*;

class FlipCounter{
    
    static HashMap<Character, LinkedList<Character>> swaps;
    static LinkedList<Edge> edges;
    
    public static boolean CheckChars(String a, String b){
        //Counts each type of char in each string and checks that they are anagrams
        HashMap<Character, Integer> counts = new HashMap<Character, Integer>();        
        for (int i = 0; i < a.length(); i++){
            if (counts.containsKey(a.charAt(i))) counts.put(a.charAt(i), counts.get(a.charAt(i)) + 1);
            else counts.put(a.charAt(i), 1);
            if (counts.containsKey(b.charAt(i))) counts.put(b.charAt(i), counts.get(b.charAt(i)) - 1);
            else counts.put(b.charAt(i), -1);
        }
        for (Integer v : counts.values())
            if (v != 0) return false;        
        return true;
    }
    
    public static int loop_finder(){  
        int tot = 1;
        System.out.println(swaps);
        Edge first = edges.pop();
        System.out.println(first.repr());
        char start = first.a_char;
        char current_head = first.b_char;
        swaps.get(start).remove((Character) current_head);
        while (! swaps.get(current_head).contains((Character) start)){
            tot += 1;
            char next_head = swaps.get(current_head).pop();
            Edge next_edge = new Edge(current_head, next_head);
            edges.remove(next_edge);            
            System.out.println(next_edge.repr());
            //for (Edge e : edges) System.out.println(e.repr());
            //System.out.println(swaps);
            current_head = next_head;
        }
        swaps.get(current_head).remove((Character) start);
        Edge final_edge = new Edge(current_head, start);
        edges.remove(final_edge);
        System.out.println(final_edge.repr());        
        return tot + 1;
    }
    
    public static class Edge {
        public char a_char;
        public char b_char;
        
        public Edge(char a_char, char b_char){
            this.a_char = a_char;
            this.b_char = b_char;
        }  
        
        public boolean equals(Object other){
            if (!(other instanceof Edge)){
                return false;
            }
            Edge other1 = (Edge) other;
            return this.a_char == other1.a_char && this.b_char == other1.b_char;
        }
        
        public String repr(){
            return "(" + String.valueOf(this.a_char) + ", " +  String.valueOf(this.b_char) + ")";
        }
    }
      
    public static void main(String args[]){
        
        String a = args[0];
        String b = args[1];
        
        swaps = new HashMap<Character, LinkedList<Character>>();
        edges = new LinkedList<Edge>();
        
        if (a.length() != b.length()) {
            System.out.println("Hey, you tool, those strings are not even the same length!!!");
            return;
        }
        if (!CheckChars(a, b)){
            System.out.println("Well, at least they are the same length, but they are not anagrams.");
            return;
        }
        for (int i = 0; i < a.length(); i++){ 
            Character a_char = a.charAt(i);
            Character b_char = b.charAt(i);
            if (!a_char.equals(b_char)){
                Edge e = new Edge((char) a_char, (char) b_char);
                edges.add(e);
                if (swaps.containsKey(a_char)){
                    LinkedList<Character> tmp = swaps.get(a_char);
                    tmp.add(b_char);
                } else{
                    LinkedList<Character> tmp = new LinkedList<Character>();
                    tmp.add(b_char);
                    swaps.put(a_char, tmp);
                }
            }
        }
        
        //System.out.println(swaps);
        //for (Edge e : edges) System.out.println(e.repr());
        int num_swaps = 0;
        int num_cycles = 0;
        while (edges.size() > 0){
            num_swaps += loop_finder() - 1;
            num_cycles += 1;
        }
        System.out.println("Number of cycles found: " + num_cycles);
        System.out.println("Answer (total number of swaps to transform " + a + " into " + b + " : " + num_swaps);
    }  
}

- robshowsides December 17, 2017 | 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