Amazon Interview Question Software Engineers
Country: United States
Interview Type: In-Person
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;
}
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
}
})
}
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;
}
}
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;
}
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)));
}
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
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
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)
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;
}
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;
}
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);
}
}
}
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++;
}
}
}
"""
Programming Language: Python
Index: 0123456789
Pattern ABCDBACADB
"""
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)
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) {
permute.add(str);
}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);
}
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) {
permute.add(str);
}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);
}
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;
}
- aonecoding4 February 19, 2019public 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; }