SDE - 1 HashedIn interview experience | Anonymous

Interview rounds

Round

Medium

Online Coding Interview

Duration90 minutes

Interview date5 Oct 2021

Coding problem2

This round started near 1 pm and was like any other normal test.

1. Sort An Array of 0s, 1s and 2s

Easy

10m average time

90% success

0/40

Asked in companies

You have been given an array/list 'arr' consisting of 'n' elements.

Each element in the array is either 0, 1 or 2.

Sort this array/list in increasing order.

Do not make a new array/list. Make changes in the given array/list.

Example :

Input: 'arr' = [2, 2, 2, 2, 0, 0, 1, 0]

Output: Final 'arr' = [0, 0, 0, 1, 2, 2, 2, 2]

Explanation: The array is sorted in increasing order.

Problem approach

Step 1 : I knew this question is to be solved using Dutch National Flag algorithm.
Step 2 : Declared 3 variables, low = 1, mid = 1, high = N
Step 3 : I traversed the array from start to end till mid is less than high
Step 4 : If current number at index i is 0, swap this number with element at low and increase both(low++, mid++)
Step 5 : If current number at index i 1, simply do mid++
Step 6 : If current number at index i is 2, swap this number with element at high and decrease both(high--, i--)
Step 7 : Return the updated array

Try solving now

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

Step 1 : Created deque and added first k element in it. But while adding we check if last element in deque is less than current element to be added, we remove that last element. We do this for all the elements left in deque and add current element only if elements at last of deque are greater
Step 2 : Now run loop for remaining elements, firstly we print the first element of deque as it is our required answer for first window. Step 3 & 4 comes under for loop
Step 3 : Then we remove the element from front of queue if they are out of the current window.
Step 4 : Ans now before adding the current element we check same condition as done in step 1 before adding
Step 5 : At last we print the first element of deque as it is answer for the last window.

Try solving now

Round

Medium

Video Call

Duration60 minutes

Interview date7 Oct 2021

Coding problem3

The time for this round was around 12 noon.

1. DBMS

What is 3-Layered Architecture of DBMS?
Explain Transaction Control Languages.
What is the difference between DDL and TCL?
What are SQL indexes?
SQL query to find second highest salary?

Problem approach

Tip 1 : I referred online platforms and tutorials for my preparation

Tip 2 : I tried to cover all interview questions for these topics and it helped me a lot

Tip 3 : Practice such questions as they are usually asked in many interviews

2. Group Anagrams

Moderate

30m average time

70% success

0/80

Asked in companies

You have been given an array/list of strings 'inputStr'. You are supposed to return the strings as groups of anagrams such that strings belonging to a particular group are anagrams of one another.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase. We can generalize this in string processing by saying that an anagram of a string is another string with the same quantity of each character in it, in any order.

Note:

The order in which the groups and members of the groups are printed does not matter.

For example:

inputStr = {"eat","tea","tan","ate","nat","bat"}
Here {“tea”, “ate”,” eat”} and {“nat”, “tan”} are grouped as anagrams. Since there is no such string in “inputStr” which can be an anagram of “bat”, thus, “bat” will be the only member in its group.

Problem approach

Step 1 : Since a array of strings is given, traverse this array and get each string.
Step 2 : Firstly I convert this string to char array and then sort the characters and again convert it to a string
Step 3 : Now check in map if this exists. If not, create a list and add as value in map.
Step 4 : Else, get the list, add current string & update map
Step 5 : Finally create 2d list and add all values of map to it & return

Try solving now

3. Longest Bitonic Sequence

Moderate

15m average time

85% success

0/80

Asked in companies

A Bitonic Sequence is a sequence of numbers that is first strictly increasing and then strictly decreasing.

A strictly ascending order sequence is also considered bitonic, with the decreasing part as empty, and same for a strictly descending order sequence.

For example, the sequences [1, 3, 5, 3, 2], [1, 2, 3, 4] are bitonic, whereas the sequences [5, 4, 1, 4, 5] and [1, 2, 2, 3] are not.

You are given an array 'arr' consisting of 'n' positive integers.

Find the length of the longest bitonic subsequence of 'arr'.

Example :

Input: 'arr' = [1, 2, 1, 2, 1]

Output: 3

Explanation: The longest bitonic subsequence for this array will be [1, 2, 1]. Please note that [1, 2, 2, 1] is not a valid bitonic subsequence, because the consecutive 2's are neither strictly increasing, nor strictly decreasing.

Problem approach

Step 1 : Firstly we find the bitonic element using binary search. We check mid, if it is greater than it's adjacent it is bitonic.
Step 2 : If mid element is greater than its next element and smaller than the previous element then maximum lies on left side of mid
Step 3 : If mid element is smaller than its next element and greater than the previous element then maximum lies on right side of mid
Step 4 : Now since we have bitonic element, we compare element to be searched with this
Step 5 : If it is greater, then it does not exist. If it is equal to it, we return this
Step 6 : If the element to be searched is less than the element at a bitonic point then search for the element in both halves of the array using binary search

Try solving now

Round

Medium

Video Call

Duration60 minutes

Interview date7 Oct 2021

Coding problem2

The interviewer was very cool and supportive in this interview. This interview held after 3 hours of completion of my second round

1. Pair Difference K

Moderate

15m average time

85% success

0/80

Asked in companies

You are given a sorted array ARR of integers of size N and an integer K. You have to find whether it is possible to find a pair of integers having an absolute difference of K.

Note:

1. K is a non-negative integer.

2. Absolute Difference between two integers A and B is equal to the difference of maximumOf(A, B) and minimumOf(A, B).

3. Pair of integers should have different indices in the array.

Problem approach

Step 1 : Set count as 0 & add all distinct elements in a hashmap
Step 2 : Traverse the given array
Step 3 : If a[i]+k is present in hashmap, increase count
Step 4 : If a[i]-k is present in hashmap, increase count
Step 5 : Remove a[i] from hashmap
Step 6 : Return count

Try solving now

2. Coin Change(Finite Supply)

Hard

0/120

Asked in companies

You are given an array of integers ‘coins’ denoting the denomination of coins and another array of integers ‘freq’ denoting the number of coins of each denomination.

You have to find the number of ways to make the sum ‘V’ by selecting some(or all) coins from the array.

The answer can be very large. So, return the answer modulo 1000000007.

For Example :

‘N’ = 3, ‘coins’ = {1, 2, 3}, ‘freq’ = {1, 1, 3}, ‘V’ = 6

For the given example, we can make six by using the following coins:
{1, 2, 3}
{3. 3}
Hence, the answer is 2.

Problem approach

Step 1 : First creating the base dp array, with first value set to 0
Step 2 : Then sorting the given coins
Step 3 : Traversing till amount to fill the dp array
Step 4 : Set dp[i]=INT_MAX
Step 5 : Traverse all the coins available, if it's greater than i(current amount) then break
Step 6 : Then set if (dp[i - c] != INT_MAX) dp[i] = min(dp[i], 1 + dp[i - c]);
Here we actually check the value of i-c, that is value of dp array after removing the value of current coin, if it is a valid value, we update dp[i] to min of dp[i] & 1+dp[i - c].
Step 7 : Finally we return -1 if dp[n]=INT_MAX else its value

Try solving now

Round

Easy

HR Round

Duration15 minutes

Interview date8 Oct 2021

Coding problem1

The round was held around 1pm and the interviewer was very friendly