Developer Associate SAP Labs interview experience | Sakshi Oberoi

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

Moderate

35m average time

70% success

0/80

Asked in companies

Given two 1-dimensional arrays containing strings of lowercase alphabets, print the elements that are common in both the arrays i.e. the strings that are present in both the arrays.

Note:

An element of one array can be mapped only to one element of the array. For example :

Array 1 = {“ab”, “dc”, “ab”, “ab”}
Array 2 = {“dc”, “ab”, “ab”} 

The common elements for the above example will be “dc”, “ab”, and “ab”.

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 problem6

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

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

2. Partition Equal Subset Sum

Moderate

25m average time

65% success

0/80

Asked in companies

You are given an array 'ARR' of 'N' positive integers. Your task is to find if we can partition the given array into two subsets such that the sum of elements in both subsets is equal.

For example, let’s say the given array is [2, 3, 3, 3, 4, 5], then the array can be partitioned as [2, 3, 5], and [3, 3, 4] with equal sum 10.

Follow Up:

Can you solve this using not more than O(S) extra space, where S is the sum of all elements of the given array?

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

3. Data Structure based Questions

explain HashMaps to me

Difference between HashMaps and array.

4. DBMS based question

difference between RDMS and DBMS

5. HR Question

On which technology you were working in your ongoing company.

6. Java based Question

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

Round

Hard

Video Call

Duration60 minutes

Interview date16 Mar 2022

Coding problem3

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

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

2. Maximum Subarray Sum

Moderate

0/80

Asked in companies

You are given an array/list ARR consisting of N integers. Your task is to find the maximum possible sum of a non-empty subarray(contiguous) of this array.

Note: An array C is a subarray of array D if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end of array D.

For e.g.- All the non-empty subarrays of array [1,2,3] are [1], [2], [3], [1,2], [2,3], [1,2,3].

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