10+ American Express Software Developer Intern Interview Questions and Answers

The task is to find the minimum number of deletions needed in a string to ensure each character appears a unique number of times.

• Iterate through the string and count the frequency of each character

• Track the frequencies in a hashmap

• Identify the characters with duplicate frequencies and calculate the minimum deletions needed

• Return the minimum number of deletions for each test case

Find the length of the longest switching subarray in a given array of positive integers.

• Iterate through the array and keep track of the longest switching subarray found so far.

• Check if the numbers at even and odd positions are identical to determine a switching subarray.

• Return the length of the longest switching subarray.

• Example: For input [1, 4, 1, 4, 3, 2, 3, 0], the longest switching subarray is [1, 4, 1, 4] with length 4.

Check if a singly linked list is a palindrome by comparing elements from both ends.

• Traverse the linked list to find the middle point

• Reverse the second half of the linked list

• Compare the first half with the reversed second half to check for palindrome

• Example: Input: 1 2 3 2 1 -1, Output: true

Implement a function to find maximum elements for each contiguous subarray of size K in an array of integers.

• Iterate through the array and maintain a deque to store the indices of elements in decreasing order.

• Pop elements from the deque that are out of the current window and add the maximum element to the result array.

• Return the result array containing maximum elements for each subarray of size K.

Find the length of the longest substring with at most K distinct characters in a given string.

• Use a sliding window approach to keep track of the characters and their counts in the substring.

• Maintain a hashmap to store the characters and their frequencies within the window.

• Update the window size and characters count as you iterate through the string.

• Keep track of the longest substring length with at most K distinct characters.

• Return the length of the longest substring for each...read more

Find the intersections of two sorted lists of closed intervals.

• Iterate through both interval lists to find intersections

• Compare the intervals and find the common range

• Handle cases where there is no intersection between intervals

Implement a stack using two queues to store integer values with specified functions.

• Use two queues to simulate stack operations efficiently.

• Maintain one queue for storing elements and another for temporary storage during push operation.

• Ensure proper handling of edge cases like empty stack or invalid operations.

• Example: Push operation involves transferring elements from one queue to another before adding the new element.

• Example: Pop operation removes and returns the top elemen...read more

Detect and remove loop in a singly linked list in place with O(n) time complexity and O(1) space complexity.

• Use Floyd's Cycle Detection Algorithm to identify the loop in the linked list.

• Once the loop is detected, use two pointers to find the start of the loop.

• Adjust the pointers to remove the loop and return the modified linked list.

The minimum number of swaps required to sort a given array of distinct elements in ascending order.

• Use a graph-based approach to find cycles in the array

• Count the number of swaps needed to fix each cycle

• Sum up the swaps needed for all cycles to get the total minimum swaps

Find the maximum sum of a subsequence without choosing adjacent elements in an array.

• Use dynamic programming to keep track of the maximum sum at each index, considering whether to include or exclude the current element.

• At each index, the maximum sum is either the sum of the current element and the sum two positions back, or the sum at the previous index.

• Iterate through the array and update the maximum sum accordingly.

• Example: For input [3, 2, 7, 10], the maximum non-adjacent ...read more