Software Developer

The recursive approach is to traverse the tree in a depth-first manner. The moment you encounter either of the nodes node1 or node2, return the node. The least common ancestor would then be the node for which both the subtree recursions return a non-NULL node. It can also be the node which itself is one of node1 or node2 and for which one of the subtree recursions returns that particular node.

Pseudo code :

LowestCommonAncestor(root, node1, node2) 
{
	if(not root)
		return NULL
	if (root == node1 or root == node2) 
		return root
	left = LowestCommonAncestor(root.left, node1, node2)
	right = LowestCommonAncestor(root.right, node1, node2)
	if(not left)
		return right
	else if(not right)
		return left
	else
		return root
}

This can be solved both: recursively and iteratively.
The recursive approach is more intuitive. First reverse all the nodes after head. Then we need to set head to be the final node in the reversed list. We simply set its next node in the original list (head -> next) to point to it and sets its next to NULL. The recursive approach has a O(N) time complexity and auxiliary space complexity.
For solving the question is constant auxiliary space, iterative approach can be used. We maintain 3 pointers, current, next and previous, abbreviated as cur, n and prev respectively. All the events occur in a chain.
1. Assign prev=NULL, cur=head .
2. Next, repeat the below steps until no node is left to reverse:
1. Initialize n to be the node after cur. i.e. (n=cur->next)
2. Then make cur->next point to prev (next node pointer).
3. Then make prev now point to the cur node.
4. At last move cur also one node ahead to n.
The prev pointer will be the last non null node and hence the answer.

Floyd's algorithm can be used to solve this question.

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; 
}

It is a type of join operation in SQL. Inner join is an operation that returns combined tuples between two or more tables where at least one attribute is in common. If there is no attribute in common between tables then it will return nothing. 

Syntax: 

select * 
from table1 INNER JOIN table2
on table1.column_name = table2.column_name;

It is a type of Join operation in SQL. Outer join is an operation that returns combined tuples from a specified table even if the join condition fails. There are three types of outer join in SQL i.e. 

Left Outer Join
Right Outer Join
Full Outer Join

Syntax of Left Outer Join: 
select *
from table1 LEFT OUTER JOIN table2
on table1.column_name = table2.column_name;

If the grid is 1×1, there is 1 rectangle. 

If the grid is 2×1, there will be 2 + 1 = 3 rectangles 

If it grid is 3×1, there will be 3 + 2 + 1 = 6 rectangles. 

we can say that for N*1 there will be N + (N-1) + (n-2) … + 1 = (N)(N+1)/2 rectangles

If we add one more column to N×1, firstly we will have as many rectangles in the 2nd column as the first, 

and then we have that same number of 2×M rectangles. 

So N×2 = 3 (N)(N+1)/2

After deducing this we can say 

For N*M we’ll have (M)(M+1)/2 (N)(N+1)/2 = M(M+1)(N)(N+1)/4

So the formula for total rectangles will be M(M+1)(N)(N+1)/4

1 pick of an eatable is required to correctly label the Jars.

Solution :
You have to pick only one eatable from jar C. Suppose the eatable is a candy, then the jar C contains candies only(because all the jars were mislabeled).
Now, since the jar C has candies only, Jar B can contain sweets or mixture. But, jar B can contain only the mixture because its label reads “sweets” which is wrong.

Therefore, Jar A contains sweets. Thus the correct labels are:
A: Sweets.
B: Candies and Sweets.
C: Candies.

If we light a stick, it takes 60 minutes to burn completely. What if we light the stick from both sides? It will take exactly half the original time, i.e. 30 minutes to burn completely.

0 minutes – Light stick 1 on both sides and stick 2 on one side.

30 minutes – Stick 1 will be burnt out. Light the other end of stick 2.

45 minutes – Stick 2 will be burnt out. Thus 45 minutes is completely measured.

Algorithm : 
Define a map m, n := size of s, set left := 0, right := 0, counter := size of p
define an array ans
store the frequency of characters in p into the map m
for right := 0 to n – 1
if m has s[right] and m[s[right]] is non zero, then decrease m[s[right]] by 1, decrease counter by 1 and if counter = 0, then insert left into ans
otherwise
while left < right{
   if s[left] is not present in m, then increase counter by 1, and increase m[s[left]] by 1
   increase left by 1
   if m has s[right] and m[s[right]] is non zero, then decrease right by 1, and come out from the loop
   if m has no s[left], then set left := right + 1
   return ans
}