SDE - 2

You have been given a Binary Tree of distinct integers and two nodes ‘X’ and ‘Y’. You are supposed to return the LCA (Lowest Common Ancestor) of ‘X’ and ‘Y’.

The LCA of ‘X’ and ‘Y’ in the binary tree is the shared ancestor of ‘X’ and ‘Y’ that is located farthest from the root.

Note :

You may assume that given ‘X’ and ‘Y’ definitely exist in the given binary tree.

For example :

For the given binary tree

LCA of ‘X’ and ‘Y’ is highlighted in yellow colour.

You are given a 2-dimensional array/list having N rows and M columns, which is filled with ones(1) and zeroes(0). 1 signifies land, and 0 signifies water.

A cell is said to be connected to another cell, if one cell lies immediately next to the other cell, in any of the eight directions (two vertical, two horizontal, and four diagonals).

A group of connected cells having value 1 is called an island. Your task is to find the number of such islands present in the matrix.

You have been given a labelled binary tree having integer value (except zero) corresponding to all its nodes. You have to find the number of possible ways to make the sum of nodes (in a particular path) exactly equal to ‘k’.

Note:

i) Nodes considered for the sum should be from parent to child.
ii) For a particular way, you can only consider nodes having the common path.
iii) Two ways are different from each other if they have an unequal number of nodes (for making sum equal to k) or at least one node is different between both the ways.

For example :

For the binary tree shown in the figure, the possible ways/paths are [8, 6, -4], [6, -3, 7], and [1, 9] for a sum of nodes equal to 10.

Design a vending machine backend and handle the different payment methods like Cash, Card, UPI, etc.