SDE - 1

You will be given a starting point (sx, sy) and a destination point (dx, dy) in the two-dimensional coordinate system representing the universe.

Your spacecraft can move only in X(left or right) or Y(up or down) direction, and not in the diagonal direction. To go from one point (x1, y1) to another point (x2, y2), total time taken is |x2 - x1| + |y2 - y1| seconds.

Also, in this two-dimensional system, N wormholes are present. If you go through a wormhole, spacecraft will take some time to travel from the entry of the wormhole to its exit point. You have to find out the minimum time in which you can go from the source to the destination.

What is a Wormhole?

A wormhole is a sort of tunnel that joins distant points in space, or even two universes, via space-time curvature. Theoretically, such a tunnel could be traversed from one point in space to another without actually travelling the distance between them.

Note:

1. Endpoints of all the wormholes are pairwise distinct.
It means if a wormhole starts or ends at the coordinate (x, y) then no other wormhole will start or end from the same coordinate. This holds true for the source and the destination coordinates as well.

2. If your path intersects with the wormhole, your spacecraft won't get sucked into the wormhole.  As soon as you reach the entry/exit point of a wormhole you will come out from the exit/entry point( Wormholes are bi-directional).

A thief wants to loot houses. He knows the amount of money in each house. He cannot loot two consecutive houses. Find the maximum amount of money he can loot.

You are given a ‘root’ of a Binary Search Tree in preorder fashion, and your task is to print all the leaf nodes in the tree. A leaf node is a node whose left and right pointer point to NULL.

More formally, you have to print all the leaf nodes from left to right, i.e., they should be sorted.

Note:

A binary search tree, also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

Example

For Example, the root node is given as follows :
‘ROOT’ = 6 4 3 -1 -1 5 -1 -1 8 7 -1 -1 9 -1 -1

Level 1 :
The root node of the tree is 6

Level 2 :
Left child of 6 = 4
Right child of 6 = 8

Level 3 :
Left child of 4 = 3
Right child of 4 = 5
Left child of 8 = 7
Right child of 8 = 9

Therefore all the leaf nodes are 3, 5, 7 and 9.

You are given an array 'ARR' of 'N' positive integers. You need to find the minimum number of operations needed to make all elements of the array equal. You can perform addition, multiplication, subtraction or division with any element on an array element.

Addition, Subtraction, Multiplication or Division on any element of the array will be considered as a single operation.

Example:

If the given array is [1,2,3] then the answer would be 2. One of the ways to make all the elements of the given array equal is by adding 1 to the array element with value 1 and subtracting 1 from the array element with value 3. So that final array would become [2,2,2]. 

You are given a Singly Linked List of integers. Sort the Linked List using merge sort.

Merge Sort is a Divide and Conquer algorithm. It divides the input into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, L, M, R) is a key process that assumes that arr[L..M] and arr[M + 1...R] are sorted and merges the two sorted subarrays into one.

You have an integer array ‘A’ of the form of [x, x+1, x+2, x+3, …….]. As the array is vast in size, you are given both endpoints of the array, i.e., If you are given two integers, ‘L’ and ‘R’, the array ‘A’ will be [L, L+1, L+2, ……., R-1, R]. Your task is to find the maximum possible value of ‘X’ such that the following two conditions hold.

a ⊕ b = X, where ⊕ denotes bitwise xor operation.
Both numbers ‘a’ and ‘b’ belong to the array ‘A’.