## 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) {
}
hi++;
}
}
return res;
}``````

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

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) {
}
hi++;
}
}
return res;
}``````

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

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)) {
}
}
return response;
}
}``````

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

}
return ans;``````

}

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

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

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``````

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

Apply rolling hash

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'
findIndices(small, large)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
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);

while((inx + wLen + 1) <= s.length())
{
subAsciiSum = subAsciiSum - sArray[inx];
subAsciiSum = subAsciiSum + sArray[inx+wLen];

inx ++;
}

}

return res;
}

private static long getAsciiSum(String s){
int sum= 0;
for(char c : s.toCharArray()){
sum = sum+ c;
}
return sum;
}``````

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

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

while((inx + wLen+1 ) <= s.length())
{
subAsciiSum = subAsciiSum - sArray[inx];
subAsciiSum = subAsciiSum + sArray[inx+wLen];

inx ++;
}

}

return res;
}

private static long getAsciiSum(String s){
int sum= 0;
for(char c : s.toCharArray()){
sum = sum+ c;
}
return sum;
}``````

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

``````public void FindIndexofAnagrams(String str, String word)
{
//Edge cases
if(word.length() < str.length() || str == "")
{
System.out.println("No anagrams possible");
}

char[] chr = str.toCharArray();
Arrays.sort(chr);
for(int i=0;i< word.length() - str.length() + 1; i++)
{
String partial = word.substring(i, i+chr.length);
System.out.println(partial);
char[] chr1 = partial.toCharArray();
Arrays.sort(chr1);
if(Arrays.equals(chr1,chr))
{
System.out.println(i);
}
}

}``````

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

``````void anagramIndex(char *anagram, char *word, int *index_array)
{
int i,j;
int len_anagram;
int anagram_started;

len_anagram = strlen(anagram);

i = 0;
j = 0;
anagram_started = 0;

while (word[i] != '\0')
{
if (word[i] == anagram[j])
{
//forward
if (anagram_started == 0)
{
anagram_started = 1;
*index_array = i;
index_array++;
}
i++; j++;
}
else if (word[i] == anagram[len_anagram-1-j])
{
//backward
if (anagram_started == 0)
{
anagram_started = 1;
*index_array = i;
index_array++;
}
i++; j++;
}
else if (anagram_started == 1)
{
anagram_started = 0;
*index_array = i-1;
j = 0; i++;
}
else
{
j = 0;
i++;
}
}
}``````

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

``````"""
Programming Language: Python

Index:  0123456789

"""
stack = []
stack2 = []
string = 'ABCDBACDAB'
word = 'AB'
match = 0
items = 0

"""
Make a stack of word & string
"""
for i in string:
stack.append(i)
for i in word:
stack2.append(i)

position = len(stack)

while(len(stack) != 0):

"""
Pop each item from the string `stack` and check to see if it is present in the word `stack`. If it is present in the word `stack`
remove the element from the word `stack` to avoid rechecking.

`items` count the number of items popped from the string `stack`. If the number of items popped are > than matched item in a row
then it means that the comparision condition is not met.
"""
c = stack.pop()
items = items + 1
position -=1

"""
Check the item popped from the string `stack` to see if the item is matched with the word `stack`.
"""

for i in stack2:
if c == i:
match += 1
stack2.remove(i)
break

"""
This condition checks to see if the items have been matched in consecutive order. If the items have not been matached in
consecutive order then reset the stack and `items` counter
"""

if (items - match) > 0:
match = 0
items = 0
stack2 = []
for i in word:
stack2.append(i)

"""
If the stack is empty it means that the condition has been met
"""

if len(stack2) == 0:

print('Position'+ str(position))
match = 0
items = 0
for i in word:
stack2.append(i)``````

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

private static Set<String> permute = new HashSet<>();
public static void permutation(String str) {
permute(str,0,str.length()-1);
}
public static void permute(String str, Integer start, Integer end) {
if(start==end) {
}else {
for(int i = start;i<=end;i++) {
str = swap(str,start,i);
permute(str,start+1,end);
str = swap(str,start,i);
}
}
}

public static String swap(String str, int start, int end) {
char[] arr = str.toCharArray();
char temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
return String.valueOf(arr);
}

public static void findIndics(String str) {
int i = 0;
String word = "AB";
permutation(word);
int len = word.length();
while(i<str.length()-1) {
String substr = str.substring(i, i+len);
if(permute.contains(substr)) {
System.out.println("Pos : "+i);
i +=(len-1);
}else {
i++;
}
}
}
public static void main(String...strings) {
Sol s = new Sol();
String str = "ABCDBACDAB";
s.findIndics(str);
}

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

``````private static Set<String> permute = new HashSet<>();
public static void permutation(String str) {
permute(str,0,str.length()-1);
}
public static void permute(String str, Integer start, Integer end) {
if(start==end) {
}else {
for(int i = start;i<=end;i++) {
str = swap(str,start,i);
permute(str,start+1,end);
str = swap(str,start,i);
}
}
}

public static String swap(String str, int start, int end) {
char[] arr = str.toCharArray();
char temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
return String.valueOf(arr);
}

public static void findIndics(String str) {
int i = 0;
String word = "AB";
permutation(word);
int len = word.length();
while(i<str.length()-1) {
String substr = str.substring(i, i+len);
if(permute.contains(substr)) {
System.out.println("Pos : "+i);
i +=(len-1);
}else {
i++;
}
}
}
public static void main(String...strings) {
Sol s = new Sol();
String str = "ABCDBACDAB";
s.findIndics(str);
}``````

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

``````static int[] GetAnagrams(string word, string ana)
{
int[] s = new int[word.Length];
int j = 0;
ana = new string(ana.OrderBy(o => o).ToArray());
for(int i=0; i<=word.Length-ana.Length; i++)
{
var sub = word.Substring(i, ana.Length).OrderBy(c=>c).ToArray();
if(new String(sub) == ana)
{
s[j] = i;
j++;
}
}
return s;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Leetcode 438. Find All Anagrams in a String

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.