SDE - 1 JP Morgan interview experience | Anonymous

Interview rounds

Round

Medium

Online Coding Test

Duration65 Minutes

Interview date19 Aug 2021

Coding problem2

This was an online proctured coding test where we had 2 questions to solve under 65 minutes. Both the questions were of difficulty Medium to Hard.

1. Make Array Elements Equal

Moderate

25m average time

75% success

0/80

Asked in companies

You are given an array of integers of size ‘N’. You have to make the elements of the array equal, and the cost of changing the element ‘x’ to ‘y’ is abs(x -y). Your task is to find the minimum cost to make the elements of the array equal.

For example:

Consider ARR = [3, 4, 5] now suppose if we want to change every element value to 4, then the cost of changing 3 to 4 is |3 - 4| which is 1, and the cost of changing 5 to 4 is |5 - 4| which is 1, so the total cost is 1 + 1 = 2. The value 2 is the minimum cost to make all values in the array equal. Hence, the answer is 2.

Problem approach

Approach :

1) We will initialize the variable lowerLimit and upperLimit with the minimum and maximum value present in the array.

2) Iterate while upperLimit - lowerLimit is more than 2.
2.1) Set the variables mid1 with lowerLimit + (upperLimit - lowerLimit)/3 and mid2 with upperLimit - (upperLimit - lowerLimit)/3.

2.2) Initialize the variable cost1 with the cost of converting all array elements to mid1. You have to iterate the complete array to calculate cost1.

2.3) Similarly, find cost2 by keeping mid2 as the target value of all elements in the array.

2.4) If cost1 is less than cost2 then set upperLimit as mid2; otherwise, set lowerLimit as mid1.

3) Set target as (lowerLimit + upperLimit)/2 and cost as 0. The variable cost stores the minimum cost to convert all elements present in the array to target.

4) Iterate index from 0 to N-1.
4.1) Increment cost by an absolute difference of ARR[index] and target.

5) Return the variable cost.

TC : O(N * log(Max(ARR) - Min(ARR))) where N = size of the array.
SC : O(1)

Try solving now

2. Pattern Matching

Moderate

15m average time

85% success

0/80

Asked in companies

You are given a pattern in the form of a string and a collection of words. Your task is to determine if the pattern string and the collection of words have the same order.

Note :

The strings are non-empty.

The strings only contain lowercase English letters.

Problem approach

Approach :

1) Create two HashMaps, charToString and alreadyMatched. The map, charToString maps characters in the pattern to the strings in the “words” array. The map, alreadyMatchedstates whether a string is previously matched to any other character.

2) If pattern.size() != words.size(), return False.

3) Run a loop from i=0 to pattern.size() and do:
3.1) If (charToString[pattern[i]] == “”):
3.2) If alreadyMatched[words[i]] == true, return false.
3.3) Make charToString[pattern[i]] = words[i].
3.4) Make alreadyMatched[words[i]] = true.
3.5) Else: If charToString[pattern[i]] != words[i], return False.

4) Finally, as there is no mismatch we can return True.

TC : O(N), where N = size of the string pattern.
SC : O(M), where M is the number of unique words in the “words” array.

Try solving now

Round

Medium

Video Call

Duration50 Minutes

Interview date19 Aug 2021

Coding problem2

This round had 2 algorithmic questions in which I first had to explain my approach with proper complexity analysis and then code the solution in any preferred IDE.

1. Pair Sum

Easy

15m average time

90% success

0/40

Asked in companies

You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to return the list of all pairs of elements such that each sum of elements of each pair equals 'S'.

Note:

Each pair should be sorted i.e the first value should be less than or equals to the second value. 

Return the list of pairs sorted in non-decreasing order of their first value. In case if two pairs have the same first value, the pair with a smaller second value should come first.

Problem approach

Approach :

1) Initialize a list to store our results.

2) For each element in the array ‘ARR[i]’, we will check whether there exists an element equals to ('S' - ‘ARR[i]’) already in the map.

3) If it exists we will add the pair('ARR[i]', ‘S’ - ‘ARR[i]’ ) ‘COUNT’ number of times to the list, where ‘COUNT’ represents the frequency of ('S' - ‘ARR[i]’) in the map.

4) Also, we will increment the frequency of the current element ('ARR[i]') in the map. Sort the list of pairs as per the given output format and return this list.

TC : O(N^2), where N = size of the array
SC : O(N)

Try solving now

2. Merge overlapping intervals

Easy

10m average time

90% success

0/40

Asked in companies

Given 'N' number of intervals, where each interval contains two integers denoting the boundaries of the interval. The task is to merge all the overlapping intervals and return the list of merged intervals sorted in ascending order.

Two intervals will be considered to be overlapping if the starting integer of one interval is less than or equal to the finishing integer of another interval, and greater than or equal to the starting integer of that interval.

Example:

for the given 5 intervals - [1,4], [3,5], [6,8], [10,12], [8,9].
Since intervals [1,4] and [3,5] overlap with each other, we will merge them into a single interval as [1,5].

Similarly [6,8] and [8,9] overlaps, we merge them into [6,9].

Interval [10,12] does not overlap with any interval.

Final List after merging overlapping intervals: [1,5], [6,9], [10,12]

Problem approach

Approach :

1) We will first sort the intervals by non-decreasing order of their start integers.

2) We will create a 2D vector “RES” which will be our resultant vector storing all the merged intervals. Now, we will add the first interval to our resultant list.

3) Now, we will run a loop for the total number of intervals and for each interval, we will check whether the current interval is overlapping with the last interval in our resultant list or not.

4) If it overlaps with the last interval, we will update the end integer of the last interval in the list by the maximum of the end integers of both overlapping intervals.

5) If it doesn't overlap, we will add the current interval to the “RES” vector.

6) Finally, we will return our resultant vector “RES” as our final answer.

TC : O(N*log(N)), where N = number of intervals.
SC : O(1)

Try solving now

Round

Medium

Video Call

Duration60 Minutes

Interview date19 Aug 2021

Coding problem4

This round had 1 standard coding question followed by some questions from OS and at last I was also asked some questions related to Statistics and Probability.

1. Spiral Matrix

Easy

0/40

Asked in companies

You are given a N x M matrix of integers, return the spiral path of the matrix

Example Of Spiral Path

Problem approach

Approach :

spiralPrint(matrix[][], R, C, rows, cols):

1) Check for base cases, i.e. if outside the boundary of the matrix then return.
2) Print the first row from left to right of the matrix i.e from column ‘C’ to ‘cols’, print the elements of the Rth row.
3) Print the last column from top to bottom of the matrix i.e from row ‘R’ to ‘rows’, print the elements of the (cols)th column.
4) Print the last row from right to left of the matrix i.e from column ‘cols’ to ‘C’, print the elements of the (rows)th row.
5) Print the first column from bottom to top of the matrix i.e from row ‘rows’ to ‘R’, print the elements of the Cth column.
6) Call the function recursively with the updated values of boundaries, spiralPrint(matrix, R + 1, C + 1, rows - 1, cols - 1).

TC : O(N*M) , where N = number of rows and M = number of columns of the matrix.
SC : O(max(N,M))

Try solving now

2. OS Question

Print 1 to 100 using more than two threads(optimized approach).

Problem approach

Prerequisite to solve this problem : Multithreading

The idea is to create two threads and print even numbers with one thread and odd numbers with another thread.
Below are the steps:

1) Create two threads T1 and T2 , where T1 and T2 are used to print odd and even numbers respectively.
2) Maintain a global counter variable and start both threads.
3) If the counter is even in the Thread T1, then wait for the thread T2 to print that even number. Otherwise, print that
odd number, increment the counter and notify to the Thread T2 .
4)If the counter is odd in the Thread T2, then wait for the thread T1 to print that even number. Otherwise, print that
even number, increment the counter and notify the Thread T1.

3. OS Question

What is meant by Multitasking and Multithreading in OS?

Problem approach

Multitasking : It refers to the process in which a CPU happens to execute multiple tasks at any given time. CPU
switching occurs very often when multitasking between various tasks. This way, the users get to collaborate with
every program together at the same time. Since it involves rapid CPU switching, it requires some time. It is because
switching from one user to another might need some resources. The processes in multi-tasking, unlike multi-
threading, share separate resources and memories.

Multithreading : It is a system that creates many threads out of a single process to increase the overall power and
working capacity of a computer. In the process of multi-threading, we use a CPU for executing many threads out of a
single process at any given time. Also, the process of creation depends entirely on the cost. The process of
multithreading, unlike multitasking, makes use of the very same resources and memory for processing the execution.

4. Aptitude Question

15 people sit around a circular table. What are odds against two particular people sitting together?

Problem approach

15 people can sit around a circular table total in (14!) no. of ways . Out of these total ways only those ways favors for the happening of the required event in which the two particular persons sit together , which can be done in

(13! ×2!) no. of ways . Hence the required probability = 13! × 2!/(14!) = 2/14 = 1/7 .

So odds in favor 1 : 6 and odds against 6 : 1 .

Round

Easy

HR Round

Duration30 Minutes

Interview date19 Aug 2021

Coding problem2

This is a cultural fitment testing round .HR was very frank and asked standard questions. Then we discussed about my role.

1. Basic HR Question

Do you know anything about the company ?

Problem approach

General Tip : Before an interview for any company , have a breif insight about the company , what it does , when was
it founded and so on . All these info can be easily acquired from the Company Website itself .

2. Basic HR Question

Why should we hire you ?

Problem approach

Tip 1 : The cross questioning can go intense some time, think before you speak.

Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.

Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round,
like what are the projects currently the company is investing, which team you are mentoring. How all is the work
environment etc.

Tip 4 : Since everybody in the interview panel is from tech background, here too you can expect some technical
questions. No coding in most of the cases but some discussions over the design can surely happen.