SDE - 1 Newgen Software interview experience | Sunakshi Bhandari

Interview rounds

Round

Easy

Online Coding Interview

Duration150 minutes

Interview date16 Dec 2021

Coding problem3

The test consists of Aptitude questions , English Questions , Technical . The technical questions were from DBMS DS algo . and 3 coding questions Those who clear the first test would have a second test of Psychometric duration 60 Mins on the same day of the test.

1. String Conversion

Moderate

15m average time

85% success

0/80

Asked in companies

You have given two strings 'A' and ‘B’ of length ‘N’ each which only consists of lowercase English letters. You have also given an integer ‘K’.

Your task is to determine if it is possible to convert string ‘A’ into ‘B’ after performing two types of operations on it:

1. Choose an index i (1 <= i <= N - 1) and swap A[i] and A[i+1].
2. Choose an index i (1 <= i <= N - K + 1) and if A[i], A[i+1],. . . . , A[i+K-1] all are equal to some character x (x != ‘z’), then you can replace each one with the next character (x + 1) , i.e. ‘a’ is replaced by ‘b’, ‘b’ is replaced by ‘c’ and so on.

Note:

You are allowed to perform any operation any number of times(possibly zero) only on string 'A'.

For example-

If the given strings are A = ‘xbbx’ and B = ‘xddx’ and K is given as 2. Then it is possible to convert string A into B by applying the second operation two times on index 2 (1 based indexing).

Problem approach

1) Loop from 1st to last element and take count is one
2) And store 1st alphabet in output array and go to next
3) Increase the count if alphabet of that index is same as previous else first store the count as string in array and then insert new alphabet in output array and again go to next element and do the same

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

Traverse every array element and find the highest bars on the left and right sides. Take the smaller of two heights. The difference between the smaller height and the height of the current element is the amount of water that can be stored in this array element.

Follow the steps mentioned below to implement the idea:

Traverse the array from start to end:

For every element:

Traverse the array from start to that index and find the maximum height (a) and
Traverse the array from the current index to the end, and find the maximum height (b).
The amount of water that will be stored in this column is min(a,b) – array[i], add this value to the total amount of water stored

Print the total amount of water stored.

Try solving now

3. Check if The String is A Palindrome

Easy

10m average time

90% success

0/40

Asked in companies

You are given a string 'S'. Your task is to check whether the string is palindrome or not. For checking palindrome, consider alphabets and numbers only and ignore the symbols and whitespaces.

Note :

String 'S' is NOT case sensitive.

Example :

Let S = “c1 O$d@eeD o1c”.
If we ignore the special characters, whitespaces and convert all uppercase letters to lowercase, we get S = “c1odeedo1c”, which is a palindrome. Hence, the given string is also a palindrome.

Problem approach

Find length of str. Let length be n.
Initialize low and high indexes as 0 and n-1 respectively.

Do following while low index ‘l’ is smaller than high index ‘h’.

If str[l] is not same as str[h], then return false.
Increment l and decrement h, i.e., do l++ and h--
If we reach here, it means we didn’t find a miss

Try solving now

Round

Medium

Video Call

Duration40 minutes

Interview date18 Dec 2021

Coding problem4

I was asked questions from DS algo and DBMS. I was also given coding questions to solve.

1. Maximum meetings

Easy

10m average time

90% success

0/40

Asked in companies

You are given the schedule of 'N' meetings with their start time 'Start[i]' and end time 'End[i]'.

You have only 1 meeting room. So, you need to return the maximum number of meetings you can organize.

Note:

The start time of one chosen meeting can’t be equal to the end time of the other chosen meeting.

For example:

'N' = 3, Start = [1, 3, 6], End = [4, 8, 7].

You can organize a maximum of 2 meetings. Meeting number 1 from 1 to 4, Meeting number 3 from 6 to 7.

Problem approach

Idea is to solve the problem using the greedy approach which is the same as Activity Selection Problem.

Sort all pairs(Meetings) in increasing order of second number(Finish time) of each pair.
Select first meeting of sorted pair as the first Meeting in the room and push it into result vector and set a variable time_limit(say) with the second value(Finishing time) of the first selected meeting.
Iterate from the second pair to last pair of the array and if the value of the first element(Starting time of meeting) of the current pair is greater then previously selected pair finish time (time_limit) then select the current pair and update the result vector (push selected meeting number into vector) and variable time_limit.
Print the Order of meeting from vector.

Try solving now

2. Insert Into A Binary Search Tree

Easy

20m average time

80% success

0/40

Asked in companies

You have been given a root node of the binary search tree and a positive integer value. You need to perform an insertion operation i.e. inserting a new node with the given value in the given binary search tree such that the resultant tree is also a binary search tree.

If there can be more than one possible tree, then you can return any.

Note :

A binary search tree is a binary tree data structure, with the following properties :

    a. The left subtree of any node contains nodes with a value less than the node’s value.

    b. The right subtree of any node contains nodes with a value equal to or greater than the node’s value.

    c. Right, and left subtrees are also binary search trees.
It is guaranteed that,

    d. All nodes in the given tree are distinct positive integers.

    e. The given BST does not contain any node with a given integer value.

Example, below the tree, is a binary search tree.

Below the tree is not a BST as node ‘2’ is less than node ‘3’ but ‘2’ is the right child of ‘3’, and node ‘6’ is greater than node ‘5’ but it is in the left subtree of node ‘5’.

Problem approach

A new key is always inserted at the leaf. Start searching a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.

Try solving now

3. OOPs based question

Can we overload the constructors

Problem approach

Yes, the constructors can be overloaded by changing the number of arguments accepted by the constructor or by changing the data type of the parame

4. OOPs based question

Is multiple inheritance possible in Java. If so, how?

Problem approach

When the child class extends from more than one superclass, it is known as multiple inheritance. However, Java does not support multiple inheritance. To achieve multiple inheritance in Java, we must use the interface.