Google Interview Question
Software EngineersCountry: United States
int minNumberOfSwaps(String s1,String s2) {
//if(!isAnagram(s1, s2)) return Integer.MAX_VALUE; //assume s1 and s2 are anagrams
int step = 0;
Set<String> s1Derives = new HashSet<>();
Set<String> s2Derives = new HashSet<>();
s1Derives.add(s1);
s2Derives.add(s2);
Set<String> visited = new HashSet<>();
int len = s1.length();
while(!containsSameString(s1Derives, s2Derives)) {
Set<String> set = step % 2 == 0 ? s1Derives: s2Derives;
Set<String> nextLevel = new HashSet<>();
for(String s: set) {
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
if(s.charAt(i) != s.charAt(j)) {
char[] charArray = swap(s.toCharArray(), i, j);
String derived = new String(charArray);
if(!visited.contains(new String(derived))) {
nextLevel.add(derived);
visited.add(derived);
}
}
}
}
}
if(step % 2 == 0) s1Derives = nextLevel;
else s2Derives = nextLevel;
step++;
}
return step;
}
from collections import deque
def f(s, t):
h = set([s])
s = [list(s), 0]
q = deque([s])
while q:
e, n = q.popleft()
if "".join(e) == t:
return n
else:
for i in range(len(e)):
for j in range(len(e)):
temp = e[i]
e[i] = e[j]
e[j] = temp
str = "".join(e)
if str not in h:
q.append([e[:], n+1])
h.add(str)
e[j] = e[i]
e[i] = temp
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int FindMinimum(int i, string s1, string& s2)
{
if(s1[i] == s2[i])
{
return 0;
}
int length = s1.length();
string final;
int MIN = INT_MAX;
for(int j=0; j<length; j++)
{
if(s1[j] != s2[j] && s1[i] == s2[j])
{
string dummy = s2;
dummy[j] = s2[i];
dummy[i] = s1[i];
int min = FindMinimum(j, s1, dummy);
if(min < MIN)
{
MIN = min;
final = dummy;
}
}
}
s2 = final;
return MIN + 1;
}
int main() {
string s1;
string s2;
cin>>s1;
cin>>s2;
int count = 0;
int length = s1.length();
for(int i=0; i<length; i++)
{
count += FindMinimum(i, s1, s2);
}
cout<<count;
}
Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
Two-way BFS, similar to 'WordLadder'.
s1Derives and s2Derives are the words reachable by swapping characters in s1 and s2 in any random way. If s1and s2 are anagrams, for sure s1Derives and s2Derives would join at some point. Find out all possible derivatives 'nextLevel' of s1/s2. Then find out all derivatives of words in 'nextLevel'......until the earliest joint of s1Derives and s2Derives occurs. Return the number of levels gone through.
- aonecoding February 03, 2018