Amazon Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

public static List<Integer> getAnagrams(String s, String word) {
        Map<Character, Integer> letters = new HashMap<>();
        int distinct_letters = 0;
        for(char c: word.toCharArray()) {
            if(!letters.containsKey(c)) distinct_letters++;
            letters.put(c, letters.getOrDefault(c, 0) + 1);
        }

        //search for anagrams with two pointers
        List<Integer> res = new ArrayList<>();
        int lo = 0, hi = 0;
        while(hi < s.length()) {
            if(!letters.containsKey(s.charAt(hi))) {
                while(lo < hi) {
                    char c = s.charAt(lo);
                    if(letters.get(c) == 0) distinct_letters++;
                    letters.put(c, letters.get(c) + 1);
                    lo++;
                }
                hi++;
                lo = hi;
            } else if(letters.get(s.charAt(hi)) == 0){
                char c = s.charAt(lo);
                if(letters.get(c) == 0) distinct_letters++;
                letters.put(c, letters.get(c) + 1);
                lo++;
            } else {
                char c = s.charAt(hi);
                letters.put(c, letters.get(c) - 1);
                if(letters.get(c) == 0) distinct_letters--;
                if(distinct_letters == 0) {
                    res.add(lo);
                }
                hi++;
            }
        }
        return res;
    }

- aonecoding4 February 19, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above solution crashes for s = "ABACDBACDAB". Here's the fix:

public static List<Integer> getAnagrams(String s, String word) {
    Map<Character, Integer> letters = new HashMap<>();
    int distinct_letters = 0;
    for (char c : word.toCharArray()) {
        if (!letters.containsKey(c)) distinct_letters++;
        letters.put(c, letters.getOrDefault(c, 0) + 1);
    }

    //search for anagrams with two pointers
    List<Integer> res = new ArrayList<>();
    int lo = 0, hi = 0;
    while (hi < s.length()) {
        if (!letters.containsKey(s.charAt(hi))) {
            while (lo < hi) {
                char c = s.charAt(lo);
                if (letters.get(c) == 0) distinct_letters++;
                letters.put(c, letters.get(c) + 1);
                lo++;
            }
            hi++;
            lo = hi;
        } else if (letters.get(s.charAt(hi)) == 0) {
            char c = s.charAt(lo);
            if (letters.get(c) == 0) distinct_letters++;
            letters.put(c, letters.get(c) + 1);
            lo++;
        } else {
            char c = s.charAt(hi);
            letters.put(c, letters.get(c) - 1);
            if (letters.get(c) == 0) distinct_letters--;
            if (distinct_letters == 0) {
                res.add(lo);
            }
            hi++;
        }
    }
    return res;
}

- jkgriesser March 11, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Scala Functional Programming approach:

def findAnagrams(s: String, p: String): List[Int] = {
    val map = p.groupBy(identity).mapValues(_.length)
    s.zipWithIndex.view.foldLeft(List.empty[Int])((acc, x) => {
      if (map.contains(x._1) && x._2 + p.length <= s.length) {
        val mapIdx = s.substring(x._2, x._2 + p.length).groupBy(identity).mapValues(_.length)
        if (map == mapIdx) acc :+ x._2 else acc
      } else {
        acc
      }
    })
  }

- guilhebl February 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
      boolean found(int i, int[] c1, int[] c2) {
		int sum = 0;
		for(int w=0; w<c1.length; w++) {
			if(c1[w]-c2[w]!=0) return false;
			
		}
		return true;
		
	}
	 public  List<Integer> findAnagrams(String s, String p) {
		 
		 List<Integer> response = new ArrayList<>();
		 if(s == null || p == null || s.length()==0 || p.length() == 0) return response;
		char[] ch = p.toCharArray();
		char[] chs = s.toCharArray();
		int[] l = new int[128];
		for (char c : ch) {
			l[c - 'a']++;
		}

		for (int i = 0; i < chs.length-ch.length+1; i++) {
			int count = 0;
			int[] window = new int[p.length()];
			int[] window2 = new int[p.length()];
			int[] c1 = new int[128];
			int[] c2 = new int[128];
			for (int j = i; j < p.length() + i; j++) {
	
				c1[chs[(i + (j - i))]-'a']++;
				c2[ch[((j - i))]-'a']++;
				//window[(j - i)] = chs[(i + (j - i))] - ch[j - i];
			}
			if(found(i, c1, c2)) {
				response.add(i);
			}
		}
		return response;
	}
}

- spiroso February 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution but its runtime is high

public boolean compare(String sub, String p){
        char A[] = sub.toCharArray();
        char B[] = p.toCharArray();
        Arrays.sort(A);
        Arrays.sort(B);
        for(int i=0; i<p.length(); ++i){
            if(A[i]!=B[i])return false;
        }
        return true;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int len = p.length();
        for(int i=0; i<s.length(); ++i){
            if(i+len<=s.length()){
                String t = s.substring(i,len+i);
                if(compare(t,p))ans.add(i);
            }

        }
        return ans;

}

- abdoibrahim1017 February 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] GetIndexesOfAnagrams(char[] in, char[] pattern)
	{
		int[] result = new int[in.length];
		
		int[] ascii_pattern = new int[255];
		
		for(int i = 0 ;i < pattern.length; ++i)
		{
			++ascii_pattern[pattern[i]];
		}
		
		int indices = 0;
		
		for(int i =0; i < in.length; )
		{
			if(ascii_pattern[in[i]] > 0)
			{
				int j = i;
				int k =0;
				do
				{
					++j;
					++k;
					
				}while(k < pattern.length && j < in.length && ascii_pattern[in[j]] > 0);
				
				if( k == pattern.length)
				{
					result[indices++] = i;
					i = j;
				}
			}
			else
			{
				++i;
			}
		}
		
		return result;
		
	}
	
	public static void main(String[] args)
	{
		char[] in = "ABCDBACDAB".toCharArray();
		char[] pattern = "AB".toCharArray();
		
		System.out.println(" " + Arrays.toString(GetIndexesOfAnagrams(in, pattern)));
	}

- Guru February 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def anagram_finder(word, target_word):
word_list = list(word)
anagram = ""
indexes = []

for letter_index, letter in enumerate(target_word):
if letter in word_list:
anagram += word_list.pop(word_list.index(letter))
if len(anagram) > 1:
anagram_start_index = (letter_index - len(anagram) + 1)
indexes.append(anagram_start_index)
anagram = ""
word_list = list(word)
return indexes

- JP March 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def anagram_finder(word, target_word):
    word_list = list(word)
    anagram = ""
    indexes = []
    
    for letter_index, letter in enumerate(target_word):
        if letter in word_list:
            anagram += word_list.pop(word_list.index(letter))
        if len(anagram) > 1:
            anagram_start_index = (letter_index - len(anagram) + 1)
            indexes.append(anagram_start_index)
            anagram = ""
            word_list = list(word)
    return indexes

- JP March 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Apply rolling hash

- koustav.adorable March 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

JavaScript does not have a queue but treating the array as if it were a queue, the run time is O(n).

function incrementChar(char, map) {
  map.set(char, map.get(char) + 1)
}

function decrementChar(char, map) {
  map.set(char, map.get(char) - 1)
}

function createCharMap(str) {
  const map = new Map()
  for(let char of str) {
    if(map.get(char)) {
      incrementChar(char, map)
    } else {
      map.set(char, 1)
    }
  }
  return map
}

function dequeueAllChars(queue, map) {
  while(queue.length > 0) {
    dequeueChar(queue, map)
  }
}

function dequeueChar(queue, map) {
  const char = queue.shift()
  incrementChar(char, map)
}

function findIndices(small, large) {
  const queue = []
  const charMap = createCharMap(small)
  const resultIndices = []

  for(let i = 0; i < large.length; i++) {
    const char = large[i]

    if(charMap.get(char) > 0) {
      queue.push(char)
      decrementChar(char, charMap)

      if(queue.length === small.length) {
        const anagramStartingIndex = i - queue.length + 1
        resultIndices.push(anagramStartingIndex)
        dequeueChar(queue, charMap)
      }
    } else {
      dequeueAllChars(queue, charMap)
    }
  }

  return resultIndices
}

const small = 'aba'
const large = 'abadhfiobaabklsjdflk'
findIndices(small, large)

- Ninja March 08, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
- aonecoding4 March 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

simple solution using ascii value sum-

public static List<Integer> getAnagrams(String s, String word) {
		List<Integer> res = new ArrayList<>();
		long wordAsciiSum= getAsciiSum(word);
		int wLen = word.length();
		int inx = 0;
		char[] sArray = s.toCharArray();
		if((inx + wLen) <= s.length())
		{
			String subStr = s.substring(inx, wLen);
			long subAsciiSum = getAsciiSum(subStr);
			
			if(subAsciiSum == wordAsciiSum){ res.add(inx);}
			
			while((inx + wLen + 1) <= s.length())
			{	
				subAsciiSum = subAsciiSum - sArray[inx];
				subAsciiSum = subAsciiSum + sArray[inx+wLen];

				if(subAsciiSum == wordAsciiSum){ res.add(inx);}
				inx ++;
			}
		
		}
		
		return res;
	}
	
	private static long getAsciiSum(String s){
		int sum= 0;
		for(char c : s.toCharArray()){
			sum = sum+ c;
		}
		return sum;
	}

- Sam March 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correction to code -

public static List<Integer> getAnagramsv2(String s, String word) {
		List<Integer> res = new ArrayList<>();
		long wordAsciiSum= getAsciiSum(word);
		int wLen = word.length();
		int inx = 0;
		char[] sArray = s.toCharArray();
		if((inx + wLen) <= s.length())
		{
			String subStr = s.substring(inx, wLen);
			long subAsciiSum = getAsciiSum(subStr);
			
			if(subAsciiSum == wordAsciiSum){ res.add(inx);}
			
			while((inx + wLen+1 ) <= s.length())
			{	
				subAsciiSum = subAsciiSum - sArray[inx];
				subAsciiSum = subAsciiSum + sArray[inx+wLen];

				if(subAsciiSum == wordAsciiSum){ res.add(inx+1);}
				inx ++;
			}
		
		}
		
		return res;
	}
	
	private static long getAsciiSum(String s){
		int sum= 0;
		for(char c : s.toCharArray()){
			sum = sum+ c;
		}
		return sum;
	}

- Sam March 17, 2019 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Leetcode 438. Find All Anagrams in a String

- Sithis February 19, 2019 | 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