SDE - 1

One idea for the solution is:

1) Reverse the whole string.

2) Then reverse the individual words.



For example, if the input is:

s = "Have a nice day!"

1) Then first reverse the whole string, 

s = "!yad ecin a evaH"

2) Then reverse the individual words,

s = "day! nice a Have"

Time Complexity:
O(n).

The first pass over the string is obviously O(n/2) = O(n). The second pass is O(n + combined length of all words / 2) = O(n + n/2) = O(n), which makes this an O(n) algorithm.

Auxiliary Space used:
O(1).

Space Complexity:
O(n).


// -------- START --------

/*
Suppose s = "abcdefgh" and we call reverse_string(s[2], 4) then this function will reverse "cdef" 
part of "abcdefgh". 
*/
void reverse_string(char *str, int len)
{
for(int i = 0; i < len / 2; i++)
{
swap(str[i], str[len - 1 - i]);
}
}

string reverse_ordering_of_words(string s)
{
int len = s.length();
// Reverse whole string.
reverse_string(&s[0], len);
int word_beginning = 0;
// Find word boundaries and reverse word by word.
for(int word_end = 0; word_end < len; word_end++)
{
if(s[word_end] == ' ') 
{
reverse_string(&s[word_beginning] , word_end - word_beginning);
word_beginning = word_end + 1;
}
}
/* 
If there is no space at the end then last word will not be reversed in the above for loop. 
So need to reverse it. 
Think about s = "hi". 
Reverse the last word.
*/
reverse_string(&s[word_beginning], len - word_beginning);
return s;
}

// -------- END --------

We need to preserve the order of elements in a sorted manner. If we can do that, we can obtain top K elements. Also, if an element is smaller than the last element in top k, then that element can be dropped as we are not deleting elements.

We can maintain a balanced BST or a sorted set collection. Keep adding new elements to the sorted set and if the size of the tree increases more than k, remove the smallest element.

Time Complexity: 
O(N*log(K))

Space Complexity: 
O(K)

We will follow the following recursive definition:

If value == 0:

// Zero coins are required to express the value of 0.

// End of recursion. Base case.

return 0

If value > 0:

minimum_coins(value) = min {1 + minimum_coins(value-coins[i])} (where i belongs to [0,n-1] and coins[i]



Basically what we are doing here is exhaustively searching for all the possible combinations of denominations which can generate our desired value and maintain a minimum number of coins required to generate that value and that will be our answer.

This method is not efficient as it computes subproblems again and again.

Time Complexity:
O(n^value).

Auxiliary Space Used:

O(value). That’s the maximum number of the recursive calls at a time.

Space Complexity:
O(n + value).

Input takes O(n) and the auxiliary space used is O(value).

int minimum_coins(vector &coins, int value) {
// If value is zero return 0.
if (value == 0) {
return 0;
}
// Maximum value assigned initially
int global_min=100005;
for(int i=0; i < coins.size(); i++){
if (coins[i] <= value) {
// To find minimum coins required to make remaining value-coins[i]
int local_min=minimum_coins(coins, value-coins[i]);
// local_min number of coins required to make remaining value-coins[i] and 
// 1 coin with value coins[i] used.
if (local_min+1 < global_min) {
global_min=local_min+1;
}
}
}
// Return maintained global minimum value
return global_min; 
}