SDE - 1 Samsung interview experience | Anonymous

Interview rounds

Round

Hard

Online Coding Test

Duration120 Minutes

Interview date16 Jul 2020

Coding problem3

This round had 3 preety good questions to be solved under 2 hours . The first question was from Graphs and DSU , the second question was related to DP and the third one was from Recursion.

1. Most Stones Removed with Same Row or Column

Hard

45m average time

55% success

0/120

Asked in companies

On a 2-D plane, we place 'n' stones at some integer coordinate points. Each coordinate point may have at most one stone.

A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

You are given an array 'stones' of length 'n' where 'stones[i]' = '[ri, ci]' represent the ith stone’s location i.e 'ri' is the row coordinate of the 'ith' stone and 'ci' is the column coordinate of the 'ith' stone. Your task is to return the largest possible number of stones that can be removed.

Example:

Input: 'stones' = [[0,1] [1,0] [0,0]]

Output: 2

Explanation:
We can remove the 1st stone at [0,1] as it has the same row as the 3rd stone [0, 0]. And remove the 2nd stone because it has the same column [0,1] as the 3rd stone.

Problem approach

Approach :

1) Imagine each stone has an ID corresponding to its index in the input array.
2) Maintain two maps of pair (int, vector), ‘rowmap’ and ‘colmap’, which stores the id of the ith
stone.
3) Map each occupied row to a vector of all stone IDs in that row.
4) Map each occupied column to a vector of all stone IDs in that column.
5) Maintain a ‘parent’ array that stores the parent of the ith node in the ‘ith’ index.
6) Union each stone ID with all other stone IDs in the same row or in the same column.
7) The union between two nodes is done in the following way:
i) Find the parent of the nodes.
ii) If they have the same parent we do nothing.
iii) Else we change the parent of one node to other.
8) Maintain a set ‘unique’ that stores the parent of the unique connected components.
9) Each connected group can have all but one stone removed. Thus, we count the number of unique
groups and subtract this from the total number of stones to get our ‘answer’.
10) Return ‘answer’.

Try solving now

2. Gold mine problem

Moderate

35m average time

70% success

0/80

Asked in companies

You have been given a gold mine represented by a 2-d matrix of size ('N' * 'M') 'N' rows and 'M' columns. Each field/cell in this mine contains a positive integer, the amount of gold in kgs.

Initially, the miner is at the first column but can be at any row.

He can move only right, right up, or right down. That is from a given cell and the miner can move to the cell diagonally up towards the right or right or diagonally down towards the right.

Find out the maximum amount of gold he can collect.

Problem approach

Approach :

1) Create a 2-D matrix ‘GOLD_TABLE’, the same size as the given mine, and initialize each cell of ‘GOLD_TABLE’ to ‘0’.
2) Now start from the very last column of the mine and move towards the first column.
2.1) For each row in the particular column, calculate the maximum of upper-right diagonal value,
straight right value, and lower right diagonal value.
2.2) If we are in the first row, we cannot move the upper right diagonal; consider ‘0’ there. Similarly, if
we are in the last row, we cannot move the lower right diagonal; hence consider ‘0’ there.
2.3) Store the maximum in ‘GOLD_TABLE’['R']['C'].
2.4) Repeat the same for all the rows of the column.
3) Hence for each column, we will have maximum gold collected for each row.
4) Now, the maximum of all the rows for the first column will be our answer.

Try solving now

3. All Possible Balanced Parentheses

Easy

10m average time

90% success

0/40

Asked in companies

You are given a positive integer 'N'. You have to generate all possible sequences of balanced parentheses using 'N' pairs of parentheses.

A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters ‘+’ and ‘1’. For example, sequences ‘(())()’, ‘()’ and ‘(()(()))’ are balanced, while ‘)(‘, ‘(()’ and ‘(()))(‘ are not.

For example :

For N = 1, there is only one sequence of balanced parentheses,  ‘()’.

For N = 2, all sequences of balanced parentheses are ‘()()’, ‘(())’.

Problem approach

Approach :

1 )Let’s define a function balancedParenthesesHelper(i, Str, O, C, N), where i is the current index, Str is the sequence of parentheses formed till (i-1)th index, O is the count of opening parentheses, C is the count of closing parentheses.

2) Base case: if i is equal to 2*N, add the sequence in the ‘ans’ list and return.

3) Recursive States:
3.1) If O is less than N, place an open parenthesis at the current index and call the next recursive state.
balancedParenthesesHelper(i + 1, Str + ‘(‘, O + 1, C, N)
3.2) If O is greater than C, place a close parenthesis at the current index and call the next recursive
state.
balancedParenthesesHelper(i + 1, Str + ‘)‘, O, C + 1, N)

Try solving now

Round

Medium

Video Call

Duration60 Minutes

Interview date16 Jul 2020

Coding problem2

This round had 2 questions from DSA. Both the questions were preety straightforward and were asked to check my implementation skills and how well do I handle Edge Cases for tricky problems.

1. Stack using queue

Moderate

25m average time

65% success

0/80

Asked in companies

Implement a Stack Data Structure specifically to store integer data using two Queues.

There should be two data members, both being Queues to store the data internally. You may use the inbuilt Queue.

Implement the following public functions :

1. Constructor:
It initializes the data members(queues) as required.

2. push(data) :
This function should take one argument of type integer. It pushes the element into the stack and returns nothing.

3. pop() :
It pops the element from the top of the stack and, in turn, returns the element being popped or deleted. In case the stack is empty, it returns -1.

4. top :
It returns the element being kept at the top of the stack. In case the stack is empty, it returns -1.

5. size() :
It returns the size of the stack at any given instance of time.

6. isEmpty() :
It returns a boolean value indicating whether the stack is empty or not.

Operations Performed on the Stack:

Query-1(Denoted by an integer 1): Pushes an integer data to the stack. (push function)

Query-2(Denoted by an integer 2): Pops the data kept at the top of the stack and returns it to the caller. (pop function)

Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the top of the stack but doesn't remove it, unlike the pop function. (top function)

Query-4(Denoted by an integer 4): Returns the current size of the stack. (size function)

Query-5(Denoted by an integer 5): Returns a boolean value denoting whether the stack is empty or not. (isEmpty function)

Example

Operations: 
1 5
1 10
2
3
4

Enqueue operation 1 5: We insert 5 at the back of the queue.
  Queue: [5]

Enqueue operation 1 10: We insert 10 at the back of the queue.
  Queue: [5, 10]

Dequeue operation 2: We remove the element from the front of the queue, which is 5, and print it.
  Output: 5
  Queue: [10]

Peek operation 3: We return the element present at the front of the queue, which is 10, without removing it.
  Output: 10
  Queue: [10]

IsEmpty operation 4: We check if the queue is empty.
  Output: False
  Queue: [10]

Problem approach

Approach : A stack can be implemented using two queues. Let stack to be implemented be ‘s’ and queues used to implement be ‘q1’ and ‘q2’. Stack ‘s’ can be implemented in two ways :

Method 1 (push - O(1) , pop - O(n) ) :

1) push(s, x) operation :
i) Enqueue x to q1 (assuming size of q1 is unlimited).

2) pop(s) operation :
i) One by one dequeue everything except the last element from q1 and enqueue to q2.
ii) Dequeue the last item of q1, the dequeued item is result, store it.
iii) Swap the names of q1 and q2
iv) Return the item stored in step 2.

TC : push(s,x) -> O(1)
pop() -> O(n)

Method 2 (push - O(n) , pop - O(1) ) :

1) push(s, x) operation :
i) Enqueue x to q2
ii) One by one dequeue everything from q1 and enqueue to q2.
iii) Swap the names of q1 and q2
2) pop(s) operation :
i) Dequeue an item from q1 and return it.

TC : push(s,x) -> O(n)
pop() -> O(1)

Try solving now

2. Rotate matrix by 90 degrees

Easy

15m average time

85% success

0/40

Asked in companies

You are given a square matrix of non-negative integers 'MATRIX'. Your task is to rotate that array by 90 degrees in an anti-clockwise direction using constant extra space.

For example:

For given 2D array :

    [    [ 1,  2,  3 ],
         [ 4,  5,  6 ],
         [ 7,  8,  9 ]  ]

After 90 degree rotation in anti clockwise direction, it will become:

    [   [ 3,  6,  9 ],
        [ 2,  5,  8 ],
        [ 1,  4,  7 ]   ]

Problem approach

Approach :

1) Initialise two variables, ‘row’ and ‘col’ to keep track of the starting row and starting column of the current
ring. Ending row and ending column can be tracked by N and M.
2) Starting from the outer ring, keep rotating the inner rings, if it exists.
3) For each ring/square of the matrix:
3.1) Move the elements of the top side.
3.2) Move the elements of the right side.
3.3) Move the elements of the bottom side.
3.4) Move the elements of the left side.
3.5) Update the ‘row’, ‘col’, ‘N’ and ‘M’ for the next inner ring.

TC : O(N*M), where N is the number of rows and M is the number of columns in the matrix.
SC : O(1)

Try solving now

Round

Medium

Video Call

Duration60 Minutes

Interview date16 Jul 2020

Coding problem5

This round also had 2 questions related to DSA where I was first expected to explain my approaches and then discuss the time and space complexities of my solution. After that , I was asked some core concepts related to OOPS and OS.

1. Triplets with Given Sum

Moderate

15m average time

85% success

0/80

Asked in companies

You are given an array/list ARR consisting of N integers. Your task is to find all the distinct triplets present in the array which adds up to a given number K.

An array is said to have a triplet {ARR[i], ARR[j], ARR[k]} with sum = 'K' if there exists three indices i, j and k such that i!=j, j!=k and i!=j and ARR[i] + ARR[j] + ARR[k] = 'K'.

Note:

1. You can return the list of values in any order. For example, if a valid triplet is {1, 2, -3}, then {2, -3, 1}, {-3, 2, 1} etc is also valid triplet. Also, the ordering of different triplets can be random i.e if there are more than one valid triplets, you can return them in any order.
2. The elements in the array need not be distinct.
3. If no such triplet is present in the array, then return an empty list, and the output printed for such a test case will be "-1".

Problem approach

Approach :

1) Sort the array in ascending order.

2) Now since we want triplets such that x + y + z = ‘K’, we have x+ y = ‘K’ - z and now we can fix z as arr[i]. So we want to find the sum of two numbers x and y as ‘K’ - arr[i] in the array.

3) We will use two pointers, one will start from i+1, and the other will start from the end of the array.

4) Let the two pointers be ‘FRONT’ and ‘BACK’, where ‘FRONT’ = i + 1 and ‘BACK’ = n - 1. Let ‘SUM’ = x + y, where x = ‘ARR[FRONT]’ and y = ‘ARR[BACK]’. We have to find the triplets such that ‘TARGET’ =‘SUM’.

5) While ‘FRONT’ < ‘BACK’, there will be 3 cases:
5.1) if ('SUM' < ‘TARGET’), we will have to increase the sum and hence increment front pointer.
5.2) Else if ('SUM' > ‘TARGET’), we will have to decrease the sum and hence decrease the ‘BACK’
pointer.
5.3) Else print the triplet and since we want distinct triplets, do the following.
a) Increment the front pointer until ‘ARR[FRONT]’ = x and ‘FRONT’ < ‘BACK’.
b) Decrement the back pointer until ‘ARR[BACK]’ = y and ‘FRONT’ < ‘BACK’.

6) While ‘ARR[i]’ = ‘ARR[i+1]’, keep on incrementing i, this will automatically ensure that we are only finding distinct triplets.

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

Try solving now

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

3. OOPS Question

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

Problem approach

Answer :
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. OS Question

What is thrashing in OS?

Problem approach

Answer :
1) It is generally a situation where the CPU performs less productive work and more swapping or paging work.
2) It spends more time swapping or paging activities rather than its execution.
3) By evaluating the level of CPU utilization, a system can detect thrashing.
4) It occurs when the process does not have enough pages due to which the page-fault rate is increased. 5) It inhibits much application-level processing that causes computer performance to degrade or collapse.

5. OS Question

What is deadlock? How to prevent deadlock?

Problem approach

Answer :

Deadlock : Deadlock is a scenario where a set of processes is blocked because each process has acquired a lock on a particular resource and is waiting for another resource locked by some other process.
A deadlock can occur in almost any situation where processes share resources. It can happen in any computing environment, but it is widespread in distributed systems, where multiple processes operate on different resources.

Steps to prevent Deadlock :

1) No Mutual Exclusion :
It means more than one process can have access to a single resource at the same time. It’s impossible because if multiple processes access the same resource simultaneously, there will be chaos. Additionally, no process will be completed. So this is not feasible. Hence, the OS can’t avoid mutual exclusion.

2) No Hold and Wait :
To avoid the hold and wait, there are many ways to acquire all the required resources before starting the execution. But this is also not feasible because a process will use a single resource at a time.
Another way is if a process is holding a resource and wants to have additional resources, then it must free the acquired resources. This way, we can avoid the hold and wait condition, but it can result in starvation.

3) Removal of No Preemption :
One of the reasons that cause the deadlock is the no preemption. It means the CPU can’t take acquired resources from any process forcefully even though that process is in a waiting state. If we can remove the no preemption and forcefully take resources from a waiting process, we can avoid the deadlock.

4) Removal of Circular Wait :
In the circular wait, two processes are stuck in the waiting state for the resources which have been held by each other. To avoid the circular wait, we assign a numerical integer value to all resources, and a process has to access the resource in increasing or decreasing order.

Round

Easy

HR Round

Duration30 Minutes

Interview date16 Jul 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

Tell me something not there in your resume.

Problem approach

If you get this question, it's an opportunity to choose the most compelling information to share that is not obvious from your resume.

Example :

Strength -> I believe that my greatest strength is the ability to solve problems quickly and efficiently, which makes me unique from others.

Ability to Handle Pressure -> I enjoy working under pressure because I believe it helps me grow and become more efficient .

Tip : Emphasize why you were inspired to apply for the job. You can also explain that you are willing to invest a great deal of energy if hired.

These are generally very open ended questions and are asked to test how quick wit a candidate is. So there is nothing to worry about if you have a good cammand over your communication skills and you are able to propagate your thoughts well to the interviewer.

SDE - 1

Interview preparation journey

Are you ready for your Dream Job?

Interview rounds

1. Most Stones Removed with Same Row or Column

On a 2-D plane, we place 'n' stones at some integer coordinate points. Each coordinate point may have at most one stone.

A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

You are given an array 'stones' of length 'n' where 'stones[i]' = '[ri, ci]' represent the ith stone’s location i.e 'ri' is the row coordinate of the 'ith' stone and 'ci' is the column coordinate of the 'ith' stone. Your task is to return the largest possible number of stones that can be removed.

Example:

2. Gold mine problem

You have been given a gold mine represented by a 2-d matrix of size ('N' * 'M') 'N' rows and 'M' columns. Each field/cell in this mine contains a positive integer, the amount of gold in kgs.

Initially, the miner is at the first column but can be at any row.

He can move only right, right up, or right down. That is from a given cell and the miner can move to the cell diagonally up towards the right or right or diagonally down towards the right.

Find out the maximum amount of gold he can collect.

3. All Possible Balanced Parentheses

You are given a positive integer 'N'. You have to generate all possible sequences of balanced parentheses using 'N' pairs of parentheses.

A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters ‘+’ and ‘1’. For example, sequences ‘(())()’, ‘()’ and ‘(()(()))’ are balanced, while ‘)(‘, ‘(()’ and ‘(()))(‘ are not.

For example :

1. Stack using queue

Implement a Stack Data Structure specifically to store integer data using two Queues.

There should be two data members, both being Queues to store the data internally. You may use the inbuilt Queue.

Implement the following public functions :

Operations Performed on the Stack:

Example

2. Rotate matrix by 90 degrees

You are given a square matrix of non-negative integers 'MATRIX'. Your task is to rotate that array by 90 degrees in an anti-clockwise direction using constant extra space.

For example:

1. Triplets with Given Sum

You are given an array/list ARR consisting of N integers. Your task is to find all the distinct triplets present in the array which adds up to a given number K.

An array is said to have a triplet {ARR[i], ARR[j], ARR[k]} with sum = 'K' if there exists three indices i, j and k such that i!=j, j!=k and i!=j and ARR[i] + ARR[j] + ARR[k] = 'K'.

Note:

2. Trapping Rain Water

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 :

Example:

Note :

3. OOPS Question

4. OS Question

5. OS Question

1. Basic HR Question