SDE - Intern Flock interview experience | Anonymous

Interview rounds

Round

Medium

Online Coding Interview

Duration90 minutes

Interview date15 Nov 2021

Coding problem3

There were three coding questions
1 Easy
1 Medium
1 Hard

1. Broken Calculator

Easy

20m average time

80% success

0/40

Asked in companies

You are given two integers ‘X’ and ‘Y’. You can convert the number ‘X’ into another integer ‘Y’ using the following two operations in any order.

i) Multiply ‘X’ by 2 
ii) Subtract 1 from ‘X’

Your task is to find the minimum number of operations needed to convert ‘X’ into ‘Y’.

Note: It is always possible to convert ‘X’ into ‘Y’

Problem approach

Case - 1 : c = d and c=0 and d = 0 then 0 will be answer.
Case - 2 : c.= d and c!=0 and d!=0 then 1 will be answer because we will choose k as c or d and we will apply first operation.
Case - 3 : c != d For this we can use the operations of the first type with k=(c+d)/2. After that, it is enough for us to use either an operation of the second type with k=c-(|c-d|/2) if c>d, or an operation of the third type with k=d-(|c-d|/2) otherwise.

Try solving now

2. Longest Palindromic Substring

Moderate

20m average time

80% success

0/80

Asked in companies

You are given a string ('STR') of length 'N'. Find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the one with the smaller start index.

Note:

A substring is a contiguous segment of a string.

For example : The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome, there is another palindromic substring of length 3 is "bab" since "aba" starting index is less than "bab", so "aba" is the answer.

Problem approach

1. For bruteforce logic we can generate each substring and can check if that substring is palindrome and choose maximum length accordingly.
2. But this logic was giving TLE on few test cases.
3. This problem can be solved with manchers algorithm which is an standard DP problem to count frequency of palindromic substrings in a string. O(n)

Try solving now

3. DFS Traversal

Moderate

35m average time

65% success

0/80

Asked in companies

Given an undirected and disconnected graph G(V, E), containing 'V' vertices and 'E' edges, the information about edges is given using 'GRAPH' matrix, where i-th edge is between GRAPH[i][0] and GRAPH[i][1]. print its DFS traversal.

V is the number of vertices present in graph G and vertices are numbered from 0 to V-1. 

E is the number of edges present in graph G.

Note :

The Graph may not be connected i.e there may exist multiple components in a graph.

Try solving now

Round

Hard

Video Call

Duration60 Minutes

Interview date16 Dec 2021

Coding problem1

This round was a DSA round and was one of the toughest round i have ever attempted.
We had a short introduction of each other (No follow up questions).
After intro he just said i will give you a question and you are expected to solve that correctly in 60 minutes.
The interview was scheduled in afternoon and i guess he was very good competitive programmer.

1. Beautiful Array

Hard

50m average time

60% success

0/120

Asked in companies

You are given two integers ‘M’ and ‘N’. Your task is to find the number of a unique beautiful array of length ‘M’.

The array of length ‘M’ is said to be beautiful if -

The array consists of elements from 1 to ‘N’.

The array contains at least one ‘N’ length strictly increasing subsequence.

Note:

A subsequence of an array is an ordered subset of the array's elements having the same sequential ordering as the original array. For example, the subsequences of the array  [1, 2, 3] are [1], [2], [3], [1, 2], [1, 3], [2, 3] and [1, 2, 3] where  [2, 1], [3,2, 1] are not subsequence of array [1, 2, 3]

The longest increasing subsequence of an array of numbers is the longest possible subsequence that can be created from its elements such that all elements are in strictly increasing order.

For example:

For M = 3 and N = 2
array : [ 1, 1, 2 ] [ 1, 2, 1 ] [ 1, 2, 2 ] [ 2, 1, 2 ] are beautiful.

array:  [ 1, 1, 1 ] [ 2, 1, 1 ] [ 2, 2, 1 ] [ 2, 2, 2 ] are not beautiful.

Problem approach

1. The very first approach i discussed with interviewer was the brute forces approach in which i will choose each possible subarray of array A and multiply that by given integer X and then find answer for that case by applying standard kadane algorithm and at the end we will take maximum answer among all answers. This solution will have time complexity of O(n*n*n)
But this is highly unoptimized approach so interviewer asked me to reduce time complexity.

2. After a lot of observations and approach discussion i came up with a approach which was based on dynamic programming and was having time complexity of O(n*n).

DP States :
dp[i][j] = max(1,i-1) + (sum(i,j))*x + max(j+1,n)

here dp[i][j] means what will be the answer if i will chose segment (i,j) for multiplication.
In that case we will have to add (sum(i,i))*x and maximum possible suffix sum from (1,i-1) and maximum possible prefix sum from (j+1,n).
Now we have three components for calculation
1. Max suffix some for given index i
2. Max prefix sum for given index j
3. sum (i,j) * x
We can calculate each component by precompuation and hence we can solve the problem in O(n*n) time complexity because we have to travese for each possible pair of (i,j).

Try solving now

Round

Medium

Video Call

Duration60 minutes

Interview date16 Dec 2021

Coding problem1

This round was a DSA round and interview started with intro of interviewer and then followed up by my intro.
Then interviewer explained me the problem and said that i have to explain the solution and have to write the code of google docs.
The interview was scheduled in the evening (3 PM).
The interviewer was quite humble and he explained problem and sample test cases in very good manner.

1. Minimum Number of Deletions and Insertions

Moderate

0/80

Asked in companies

You are given 2 non-empty strings 's1' and 's2' consisting of lowercase English alphabets only.

In one operation you can do either of the following on 's1':

(1) Remove a character from any position in 's1'.

(2) Add a character to any position in 's1'.

Find the minimum number of operations required to convert string 's1' into 's2'.

Example:

Input: 's1' = "abcd", 's2' = "anc"

Output: 3

Explanation:
Here, 's1' = "abcd", 's2' = "anc".
In one operation remove 's1[3]', after this operation 's1' becomes "abc".    
In the second operation remove 's1[1]', after this operation 's1' becomes "ac".
In the third operation add 'n' in 's1[1]', after this operation 's1' becomes "anc".

Hence, the minimum operations required will be 3. It can be shown that there's no way to convert s1 into s2 in less than 3 moves.

Try solving now

Round

Medium

Video Call

Duration90 Minutes

Interview date21 Dec 2021

Coding problem0

This round was mainly based on subjects and system design.
The interview started with introduction of Interviewer , he gave me a detailed introduction of his past experience and the projects he was working on and the tech stack he have been dealing with.
The interviewer was quite experienced and he was going very deep in subjective knowledge i was able to answer most of the questions but few of the questions were way more detailed so i was simply denying that i do not know the answer.
At the end he asked me to design rate limiter of API server (Ex : In 1 hour our server will serve only x number of request and rest requests will be denied).
The interview extended to 90 minutes because of a lot of deatled question.
Ultimately all rounds of Flock interview were pretty good so prepare in well manner.
Fortunately i had enough knowledge of DSA and subjects and system design so i cracked every interview.
After 2-3 days of this final interview i got internship offer from Flock but i denied that offer and joined Sharechat.