## Google Interview Question for SDE1s

Country: United States

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

We can scan the strings and whenever we see a different char, build two arrays of diff. If the diff arrays become larger than 2, return false. If at the end of the scan the diff arrays contain 2 elements and swapping 2 elements in one diff array makes the diff array equal, return true.

The code below is for the follow up question.

``````#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

bool SwappableRec(string &s1, string &s2, unordered_map<char, unordered_set<int>> s2_char_to_swap_idxes, int idx = 0)
{
for (int i = idx; i < s1.size(); ++i) {
if (s1[i] != s2[i]) {
auto it = s2_char_to_swap_idxes.find(s1[i]);
if (it != s2_char_to_swap_idxes.end()) {
vector<int> idxes(it->second.begin(), it->second.end());
for (int j : idxes) {
if (j > i &&
s2[i] == s1[j])
{
swap(s2[i], s2[j]);
it->second.erase(j);
if (SwappableRec(s1, s2, s2_char_to_swap_idxes, idx + 1)) {
return true;
}
it->second.insert(j);
swap(s2[i], s2[j]);
}
}
}
return false;
}
}
return true;
}

bool Swappable(string s1, string s2)
{
if (s1.size() != s2.size() ||
s1 == s2)
{
return false;
}
unordered_map<char, unordered_set<int>> s2_char_to_swap_idxes;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) {
s2_char_to_swap_idxes[s2[i]].insert(i);
}
}
return SwappableRec(s1, s2, s2_char_to_swap_idxes);
}

int main()
{
cout << Swappable("abcde", "decab") << "\n";
}``````

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

``````private boolean areSameBySwap(String st1, String st2) {
if (st1.length() != st2.length()) return false;

int count = 0;
int prev = -1;
int cur = -1;

for (int i = 0; i < st1.length(); i++) {
if (st1.charAt(i) != st2.charAt(i)) {
count++;
if (count > 2) return false;
prev = cur;
cur = i;
}
}

return count == 2 &&
st1.charAt(prev) == st2.charAt(cur) &&
st1.charAt(cur) == st2.charAt(prev);
}``````

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.

### 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.