Interview Experience | On Campus - Feb 2024

Interview rounds

Round

Medium

Online Coding Test

Duration90 minutes

Interview date2 Feb 2022

Coding problem3

1. Equilibrium Index

Easy

0/40

Asked in companies

You are given an array Arr consisting of N integers. You need to find the equilibrium index of the array.

An index is considered as an equilibrium index if the sum of elements of the array to the left of that index is equal to the sum of elements to the right of it.

Note:

1. The array follows 0-based indexing, so you need to return the 0-based index of the element.
2. Note that the element at the equilibrium index won’t be considered for either left sum or right sum.
3. If there are multiple indices which satisfy the given condition, then return the left-most index i.e if there are indices i,j,k…. which are equilibrium indices, return the minimum among them
4. If no such index is present in the array, return -1.

Problem approach

Brute force approach - The fundamental approach involves using nested loops.

Outer Loop: Iterate through each element of the array, treating it as the "Pivot" element.
Inner Loop: For each Pivot element, check if it is an equilibrium index by comparing the sum of elements to its left with the sum of elements to its right.

Try solving now

2. Equalizing Block Lengths in Strings with Minimum Letter Additions

You are given a string S consisting of letters 'a' and/or 'b'. A block is a consecutive fragment of S composed of the same letters and surrounded by different letters or string endings. For example, S = "abbabbaaa" has five blocks: "a", "bb", "a", "bb" and "aaa".

What is the minimum number of additional letters needed to obtain a string?

containing blocks of equal lengths? Letters can be added only at the

beginning or at the end of an existing block.

Problem approach

Traverse the String: Identify and count the lengths of contiguous blocks of the same character.

Calculate Maximum Block Length: Find the length of the longest block from the previously identified blocks.

Compute Additional Letters:

For each block, calculate the difference between the maximum length and the block’s length.
Sum these differences to get the total number of additional letters required.

3. Frog - river

A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river. You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds. The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall into the river.

Problem approach

Track Covered Positions: Use a boolean array or a set to keep track of which positions (from 1 to X) have been covered by falling leaves.

Iterate Through the Array: Traverse the array of falling leaves and update the tracking structure to mark the covered positions.

Check for Complete Coverage: As you process each leaf, check if all required positions (1 to X) have been covered.

Return the Earliest Time: The first time you encounter a moment when all positions from 1 to X are covered is the earliest time when the frog can jump to the other side.

Round

Medium

Video Call

Duration90 minutes

Interview date4 Feb 2022

Coding problem2

1. Target Sum

Moderate

0/80

Asked in companies

You are given an array ‘ARR’ of ‘N’ integers and a target number, ‘TARGET’. Your task is to build an expression out of an array by adding one of the symbols '+' and '-' before each integer in an array, and then by concatenating all the integers, you want to achieve a target. You have to return the number of ways the target can be achieved.

For Example :

You are given the array ‘ARR’ = [1, 1, 1, 1, 1], ‘TARGET’ = 3. The number of ways this target can be achieved is:
1. -1 + 1 + 1 + 1 + 1 = 3
2. +1 - 1 + 1 + 1 + 1 = 3
3. +1 + 1 - 1 + 1 + 1 = 3
4. +1 + 1 + 1 - 1 + 1 = 3
5. +1 + 1 + 1 + 1 - 1 = 3
These are the 5 ways to make. Hence the answer is 5.

Problem approach

The brute force approach relies on recursion, where we explore placing both + and - signs at each position in the given `nums` array to find the combinations that result in the target sum S.

I used a recursive function `calculate(nums, i, sum, S)` to determine the number of valid assignments. This function starts from the ith index, with the current sum up to that point being `sum`. It adds both a + and a - sign to the element at the current index, then recursively calls itself with the updated sum as `sum + nums[i]` and `sum - nums[i]`, and the updated index as `i + 1`. When the end of the array is reached, the resulting sum is compared with S, and if they match, the count is incremented.

Finally, the call to `calculate(nums, 0, 0, S)` returns the total number of assignments that achieve the desired sum.

Try solving now

2. Find a value in BST

Easy

15m average time

85% success

0/40

Asked in companies

You have been given a Binary Search Tree and a key value ‘X’, find if a node with value ‘X’ is present in the BST or not.

Note:

You may assume that duplicates do not exist in the tree.

For example :

For the given tree shown below:

For the binary tree shown in the figure, if ‘X’ = 6, the output will be 1 as node value 6 is present in the BST.

Problem approach

To find a given element in a Binary Search Tree (BST) without using recursion, start by initializing the current node with the root of the BST. Then, enter a loop that continues until the current node becomes null. Within the loop, check if the current node's value matches the target value; if it does, return the current node (or True if you're only checking for existence). If the target value is less than the current node's value, move to the left child; if it's greater, move to the right child. If you reach a null node, the element is not in the tree. If the loop ends without finding the target, return null (or False if only checking for existence).

Try solving now

Round

Medium

Video Call

Duration60 minutes

Interview date9 Feb 2022

Coding problem4

1. Next Greater Element

Moderate

20m average time

90% success

0/80

Asked in companies

You are given an array arr of length N. You have to return a list of integers containing the NGE(next greater element) of each element of the given array. The NGE for an element X is the first greater element on the right side of X in the array. Elements for which no greater element exists, consider the NGE as -1.

For Example :

If the given array is [1, 3, 2], then you need to return [3, -1, -1]. Because for 1, 3 is the next greater element, for 3 it does not have any greater number to its right, and similarly for 2.

Problem approach

Understand the Problem:
You are given two arrays, nums1 and nums2. All elements in nums1 are present in nums2, and the order in nums2 matters.
The goal is to find, for each element in nums1, the first element to its right in nums2 that is larger.
Constraints and Edge Cases:
Consider edge cases where nums1 or nums2 might be empty.
Handle scenarios where no element to the right is greater.

Optimal Solution:
A brute force approach would involve nested loops, but this would be inefficient with a time complexity of O(n*m), where n is the length of nums1 and m is the length of nums2.
Instead, use a stack and a hash map to achieve this in O(m + n) time.
Using a Stack and Hash Map:

Traverse nums2 from right to left. Use a stack to keep track of elements for which we haven't yet found a greater element.
As you iterate through nums2, compare each element with the top of the stack. If the current element is greater than the stack's top element, pop the stack and record the current element as the next greater element for that popped element.
Store these results in a hash map for quick lookup.
Finally, for each element in nums1, simply look up its next greater element in the hash map.

Try solving now

2. System Design

System Design of Instagram.

3. DBMS

Write a SQL query to find the 3rd Highest Salary in the table.

4. DBMS

Write a SQL query to fetch the Employee name (in the Employee table) and Project name (in the Project table) having the same project ID.

Round

Easy

HR Round

Duration30 minutes

Interview date10 Feb 2022

Coding problem1

1. HR Questions

What were the challenges faced while working in a college society? (Also, challenges faced while working in a team for Minor Project?)
What technologies have you been working on?
Why HashedIn? And What is its area of expertise?
What is HashedIn University?
Do you intend to pursue higher studies?