SDE - 1 Adobe interview experience | Anonymous

Interview rounds

Round

Medium

Face to Face

Duration60 Minutes

Interview date6 May 2015

Coding problem2

The interviewer asked me 2 questions related to DS/Algo in this round . Both the questions were of Easy-Medium difficulty and I was also required to code them in a production ready manner.

1. Maximum Sum Path Of A Binary Tree

Hard

25m average time

75% success

0/120

Asked in companies

You are given a binary tree having 'n' nodes. Each node of the tree has an integer value.

Your task is to find the maximum possible sum of a simple path between any two nodes (possibly the same) of the given tree.

A simple path is a path between any two nodes of a tree, such that no edge in the path is repeated twice. The sum of a simple path is defined as the summation of all node values in a path.

Problem approach

Approach : I approached this problem using DFS .

1) Create a boolean recursive function with parameters as root and target .
2) If we reached at the leaf node (root and !root->left and !root->right) and target-root->value==0 , return true as we found out a path that sums up to target.
3) If root is not null , call 1) dfs with root->left and target-root->val and 2) dfs with root->right and target-root->value . Return the OR of both these values.

TC : O(N) where N=number of nodes in the binary tree.
SC : O(N)

Try solving now

2. Intersection Of Two Arrays

Easy

10m average time

90% success

0/40

Asked in companies

You are given two arrays 'A' and 'B' of size 'N' and 'M' respectively. Both these arrays are sorted in non-decreasing order. You have to find the intersection of these two arrays.

Intersection of two arrays is an array that consists of all the common elements occurring in both arrays.

Note :

1. The length of each array is greater than zero.
2. Both the arrays are sorted in non-decreasing order.
3. The output should be in the order of elements that occur in the original arrays.
4. If there is no intersection present then return an empty array.

Problem approach

Approach 1 (Using Hashing) :

1) Initialize an empty set hs.
2) Iterate through the first array and put every element of the first array in the set S.
3) For every element x of the second array, do the following :
Search x in the set hs. If x is present, then print it.

TC : O(N+M) under the assumption that hash table search and insert operations take O(1) time, here N=size of array 1 and M=size of array 2.

SC : O(min(N,M))

Approach 2 (Using Sorting and Binary Search) :

1) Sort the smaller array.
2) Iterate through the larger array and for every element search if it is present in the smaller array or not using Binary Search.
3) If the element is present , then print it.

TC : min( O((M+N)*log(M)) , O((M+N)*log(N)) )
SC : O(1)

Try solving now

Round

Medium

Face to Face

Duration50 Minutes

Interview date6 May 2015

Coding problem3

This round had 2 questions of DS/Algo to solve under 50 minutes and one question related to Operating Systems.

1. Next Greater Element

Easy

10m average time

90% success

0/40

Asked in companies

You have been given an array/list ‘ARR’ consisting of ‘N’ positive integers. Your task is to return the Next Greater Element(NGE) for every element.

The Next Greater Element for an element ‘X’ is the first element on the right side of ‘X’ in the array 'ARR', which is greater than ‘X’. If no such element exists to the right of ‘X’, then return -1.

For example:

For the given array 'ARR' = [7, 12, 1, 20]

The next greater element for 7 is 12.
The next greater element for 12 is 20. 
The next greater element for 1 is 20. 
There is no greater element for 20 on the right side.

So, the output is [12, 20, 20, -1].

Problem approach

Approach 1 (Naive Solution) :

1) Use two loops: The outer loop picks all the elements one by one.
2) The inner loop looks for the first greater element for the element picked by the outer loop.
3) If a greater element is found then that element is printed as next, otherwise, -1 is printed.

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

Approach 2 (Using Stack) :

1) Push the first element to stack.
2) Pick rest of the elements one by one and follow the following steps in loop.
2.1) Mark the current element as next.
2.2) If stack is not empty, compare top element of stack with next.
2.3) If next is greater than the top element, Pop element from stack. next is the next greater element for
the popped element.
2.4) Keep popping from the stack while the popped element is smaller than next. next becomes the next
greater element for all such popped elements.
3) Finally, push the next in the stack.
4) After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.

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

Try solving now

2. Number In AP

Moderate

15m average time

85% success

0/80

Asked in companies

You’re given three integers X, C, and Y, where X denotes the first term of an arithmetic sequence whose common difference is C. Your task is to determine whether Y belongs to this arithmetic sequence or not.

For example:

If X is 6 and C is 3, the sequence becomes 6,9,12,15,18,21,24…

Problem approach

Approach 1 (Naive Solution) :

1) The simplest approach to solve the problem is to generate all possible subarrays.
2) For each subarray, check if the difference between adjacent elements remains the same throughout or not.
3) Among all such subarrays satisfying the condition, store the length of the longest subarray and print it as the result.

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

Approach 2 (Efficient Solution) :

1) Initialize a variable called res to store the length of the longest subarray forming an AP.
2) Iterate over remaining arrays and compare the current adjacent difference with the previous adjacent difference.
3) Iterate over the array, and for each element, calculate the difference between the current pair of adjacent elements and check if it is equal to the previous pair of adjacent elements.
4) If found to be true, continue the ongoing subarray by incrementing res by 1.
5) Otherwise, consider a new subarray. Update the maximum length obtained so far, i.e. res by comparing it with the length of the previous subarray.
6) Finally, return the res as the required answer.

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

Try solving now

3. OS Question

Define Process and Threads in OS.

Problem approach

Answer :

Process : A process is an instance of a program that is being executed. When we run a program, it does not execute directly. It takes some time to follow all the steps required to execute the program, and following these execution steps is known as a process.

A process can create other processes to perform multiple tasks at a time; the created processes are known as clone or child process, and the main process is known as the parent process. Each process contains its own memory space and does not share it with the other processes. It is known as the active entity.

Thread : A thread is the subset of a process and is also known as the lightweight process. A process can have more than one thread, and these threads are managed independently by the scheduler. All the threads within one process are interrelated to each other. Threads have some common information, such as data segment, code segment, files, etc., that is shared to their peer threads. But contains its own registers, stack, and counter.

Round

Medium

Face to Face

Duration50 Minutes

Interview date6 May 2015

Coding problem3

This round had 2 questions of DSA of Easy-Medium difficulty and at the end I was asked a Puzzle to check my general problem solving ability.

1. Max Product Subset

Moderate

15m average time

85% success

0/80

Asked in companies

You are given an array/list ‘arr’ of size ‘n’. Your task is to find the maximum product possible by taking any subset of the array/list ‘arr’.

Since the product can be large, return it modulo 10^9+7

For example:

Let arr=[-1,-1,-2,4,3] 

We can take the subset {-1,-2,4,3} which will have the product as 24. We can verify that this is the largest product possible. Hence we return 24.

Problem approach

Approach 1 (Time Efficient) :

1) Construct four auxiliary arrays leftMax[], rightMax[], leftMin[] and rightMin[] of same size as input array.
2) Fill leftMax[], rightMax[], leftMin[] and rightMin[] in below manner.
2.1) leftMax[i] will contain maximum element on left of arr[i] excluding arr[i]. For index 0, left will contain
-1.
2.2) leftMin[i] will contain minimum element on left of arr[i] excluding arr[i]. For index 0, left will contain
-1.
2.3) rightMax[i] will contain maximum element on right of arr[i] excluding arr[i]. For index n-1, right will
contain -1.
2.4) rightMin[i] will contain minimum element on right of arr[i] excluding arr[i]. For index n-1, right will
contain -1.
3) For all array indexes i except first and last index, compute maximum of arr[i]*x*y where x can be leftMax[i] or leftMin[i] and y can be rightMax[i] or rightMin[i].
4) Return the maximum from step 3.

TC : O(N)
SC : O(N)

Approach 2 (Space Efficient) :

1)Sort the array in ascending order.
2) Return the maximum of product of last three elements of the array and product of first two elements and last element.

TC : O(N*log(N))
SC : O(1)

Approach 3 (Time as well as Space Efficient) :

1) Scan the array and compute Maximum, second maximum and third maximum element present in the array.
2) Scan the array and compute Minimum and second minimum element present in the array.
3) Return the maximum of product of Maximum, second maximum and third maximum and product of Minimum, second minimum and Maximum element.

Note – Step 1 and Step 2 can be done in single traversal of the array.

TC : O(N)
SC : O(1)

Try solving now

2. Populating Next Right Pointers in Each Node

Moderate

25m average time

75% success

0/80

Asked in companies

You have been given a complete binary tree of ‘N’ nodes. The nodes are numbered 1 to ‘N’.

You need to find the ‘next’ node that is immediately right in the level order form for each node in the given tree.

Note :

1. A complete binary tree is a binary tree in which nodes at all levels except the last level have two children and nodes at the last level have 0 children.
2. Node ‘U’ is said to be the next node of ‘V’ if and only if  ‘U’ is just next to ‘V’ in tree representation.
3. Particularly root node and rightmost nodes have ‘next’ node equal to ‘Null’ 
4. Each node of the binary tree has three-pointers, ‘left’, ‘right’, and ‘next’. Here ‘left’ and ‘right’ are the children of node and ‘next’ is one extra pointer that we need to update.

For Example :

The‘next’ node for ‘1’ is ‘Null’, ‘2’ has ‘next’ node ‘6’, ‘5’ has ‘next’ node ‘3’, For the rest of the nodes check below.

Problem approach

Approach :

1) We can augment queue entries to contain level of nodes also which is 0 for root, 1 for root’s children and so on. So a queue node will now contain a pointer to a tree node and an integer level.
2) When we enqueue a node, we make sure that correct level value for node is being set in queue.
3) To set nextRight, for every node N, we dequeue the next node from queue, if the level number of next node is same, we set the nextRight of N as address of the dequeued node.
4) Otherwise we set nextRight of N as NULL.
5) We initialize a node Prev which points at the previous node.
6) While traversing the nodes in the same level we keep track of the previous node and point the nextRight pointer to the current node in every iteration.

TC : O(N), where N=number of nodes in the binary tree
SC : O(N)

Try solving now

3. Puzzle

Two wire burning puzzle.

Problem approach

If we light a stick, it takes 60 minutes to burn completely. What if we light the stick from both sides? It will take exactly half the original time, i.e. 30 minutes to burn completely.

1) 0 minutes – Light stick 1 on both sides and stick 2 on one side.
2) 30 minutes – Stick 1 will be burnt out. Light the other end of stick 2.
3) 45 minutes – Stick 2 will be burnt out. Thus 45 minutes is completely measured.

Round

Medium

Face to Face

Duration50 Minutes

Interview date6 May 2015

Coding problem2

This round consisted of 2 questions from DSA where I was first asked to explain my approach to the interviewer with proper complexity analysis and then code the problems. The interviewer was quite friendly and also provided me some hints when I was stuck.

1. Design a stack that supports getMin() in O(1) time and O(1) extra space

Moderate

15m average time

85% success

0/80

Asked in companies

Create a stack data structure that allows operations such as push (adding an element), pop (removing the top element), top (retrieving the top element), and also provides a way to retrieve the minimum element in constant time.

Implement the following public functions :

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

2. pop() :
It pops the element from the top of the stack and returns nothing.

3. top() :
It returns the element being kept at the top of the stack.

4.  getMin() :
It returns the smallest element present in the stack.

Operations Performed on the Stack:

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

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

Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the top of the stack. (top function)

Query-4(Denoted by an integer 4): Returns the smallest element present in the stack. (getMin() function)

Problem approach

Approach :
Below are the different functions designed to push and pop elements from the stack.

Push(x) :
1) Inserts x at the top of stack.
2) If stack is empty, insert x into the stack and make maxEle equal to x.
3) If stack is not empty, compare x with maxEle. Two cases arise:
3.1) If x is less than or equal to maxEle, simply insert x.
3.2) If x is greater than maxEle, insert (2*x – maxEle) into the stack and make maxEle equal to x.

Pop() :

1) Remove element from top.
2) Let the removed element be y. Two cases arise:
2.1) If y is less than or equal to maxEle, the maximum element in the stack is still maxEle.
2.2) If y is greater than maxEle, the maximum element now becomes (2*maxEle – y), so update
(maxEle = 2*maxEle – y). This is where we retrieve previous maximum from current maximum and its
value in stack.

getMax() :

1) Returns the max element in the stack.
2) The way in which push and pop operations are designed , the maxEle variable will give us the maximum element in O(1) time when getMax() function is called.

TC : O(1)
SC : O(1) //Not taking into the account the stack that we were given

Try solving now

2. Split Array Into Maximum Subarrays

Moderate

25m average time

50% success

0/80

Asked in companies

You have given an integer array/list ‘arr’ of size ‘N’. You have to split the array into the maximum number of subarrays such that the first and last occurrence of every distinct element lies in a single subarray.

You are required to return the number of maximum subarrays in which the array can be split.

An array ‘C’ is a subarray of array ‘D’ if ‘C’ can be obtained from ‘D’ by deletion of several elements from the beginning and several elements from the end.

For Example:

Let an array ‘arr’ = [2,2,1,1].

In this example, the array can be split like this [2,2], [1,1] in this 
case the first and last occurrence of 2 lies in a first subarray and 
similarly first and the last occurrence of 1 lies in a second 
subarray.

Problem approach

Approach :

1) Initialize array hash of size equal to maximum element in the array to store the occurrences, initialize it with value -1.
2) Initialize answer by 0.
3) Iterate over the array and update the occurrence index of every element in the hash array.
3.1) Initialize variable maxIndex with -1.
3.2) Update maxIndex with maximum value of ‘MaxIndex’ and ‘HASH[Arr[i]]’ each time.
3.3) If maxIndex becomes equal to the current index, then increment the answer by 1.
4) Return ‘ANSWER’ .

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

Try solving now

SDE - 1

Interview preparation journey

Are you ready for your Dream Job?

Interview rounds

1. Maximum Sum Path Of A Binary Tree

You are given a binary tree having 'n' nodes. Each node of the tree has an integer value.

Your task is to find the maximum possible sum of a simple path between any two nodes (possibly the same) of the given tree.

A simple path is a path between any two nodes of a tree, such that no edge in the path is repeated twice. The sum of a simple path is defined as the summation of all node values in a path.

2. Intersection Of Two Arrays

You are given two arrays 'A' and 'B' of size 'N' and 'M' respectively. Both these arrays are sorted in non-decreasing order. You have to find the intersection of these two arrays.

Intersection of two arrays is an array that consists of all the common elements occurring in both arrays.

Note :

1. Next Greater Element

You have been given an array/list ‘ARR’ consisting of ‘N’ positive integers. Your task is to return the Next Greater Element(NGE) for every element.

The Next Greater Element for an element ‘X’ is the first element on the right side of ‘X’ in the array 'ARR', which is greater than ‘X’. If no such element exists to the right of ‘X’, then return -1.

For example:

2. Number In AP

You’re given three integers X, C, and Y, where X denotes the first term of an arithmetic sequence whose common difference is C. Your task is to determine whether Y belongs to this arithmetic sequence or not.

For example:

3. OS Question

1. Max Product Subset

You are given an array/list ‘arr’ of size ‘n’. Your task is to find the maximum product possible by taking any subset of the array/list ‘arr’.

Since the product can be large, return it modulo 10^9+7

For example:

2. Populating Next Right Pointers in Each Node

You have been given a complete binary tree of ‘N’ nodes. The nodes are numbered 1 to ‘N’.

You need to find the ‘next’ node that is immediately right in the level order form for each node in the given tree.

Note :

For Example :

The‘next’ node for ‘1’ is ‘Null’, ‘2’ has ‘next’ node ‘6’, ‘5’ has ‘next’ node ‘3’, For the rest of the nodes check below.

3. Puzzle

1. Design a stack that supports getMin() in O(1) time and O(1) extra space

Create a stack data structure that allows operations such as push (adding an element), pop (removing the top element), top (retrieving the top element), and also provides a way to retrieve the minimum element in constant time.

Implement the following public functions :

Operations Performed on the Stack:

2. Split Array Into Maximum Subarrays

You have given an integer array/list ‘arr’ of size ‘N’. You have to split the array into the maximum number of subarrays such that the first and last occurrence of every distinct element lies in a single subarray.

You are required to return the number of maximum subarrays in which the array can be split.

An array ‘C’ is a subarray of array ‘D’ if ‘C’ can be obtained from ‘D’ by deletion of several elements from the beginning and several elements from the end.

For Example: