American Express Software Developer Intern Interview Questions, Process, and Tips

Round duration - 90 minutes
Round difficulty - Medium

It consist three question - first que is of related to tree and i gave difficulty level of this question as hard. second que is of based on logical and reasoning , it is medium level question and third que can be done by map and it is also medium level que.
In codility platform we are not able to see hidden test cases whether it is satisfied or not . we just have to submit after passing sample testcases.

Q1. Minimum number of swaps required to sort an array
You have been given an array 'ARR' of 'N' distinct elements.
Your task is to find the minimum no. of swaps required to sort the array.
F...read more
Ans. Naive Approach
While iterating over the array, check the current element, and if not in the correct place, replace that element with the index of the element which should have come in this place.
 
Below is the algorithm:
1. Create a copy of the given input array and store it in temp.
2. Sort the temp array.
3. Iterate over the input array, and check whether the current element is at the right place or not by comparing it with t...read more
Answered by CodingNinjas
View 1 more answer
Q2. Maximum sum of non-adjacent elements
You are given an array/list of ‘N’ integers. You are supposed to return the maximum sum of the subsequence with the constraint that no two elements are adjacent in the ...read more
Ans. Recursive Approach (top down)
We are going to explore all the possibilities of subsequences in which there will be no two elements that are adjacent to one another in the given array/list. So if we take the current element, let’s say ‘CURR’ then we are not allowed to take the element adjacent to ‘CURR’. So for that, we will call a recursive function one step forward to the ‘CURR’. 
 
The Steps are as follows:
&nb...read more
Answered by CodingNinjas
View 2 more answers
Q3. Left View Of Binary Tree
Given a binary tree. Print the Left View of the Tree.
Example :
If the input tree is as depicted in the picture: 
The Left View of the tree will be:  2 35 2 
Input format :
...read more
Ans. Recursive Approach
This problem can be solved through recursion.We will maintain max_level variable which will keep track of maxLevel and will pass current level in recursion as argument. Whenever we see a node whose current level is more than maxLevel then we will print that node as that will be first node for that current level. Also update maxLevel with current level.
Space Complexity: O(n)Explanation:
O(N), where ‘N’...read more
Answered by CodingNinjas
View 1 more answer

Round duration - 30 minutes
Round difficulty - Medium

basically this round is just same as HR round . they asked me behavioural questions and about my projects , hackathon. the timing is mid noon and interviewer is supportive , it makes first comfortable then start questioning . for this round i suggest be honest , don't just express your qualities but trying to show them by your skills and work.

Q1. Basic HR Questions
Who is your role model?
Why do you want to join the company?
Add your answer

Round duration - 120 minutes
Round difficulty - Easy

It consisted of 3 coding questions which were purely based on Data Structures and Algorithms.

Question 1 - Find the length of the longest switching sub-array. An array is called switching if all numbers in even positions are equal and all numbers in odd positions are equal. 


Question 2 - It was a long passage question on Dynamic Programming but the solution was really easy.

Question 3 - Given a string S consisting of N lowercase letters, return the minimum number of letters that must be deleted to obtain a word in which every letter occurs a unique number of times. Ex - "aaaabbbb" should return 1, as when we delete 1 a or 1 b , a and b will have different frequencies.


The major point to note in the coding round was that they did not have any time or space limit, so brute force solutions were also accepted. 
The result of my test was declared just as the test ended and I scored a 100%, but they took a long time to release the final shortlist. There was a gap of about a week between the test and interviews.

Q1. Find the length of the longest switching sub-array. An array is called switching if all numbers in even positions are equal and all numbers in odd positions are equal.
You are given an array 'ARR'...read more
Ans. 
It's like a sliding window problem.
We keep track of even and odd equality with 2 variables, even and odd.
Whenever we come across a unmet condition, like index even but not equal with even variable and same goes for odd, we first
Record the length till now in max_len.
Reset start to i-1 as this is need incase of all elements equal.
Reset even and odd according to current index i to arr[i] and arr[i-1] respectively.
Answered by CodingNinjas
View 2 more answers
Q2. Chips at Casino
Given two integer N and K representing number of chips a person has and the number of chips he can use at max at a time, return the minimum number of rounds that are necessary for John to le...read more
Ans. 
It was a dynamic programming question but I was able to solve it with recursion as well.
The approach was simply, that if he wins then he gets 2C chips back. that means 1 turn is used to deploy half the chips he had. while in the other case he just loses a chip and same number of turns are restored.
Answered by CodingNinjas
Add your answer
Q3. Given a string S consisting of N lowercase letters, return the minimum number of letters that must be deleted to obtain a word in which every letter occurs a unique number of times.For Ex - "aaaabbbb" shou...read more
Ans. Brute Force
As we are only allowed to delete the character, thus the resulting string after deletion of some character would be the subsequence of the string. So, we have to find such a subsequence which has the unique frequency of each character. 
 
Initialise a variable ‘ans’ that will store the minimum number of characters that are needed to remove from the string. Create all the subsequences of the string an...read more
Answered by CodingNinjas
View 1 more answer

Round duration - 40 minutes
Round difficulty - Easy

Amex came for two profiles - Tech Role and Analyst, 19 and 23 people respectively were shortlisted for the interviews. Fortunately, I was shortlisted for both the roles. I was asked basic question of C++ and it was majorly an HR Round

Round duration - 20 minutes
Round difficulty - Easy

It was a fairly simple round conssting of 5 - 6 questions related to coding, puzzles and me.

What are your interests? 
What projects have you done and your field of interest?

Q1. Q1. How many stacks are used to implement a queue.
Ans. 
Just the answer which is 2.
Answered by CodingNinjas
Add your answer
Q2. Q2. What is the difference between a reference and a pointer? Explain with an example.
Ans. 
Reference - No memory is allocated and it is just an alias of the same memory location
Pointer - New memory location is created which stores the address of the location it is pointing to.
Ex -
int& a = b (reference)
int* a = &b (pointer)
Answered by CodingNinjas
Add your answer
Q3. There is a bulb in a room, you are outside the room and there are 3 switches, what is the minimum number of times you need to open the door to know to which switch the bulb belongs
Add your answer
Q4. You are given a number if the number is positive, then if n is divisible by 3, print “GO” if n is divisible by 5, print “SLEEP” , if n is divisible by both 3 and 5, print “RETIRE”. If the number equals 0, ...read more
Ans. 
The question explains everything. Just need to use try catch blocks for exception handling
Answered by CodingNinjas
Add your answer

Round duration - 50 minutes
Round difficulty - Easy

This round was purely technical
No introduction was done, straight to the point

My preference was the Tech Role, so as I was selected in this, I never had to give interviews for the Analyst role. In total 5 people were selected in the Analyst profile and 4 in the Tech profile.

In the end, I was offered a 6 months internship at Amex.

Q1. Given a linked list of characters, tell if it is a palindrome linked list or not.
You are given a singly Linked List of integers. Your task is to return true if the given singly linked list is a palindrome...read more
Ans. 
I gave the two pointer approach. Then he said what if we are provided with the length of the list. I said that we will move forward in the list till n/2 nodes and then the same approach as above. Then he said what if we had to do it with a stack. I said we will add elements into the stack till n/2 nodes and then start popping elements while simultaneously traversing the linked list from the (n/2+1)th node till n if the...read more
Answered by CodingNinjas
View 4 more answers
Q2. You are given a student table and a course table with primary keys -> roll number and course_id in each respectively. Since we know that a student can enroll in many courses and a course can be taken by ma...read more
Ans. 
We will create a third table that will store only two columns which are the Primary Keys of both the tables and they together can uniquely identify records in both the tables.

I thought of it but did not reach the solution at once, it took me 3 – 4 attempts for it but he didn’t tell me anything, and finally, I got to the solution.
Answered by CodingNinjas
Add your answer

Round duration - 120 minutes
Round difficulty - Easy

The coding round was at 11 am in the morning. The questions were of medium level. The questions were purely based on Data Structures and Algorithms.

Q1. Sliding Maximum
You are given an array 'ARR' of integers of length 'N' and a positive integer 'K'. You need to find the maximum elements for each and every contiguous subarray of s...read more
Ans. Brute Force
1. We know that an array of size ‘N’ will have in total ‘N’ - ‘K’ - 1 subarray of size ‘K'.
2. Thus, what a trivial solution suggests is that we traverse over all subarrays of size ‘K', and calculate the maximum element in each of these subarrays individually.
3. So, we can run two nested loops, the outer one will iterate over the starting index of the subarray, and the inner loop will be used to calculate the max...read more
Answered by CodingNinjas
View 2 more answers
Q2. Longest Sub-string with at most K Distinct Characters
You are given string S of length N, and an integer K. Your task is to find the length of the longest substring that contains at most K distinct charact...read more
Ans. Brute Force
• We will generate all the substrings using 2 nested for loops and we will have a ‘CHECK’ function which returns true if the number of distinct character in the substring is less than equal to K otherwise false.
• We will have an ans variable initialize to 0. We will call the ‘CHECK’ function with every substring and if it returns true then
  • ANS = MAX(ANS , CURRENT_SUBSTRING.SIZE())
• To implement the check function w...read more
Answered by CodingNinjas
View 3 more answers

Round duration - 45 minutes
Round difficulty - Easy

I was selected for the interview. The interview was conducted early in the morning at 10 am. The interviewer was very friendly and calm.

Q1. Technical Questions
1. Tell in detail about your one project. 
2. Questions related to the project were followed, such as what challenges I faced during the course of making the project.
3. What is copy ...read more
Add your answer

Round duration - 30 minutes
Round difficulty - Easy

This round was a mix of technical, puzzles and HR. The interview was fairly easy, The interviewer asked for my introduction and continued with the interview then.

Q1. Stack using queue
Implement a Stack Data Structure specifically to store integer data using two Queues.
There should be two data members, both being Queues to store the data internally. You may use the i...read more
Ans. Approach 1
• This method ensures that every new element entered in the queue ‘q1’ is always at the front.
• Hence, during pop operation, we just dequeue from ‘q1’.
• For this, we need another queue ‘q2., which is used to keep every new element to the front of ‘q1’.
• During push operation :
  • Enqueue new element ‘x’ to queue ‘q2’.
  • One by one, dequeue everything from ‘q1’ and enqueue to ‘q2’.
  • Swap the names of ‘q1’ and ‘q2’.
• During pop o...read more
Answered by CodingNinjas
View 2 more answers
Q2. Puzzle
There is a room with a door (closed) and three light bulbs. Outside the room, there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door...read more
Add your answer

Round duration - 45 minutes
Round difficulty - Easy

This was the last round for getting selected as an intern. However, this was a pure technical round. Only coding questions were asked. Also, at the end he asked me the question, Why American express?

Q1. Detect and Remove Loop
Given a singly linked list, you have to detect the loop and remove the loop from the linked list, if present. You have to make changes in the given linked list itself and return the ...read more
Ans. 
1. Traverse linked list using two pointers, that is, slow and fast pointer
2. Move slow pointer by one and fast pointerby two.
3. If these pointers meet at the same node then there is a loop. If pointers do not meet then linked list doesn’t have a loop.
Answered by CodingNinjas
View 3 more answers
Q2. DBMS Questions
Explain Natural Join, Cross Join, Right Outer and Left Outer Join with diagrams. Also write queries using GROUP BY and HAVING.
Add your answer
Q3. Interval List Intersection
You have been given two sorted arrays/lists of closed intervals ‘INTERVAL1’ and ‘INTERVAL2’. A closed interval [x, y] with x < y denotes the set of real numbers ‘z’ with x &l...read more
Ans. Two-Pointer Approach
The main intuition behind this approach is that ‘INTERVAL1’ and ‘INTERVAL2’ are already sorted. So two cases arise:
 
1. If INTERVAL1[0] has the smallest endpoint, it can only intersect INTERVAL2[0]. After that, we can discard INTERVAL1[0] since it cannot intersect with anything else.
2. If INTERVAL2[0] has the smallest endpoint, it can only intersect INTERVAL1[0]. After that can discard INTERVAL2[0] si...read more
Answered by CodingNinjas
Add your answer

Q1. Travelling Salesman Problem
Given a list of cities numbered from 0 to N-1 and a matrix 'DISTANCE' consisting of 'N' rows and 'N' columns denoting the distances between each pair of ...read more
Ans. Brute-force
The idea here is to visit all possible permutations of visiting the vertex.
Example-

 
Consider the above graph one possible permutation is A -> B -> C -> D -> A. Similarly we try all permutations and calculate the cost of each of the routes and update the 'ANS' to a minimum such route.
If we notice B -> C -> D -> A -> B is a cyclic permutation of A -> B -> C -> D -> A. A...read more
Answered by CodingNinjas
View 1 more answer