Amazon Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: Written Test




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

Hi, you can use moving window algorithm to solve this problem, the complexity is O(n). Here's Java code.

public Set<String> findAnagrams(String a, String b) {
    // create two array for counter
    // number of each letter in String a and Substring b
    char[] aCounter = new char[300];
    char[] bCounter = new char[300];

    // count number of each letter in String a
    for (char c : a.toCharArray()) {
        aCounter[c]++;
    }

    Set<String> answer = new HashSet<>();

    // create two variable for moving window
    int left = 0;
    int right = 0;

    while (right < b.length()) {
        // update counter letter of window
        bCounter[b.charAt(right)]++;

        // if window length equal a length,
        // check if this window same letter with a or not
        if (right - left + 1 == a.length()) {
            if (isSame(aCounter, bCounter)) {
                // if this window same letter with a,
                // add substring from left to right to answer
                answer.add(b.substring(left, right + 1));
            }

            // moving window to right
            bCounter[b.charAt(left)]--;
            left++;
        }


        right++;
    }

    return answer;
}

private boolean isSame(char[] aCounter, char[] bCounter) {
    for (char c = 'a'; c <= 'z'; c++) {
        if (aCounter[c] != bCounter[c]) {
            return false;
        }
    }
    return true;
}

- techinterviewquestion.com July 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this number of sequential subsequences that are anagrams? Or subsets?

- Jimbo July 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
};

- technocast July 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
};

- technodrive July 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
};

- Darshan Washimkar July 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
           
        }
    }

- Anonymous July 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
           
        }
    }

- KD July 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Fernando July 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous July 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- DR ADM July 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- DR ADM July 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

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

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;
	}

}

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

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;
}
}

- Anonymous July 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

}

- srk July 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- srk July 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- srk July 21, 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