Specialist Programmer Infosys interview experience | Sohil Khattar

Interview rounds

Round

Medium

Online Coding Test

Duration180 Minutes

Interview date10 Mar 2022

Coding problem3

It was a subjective Coding round with 3 DSA questions to be solved in 180 mins time. 2 Sample test cases were given to test the code before submitting and 10-12 hidden test cases were there.There was partial marking also if a candidate is able to pass 3-4 test cases rather than all.

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

So we basically use the Kadane's algorithm to solve this problem.
Step 1: Make two variables max_ending_here min_ending_here, max_so_far
Step 2: Make the following Calculations for each element in the array

maxhere = Math.max(Math.max(maxherepre * A[i], minherepre * A[i]), A[i]);
minhere = Math.min(Math.min(maxherepre * A[i], minherepre * A[i]), A[i]);
maxsofar = Math.max(maxhere, maxsofar);
maxherepre = maxhere;
minherepre = minhere;

Step 3: return max_so_far

Try solving now

2. Gas Stations

Moderate

10m average time

90% success

0/80

Asked in companies

You have been given a circular path. There are 'N' petrol pumps on this path that are numbered from 0 to N - 1 (Both inclusive). Each petrol pump has two values associated with it:

1)The amount of petrol that is available at this particular petrol pump.
2)The distance to reach the next petrol pump.

You are on a truck having an empty tank of infinite capacity. You can start the tour from any of the petrol pumps. Your task is to calculate the first petrol pump from where the truck will be able to complete the full circle or determine if it is impossible to do so.

You may assume that the truck will stop at every petrol pump and it will add the petrol from that pump to its tank. The truck will move one kilometre for each litre of petrol consumed.

Problem approach

The basic idea is every time we start from a station, we go as far as possible by increasing the end until the remaining gas is less than 0. If 'end' finally hits start we know we can travel around from 'start'. If we haven't traveled around, we know we cannot start from this station. Then we check the station before our start station if we can start from this station. Repeat until we have checked all stations.

Note there is a little trick that every time we try to find the next start station, we always go back to extend the distance from start to end so that we can check all stations on the circuit. Otherwise, if we move start forward to decrease the distance from start to end, we are likely to end up only checking part of the circuit. Another trick is we start from the end of the array so as to avoid some corner cases.

Try solving now

3. Longest Substring Without Repeating Characters

Moderate

30m average time

65% success

0/80

Asked in companies

Given a string input of length n, find the length of the longest substring without repeating characters i.e return a substring that does not have any repeating characters.

Substring is the continuous sub-part of the string formed by removing zero or more characters from both ends.

Problem approach

the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.

Try solving now

Round

Medium

Face to Face

Duration60 minutes

Interview date18 May 2022

Coding problem1

I was a face to face interview with a specialist programmer in Infosys. 1 DSA question was asked and a detailed discussion on my resume, skills, projects and previous internships was there.

1. Rotting Oranges

Moderate

20m average time

78% success

0/80

Asked in companies

You have been given a grid containing some oranges. Each cell of this grid has one of the three integers values:

Value 0 - representing an empty cell.

Value 1 - representing a fresh orange.

Value 2 - representing a rotten orange.

Every second, any fresh orange that is adjacent(4-directionally) to a rotten orange becomes rotten.

Your task is to find out the minimum time after which no cell has a fresh orange. If it's impossible to rot all the fresh oranges then print -1.

Note:

1. The grid has 0-based indexing.
2. A rotten orange can affect the adjacent oranges 4 directionally i.e. Up, Down, Left, Right.

Problem approach

So this a multi-source BFS problem where we need to apply the BFS algorithm.

First, count fresh oranges. Then, until fresh is non-zero, perform BFS to rot oranges, decreasing fresh. Count days (d) and return it in the end. If, after another day, fresh does not change, return -1.

For BFS, we can use the day counter (d + 2) to only process oranges that rotted yesterday.

Try solving now

Specialist Programmer

Interview preparation journey

Interview rounds

1. Maximum Product Subarray

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.

For Example:

Follow Up:

2. Gas Stations

You have been given a circular path. There are 'N' petrol pumps on this path that are numbered from 0 to N - 1 (Both inclusive). Each petrol pump has two values associated with it:

You are on a truck having an empty tank of infinite capacity. You can start the tour from any of the petrol pumps. Your task is to calculate the first petrol pump from where the truck will be able to complete the full circle or determine if it is impossible to do so.

You may assume that the truck will stop at every petrol pump and it will add the petrol from that pump to its tank. The truck will move one kilometre for each litre of petrol consumed.

3. Longest Substring Without Repeating Characters

Given a string input of length n, find the length of the longest substring without repeating characters i.e return a substring that does not have any repeating characters.

Substring is the continuous sub-part of the string formed by removing zero or more characters from both ends.

1. Rotting Oranges

You have been given a grid containing some oranges. Each cell of this grid has one of the three integers values:

Value 0 - representing an empty cell.

Value 1 - representing a fresh orange.

Value 2 - representing a rotten orange.

Every second, any fresh orange that is adjacent(4-directionally) to a rotten orange becomes rotten.

Your task is to find out the minimum time after which no cell has a fresh orange. If it's impossible to rot all the fresh oranges then print -1.

Note: