SDE - 1

DFS can be used to solve this problem. The idea is to place queens in different columns one by one, starting from the leftmost column. As we cannot place 2 queens in the same column, when we place the queen in the nth column and if its valid position, dfs again starting n+1 th column and try placing the next queen in all the rows of n+1th column and find a valid position. If no valid queen row found in n+1th row, backtrack and go to nth column, and change the queen position to the next row and repeat the process.

The simple approach is to simply count the number of 0’s, 1’s, and 2’s. Then, place all 0’s at the beginning of the array followed by 1’s and 2's. The time complexity of this approach would be O(n) and space complexity O(1). 
However, the approach requires two traversals of the array. The question can also be solved in a single scan of the array by maintaining the correct order of 0’s, 1’s, and 2’s using variables. 
We divide the array into four groups using three pointers. Let us name these pointers as low, mid, and high.
1. a[0…low-1] only zeroes
2. a[low..mid-1] only ones
3. a[mid…high] unknown
4. a[high+1..n-1] only twos
Algorithm : 
1. Initialize three pointers low = 0, mid = 0 and high = n -1
2. Run a while loop until mid<=high : 
2.1 If (a[mid] ==0), then swap the element with the element low and increment low and mid (low++ and mid++).
2.2 If (a[mid] ==1), then increment mid (mid++).
2.3 If (a[mid] ==2), then swap it with an element in high range and decrement high (high--).

Define two pointers slow and fast. Both point to the head node, fast is twice as fast as slow. There will be no cycle if it reaches the end. Otherwise, it will eventually catch up to the slow pointer somewhere in the cycle.
Let X be the distance from the first node to the node where the cycle begins, and let X+Y be the distance the slow pointer travels. To catch up, the fast pointer must travel 2X + 2Y. L is the cycle size. The total distance that the fast pointer has travelled over the slow pointer at the meeting point is what we call the full cycle.
X+Y+L = 2X+2Y
L=X+Y
Based on our calculation, slow pointer had already traveled one full cycle when it met fast pointer, and since it had originally travelled A before the cycle began, it had to travel A to reach the cycle's beginning! 
After the two pointers meet, fast pointer can be made to point to head. And both slow and fast pointers are moved till they meet at a node. The node at which both the pointers meet is the beginning of the loop.
Pseudocode :

detectCycle(Node *head) {
Node *slow=head,*fast=head;
while(slow!=NULL && fast!=NULL && fast->next!=NULL) {
slow = slow->next; 
fast = fast->next->next; 
if(slow==fast) 
{
fast = head;
while(slow!=fast) 
{ 
slow = slow->next;
fast=fast->next;
}
return slow;
}
}
return NULL; 
}

The brute force solution is to check for every index in the string whether the sub-string can be formed at that index or not. To implement this, run a nested loop traversing the given string and check for sub-string from every index in the inner loop. 
Time Complexity : O(n^2)
The solution can be optimised by using KMP Algorithm. The KMP matching algorithm uses degenerating property (pattern having same sub-patterns appearing more than once in the pattern) of the pattern. The basic idea behind KMP algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text of the next window. 

Pseudocode:

Find Prefix:
Begin
length := 0
prefArray[0] := 0

for all character index i of pattern, do
if pattern[i] = pattern[length], then
increase length by 1
prefArray[i] := length
else
if length !=0 then
length := prefArray[length - 1]
decrease i by 1
else
prefArray[i] := 0
done
End

KMP Algorithm:
Begin
n := size of text
m := size of pattern
call findPrefix(pattern, m, prefArray)

while i < n, do
if text[i] = pattern[j], then
increase i and j by 1
if j = m, then
print the location (i-j) as there is the pattern
j := prefArray[j-1]
else if i < n AND pattern[j] != text[i] then
if j != 0 then
j := prefArray[j - 1]
else
increase i by 1
done
End

The question can be solved using a recursive approach. The idea is to search for the node in the tree and update the successor to the current node before visiting its left subtree. If the node is found in the BST, return the least value node in its right subtree, and if the right subtree of the node doesn’t exist, then inorder successor is one of the ancestors of it, which has already been updated while searching for the given key. Travel down the tree, if a node’s data is greater than root’s data then go right side, otherwise, go to left side.

Time Complexity : O(h) where h is the height of the tree

The question can be solved using a backtracking approach. Use two integers to count the remaining left parenthesis (n) and the right parenthesis (m) to be added. At each function call add a left parenthesis if n >0 and add a right parenthesis if m>n. Append the result and terminate recursive calls when both m and n are zero.
Steps :
1. Create a backtrack function that updates the current string if open_brackets are less than n or close_bracket are less than open_bracket
2. When the length of current string becomes equal to 2*n , add it to the combination result array.