SDE - 1

See, here each coin of a given denomination can come an infinite number of times. (Repetition allowed), this is what we call UNBOUNDED KNAPSACK. We have 2 choices for a coin of a particular denomination, either i) to include, or ii) to exclude. But here, the inclusion process is not for just once; we can include any denomination any number of times until N<0.

Basically, If we are at s[m-1], we can take as many instances of that coin ( unbounded inclusion ) i.e count(S, m, n – S[m-1] ) ; then we move to s[m-2]. After moving to s[m-2], we can’t move back and can’t make choices for s[m-1] i.e count(S, m-1, n ).

Finally, as we have to find the total number of ways, so we will add these 2 possible choices, i.e count(S, m, n – S[m-1] ) + count(S, m-1, n ) ; which will be our required answer.

Take care of some base cases, i.e when the given number is 0 or 1.
Create some variables, lowerbound l = 0, upperbound r = n, where n is the given number, mid and ans to store the answer.
Run a loop until l <= r , the search space vanishes
Check if the square of mid (mid = (l + r)/2 ) is less than or equal to n, If yes then search for a larger value in second half of search space, i.e l = mid + 1, update ans = mid
Else if the square of mid is more than n then search for a smaller value in first half of search space, i.e r = mid – 1
Print the value of answer ( ans)

An efficient solution is to use the Greedy approach. The basic idea of the greedy approach is to calculate the ratio value/weight for each item and sort the item on basis of this ratio. Then take the item with the highest ratio and add them until we can’t add the next item as a whole and at the end add the next item as much as we can. Which will always be the optimal solution to this problem.
A simple code with our own comparison function can be written as follows, please see the sort function more closely, the third argument to sort function is our comparison function which sorts the item according to value/weight ratio in non-decreasing order. 
After sorting we need to loop over these items and add them in our knapsack satisfying above-mentioned criteria.

We can find the kth smallest element in time complexity better than O(N log N). we know the Set in C++ STL is implemented using Binary Search Tree and we also know that the time complexity of all cases(searching, inserting, deleting ) in BST is log (n) in the average case and O(n) in the worst case. We are using set because it is mentioned in the question that all the elements in an array are distinct.

The simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far

In this Divide and Conquer approach is used. This approach doesn’t require extra space for heap and works in O(nk Log k)
It is known that the merging of two linked lists can be done in O(n) time and O(n) space. 

The idea is to pair up K lists and merge each pair in linear time using O(n) space.
After the first cycle, K/2 lists are left each of size 2*N. After the second cycle, K/4 lists are left each of size 4*N and so on.
Repeat the procedure until we have only one list left.

To rotate a linked list by k, we can first make the linked list circular and then moving k-1 steps forward from head node, making (k-1)th node’s next to null and make kth node as head.

Tip 1 : Proper understanding of basic concepts
Tip 2 : Hands-one practice is a must

We can assume this problem as a Shortest path problem/Minimum spanning tree problem. In this problem, in a graph, consider cities as nodes, pipe connects two cities as edges with cost. Now wells cost, they are self-connected edges, we can add an extra node as root node 0, and connect all 0 and every node with costs ‘WELLS[i]’. So that we can have one graph/tree, and can get minimum spanning trees / shortest path in a graph.