SDE - 1 American Express interview experience

Interview rounds

Round

Medium

Online Coding Test

Duration90 Minutes

Interview date13 Jul 2022

Coding problem3

This was an online test on the hackerrank platform. The test consists of 3 coding questions to be solved in 90 mins.

1. Implement Map Sum Pair

Moderate

30m average time

60% success

0/80

Asked in companies

Ninja has to implement a data structure called ‘MapSum’. Ninja has to implement two functions and one constructor.

1) MapSum(): Ninja has to initialize the ‘MapSum’.
2) insert(‘KEY’, ‘VAL’): Ninja has to insert this key-value pair in this ‘MapSum’.
3) sum(‘PREFIX’): Ninja has to find the sum of all values whose prefix of the keys is equal to ‘PREFIX’

Note :

During insertion, In the ‘MapSum’ if a ‘KEY’ is already present in the ‘MapSum’ then replace it with the new one.

Problem approach

Try solving now

2. Zig-Zag Conversion

Moderate

0/80

Asked in companies

You are given a string ‘S’ and an integer ‘ROW’, convert the row into a zig-zag pattern with rows equal to ‘ROW’ and output it row-wise. You may refer to the example below to better understand what the zig-zag pattern means.

Example :

If ‘S’ = “beaninjacoder” and ‘ROW’ = 4

Then the zig-zag pattern is:
b         j        r
e     n   a     e
a   i     c   d
n         o

Therefore, we will print “bjrenaeaicdno”.

Problem approach

First I am creating the zigzag pattern and filling in the empty spaces with 0's and then I am just traversing the pattern to get the final answer.

So first I am filling all the rows in first column, then I am filling one row each for the next columns until I move up again to the 0th row and the process repeats.

class Solution {
public String convert(String s, int numRows) {

ArrayList > pattern = new ArrayList<>();

int pos = 0;
int i = 0, k = 0;

String ans = "";

while(pos< s.length()){

ArrayList arr = new ArrayList();

//forming the column where every row has an element
if(i==0){
for(; i= 0) //taking care of a case where num of rows = 2
i = i-2;
else
i = 0;
continue;
}

//forming the column where only one row has an element
for(int j = 0 ; j < numRows; ++j){
if(pos< s.length() && j == i){
arr.add(s.charAt(pos++));
--i;
}
else
arr.add('0');
}
// System.out.println(arr + " , " + i);
pattern.add(arr);
// System.out.println(pattern);

}

// System.out.println(pattern);

for(i = 0 ; i for(int j = 0 ; j< pattern.size() ; ++j){
if((pattern.get(j)).get(i) != '0')
ans = ans + (pattern.get(j)).get(i);
}
}

return ans;

}
}

Try solving now

3. Remove Duplicates from Sorted Array

Easy

15m average time

85% success

0/40

Asked in companies

You are given a sorted integer array 'arr' of size 'n'.

You need to remove the duplicates from the array such that each element appears only once.

Return the length of this new array.

Note:

Do not allocate extra space for another array. You need to do this by modifying the given input array in place with O(1) extra memory.

For example:

'n' = 5, 'arr' = [1 2 2 2 3].
The new array will be [1 2 3].
So our answer is 3.

Problem approach

Java Solution

class Solution {
public int removeDuplicates(int[] nums) {

int index =1 ;
for(int i=0;i if(nums[i]!=nums[i+1]){
nums[index++]=nums[i+1];
}
}
return index;
}
}

Try solving now

Round

Easy

Video Call

Duration45 Minutes

Interview date15 Jul 2022

Coding problem2

This was 1st technical round taken by the software engineer at American Express. Interviewer was very friendly, he started with his introduction and then asked me to introduce myself.

1. Best time to buy and sell stock

Moderate

20m average time

80% success

0/80

Asked in companies

You are given an array/list 'prices' where the elements of the array represent the prices of the stock as they were yesterday and indices of the array represent minutes. Your task is to find and return the maximum profit you can make by buying and selling the stock. You can buy and sell the stock only once.

Note:

You can’t sell without buying first.

For Example:

For the given array [ 2, 100, 150, 120],
The maximum profit can be achieved by buying the stock at minute 0 when its price is Rs. 2 and selling it at minute 2 when its price is Rs. 150.
So, the output will be 148.

Problem approach

class Solution:
def maxProfit(self, prices: List[int]) -> int:
cheap = prices[0]
res = 0

for i in range (1, len(prices)):
cheap = min(cheap, prices[i])
res = max(res, prices[i] - cheap)

return res
Because we set the "cheap" as 0-index value from prices, we have to iterate from 1-index to the end.

Try solving now

2. Add One To Number

Easy

10m average time

90% success

0/40

Asked in companies

Given a non-negative number represented as an array of digits, you have to add 1 to the number, i.e, increment the given number by one.

The digits are stored such that the most significant digit is at the starting of the array and the least significant digit is at the end of the array.

For Example

If the given array is {1,5,2}, the returned array should be {1,5,3}.

Note

Input array can contain leading zeros, but the output array should not contain any leading zeros (even if the input array contains leading zeroes).
For Example: 
If the given array is {0,2}, the returned array should be {3}.

Problem approach

C++ solution

class Solution {
public:
vector plusOne(vector& digits) {
reverse(digits.begin(),digits.end());
int carry=0;
for(int i=0;i if(digits[i]!=9){
digits[i]+=1;
break;
}
else if(digits[i]==9){
carry=1;
digits[i]=0;
}
}
if(digits[digits.size()-1]==0){
digits.push_back(1);
}
reverse(digits.begin(),digits.end());
return digits;
}
};

Try solving now

Round

Medium

Video Call

Duration45 minutes

Interview date19 Jul 2022

Coding problem1

This was 2nd technical round taken by the senior software developer. Interviewer was very friendly and helped my whenever I strucked. He started with his introduction and then asked me to introduce myself.

He asked about my project work in detail
What are OOPs concepts and its pillar
Is java support multiple inheritance or not
what are acid properties
Write a SQL query to find the 2nd largest salary from employee table

1. Maximum Product Subarray

Moderate

25m average time

75% success

0/80

Asked in companies

You are given an array “arr'' of integers. Your task is to find the contiguous subarray within the array which has the largest product of its elements. You have to report this maximum product.

An array c is a subarray of array d if c can be obtained from d by deletion of several elements from the beginning and several elements from the end.

For e.g.- The non-empty subarrays of an array [1,2,3] will be- [1],[2],[3],[1,2],[2,3],[1,2,3].

For Example:

If arr = {-3,4,5}.
All the possible non-empty contiguous subarrays of “arr” are {-3}, {4}, {5}, {-3,4}, {4,5} and {-3,4,5}.
The product of these subarrays are -3, 4, 5, -12, 20 and -60 respectively.
The maximum product is 20. Hence, the answer is 20.

Follow Up:

Can you solve this in linear time and constant space complexity?

Problem approach

C++ solution

class Solution {
public:
int maxProduct(vector& nums) {
long int maxi = INT_MIN,prod=1;

for(auto& num : nums){
prod*=num;
maxi = max(maxi,prod);
if(prod==0) prod=1;
}
prod=1;
for(int i=nums.size()-1;i>=0;i--){
prod*=nums[i];
maxi = max(maxi,prod);
if(prod==0) prod=1;
}
return maxi;
}
};