Google Interview Question
SDE1sCountry: United States
"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.
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
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);
}
}
"flips of characters" is ambiguous. The implementation will vary depending on how the interviewer defines a "flip of characters".
- fgharo91 December 14, 2017For 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.