SDE - 2

You are given an array “NUMS” consisting of N integers and an integer, K. Your task is to determine the maximum sum of an increasing subsequence of length K.

Note:

1. The array may contain duplicate elements.
2. The array can also contain negative integers.
3. Every element of the subsequence must be greater than or equal to the previous element.

The subsequence of an array is a sequence of numbers that can be formed by deleting some or no elements without changing the order of the remaining elements. For example, if the given array “NUMS” = {1, 2, 5, 4, 8}, then {1, 2, 5, 4, 8}, {1, 5, 8}, {2} are some of the valid subsequences whereas the sequence {4, 2} is not a valid subsequence as the order of the elements differ from the original array.

Given 'N' number of intervals, where each interval contains two integers denoting the boundaries of the interval. The task is to merge all the overlapping intervals and return the list of merged intervals sorted in ascending order.

Two intervals will be considered to be overlapping if the starting integer of one interval is less than or equal to the finishing integer of another interval, and greater than or equal to the starting integer of that interval.

Example:

for the given 5 intervals - [1,4], [3,5], [6,8], [10,12], [8,9].
Since intervals [1,4] and [3,5] overlap with each other, we will merge them into a single interval as [1,5].

Similarly [6,8] and [8,9] overlaps, we merge them into [6,9].

Interval [10,12] does not overlap with any interval.

Final List after merging overlapping intervals: [1,5], [6,9], [10,12]

Design a movie ticket booking system and explain your thought process while designing.

You have been given a binary search tree of integers with ‘N’ nodes. Your task is to convert it into a balanced BST with the minimum height possible.

A binary search tree (BST) is a binary tree data structure that has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

A Balanced BST is defined as a BST, in which the height of two subtrees of every node differs no more than 1.

For Example:

For the given BST:

The modified BST will be:

Design a HashSet without using any built-in hash table libraries.

Implement the following public functions :

1) Constructor: It initializes the data members as required.

2) add(value): It inserts an element into the HashSet. The function takes one argument which is the value that needs to be added and returns nothing

3) contains(value): It checks whether the element exists in the HashSet or not. The function takes one argument which is the value that needs to be searched for in the HashSet. The function returns true if the element exists, otherwise returns false.

4) remove(value): It removes an element from the HashSet. The function takes one argument which is the value that needs to be removed from the HashSet and returns the element which is being removed. If the element does not exist in the HashSet or if HashSet is empty, return -1.

Operations Performed on the HashSet:

Query-1 (Denoted by an integer 1)- Inserts an element in the HashSet

Query-2 (Denoted by an integer 2)- Returns a boolean value denoting whether the element is present in the HashSet or not.

Query-3 (Denoted by an integer 3)- Removes the element from the HashSet.

Interviewer Explained me everything about team, their requirements, what is expected out of me. It was great interacting with her. She asked a new situation based questions like : What will you do incase there's a deadline and you know that you won't be able to complete the task by EOD?