Determine max remainders and anagram after deletions

Q: Determine max remainders and anagram after deletions

This is a Coding & Algorithms interview question from Amazon for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Part 1 (Array Remainders): Given an integer array A of length n with A[i] > 0. You may choose any integer array B of length n. Define C[i] = B[i] mod A[i] for 0 ≤ i < n. What is the maximum possible number of distinct values in C? Describe an efficient algorithm to compute this maximum for a given A and provide time/space complexities. Part 2 (String Similarity by Deleting One Letter Type): Given two lowercase strings s and t. In each string, you may select one letter (possibly a different letter in each string) and delete any number of occurrences of that letter (including zero). After these deletions, can s and t become anagrams (i.e., have identical letter-frequency vectors)? Design an algorithm to decide this and analyze its complexity.

Determine max remainders and anagram after deletions

Comments (0)