Developer Associate SAP Labs interview experience

Interview rounds

Round

Medium

Online Coding Interview

Duration60 minutes

Interview date11 Mar 2022

Coding problem2

Test consisted of 10-15 MCQ questions and 2 coding questions.

1. Diameter Of Binary Tree

Easy

10m average time

90% success

0/40

Asked in companies

You are given a Binary Tree.

Return the length of the diameter of the tree.

Note :

The diameter of a binary tree is the length of the longest path between any two end nodes in a tree.

The number of edges between two nodes represents the length of the path between them.

Example :

Input: Consider the given binary tree:

Output: 6

Explanation:
Nodes in the diameter are highlighted. The length of the diameter, i.e., the path length, is 6.

Problem approach

Diameter of a tree can be calculated by only using the height function, because the diameter of a tree is nothing but maximum value of (left_height + right_height + 1) for each node. So we need to calculate this value (left_height + right_height + 1) for each node and update the result. Time complexity – O(n)

Try solving now

2. Common Elements In Three Sorted Arrays

Moderate

35m average time

65% success

0/80

Asked in companies

You are given three arrays 'A', 'B' and 'C' of length 'N', 'M' and 'K' respectively. All the three arrays are sorted in non-decreasing order. Your task is to find all such elements which are present in all the three given arrays.

Note:

1. The output array should have the same ordering of elements as the original arrays.
2. Even if a particular element appears more than once in each of the three arrays, it should still be present only once in the output array.
3. If there are no common elements in the arrays, return an empty array.

For example:

Consider the three arrays A = [ 2, 3, 4, 7 ] , B = [ 0, 0, 3, 5 ] , C = [ 1, 3, 8, 9 ]
The output array should be [ 3 ] as 3 is the only element which is present in all the three arrays.

Problem approach

A simple solution is to first find intersection of two arrays and store the intersection in a temporary array, then find the intersection of third array and temporary array.
Time complexity of this solution is O(n1 + n2 + n3) where n1, n2 and n3 are sizes of ar1[], ar2[] and ar3[] respectively

Try solving now

Round

Medium

Video Call

Duration90 minutes

Interview date14 Mar 2022

Coding problem7

Interviewer ask questions from resume , and gave coding questions to solve.

1. Subset Sum

Easy

0/40

Asked in companies

You are given an array 'nums' of ‘n’ integers.

Return all subset sums of 'nums' in a non-decreasing order.

Note:

Here subset sum means sum of all elements of a subset of 'nums'. A subset of 'nums' is an array formed by removing some (possibly zero or all) elements of 'nums'.

For example

Input: 'nums' = [1,2]

Output: 0 1 2 3

Explanation:
Following are the subset sums:
0 (by considering empty subset)
1 
2
1+2 = 3
So, subset sum are [0,1,2,3].

Problem approach

Approach: For the recursive approach we will consider two cases.

Consider the last element and now the required sum = target sum – value of ‘last’ element and number of elements = total elements – 1
Leave the ‘last’ element and now the required sum = target sum and number of elements = total elements – 1

Try solving now

2. Search In Rotated Sorted Array

Moderate

30m average time

65% success

0/80

Asked in companies

Aahad and Harshit always have fun by solving problems. Harshit took a sorted array consisting of distinct integers and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4, 5] and if he rotates it by 2, then the array becomes: [4, 5, 1, 2, 3].

After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i]. which Harshit wanted him to search in the array. For each query, if he found it, he had to shout the index of the number, otherwise, he had to shout -1.

For each query, you have to complete the given method where 'key' denotes Q[i]. If the key exists in the array, return the index of the 'key', otherwise, return -1.

Note:

Can you solve each query in O(logN) ?

Problem approach

The idea is to find the pivot point, divide the array into two sub-arrays and perform a binary search.

The main idea for finding a pivot is –

For a sorted (in increasing order) and rotated array, the pivot element is the only element for which the next element to it is smaller than it.
Using binary search based on the above idea, pivot can be found.
It can be observed that for a search space of indices in range [l, r] where the middle index is mid,
If rotation has happened in the left half, then obviously the element at l will be greater than the one at mid.
Otherwise the left half will be sorted but the element at mid will be greater than the one at r.
After the pivot is found divide the array into two sub-arrays.
Now the individual sub-arrays are sorted so the element can be searched using Binary Search.

Try solving now

3. DS Question

explain HashMap's to me?

4. DS Question

Difference between HashMaps and array.

5. Technical Question

On which technology you were working in your ongoing company.

6. DBMS Question

difference between RDMS and DBMS

7. OOPS Question

what are interfaces in java. How it is different from inheritance.

Round

Hard

Face to Face

Duration60 minutes

Interview date16 Mar 2022

Coding problem4

This round was difficult then previous round. Ask about my introduction . Then questions came from my resume. Ask about projects I did.

1. Maximum Subarray Sum

Moderate

25m average time

75% success

0/80

Asked in companies

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be -1.

Follow up: Do this in O(N) time.

Problem approach

The simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of the maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive-sum compare it with max_so_far and update max_so_far if it is greater than max_so_far

Try solving now

2. Next Permutation

Moderate

15m average time

85% success

0/80

Asked in companies

You have been given a permutation of ‘N’ integers. A sequence of ‘N’ integers is called a permutation if it contains all integers from 1 to ‘N’ exactly once. Your task is to rearrange the numbers and generate the lexicographically next greater permutation.

To determine which of the two permutations is lexicographically smaller, we compare their first elements of both permutations. If they are equal — compare the second, and so on. If we have two permutations X and Y, then X is lexicographically smaller if X[i] < Y[i], where ‘i’ is the first index in which the permutations X and Y differ.

For example, [2, 1, 3, 4] is lexicographically smaller than [2, 1, 4, 3].

Problem approach

The Idea is Based on the Following Facts:

A sequence sorted in descending order does not have the next permutation. For example “edcba” does not have the next permutation.
For a sequence that is not sorted in descending order for example “abedc”, we can follow these steps.
a) Traverse from the right and find the first item that is not following the ascending order. For example in “abedc”, the character ‘b’ does not follow the ascending order.
b) Swap the found character with the closest greater (or smallest greater) element on the right side of it. In the case of “abedc”, we have ‘c’ as the closest greater element. After swapping ‘b’ and ‘c’, the string becomes “acedb”.
c) After swapping, reverse the string after the position of the character found in step a. After reversing the substring “edb” of “acedb”, we get “acbde” which is the required next permutation.

Try solving now