SDE - 1 Algogenix Pvt Ltd interview experience

Interview rounds

Round

Medium

Online Coding Interview

Duration40 minutes

Interview date28 Mar 2023

Coding problem9

In this round aptitude and DSA based questions were asked and 2 coding questions were asked

1. Balanced parentheses

Moderate

10m average time

90% success

0/80

Asked in companies

Given an integer ‘N’ representing the number of pairs of parentheses, Find all the possible combinations of balanced parentheses with the given number of pairs of parentheses.

Note :

Conditions for valid parentheses:
1. All open brackets must be closed by the closing brackets.

2. Open brackets must be closed in the correct order.

For Example :

()()()() is a valid parentheses.
)()()( is not a valid parentheses.

Problem approach

The idea is to put all the opening brackets in the stack. Whenever you hit a closing bracket, search if the top of the stack is the opening bracket of the same nature. If this holds then pop the stack and continue the iteration, in the end if the stack is empty, it means all brackets are well-formed . Otherwise, they are not balanced.

Try solving now

2. Rotate array

Easy

25m average time

80% success

0/40

Asked in companies

Given an array 'arr' with 'n' elements, the task is to rotate the array to the left by 'k' steps, where 'k' is non-negative.

Example:

'arr '= [1,2,3,4,5]
'k' = 1  rotated array = [2,3,4,5,1]
'k' = 2  rotated array = [3,4,5,1,2]
'k' = 3  rotated array = [4,5,1,2,3] and so on.

Problem approach

At each iteration, shift the elements by one position to the left circularly (i.e., first element becomes the last).
Perform this operation d times to rotate the elements to the left by d position.

Try solving now

3. Puzzle

From a point P on a level ground, the angle of elevation of the top tower is 30°. If the tower is 100 m high, the distance of point P from the foot of the tower is:

Problem approach

Let AB be the tower.

Then, APB = 30° and AB = 100 m.

AB = tan 30°
AP = (AB x 3) m
= 1003 m
= (100 x 1.73) m
= 173 m.

4. Puzzle

In one hour, a boat goes 11 km/hr along the stream and 5 km/hr against the stream. The speed of the boat in still water (in km/hr) is:

Problem approach

Speed in still water = 1/2(11 + 5) kmph = 8 kmph.

5. Puzzle

Two pipes A and B can fill a cistern in 37 minutes and 45 minutes respectively. Both pipes are opened. The cistern will be filled in just half an hour, if the B is turned off after:

6. Puzzle

A car travelling with of its actual speed covers 42 km in 1 hr 40 min 48 sec. Find the actual speed of the car.

7. Technical Question

What is the time complexity of the following code snippet in C++?

void solve() {
string s = "scaler";
int n = s.size();
for(int i = 0; i < n; i++) {
s = s + s[i];
}
cout << s << endl;
}

Problem approach

The s = s + s[i] line first makes a copy of the original string and then appends the new character in it, leading to each operation being O(n). So the total time complexity is O(n^2).

8. Output Question

What will be the output of the following code snippet?

void solve() {
string s = "00000001111111";
int l = 0, r = s.size() - 1, ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(s[mid] == '1') {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ans << endl;
}

Problem approach

This code snippet shows one of the many applications of binary search. Here, we are binary searching for the index of the first occurrence of the character ‘1’ in the given string. When we get the character ‘1’ at the mid index, we store it as the answer and move to the left half which will have the first index of ‘1’ if it occurs. Else we move to the right half. So, the answer will be 7 (0-based indexing).

9. Output Question

void solve() {
string s = "00000001111111";
int l = 0, r = s.size() - 1, ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(s[mid] == '1') {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ans << endl;
}

Problem approach

Round

Medium

Online Coding Test

Duration50 minutes

Interview date28 Mar 2023

Coding problem3

This round consists pf 3 questions of easy to medium level

1. Rearrange The Array

Moderate

15m average time

90% success

0/80

Asked in companies

You are given an array/list 'NUM' of integers. You are supposed to rearrange the elements of the given 'NUM' so that after rearranging the given array/list there are no two adjacent elements present in the rearranged 'NUM' which will be the same.

For example:

Input: NUM[] = {1,1,1,2,2,2} 
Output: {1,2,1,2,1,2}
Note: {2,1,2,1,2,1} is also valid because there are no two adjacent which are the same.

Problem approach

The idea is to use an auxiliary array. We maintain two pointers one to the leftmost or smallest element and the other to the rightmost or largest element. We move both pointers toward each other and alternatively copy elements at these pointers to an auxiliary array. Finally, we copy the auxiliary array back to the original array.

Try solving now

2. Return Subsets Sum to K

Moderate

40m average time

75% success

0/80

Asked in companies

Given an integer array 'ARR' of size 'N' and an integer 'K', return all the subsets of 'ARR' which sum to 'K'.

Subset of an array 'ARR' is a tuple that can be obtained from 'ARR' by removing some (possibly all) elements of 'ARR'.

Note :

The order of subsets is not important. 

The order of elements in a particular subset should be in increasing order of the index.

Problem approach

A simple approach is to solve this problem by generating all the possible subsets and then checking whether the subset has the required sum

Try solving now

3. Boxes Of Chocolates

Moderate

20m average time

86% success

0/80

Asked in companies

This is the time when Dr. Stephen wants to distribute chocolates. He has N number of boxes in a row, and each box contains some chocolates. Now, He wants to distribute chocolates to K children keeping in mind that distribution should be as fair as possible. To fairly distribute the gift boxes, he decided to give the maximum number of chocolates equally to K children.

Formally, There are N boxes with a different number of chocolates in them. The task is to divide the chocolates equally among K children where you can only choose consecutive boxes(subarray) to distribute chocolates. You need to print the maximum number of chocolates each child can get.

For Example: for the given boxes of chocolates [3,2,2,5,4,1] and 5 students.

Output: 2 

If there is no restriction on choosing the boxes then the maximum number of chocolates the 5 students equally can have is 3 by picking all boxes except the box at index 2(0-based indexing). So total candies will be 3+2+5+4+1 = 15 and each of the 5 students will get 15/5=3 candies. 

But we are allowed to choose only consecutive boxes. So if we choose boxes [0,1] then 3+2=5 then each student will have only 1 chocolate and when we choose boxes[4,6] as 5+4+1=10 then each student will have 2 chocolates. So the maximum number of chocolates each student can get is 2.

Problem approach

The idea is based on the observation that to minimize the difference, we must choose consecutive elements from a sorted packet. We first sort the array arr[0..n-1], then find the subarray of size m with the minimum difference between the last and first elements.

Try solving now

Round

Medium

Face to Face

Duration45 minutes

Interview date28 Mar 2023

Coding problem4

This is a technical round. Interviewer asks me 2 coding questions approach and starts rapid fire DSA questions. I was not selected after this round

1. Check Permutation

Easy

15m average time

85% success

0/40

Asked in companies

You have been given two strings 'STR1' and 'STR2'. You have to check whether the two strings are anagram to each other or not.

Note:

Two strings are said to be anagram if they contain the same characters, irrespective of the order of the characters.

Example :

If 'STR1' = “listen” and 'STR2' = “silent” then the output will be 1.

Both the strings contain the same set of characters.

Problem approach

Sort the two given strings and compare, if they are equal then they are anagram of each other.

Try solving now

2. 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

The Idea to Solve this Problem is by using the Bottom Up(Tabulation). By using the linear array for space optimization.

Follow the below steps to Implement the idea:

Initialize with a linear array table with values equal to 0.
With sum = 0, there is a way.
Update the level wise number of ways of coin till the ith coin.
Solve till j <= sum

Try solving now