SDE - 1

You are given ‘N’ items with certain ‘PROFIT’ and ‘WEIGHT’ and a knapsack with weight capacity ‘W’. You need to fill the knapsack with the items in such a way that you get the maximum profit. You are allowed to take one item multiple times.

f(n)= max( An + f(n-2) , f(n-1) )

This is a recursive formula which we can implement through simple recursion but here the time complexity will be O(2^n). Therefore we will use dynamic programming approach and store the intermediate results in an array.
After calculating we will return the value stored at nth(last) index in array.

You have given a Singly linkedlist. Your task is to reverse that linkedlist with the help of recursion

Given a binary tree with N number of nodes, check if that input tree is Partial BST (Binary Search Tree) or not. If yes, return true, return false otherwise.

A binary search tree (BST) is said to be a Partial BST if it follows the following properties.

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

Example:

Input:

Answer:

Level 1: 

All the nodes in the left subtree of 4 (2, 1, 3) are smaller 
than 4, all the nodes in the right subtree of the 4 (5) are 
larger than 4.

Level 2 :

For node 2:
All the nodes in the left subtree of 2 (1) are smaller than 
2, all the nodes in the right subtree of the 2 (3) are larger than 2.
For node 5:
The left and right subtree for node 5 is empty.

Level 3:

For node 1:
The left and right subtree for node 1 are empty.
For node 3:
The left and right subtree for node 3 are empty.
Because all the nodes follow the property of a Partial binary 
search tree, the above tree is a Partial binary search tree.

A counting semaphore S is initialized to 10. Then, 6 P operations and 4 V operations are performed on S. What is the final value of S?

• What is normalization?
• What are the different normalized forms?
• What are the Acid Properties?
• Write the SQL query to get the third maximum salary of an employee from a table named employees.

• Tell me about yourself
• What are your hobbies?
• Tell me one thing that you don't like about Swiggy?
• What are your strength and weakness?