SDE - 1 LinkedIn interview experience | Anonymous

Interview rounds

Round

Hard

Video Call

Duration45 minutes

Interview date13 Aug 2022

Coding problem2

1. Similar Strings

Ninja

70m average time

30% success

0/200

Asked in companies

You are given three strings, 'A', 'B', and 'C', each of length 'N' consisting of lower case alphabets. The difference between the three strings is defined as ∑|A[i] − B[i]| + |A[i] − C[i]| where |A[i] − B[i]| and |A[i] − C[i]| are the absolute differences between ASCII values of the characters at the position i in strings 'A', 'B' and 'A' ,'C' respectively. You are allowed to rotate the string 'A' cyclically. There are a total of 'N' possible rotations of a string of length 'N'.

Your task is to return the maximum and minimum difference of the three strings for all the possible rotations of string a.

For Example:

If the value of 'N' is 2, 'A' is "ab" , 'B' is "aa" and 'C' is "bb".
Then the answer for this input is
min = 2 
max = 2

Because current difference is 1 + 1 = 2
After one rotation difference will be 1 + 1 = 2
Hence, the minimum and the maximum answer is 2.

Problem approach

I solved this problem using this approach.
Let’s define the following operation on string S. We can divide it into two halves and if we want we can swap them. And also, we can recursively apply this operation to both of its halves. By careful observation, we can see that if after applying the operation on some string A, we can obtain B, then after applying the operation on B we can obtain A. And for the given two strings, we can recursively find the least lexicographic string that can be obtained from them. Those obtained strings if are equal, the answer is YES, otherwise NO. For example, the least lexicographically string for “aaba” is “aaab”. And least lexicographically string for “abaa” is also “aaab”. Hence both of these are equivalent.

Try solving now

2. Nth Fibonacci Number

Easy

0/40

Asked in companies

The n-th term of Fibonacci series F(n), where F(n) is a function, is calculated using the following formula -

    F(n) = F(n - 1) + F(n - 2), 
    Where, F(1) = 1, F(2) = 1

Provided 'n' you have to find out the n-th Fibonacci Number. Handle edges cases like when 'n' = 1 or 'n' = 2 by using conditionals like if else and return what's expected.

"Indexing is start from 1"

Example :

Input: 6

Output: 8

Explanation: The number is ‘6’ so we have to find the “6th” Fibonacci number.
So by using the given formula of the Fibonacci series, we get the series:    
[ 1, 1, 2, 3, 5, 8, 13, 21]
So the “6th” element is “8” hence we get the output.

Problem approach

This problem is a simple recursive problem. But time complexity of simple recursive calls is exponential. In O(long) this problem can be solved using a simple trick.

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

This method will solve this question in O(long).

Try solving now

Round

Medium

Video Call

Duration45 minutes

Interview date13 Aug 2022

Coding problem2

1. Minimum Cost To Connect Sticks

Moderate

15m average time

85% success

0/80

Asked in companies

You are given an array/list ‘ARR’ of ‘N’ positive integers where each element describes the length of the stick. You have to connect all sticks into one. At a time, you can join any two sticks by paying a cost of ‘X’ and ‘Y’ where ‘X’ is the length of the first stick and ‘Y’ is the length of the second stick and the new stick we get will have a length equal to (X+Y). You have to find the minimum cost to connect all the sticks into one.

Problem approach

It is a greedy approach where we will form a min-heap of all the lengths of sticks that are given to us. In this approach, we will always find two sticks with minimum length and connect them and add their cost to our answer. Also, we will add the newly formed stick back into our min-heap. And then we will continue to do the same procedure for all the remaining sticks. Since we need to minimize the cost to connect all the sticks into one, therefore we have to greedily pick the two smallest lengths of sticks from given lengths and add them to the answer and continue it until we are left with one stick in our heap. We are picking the two smallest sticks every time because the new stick formed will also be added to our cost later. Therefore picking smaller sticks will reduce the total cost than using longer sticks which will increase the cost.

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

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.

Try solving now