SDE - Intern American Express interview experience | Akshat Bhargava

Interview rounds

Round

Easy

Online Coding Interview

Duration120 minutes

Interview date29 Aug 2020

Coding problem3

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.

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.

Easy

15m average time

90% success

0/40

Asked in companies

You are given an array 'ARR' of 'N' positive integers. You need to find the length of the longest switching contiguous subarray.

An array is called Switching if all the elements at even indices are equal and all the elements at odd indices are also equal.

For Example :

If the given 'ARR' is [1, 4, 1, 4, 3, 2, 3, 0]. Then {1, 4, 1, 4}, {3, 2, 3}, {3, 0}, {0} are some of the switching subarrays. But {1, 4, 3}, {1, 4, 1, 4, 3, 2, 3} are not.

Problem approach

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.

Try solving now

2. 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 leave the casino with N chips, having placed all-in no more than K times. If the person bets C chips and wins he gets 2C chips back and if he loses he doesn't get anything.

Problem approach

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.

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.For Ex - "aaaabbbb" should return 1, as when we delete 1 a or 1 b , a and b will have different frequencies.

Moderate

15m average time

80% success

0/80

Asked in companies

You are given a string ‘STR’. You need to find and return the minimum number of characters to be deleted from ‘STR’ so that the frequency of each character in the string becomes unique.

Example:

If the given string is “aaBBccc” then the frequency of characters: { a:2, B:2, c:3 }. Now, as ‘a’ and ‘B’ both have the same frequency 2, we need to delete one character either one ‘a’ or one ‘B’, to make their frequency different. After deleting any character we will get frequency as 1,2 and 3, as they all are different. Thus we got our solution as 1.

Try solving now

Round

Easy

HR Round

Duration40 minutes

Interview date5 Sep 2020

Coding problem1

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

1.

Problem approach

Tip 1: Be confident answer honestly as they can catch you easily
Tip 2: Know everything on your resume
Tip 3: Be gentle as you speak

Round

Easy

Telephonic

Duration20 minutes

Interview date5 Sep 2020

Coding problem4

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?

1. Q1. How many stacks are used to implement a queue.

Problem approach

Just the answer which is 2.

2. Q2. What is the difference between a reference and a pointer? Explain with an example.

Problem approach

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)

3. 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

Problem approach

Answer = 1

4. 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, then throw an exception and print that you have entered 0. If the number is negative, then throw an exception and print that you have entered a negative number.

Problem approach

The question explains everything. Just need to use try catch blocks for exception handling

Round

Easy

Face to Face

Duration50 minutes

Interview date5 Sep 2020

Coding problem2

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.

1. Given a linked list of characters, tell if it is a palindrome linked list or not.

Easy

20m average time

90% success

0/40

Asked in companies

You are given a singly Linked List of integers. Your task is to return true if the given singly linked list is a palindrome otherwise returns false.

For example:

The given linked list is 1 -> 2 -> 3 -> 2-> 1-> NULL.

It is a palindrome linked list because the given linked list has the same order of elements when traversed forwards and backward.

Follow Up:

Can you solve the problem in O(N) time complexity and O(1) space complexity iteratively?

Problem approach

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 character at the top of the stack and the current character match. Finally, if the stack is empty then will return true else false.

Try solving now

2. 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 many students, so how will you establish normalization here in many to many relationships.

Problem approach

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.

SDE - Intern

Interview preparation journey

Interview rounds

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.

You are given an array 'ARR' of 'N' positive integers. You need to find the length of the longest switching contiguous subarray.

An array is called Switching if all the elements at even indices are equal and all the elements at odd indices are also equal.

For Example :

2. Chips at Casino

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.For Ex - "aaaabbbb" should return 1, as when we delete 1 a or 1 b , a and b will have different frequencies.

You are given a string ‘STR’. You need to find and return the minimum number of characters to be deleted from ‘STR’ so that the frequency of each character in the string becomes unique.

Example:

1.

1. Q1. How many stacks are used to implement a queue.

2. Q2. What is the difference between a reference and a pointer? Explain with an example.

3. 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

1. 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 otherwise returns false.

For example:

Follow Up:

2. 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 many students, so how will you establish normalization here in many to many relationships.