SDE - 2

You have been given weights and values of ‘N’ items. You are also given a knapsack of size ‘W’.

Your task is to put the items in the knapsack such that the total value of items in the knapsack is maximum.

Note:

You are allowed to break the items.

Example:

If 'N = 4' and 'W = 10'. The weights and values of items are weights = [6, 1, 5, 3] and values = [3, 6, 1, 4]. 
Then the best way to fill the knapsack is to choose items with weight 6, 1 and  3. The total value of knapsack = 3 + 6 + 4 = 13.00   

You are a student of Netaji Subhas Institute of Technology. You have to take ‘N’ number of courses labelled from 1 to N to complete your B.Tech Degree.

Some courses may have prerequisites, for example, to take course 1 you have to first take course 2, which is expressed as a pair: [1, 2]. Now, your task is to find is it possible for you to finish all courses.

Note: There are no duplicate pairs in the prerequisites array.

For example-

If N = 2 and prerequisite = [[1, 2]]. Then, there are a total of 2 courses you need to take. To take course 1 you need to finish course 2. So, it is possible to complete all courses. 

You are given a matrix having ‘N’ rows and ‘M’ columns. Each cell of the matrix is either ‘X’ or ‘O’. You need to flip all those regions of ‘O’ which are surrounded by ‘X’ i.e. you need to change all ‘O’s which are present in the region to ‘X’.

Note

1. Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the matrix is not flipped to 'X'. 
2. Any ‘O’ or group of connected ‘O’ are said to be surrounded by ‘X’ when all cells touching the boundary of the group of ‘O’ must contain ‘X’.

For example

Design a scalable cache system. 
This is a LLD + problem solving round. Design all the classes and write the algorithm for cache.

Design election result computation system kind of problem.
Class design and algorithm writing for the same.

Discussion on mutex, semaphores, threads.
A problem on multi-threading system. By using multi-threading how you can achieve a task more efficiently.