Developer Associate SAP Labs interview experience | Sunakshi Bhandari

Interview rounds

Round

Medium

Online Coding Interview

Duration60 minutes

Interview date11 Oct 2021

Coding problem2

Test consisted of 10-15 MCQ questions based on OOPs , DS algo , DBMS and 2 coding questions

1. Longest Substring Without Repeating Characters

Moderate

20m average time

80% success

0/80

Asked in companies

Given a string 'S' of length 'L', return the length of the longest substring without repeating characters.

Example:

Suppose given input is "abacb", then the length of the longest substring without repeating characters will be 3 ("acb").

Try solving now

2. Check If Binary Tree Is Sum Tree Or Not

Moderate

15m average time

85% success

0/80

Asked in companies

You are given an arbitrary binary tree consisting of N nodes where each node is associated with a certain value. You need to check whether the given tree is a sum tree or not.

A binary tree is a sum tree if the value of each node is equal to the sum of nodes present in the left and the right subtree. An empty tree is a sum tree with 0 sums. A leaf node is also considered a sum tree with a sum equal to the value of the leaf node.

Try solving now

Round

Medium

Video Call

Duration60 minutes

Interview date15 Oct 2021

Coding problem3

This round was technical round -1 . Interviewer ask questions from resume , and gave coding questions to solve.

1. Edit Distance

Moderate

30m average time

70% success

0/80

Asked in companies

You are given two strings 'S' and 'T' of lengths 'N' and 'M' respectively. Find the "Edit Distance" between the strings.

Edit Distance of two strings is the minimum number of steps required to make one string equal to the other. In order to do so, you can perform the following three operations:

1. Delete a character
2. Replace a character with another one
3. Insert a character

Note:

Strings don't contain spaces in between.

Problem approach

The idea is to process all characters one by one starting from either from left or right sides of both strings.
Let us traverse from right corner, there are two possibilities for every pair of character being traversed.

m: Length of str1 (first string)
n: Length of str2 (second string)
If last characters of two strings are same, nothing much to do. Ignore last characters and get count for remaining strings. So we recur for lengths m-1 and n-1.
Else (If last characters are not same), we consider all operations on ‘str1’, consider all three operations on last character of first string, recursively compute minimum cost for all three operations and take minimum of three values.
Insert: Recur for m and n-1
Remove: Recur for m-1 and n
Replace: Recur for m-1 and n-1

Try solving now

2. Uncommon Characters

Moderate

25m average time

65% success

0/80

Asked in company

Given two strings S1 and S2 of lowercase alphabets, find the list of uncommon characters for the two strings.

A character is uncommon if it is present only in one of the strings i.e. it is either present in S1 or S2, but not in both.

Note :

1. Both the strings contain only lowercase alphabets and can contain duplicates.

2. Return the uncommon characters in lexicographically sorted order.

Problem approach

Concept of hashing can be applied to solve this problem.
1. Create a hash table with a size of 26 for all lowercase characters.
2. Mark each character as '0' (indicating it is not present in both strings).
3. Mark the presence of each character in the 1st string as a '1' in the hash table, denoting the 1st string.
4. Next, traverse the 2nd string. For every character in string 2, check whether its presence in the hash table is '1' or not. If it is a 1, you should mark its presence as a -1 (indicating that the character is common to both strings), otherwise you should mark it as a 2 (indicating the 2nd string).

Try solving now

3. Technical Questions

explain your project.

explain recursion to me.

difference between RDMS and DBMS

SQL program to find salary of a particular person in the office .

what are interfaces in java.

Round

Hard

Face to Face

Duration60 minutes

Interview date18 Oct 2021

Coding problem2

This was technical round -2. This round was tougher than previous round. The interviewer starts by asking questions from DS algo basics , DBMS , OS

1. Minimize The Maximum

Easy

15m average time

85% success

0/40

Asked in companies

You are given an array of N integers and an integer K. For each array element, you are allowed to increase or decrease it by a value k. The task is to minimize the difference between the maximum element and the minimum element after modifications.

Try solving now

2. Smallest Window

Moderate

10m average time

90% success

0/80

Asked in companies

You are given two strings S and X containing random characters. Your task is to find the smallest substring in S which contains all the characters present in X.

Example:

Let S = “abdd” and X = “bd”.

The windows in S which contain all the characters in X are: 'abdd', 'abd', 'bdd', 'bd'. 
Out of these, the smallest substring in S which contains all the characters present in X is 'bd'. 
All the other substring have a length larger than 'bd'.

Problem approach

First check if the length of the string is less than the length of the given pattern, if yes then “no such window can exist “.
Store the occurrence of characters of the given pattern in a hash_pat[].
we will be using two pointer technique basically
Start matching the characters of pattern with the characters of string i.e. increment count if a character matches.
Check if (count == length of pattern ) this means a window is found.
If such a window found, try to minimize it by removing extra characters from the beginning of the current window.
delete one character from first and again find this deleted key at right, once found apply step 5 .
Update min_length.
Print the minimum length window.

Try solving now

Developer Associate

Interview preparation journey

Are you ready for your Dream Job?

Interview rounds

1. Longest Substring Without Repeating Characters

Given a string 'S' of length 'L', return the length of the longest substring without repeating characters.

Example:

2. Check If Binary Tree Is Sum Tree Or Not

You are given an arbitrary binary tree consisting of N nodes where each node is associated with a certain value. You need to check whether the given tree is a sum tree or not.

A binary tree is a sum tree if the value of each node is equal to the sum of nodes present in the left and the right subtree. An empty tree is a sum tree with 0 sums. A leaf node is also considered a sum tree with a sum equal to the value of the leaf node.

1. Edit Distance

You are given two strings 'S' and 'T' of lengths 'N' and 'M' respectively. Find the "Edit Distance" between the strings.

Edit Distance of two strings is the minimum number of steps required to make one string equal to the other. In order to do so, you can perform the following three operations:

Note:

2. Uncommon Characters

Given two strings S1 and S2 of lowercase alphabets, find the list of uncommon characters for the two strings.

A character is uncommon if it is present only in one of the strings i.e. it is either present in S1 or S2, but not in both.

Note :

3. Technical Questions

1. Minimize The Maximum

You are given an array of N integers and an integer K. For each array element, you are allowed to increase or decrease it by a value k. The task is to minimize the difference between the maximum element and the minimum element after modifications.

2. Smallest Window

You are given two strings S and X containing random characters. Your task is to find the smallest substring in S which contains all the characters present in X.

Example: