Amazon Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Written Test
This is more generic solution using hash table.
class Solution {
public:
bool compareTwoMap(unordered_map<char, int> &refMap, unordered_map<char, int> &winMap){
for(auto it = refMap.begin(); it != refMap.end(); it++){
auto winit = winMap.find(it->first);
if(winit == winMap.end()){
return(false);
}
else{
if(winit->second != it->second){
return(false);
}
}
}
return(true);
}
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> refMap;
unordered_map<char, int> winMap;
vector<int> ans;
for(int i = 0; i < p.length(); i++){
auto it = refMap.find(p[i]);
if(it != refMap.end()){
it->second++;
}
else{
refMap[p[i]] = 1;
}
}
if(s.length() < p.length()){
return(ans);
}
for(int i = 0; i < p.length(); i++){
auto it = winMap.find(s[i]);
if(it != winMap.end()){
it->second++;
}
else{
winMap[s[i]] = 1;
}
}
if(compareTwoMap(winMap, refMap)){
ans.push_back(0);
}
for(int i = p.length(); i < s.length(); i++){
auto previt = winMap.find(s[i - p.length()]);
if(previt->second == 1){
winMap.erase(s[i-p.length()]);
}
else{
previt->second--;
}
auto newit = winMap.find(s[i]);
if(newit != winMap.end()){
newit->second++;
}
else{
winMap[s[i]] = 1;
}
if(compareTwoMap(winMap, refMap)){
ans.push_back(i - p.length() + 1);
}
}
return(ans);
}
};
This is generic solution using hash table.
class Solution {
public:
bool compareTwoMap(unordered_map<char, int> &refMap, unordered_map<char, int> &winMap){
for(auto it = refMap.begin(); it != refMap.end(); it++){
auto winit = winMap.find(it->first);
if(winit == winMap.end()){
return(false);
}
else{
if(winit->second != it->second){
return(false);
}
}
}
return(true);
}
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> refMap;
unordered_map<char, int> winMap;
vector<int> ans;
for(int i = 0; i < p.length(); i++){
auto it = refMap.find(p[i]);
if(it != refMap.end()){
it->second++;
}
else{
refMap[p[i]] = 1;
}
}
if(s.length() < p.length()){
return(ans);
}
for(int i = 0; i < p.length(); i++){
auto it = winMap.find(s[i]);
if(it != winMap.end()){
it->second++;
}
else{
winMap[s[i]] = 1;
}
}
if(compareTwoMap(winMap, refMap)){
ans.push_back(0);
}
for(int i = p.length(); i < s.length(); i++){
auto previt = winMap.find(s[i - p.length()]);
if(previt->second == 1){
winMap.erase(s[i-p.length()]);
}
else{
previt->second--;
}
auto newit = winMap.find(s[i]);
if(newit != winMap.end()){
newit->second++;
}
else{
winMap[s[i]] = 1;
}
if(compareTwoMap(winMap, refMap)){
ans.push_back(i - p.length() + 1);
}
}
return(ans);
}
};
This is a generic solution using a hash table.
class Solution {
public:
bool compareTwoMap(unordered_map<char, int> &refMap, unordered_map<char, int> &winMap){
for(auto it = refMap.begin(); it != refMap.end(); it++){
auto winit = winMap.find(it->first);
if(winit == winMap.end()){
return(false);
}
else{
if(winit->second != it->second){
return(false);
}
}
}
return(true);
}
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> refMap;
unordered_map<char, int> winMap;
vector<int> ans;
for(int i = 0; i < p.length(); i++){
auto it = refMap.find(p[i]);
if(it != refMap.end()){
it->second++;
}
else{
refMap[p[i]] = 1;
}
}
if(s.length() < p.length()){
return(ans);
}
for(int i = 0; i < p.length(); i++){
auto it = winMap.find(s[i]);
if(it != winMap.end()){
it->second++;
}
else{
winMap[s[i]] = 1;
}
}
if(compareTwoMap(winMap, refMap)){
ans.push_back(0);
}
for(int i = p.length(); i < s.length(); i++){
auto previt = winMap.find(s[i - p.length()]);
if(previt->second == 1){
winMap.erase(s[i-p.length()]);
}
else{
previt->second--;
}
auto newit = winMap.find(s[i]);
if(newit != winMap.end()){
newit->second++;
}
else{
winMap[s[i]] = 1;
}
if(compareTwoMap(winMap, refMap)){
ans.push_back(i - p.length() + 1);
}
}
return(ans);
}
};
Simple Solution using rec function in C#
class AnagramSubstring
{
/*
*
* Given string a and string b, find all the occurrences of the anagrams of a in b
*/
public AnagramSubstring() {
string anagramString = "xyz";
string originalString = "afdgzyxksldfm";
if (findAnagram(anagramString, originalString))
Console.WriteLine("String {0} found under {1}", anagramString, originalString);
else
Console.WriteLine("String Not found!!");
}
public bool findAnagram(string a,string b)
{
if (a.Length == 0) return true;
var s = b.IndexOf(a[0]);
if (s >= 0)
{
var str = b.Remove(s, 1);
return findAnagram(a.Substring(1), str);
} else return false;
}
}
Here one solution using C#
class AnagramSubstring
{
/*
*
* Given string a and string b, find all the occurrences of the anagrams of a in b
*/
public AnagramSubstring() {
string anagramString = "xyz";
string originalString = "afdgzyxksldfm";
if (findAnagram(anagramString, originalString))
Console.WriteLine("String {0} found under {1}", anagramString, originalString);
else
Console.WriteLine("String Not found!!");
}
public bool findAnagram(string a,string b)
{
if (a.Length == 0) return true;
var s = b.IndexOf(a[0]);
if (s >= 0)
{
var str = b.Remove(s, 1);
return findAnagram(a.Substring(1), str);
} else return false;
}
}
Here it is a short solution in python. The cost is n * (x lg x) being x the length of the shortest string
def get_chunks(s, n, step=1):
for x in xrange(0, len(s)-n+1, step):
yield s[x:x+n]
def find_anagrams(a, b):
total = 0
s1, s2 = a, b
sorted_str = sorted(b)
if len(b) > len(a):
s1, s2 = b, a
sorted_str = sorted(a)
for chunk in get_chunks(s1, len(s2)):
if sorted(chunk) == sorted_str:
total += 1
return total
vector<int> get_anagram_starts(char *a, char *b)
{
int la = strlen(a);
int lb = strlen(b);
int letter_count[256];
int bad_letter_count = 0;
vector<int> out;
int i;
for (i = 0; i < 256; i++) // clear the count array
{
letter_count[i] = 0;
}
for (i = 0; i < la; i++) // get the count for letters in a Make a negative impression in the counts array
{
letter_count[a[i]]--;
}
for (i = 0; i < la; i++) // look at the start part of b
{
letter_count[b[i]]++;
if (letter_count[b[i]] > 0) // you have too many of this letter
{
bad_letter_count++;
}
}
if (bad_letter_count == 0)
{
out.push_back(0);
}
for (i = la; i < lb; i++) // look at the rest of b
{
int j = i - la; // letter we are removing
letter_count[b[j]]--;
if (letter_count[b[j]] == 0) // we got rid of a bad letter
{
bad_letter_count--;
}
if (letter_count[b[i]] == 0) // we are going to add a bad letter
{
bad_letter_count++;
}
letter_count[b[i]]++;
if (bad_letter_count == 0)
{
out.push_back(j+1);
}
}
return out;
}
vector<int> get_anagram_starts(char *a, char *b)
{
int la = strlen(a);
int lb = strlen(b);
int letter_count[256];
int bad_letter_count = 0;
vector<int> out;
int i;
for (i = 0; i < 256; i++) // clear the count array
{
letter_count[i] = 0;
}
for (i = 0; i < la; i++) // get the count for letters in a Make a negative impression in the counts array
{
letter_count[a[i]]--;
}
for (i = 0; i < la; i++) // look at the start part of b
{
letter_count[b[i]]++;
if (letter_count[b[i]] > 0) // you have too many of this letter
{
bad_letter_count++;
}
}
if (bad_letter_count == 0)
{
out.push_back(0);
}
for (i = la; i < lb; i++) // look at the rest of b
{
int j = i - la; // letter we are removing
letter_count[b[j]]--;
if (letter_count[b[j]] == 0) // we got rid of a bad letter
{
bad_letter_count--;
}
if (letter_count[b[i]] == 0) // we are going to add a bad letter
{
bad_letter_count++;
}
letter_count[b[i]]++;
if (bad_letter_count == 0)
{
out.push_back(j+1);
}
}
return out;
}
vector<int> get_anagram_starts(char *a, char *b)
{
int la = strlen(a);
int lb = strlen(b);
int letter_count[256];
int bad_letter_count = 0;
vector<int> out;
int i;
for (i = 0; i < 256; i++) // clear the count array
{
letter_count[i] = 0;
}
for (i = 0; i < la; i++) // get the count for letters in a Make a negative impression in the counts array
{
letter_count[a[i]]--;
}
for (i = 0; i < la; i++) // look at the start part of b
{
letter_count[b[i]]++;
if (letter_count[b[i]] > 0) // you have too many of this letter
{
bad_letter_count++;
}
}
if (bad_letter_count == 0)
{
out.push_back(0);
}
for (i = la; i < lb; i++) // look at the rest of b
{
int j = i - la; // letter we are removing
letter_count[b[j]]--;
if (letter_count[b[j]] == 0) // we got rid of a bad letter
{
bad_letter_count--;
}
if (letter_count[b[i]] == 0) // we are going to add a bad letter
{
bad_letter_count++;
}
letter_count[b[i]]++;
if (bad_letter_count == 0)
{
out.push_back(j+1);
}
}
return out;
}
package test.test;
import java.util.ArrayList;
import java.util.List;
public class FindAnagram {
public static void main(String[] args) {
String toFind = "xyz";
String mainString = "axbcxzyzzxycyxzbyx";
List<String> answer = findAnagram(mainString, toFind);
System.out.println("answer is : " +answer);
}
private static List<String> findAnagram(String mainString, String toFind) {
List<String> ans = new ArrayList<String>();
String localToFind = toFind;
int anagramIndex = -1;
for (int index = 0 ; index < mainString.length(); index ++ ) {
char current = mainString.charAt(index);
if (localToFind.contains(String.valueOf(current))) {
if (anagramIndex == -1)
anagramIndex = index;
localToFind = localToFind.replaceAll(String.valueOf(current), "");
if (localToFind.isEmpty() && anagramIndex != -1) {
ans.add(mainString.substring(anagramIndex,(anagramIndex+ toFind.length())));
localToFind = toFind;
index = anagramIndex;
}
}
else {
anagramIndex = -1;
localToFind = toFind;
}
}
return ans;
}
}
package test.test;
import java.util.ArrayList;
import java.util.List;
public class FindAnagram {
public static void main(String[] args) {
String toFind = "xyz";
String mainString = "axbcxzyzzxycyxzbyx";
List<String> answer = findAnagram(mainString, toFind);
System.out.println("answer is : " +answer);
}
private static List<String> findAnagram(String mainString, String toFind) {
List<String> ans = new ArrayList<String>();
String localToFind = toFind;
int anagramIndex = -1;
for (int index = 0 ; index < mainString.length(); index ++ ) {
char current = mainString.charAt(index);
if (localToFind.contains(String.valueOf(current))) {
if (anagramIndex == -1)
anagramIndex = index;
localToFind = localToFind.replaceAll(String.valueOf(current), "");
if (localToFind.isEmpty() && anagramIndex != -1) {
ans.add(mainString.substring(anagramIndex,(anagramIndex+ toFind.length())));
localToFind = toFind;
index = anagramIndex;
}
}
else {
anagramIndex = -1;
localToFind = toFind;
}
}
return ans;
}
}
public class FindAnagram {
public static void main(String[] args) {
String toFind = "xyz";
String mainString = "axbcxzyzzxycyxzbyx";
List<String> answer = findAnagram(mainString, toFind);
System.out.println("xyz in axbcxzyzzxycyxzbyx is : " +answer);
String mainString2 = "axbcxzyxzxycyxzbyx";
List<String> answer2 = findAnagram(mainString2, toFind);
System.out.println("xyz in axbcxzyxzxycyxzbyx is : " +answer2);
}
private static List<String> findAnagram(String mainString, String toFind) {
List<String> ans = new ArrayList<String>();
String localToFind = toFind; // set to original toFind
int anagramIndex = -1; // set to -1
for (int index = 0 ; index < mainString.length(); index ++) {
char current = mainString.charAt(index);
if (localToFind.contains(String.valueOf(current))) {
if (anagramIndex == -1){
anagramIndex = index;
}
localToFind = localToFind.replaceAll(String.valueOf(current), "");
if (localToFind.isEmpty() && anagramIndex != -1) {
ans.add(mainString.substring(anagramIndex,(anagramIndex+ toFind.length())));
index = anagramIndex;
anagramIndex = -1; // reset to -1
localToFind = toFind; // reset to original toFind
}
}
else {
anagramIndex = -1; // reset to -1
localToFind = toFind; // reset to original toFind
}
}
return ans;
}
}
import java.util.ArrayList;
import java.util.List;
/**
* Given string a and string b,
* find all the occurences of the anagrams of a in b.
*
*
*/
public class FindAnagram {
public static void main(String[] args) {
String toFind = "xyz";
String mainString = "axbcxzyzzxycyxzbyx";
List<String> answer = findAnagram(mainString, toFind);
System.out.println("xyz in axbcxzyzzxycyxzbyx is : " +answer);
String mainString2 = "axbcxzyxzxycyxzbyx";
List<String> answer2 = findAnagram(mainString2, toFind);
System.out.println("xyz in axbcxzyxzxycyxzbyx is : " +answer2);
}
private static List<String> findAnagram(String mainString, String toFind) {
List<String> ans = new ArrayList<String>();
String localToFind = toFind; // set to original toFind
int anagramIndex = -1; // set to -1
for (int index = 0 ; index < mainString.length(); index ++) {
char current = mainString.charAt(index);
if (localToFind.contains(String.valueOf(current))) {
if (anagramIndex == -1){
anagramIndex = index;
}
localToFind = localToFind.replaceAll(String.valueOf(current), "");
if (localToFind.isEmpty() && anagramIndex != -1) {
ans.add(mainString.substring(anagramIndex,(anagramIndex+ toFind.length())));
index = anagramIndex;
anagramIndex = -1; // reset to -1
localToFind = toFind; // reset to original toFind
}
}
else {
anagramIndex = -1; // reset to -1
localToFind = toFind; // reset to original toFind
}
}
return ans;
}
}
import java.util.ArrayList;
import java.util.List;
/**
* Given string a and string b,
* find all the occurences of the anagrams of a in b.
*
*
*/
public class FindAnagram {
public static void main(String[] args) {
String toFind = "xyz";
String mainString = "axbcxzyzzxycyxzbyx";
List<String> answer = findAnagram(mainString, toFind);
System.out.println("xyz in axbcxzyzzxycyxzbyx is : " +answer);
String mainString2 = "axbcxzyxzxycyxzbyx";
List<String> answer2 = findAnagram(mainString2, toFind);
System.out.println("xyz in axbcxzyxzxycyxzbyx is : " +answer2);
}
private static List<String> findAnagram(String mainString, String toFind) {
List<String> ans = new ArrayList<String>();
String localToFind = toFind; // set to original toFind
int anagramIndex = -1; // set to -1
for (int index = 0 ; index < mainString.length(); index ++) {
char current = mainString.charAt(index);
if (localToFind.contains(String.valueOf(current))) {
if (anagramIndex == -1){
anagramIndex = index;
}
localToFind = localToFind.replaceAll(String.valueOf(current), "");
if (localToFind.isEmpty() && anagramIndex != -1) {
ans.add(mainString.substring(anagramIndex,(anagramIndex+ toFind.length())));
index = anagramIndex;
anagramIndex = -1; // reset to -1
localToFind = toFind; // reset to original toFind
}
}
else {
anagramIndex = -1; // reset to -1
localToFind = toFind; // reset to original toFind
}
}
return ans;
}
}
import java.util.ArrayList;
import java.util.List;
/**
* Given string a and string b,
* find all the occurences of the anagrams of a in b.
*
*
*/
public class FindAnagram {
public static void main(String[] args) {
String toFind = "xyz";
String mainString = "axbcxzyzzxycyxzbyx";
List<String> answer = findAnagram(mainString, toFind);
System.out.println("xyz in axbcxzyzzxycyxzbyx is : " +answer);
String mainString2 = "axbcxzyxzxycyxzbyx";
List<String> answer2 = findAnagram(mainString2, toFind);
System.out.println("xyz in axbcxzyxzxycyxzbyx is : " +answer2);
}
private static List<String> findAnagram(String mainString, String toFind) {
List<String> ans = new ArrayList<String>();
String localToFind = toFind; // set to original toFind
int anagramIndex = -1; // set to -1
for (int index = 0 ; index < mainString.length(); index ++) {
char current = mainString.charAt(index);
if (localToFind.contains(String.valueOf(current))) {
if (anagramIndex == -1){
anagramIndex = index;
}
localToFind = localToFind.replaceAll(String.valueOf(current), "");
if (localToFind.isEmpty() && anagramIndex != -1) {
ans.add(mainString.substring(anagramIndex,(anagramIndex+ toFind.length())));
index = anagramIndex;
anagramIndex = -1; // reset to -1
localToFind = toFind; // reset to original toFind
}
}
else {
anagramIndex = -1; // reset to -1
localToFind = toFind; // reset to original toFind
}
}
return ans;
}
}
Hi, you can use moving window algorithm to solve this problem, the complexity is O(n). Here's Java code.
- techinterviewquestion.com July 09, 2017