SDE - 1 Infosys interview experience | Parag Kumar

Interview rounds

Round

Hard

Online Coding Test

Duration180 minutes

Interview date17 Mar 2022

Coding problem3

In this round, we had 3 questions to solve under 3 hours. I found the first two questions to be of medium level and the last one to be a bit on the harder side

1. Maximize the sum

Moderate

15m average time

85% success

0/80

Asked in companies

You are given two sorted arrays of distinct integers, ‘ARR1’ and ‘ARR2’. If you find a common element in both arrays, you can switch from one array to another.

Your task is to find a path through the intersections i.e common integers of ‘ARR1’ and ‘ARR2’, that produces maximum sum and return that maximum sum as the answer.

For example:

Let ‘ARR1’ = [1, 5, 10, 15, 20]  and ‘ARR2’ = [2, 4, 5, 9, 15]
In this example, common points are 5, 15.

First, we start with ARR2 and take the sum till 5 (i.e. sum = 11). Then we will switch to ‘ARR1’ at element 10 and take the sum till 15. So sum = 36. Now no element is left in ‘ARR2’ after 15, so we will continue in array 1. Hence sum is 56. And the path is 2 -> 4 -> 5 -> 10 -> 15 -> 20.

Problem approach

Create some variables, result, sum1, sum2. Initialize result as 0. Also initialize two variables sum1 and sum2 as 0. Here sum1 and sum2 are used to store sum of element in ar1[] and ar2[] respectively. These sums are between two common points.
Now run a loop to traverse elements of both arrays. While traversing compare current elements of array 1 and array 2 in the following order.
If current element of array 1 is smaller than current element of array 2, then update sum1, else if current element of array 2 is smaller, then update sum2.
If the current element of array 1 and array 2are same, then take the maximum of sum1 and sum2 and add it to the result. Also add the common element to the result.
This step can be compared to the merging of two sorted arrays, If the smallest element of the two current array indices is processed then it is guaranteed that if there is any common element it will be processed together. So the sum of elements between two common elements can be processed.

Try solving now

2. Longest Alternating Subsequence

Moderate

15m average time

85% success

0/80

Asked in companies

You are given an array ‘ARR’ of integers. Your task is to find the length of the longest alternating subsequence.

Note:

A sequence a1, a2, .... an is called an alternating sequence if its elements satisfy one of the following relations : a1 < a2 > a3 < a4 > a5..... or  a1 > a2 < a3 > a4 < a5.

For example:

'ARR' = {3, 10, 1, 2, 30}, the longest alternating subsequence for this array can be {3, 10, 1, 30} or {3, 10, 2, 30}. Therefore, the answer will be 4.

Problem approach

At any moment we are keeping track of two values (Length of the longest alternating subsequence ending at index i, and last element is smaller than or greater than previous element), for every element on array. To optimise space, we only need to store two variables for element at any index i.

inc = Length of longest alternative subsequence so far with current value being greater than it's previous value.
dec = Length of longest alternative subsequence so far with current value being smaller than it's previous value.
The tricky part of this approach is to update these two values.

"inc" should be increased, if and only if the last element in the alternative sequence was smaller than it's previous element.
"dec" should be increased, if and only if the last element in the alternative sequence was greater than it's previous element.

Try solving now

3. Ways To Make Coin Change

Moderate

20m average time

80% success

0/80

Asked in companies

You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change for value V using coins of denominations from D. Print 0, if a change isn't possible.

Problem approach

See, here each coin of a given denomination can come an infinite number of times. (Repetition allowed), this is what we call UNBOUNDED KNAPSACK. We have 2 choices for a coin of a particular denomination, either i) to include, or ii) to exclude. But here, the inclusion process is not for just once; we can include any denomination any number of times until N<0.
Basically, If we are at s[m-1], we can take as many instances of that coin ( unbounded inclusion ) i.e count(S, m, n - S[m-1] ) ; then we move to s[m-2]. After moving to s[m-2], we can't move back and can't make choices for s[m-1] i.e count(S, m-1, n ).
Finally, as we have to find the total number of ways, so we will add these 2 possible choices, i.e count(S, m, n - S[m-1] ) + count(S, m-1, n ) ; which will be our required answer.

Try solving now

Round

Medium

Face to Face

Duration50 minutes

Interview date4 Apr 2022

Coding problem2

In this round, I was asked some questions related to Data structures and DBMS. Some output based questions were also asked and 2 coding problems were given to solve.

1. Partition Equal Subset Sum

Moderate

25m average time

65% success

0/80

Asked in companies

You are given an array 'ARR' of 'N' positive integers. Your task is to find if we can partition the given array into two subsets such that the sum of elements in both subsets is equal.

For example, let’s say the given array is [2, 3, 3, 3, 4, 5], then the array can be partitioned as [2, 3, 5], and [3, 3, 4] with equal sum 10.

Follow Up:

Can you solve this using not more than O(S) extra space, where S is the sum of all elements of the given array?

Problem approach

The key point to notice here is that we have to partition an array into two equal subsets sum so two equal subsets must have the sum equal to 'TOTALSUM'/2, where 'TOTALSUM' represents the sum of all elements in the given array, and also 'TOTALSUM' should be even as we cant partitioned an array into two equal if 'TOTALSUM' is odd.
So now the problem is to check if there is any subset in a given array with sum 'TOTALSUM'/2.
And now this problem is similar to the classical 0/1 Knapsack Problem in which in the recursion call at any index, we have two choices whether to include that element in sum or exclude that element.
Now if we choose the current number to add to the sum then recur for index 'I'+1 or If we don’t choose the current index element to sum then recur for index 'I'+1 and this way we check if there is a subset with sum 'TOTALSUM'/2 in the given array.

Try solving now

2. Two Stacks

Moderate

15m average time

85% success

0/80

Asked in companies

Design a data structure, which represents two stacks using only one array common for both stacks. The data structure should support the following operations:

push1(NUM) - Push ‘NUM’ into stack1.
push2(NUM) - Push ‘NUM’ into stack2.
pop1() - Pop out a top element from stack1 and return popped element, in case of underflow return -1.
pop2() - Pop out a top element from stack2 and return popped element, in case of underflow return -1.

There are 2 types of queries in the input

Type 1 - These queries correspond to Push operation.
Type 2 - These queries correspond to Pop operation.

Note:

1. You are given the size of the array.

2. You need to perform push and pop operations in such a way that we are able to push elements in the stack until there is some empty space available in the array.

3. While performing Push operations, do nothing in the situation of the overflow of the stack.

Problem approach

I was not able to solve this question but the approach is given below.

A simple way to implement two stacks is to divide the array in two halves and assign the half space to two stacks, i.e., use arr[0] to arr[n/2] for stack1, and arr[(n/2) + 1] to arr[n-1] for stack2 where arr[] is the array to be used to implement two stacks and size of array be n.
The problem with this method is inefficient use of array space. A stack push operation may result in stack overflow even if there is space available in arr[]. For example, say the array size is 6 and we push 3 elements to stack1 and do not push anything to second stack2. When we push 4th element to stack1, there will be overflow even if we have space for 3 more elements in array.

Try solving now