SDE - 1 Salesforce interview experience | Anonymous

Interview rounds

Round

Hard

Online Coding Test

Duration75 Minutes

Interview date13 Oct 2020

Coding problem2

This was an online coding round where we had 2 questions to solve under 75 minutes. I found both the questions to be of Medium to Hard level of difficulty.

1. Mixtures

Hard

50m average time

50% success

0/120

Asked in company

Hermione is attending the Magic Potion's Class in Hogwarts. She has ‘N’ potions in front of her lying in a row. Her task is to combine these potions into 1. To do so, she can pick any two adjacent potions of color ‘A’, ‘B’ and mix them to form another potion of color ‘C’=(‘A’ + ‘B’)%100, which will then replace ‘A’ and ‘B’ in the row (Two potions combine to form one potion). But when a new potion is formed, it produces smoke of value ‘A’ * ‘B’. Hermione needs your help to minimize the smoke produced in the above task.

For example:

For the given array [ 1, 3, 1, 2, 4 ].

The optimal way will be:

Mix the last two elements. The array will be [1, 3, 1, 6 ], and the smoke will be 8.
Mix the first two elements. The array will be [4, 1, 6 ], and the smoke will be 11.
Mix the last two elements. The array will be [4, 7], and the smoke will be 17.
Mix the remaining two elements. The array will be [11], and the smoke will be 45.

So, the output will be 45.

Problem approach

Approach (Using DP) :

1) We will implement a prefix sum array ‘pref’ to calculate the prefix sum mod 100.

2) We will take a two-dimensional array and initialize it with zero.

3) Then we will iterate over all the possible lengths of the subarrays(starting from 2) and calculate the optimal answer for the current subarray.

4) ‘l+1’ is the length of the subarray. ‘I’ is the starting index and ‘j’ is the ending index.

5) Now to calculate the optimal answer for indices ‘i’ and ‘j’, we will iterate from ‘i’ to ‘j’ and will choose the adjacent indices which we should mix to produce minimum smoke.

6) For two adjacent indices, ‘I’ and ’I+1’, the smoke produced will be the sum of the smoke produced from ‘X’ to ‘I’, smoke produced from ‘I+1’ to ‘Y’, and the product of the sums of ‘X’ to ‘I’ and ‘I+1’ to ‘Y’.

7) We will take the minimum smoke from all the possible values, store it in the ‘DP’ array.

8) The output will be the optimal answer considering the whole array. So, ‘DP[0][n-1]’ will be the final output.

TC : O(N^3), where N = size of the array
SC : O(N^2)

Try solving now

2. Longest Happy String

Moderate

25m average time

75% success

0/80

Asked in companies

Ninja likes to play with strings, and he calls a string ‘S’ Happy if it only contains letters ‘a’, ‘b’, and ‘c’, and no three consecutive letters in the string are the same. For example, ‘aa’, ‘aab’, ‘aabbcc’ are the happy strings, but ‘aaa’, ‘aaza’, ‘aaabbb’ are not happy strings.

You are given three non-negative integers ‘X’, ‘Y’, ‘Z’. You need to find the longest happy string such that it contains ‘a’ at most ‘X’ times, ‘b’ at most ‘Y’ times, and ‘c’ almost ‘Z’ times.

Note:

There can be more than one possible string with maximum size. In that case, you can return any of them.

Problem approach

Approach :

1) Let the 'X', 'Y', 'Z' be the maximum availability ‘a’, ‘b’, ‘c’ respectively.

2) Declare an empty string say ‘S’ to store the answer string.

3) Run a loop till (x + y + z)
3.1) If ( 'X' >= 'Y' and 'X' >= 'Z' and the last two letters in ‘S’ is not “aa” ) or ( the last two letters in ‘S’ are “bb” or “cc”
and 'X' is nonzero).
Add ‘a’ to ‘S’, and update 'X' to ‘x - 1’.

3.2) If ( 'Y' >= 'X' and 'Y' >= 'Z' and the last two letters in ‘S’ is not “bb” ) or ( the last two letters in ‘S’ are “aa” or “cc”
and 'Y' is nonzero).
Add ‘b’ to ‘S’, and update 'Y' to ‘y - 1’.

3.3) If ( 'Z' >= 'Y' and 'Z' >= 'X' and the last two letters in ‘S’ is not “cc” ) or ( the last two letters in ‘S’ are “bb” or “aa”
and 'Z' is nonzero).
Add ‘c’ to ‘S’, and update 'Z' to ‘z - 1’.

4) Return S.

TC : O(X+Y+Z), where X, Y, Z are the given maximum number a, b, and c respectively that the output string can
have.
SC : O(X+Y+Z)

Try solving now

Round

Easy

Video Call

Duration40 Minutes

Interview date13 Oct 2020

Coding problem2

This round had 2 very standard coding questions , the first one was related to sorting and the second one was a easy Linked List problem. I had already solved them on platforms like LeetCode and CodeStudio so I was able to code both the solutions preety fast and also gave the interviewer proper time and space complexities of the both the solutions.

1. Merge Intervals

Moderate

20m average time

80% success

0/80

Asked in companies

You are given N number of intervals, where each interval contains two integers denoting the start time and the end time for the interval.

The task is to merge all the overlapping intervals and return the list of merged intervals sorted by increasing order of their start time.

Two intervals [A,B] and [C,D] are said to be overlapping with each other if there is at least one integer that is covered by both of them.

For example:

For the given 5 intervals - [1, 4], [3, 5], [6, 8], [10, 12], [8, 9].

Since intervals [1, 4] and [3, 5] overlap with each other, we will merge them into a single interval as [1, 5].

Similarly, [6, 8] and [8, 9] overlap, merge them into [6,9].

Interval [10, 12] does not overlap with any interval.

Final List after merging overlapping intervals: [1, 5], [6, 9], [10, 12].

Problem approach

Approach :

1) We will first sort the intervals by non-decreasing order of their start time.

2) Then we will add the first interval to our resultant list.

3) Now, for each of the next intervals, we will check whether the current interval is overlapping with the last interval in our resultant list.

4) If it is overlapping then we will update the finish time of the last interval in the list by the maximum of the finish time of both overlapping intervals.

5) Otherwise, we will add the current interval to the list.

TC : O(N * log(N)), where N = number of intervals
SC : O(1)

Try solving now

2. Palindrome Linked List

Easy

20m average time

90% success

0/40

Asked in companies

You are given a singly Linked List of integers. Your task is to return true if the given singly linked list is a palindrome otherwise returns false.

For example:

The given linked list is 1 -> 2 -> 3 -> 2-> 1-> NULL.

It is a palindrome linked list because the given linked list has the same order of elements when traversed forwards and backward.

Follow Up:

Can you solve the problem in O(N) time complexity and O(1) space complexity iteratively?

Problem approach

Approach :

1) Recursively traverse the entire linked list to get the last node as a rightmost node.

2) When we return from the last recursion stack. We will be at the last node of the Linked List. Then the last node value is compared with the first node value of Linked List.

3) In order to access the first node of Linked List, we create a global left pointer that points to the head of Linked List initially that will be available for every call of recursion and the right pointer which passes in the function parameter of recursion.

4) Now, if the left and right pointer node value is matched then return true from the current recursion call. Then the recursion falls back to (n-2)th node, and then we need a reference to the 2nd node from head. So we advance the left pointer in the previous call to refer to the next node in the Linked List.

5) If all the recursive calls are returning true, it means the given Linked List is a palindrome else it is not a palindrome.

TC : O(N), where N = number of nodes in the linked list.
SC : O(N)

Try solving now

Round

Medium

Video Call

Duration60 Minutes

Interview date13 Oct 2020

Coding problem4

This round had 2 Algorithmic questions wherein I was supposed to code both the problems after discussing their
approaches and respective time and space complexities . After that , I was grilled on some OOPS concepts related to
C++.

1. Trapping Rain Water

Moderate

15m average time

80% success

0/80

Asked in companies

You have been given a long type array/list 'arr’ of size 'n’.

It represents an elevation map wherein 'arr[i]’ denotes the elevation of the 'ith' bar.

Print the total amount of rainwater that can be trapped in these elevations.

Note :

The width of each bar is the same and is equal to 1.

Example:

Input: ‘n’ = 6, ‘arr’ = [3, 0, 0, 2, 0, 4].

Output: 10

Explanation: Refer to the image for better comprehension:

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Problem approach

Approach 1 (Brute Force) :

1) Iterate over every elevation or element and find the maximum elevation on to the left and right of it. Say, the
maximum elevation on to the left of the current elevation or element that we are looking at is ‘maxLeftHeight’ and the
maximum elevation on to the right of it is ‘maxRightHeight’.

2) Take the minimum of ‘maxLeftHeight’ and ‘maxRightHeight’ and subtract it from the current elevation or element.
This will be the units of water that can be stored at this elevation.

3) Compute units of water that every elevation can store and sum them up to return the total units of water that can
be stored.

TC : O(N^2), where ‘N’ is the total number of elevations in the map.
SC : O(1)

Approach 2 (Efficient Approach) :

1) Create two lists or arrays, say, ‘leftMax’ and ‘rightMax’.

2) At every index in the ‘leftMax’ array store the information of the ‘leftMaxHeight’ for every elevation in the map.

3) Similarly, at every index in the ‘rightMax’ array store the information of the ‘rightMaxHeight' for every elevation in
the map.

4) Iterate over the elevation map and find the units of water that can be stored at this location by getting the left max
height and right max height from the initial arrays that we created.

TC : O(N), where ‘N’ is the total number of elevations in the map.
SC : O(N)

Try solving now

2. Optimal Strategy for a Game

Easy

15m average time

85% success

0/40

Asked in companies

You and your friend Ninjax are playing a game of coins. Ninjax place the 'N' number of coins in a straight line.

The rule of the game is as follows:

1. Each coin has a value associated with it.

2. It’s a two-player game played against an opponent with alternating turns. 

3. At each turn, the player picks either the first or the last coin from the line and permanently removes it.

4. The value associated with the coin picked by the player adds up to the total amount the player wins.

Ninjax is a good friend of yours and asks you to start first.

Your task is to find the maximum amount you can definitely win at the end of this game.

Note:

'N' is always even number.

Ninjax is as smart as you, so he will play so as to maximize the amount he wins.

Example 1:

Let the values associated with four coins be: [9, 5, 21, 7] 

Let’s say that initially, you pick 9 and Ninjax picks 7.
Then, you pick 21 and Ninjax picks 5. 
So, you win a total amount of (9+21), i.e. 30.

In case you would have picked up 7 initially and Ninjax would have picked 21 (as he plays optimally). 
Then, you would pick 9 and Ninjax would choose 5. So, you win a total amount of (7+9), i.e. 16, which is not the maximum you can obtain.

Thus, the maximum amount you can win is 30.

Example 2:

Let the values associated with four coins be: [20, 50, 5, 10] 

Let’s say that initially, you pick 10 and Ninjax picks 20.
Then, you pick 50 and Ninjax picks 5. 
So, you win a total amount of (10+50), i.e. 60.

In case you would have picked up 20 initially and Ninjax would have picked 50 (as he plays optimally). 
Then, you would pick 10 and Ninjax would choose 5. So, you win a total amount of (20+10), i.e. 30, which is not the maximum you can obtain.

Thus, the maximum amount you can win is 60.

Problem approach

Approach :

1) The idea is to create a 2D table of size N*N.

2) Each entry in the table stores the solution to a subproblem i.e. ‘TABLE’['I']['J'] represents the maximum amount you can win for the subarray ‘COINS’['I', 'J'] given that you start first.

3) The algorithm for filling the table is as follows :
Loop 1: For ‘LEN’ = 1 to ‘N’:
Loop 2: For ‘I’ = 0 to ('N' - ‘LEN’):
→Let 'J' = 'I' + ‘LEN’ - 1
→If ('I'+1) < N && ('J'-1) >= 0 then, A = ‘DP’['I'+1]['J'-1], otherwise A = 0.
→If (i+2) < N then, B = ‘DP’['I'+2]['J'], otherwise B = 0.
→ If ('J'-2) >= 0 then, C = ‘DP’['I']['J'-2], otherwise C = 0.
→ Update ‘DP’['I']['J'] = max(‘COINS’['I'] + min(A, B), coins['J'] + min(A, C)).
End Loop 2.
End Loop 1.

4) ‘DP’[0]['N'-1] stores the final answer.

TC : O(N^2) , where N = number of coins
SC : O(N^2)

Try solving now

3. OOPS Question

What is Diamond Problem in C++ and how do we fix it?

Problem approach

The Diamond Problem : The Diamond Problem occurs when a child class inherits from two parent classes who both
share a common grandparent class i.e., when two superclasses of a class have a common base class.

Solving the Diamond Problem in C++ : The solution to the diamond problem is to use the virtual keyword. We make
the two parent classes (who inherit from the same grandparent class) into virtual classes in order to avoid two copies
of the grandparent class in the child class.

4. OOPS Question

What are Friend Functions in C++?

Problem approach

1) Friend functions of the class are granted permission to access private and protected members of the class in C++.
They are defined globally outside the class scope. Friend functions are not member functions of the class.

2) A friend function is a function that is declared outside a class but is capable of accessing the private and protected
members of the class.

3) There could be situations in programming wherein we want two classes to share their members. These members
may be data members, class functions or function templates. In such cases, we make the desired function, a friend to
both these classes which will allow accessing private and protected data members of the class.

4) Generally, non-member functions cannot access the private members of a particular class. Once declared as a
friend function, the function is able to access the private and the protected members of these classes.

Some Characteristics of Friend Function in C++ :

1) The function is not in the ‘scope’ of the class to which it has been declared a friend.
2) Friend functionality is not restricted to only one class
3) Friend functions can be a member of a class or a function that is declared outside the scope of class.
4) It cannot be invoked using the object as it is not in the scope of that class.
5) We can invoke it like any normal function of the class.

Round

Easy

HR Round

Duration30 Minutes

Interview date13 Oct 2020

Coding problem1

This was my last round and I hoped it to go good just like the other rounds. The interviewer was very straight to point
and professional. The interview lasted for 30 minutes.

1. Basic HR Question

Why should we hire you ?

Problem approach

Tip 1 : The cross questioning can go intense some time, think before you speak.

Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.

Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round,
like what are the projects currently the company is investing, which team you are mentoring. How all is the work
environment etc.

Tip 4 : Since everybody in the interview panel is from tech background, here too you can expect some technical
questions. No coding in most of the cases but some discussions over the design can surely happen.