SDE - 1 Practo interview experience | vidya gupta

Interview rounds

Round

Medium

Online Coding Test

Duration90 minutes

Interview date7 Mar 2022

Coding problem3

There was an hackerrank test whose link I got 1 day prior to test.

1. Make all elements of the array distinct.

Moderate

30m average time

70% success

0/80

Asked in companies

You have been given an array/list ‘ARR’ of integers consisting of ‘N’ integers. In one operation you can increase an element by 1. Your task is to return the minimum number of operations to make the array distinct.

Example:

Let’s say you have an array/list [1,4,4,5]. We can increase the third element by 1 and the fourth element by 1. Finally, our array will look like [1,4,5,6] where all elements are distinct. Therefore the minimum number of operations is 2.

Problem approach

Create an array of size N and fill it with first N numbers. So total sum of the array will be smallest possible sum.
Find the largest element of the array, but as the array is sorted so array[N] will be largest.
If the largest element is less than K, we replace it with K and check the new sum of the array.
If it is less than given SUM, we move to N-1 position in the array because array[N] can’t be further incremented and to maintain uniqueness we decrease K by 1.
If it is greater than given SUM, we replace an element such that sum will be given SUM, and will come out of loop.
If the largest element is equal to K, we move to N-1 position in the array because array[N] can’t be further incremented and to maintain uniqueness we will decrease K by 1.l

Try solving now

2. Rearrange Array

Easy

15m average time

85% success

0/40

Asked in companies

You're given an array ARR[] of size N, where every element belongs to the range 0 to N-1. Your task is to rearrange the given array so that ARR[i] becomes ARR[ARR[i]] and make sure that this task is done with O(1) extra space.

Problem approach

Traverse the array from start to end.
For every index increment the element by array[array[index] ] % n. To get the ith element find the modulo with n, i.e array[index]%n.
Again Traverse the array from start to end
Print the ith element after dividing the ith element by n, i.e. array[i]/n.

Try solving now

3. Reconstruct Itinerary

Moderate

15m average time

85% success

0/80

Asked in companies

You are given a matrix of flight 'TICKETS', where the 'i'th row represents 'i’th flight ticket. 'TICKETS'[i] = [SOURCE, DESTINATION] represents that there is a one-way flight starting from the city 'SOURCE' and ending at city 'DESTINATION'. All the flight tickets belong to a man who is initially in city "DEL".

You are supposed to reconstruct the journey satisfying the following conditions:

1. He should begin his journey from “DEL”.

2. He should use all the tickets and complete the journey.

3. He must use all the tickets only once.

Note:

1. Journey means the order in which the cities will be visited.

2. The given tickets have at least one itinerary.

3. If multiple valid itineraries are possible, then return the itinerary that is a lexicographically smallest itinerary.

Problem approach

The idea is DFS backtracking and we greedily pick the smallest lexical order possible first when we iterate over all our paths. In this case local optimum leads to global optimum. If we try airports with smallest lexical order first then we always find the desired solution first.

Try solving now

Round

Easy

Video Call

Duration30 minutes

Interview date10 Mar 2022

Coding problem2

This round was conducted on Google meet and was a coding round. He asked 2 problems.

1. String Palindrome

Easy

0/40

Asked in companies

Given a string, determine if it is a palindrome, considering only alphanumeric characters.

Palindrome

A palindrome is a word, number, phrase, or other sequences of characters which read the same backwards and forwards.

Example:

If the input string happens to be, "malayalam" then as we see that this word can be read the same as forward and backwards, it is said to be a valid palindrome.

The expected output for this example will print, 'true'.

From that being said, you are required to return a boolean value from the function that has been asked to implement.

Problem approach

We will take two pointers i pointing to the start of the string and j pointing to the end of the string.
Keep incrementing i and decrementing j while i < j and at every step
Check whether the characters at these pointers are the same or not. We are doing this through recursion – (i+1, j-1
If all the characters are the same on the ith and jth index till i>=j condition satisfies, print true else false

Try solving now

2. Minimum insertions to make a string palindrome

Moderate

30m average time

70% success

0/80

Asked in companies

A palindrome string is one that reads the same backward as well as forward.

You are given a string 'str'.

Find the minimum number of characters needed to insert in 'str' to make it a palindromic string.

Example :

Input: 'str' = "abca"

Output: 1

Explanation:
If we insert the character ‘b’ after ‘c’, we get the string "abcba", which is a palindromic string. Please note that there are also other ways possible.

Problem approach

Every time we will be moving diagonally up, from left corner we will get number of removals to get the same substring backwards. Thing to notice here is that it is like having on string two pointers, one moving from beginning and other from end. Very important spot is that strings do not necessary has to have even number of characters, so this is the reason we also has to check upper and lower values in dp[][].

Try solving now

Round

Easy

Video Call

Duration30 minutes

Interview date10 Mar 2022

Coding problem1

This round was also taken on Google meet and was taken by a senior engineer who asked about my projects in depth followed by 1 DSA problem

1. Maximum In Sliding Windows Of Size K

Moderate

20m average time

80% success

0/80

Asked in companies

Given an array/list of integers of length ‘N’, there is a sliding window of size ‘K’ which moves from the beginning of the array, to the very end. You can only see the ‘K’ numbers in a particular window at a time. For each of the 'N'-'K'+1 different windows thus formed, you are supposed to return the maximum element in each of them, from the given array/list.

Problem approach

Create a deque to store K elements.
Run a loop and insert the first K elements in the deque. Before inserting the element, check if the element at the back of the queue is smaller than the current element, if it is so remove the element from the back of the deque until all elements left in the deque are greater than the current element. Then insert the current element, at the back of the deque.
Now, run a loop from K to the end of the array.
Print the front element of the deque.
Remove the element from the front of the queue if they are out of the current window.
Insert the next element in the deque. Before inserting the element, check if the element at the back of the queue is smaller than the current element, if it is so remove the element from the back of the deque until all elements left in the deque are greater than the current element. Then insert the current element, at the back of the deque.
Print the maximum element of the last window.

Try solving now