Software Development

A high-security meeting has been arranged. Tables for the delegates and security personnel have been arranged. A total of ‘N’ rows of tables has been set up. The first row has one table, the second row has two, and so on. To ensure maximum security, the tables on either end of each row have been assigned for security personnel each. If there is only one table in a row, it will be assigned to a security personnel. The tables assigned for security personnel will host exactly one security personnel each. All the other tables will host two guests each.

You are given an integer ‘N’, which denotes the number of rows., You are supposed to print the table pattern indicating the number of guests or security personnel at each table. In other words, print the number of people in each table.

For example, if the number of rows are 4, the table pattern is as follows:

1
11
121
1221

You are given a list of ‘N’ non-overlapping intervals (each interval can be represented using two integers ‘start’ and ‘end’), sorted in ascending order (based on ‘start’ values). Your task is to insert a given interval in the list, such that all the intervals are present in sorted order.

In case the given interval overlaps with other intervals, merge all necessary intervals to produce a list containing only non-overlapping intervals.

Example:

Let’s say the list of intervals is: [[1,3], [5,7], [8,12]] and we need to insert the interval [4,6] into the list. [4,6] must be inserted in the second position. After insertion, since [4,6] overlaps with [5,7], we merge them into one interval [4,7]. So, our resulting list is:  [[1,3], [4,7], [8,12]]

1. OOPS concepts
2. Implement runtime polymorphism using virtual functions

You are given an array of integers. You need to sort the array in ascending order using quick sort.

Quick sort is a divide and conquer algorithm in which we choose a pivot point and partition the array into two parts i.e, left and right. The left part contains the numbers smaller than the pivot element and the right part contains the numbers larger than the pivot element. Then we recursively sort the left and right parts of the array.

Example:

Let the array = [ 4, 2, 1, 5, 3 ]
Let pivot to be the rightmost number.

After the 1st level partitioning the array will be { 2, 1, 3, 4, 5 } as 3 was the pivot. After 2nd level partitioning the array will be { 1, 2, 3, 4, 5 } as 1 was the pivot for the left part and 5 was the pivot for the right part. Now our array is sorted and there is no need to divide it again.