SDE - 1

Observations:
1. If all digits are sorted in descending order, then output is always “Not Possible”. 
2. If all digits are sorted in ascending order, then we need to swap last two digits. 
3. For other cases, we need to process the number from rightmost side to find the smallest of all greater numbers. 

Steps:
1. Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. If no such digit is found, then output is “Not Possible”.
2. Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. 
3. Swap the above found two digits.
4. Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the required output.

Steps : 
1. Reverse the individual words of the given string one by one. 
2. Then, reverse the whole string from start to end to get the desired output.

Time Complexity : O(n)

To solve the question using a max heap, make a max heap of all the elements of the list. Run a loop for k-1 times and remove the top element of the heap. After running the loop, the element at top will be the kth largest element, return that. Time Complexity : O(n + klogn)
The question can also be solved using a min heap. 

Approach:
1. Create a min heap class with a capacity of k
2. When the heap reaches capacity eject the minimum number. 
3. Loop over the array and add each number to the heap. 
4. At the end, the largest k number of elements will be left in the heap, the smallest of them being at the top of the heap, which is the kth largest number
The time complexity for this solution is O(N logK).

A queue can be used to do level order traversal of the tree. For each node, first visit the node and then push its children nodes in the FIFO queue. 
printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
a) print temp_node->data.
b) Enqueue temp_node’s children 
(first left then right children) to q
c) Dequeue a node from q.
Time Complexity: O(n) where n is the number of nodes in the binary tree 
Space Complexity: O(n) where n is the number of nodes in the binary tree

Initialization of semaphores – 
mutex = 1 
Full = 0 // Initially, all slots are empty. Thus full slots are 0 
Empty = n // All slots are empty initially 

Solution for Producer – 

do{

//produce an item

wait(empty);
wait(mutex);

//place in buffer

signal(mutex);
signal(full);

}while(true)

When producer produces an item then the value of “empty” is reduced by 1 because one slot will be filled now. The value of mutex is also reduced to prevent consumer to access the buffer. Now, the producer has placed the item and thus the value of “full” is increased by 1. The value of mutex is also increased by 1 because the task of producer has been completed and consumer can access the buffer. 

Solution for Consumer – 

do{

wait(full);
wait(mutex);

// remove item from buffer

signal(mutex);
signal(empty);

// consumes item

}while(true)

As the consumer is removing an item from buffer, therefore the value of “full” is reduced by 1 and the value is mutex is also reduced so that the producer cannot access the buffer at this moment. Now, the consumer has consumed the item, thus increasing the value of “empty” by 1. The value of mutex is also increased so that producer can access the buffer now.

The brute force solution would be to do a linear search and find the element. 
Time Complexity : O(n) 

The brute force solution can be optimized using Binary Search. The idea is to find the bitonic point k which is the index of the maximum element of a given sequence. If the element to be searched is greater than the maximum element return -1, else search the element in both halves. 
Steps : 
1. Find the bitonic point in the given array, i.e the maximum element in the given bitonic array using binary search.
2. If the element to be searched is equal to the element at the bitonic point then print the index of the bitonic point.
3. If the element to be searched is greater than the element at a bitonic point then the element does not exist in the array.
4. If the element to be searched is less than the element at a bitonic point then search for the element in both halves of the array using binary search.

An index is a data structure (most commonly a B- tree) that stores the values for a specific column in a table. An index is created on a column of a table. So, the key points to remember are that an index consists of column values from one table, and that those values are stored in a data structure. The index is a data structure – remember that.
B- trees are the most commonly used data structures for indexes. The reason B- trees are the most popular data structure for indexes is due to the fact that they are time efficient – because look-ups, deletions, and insertions can all be done in logarithmic time. And, another major reason B- trees are more commonly used is because the data that is stored inside the B- tree can be sorted. The RDBMS typically determines which data structure is actually used for an index.

I gave a solution by indexing marks with a linked list of students creating an array of link lists. 
He then modified the question by adding marks in floating points were also allowed .
I gave him a solution using map (c++) based on a key value pair of marks and list of students but he asked to optimize the time complexity
I then gave a modification of my first solution and added concept of buckets and binary search .