SDE - 2

You are given a Singly Linked List of integers. Return true if it has a cycle, else return false.

A cycle occurs when a node's next points back to a previous node in the list.

Example:

In the given linked list, there is a cycle, hence we return true.

Given a binary tree, return the vertical order traversal of the values of the nodes of the given tree.

For each node at position (X, Y), (X-1, Y-1) will be its left child position while (X+1, Y-1) will be the right child position.

Running a vertical line from X = -infinity to X = +infinity, now whenever this vertical line touches some nodes, we need to add those values of the nodes in order starting from top to bottom with the decreasing ‘Y’ coordinates.

Note:

If two nodes have the same position, then the value of the node that is added first will be the value that is on the left side.

For example:

For the binary tree in the image below.

The vertical order traversal will be {2, 7, 5, 2, 6, 5, 11, 4, 9}.

Aahad and Harshit always have fun by solving problems. Harshit took a sorted array consisting of distinct integers and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4, 5] and if he rotates it by 2, then the array becomes: [4, 5, 1, 2, 3].

After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i]. which Harshit wanted him to search in the array. For each query, if he found it, he had to shout the index of the number, otherwise, he had to shout -1.

For each query, you have to complete the given method where 'key' denotes Q[i]. If the key exists in the array, return the index of the 'key', otherwise, return -1.

Note:

Can you solve each query in O(logN) ?

You are given an array ‘ARR’ consisting of 'N' integers, and your task is to sort the given array in non-decreasing order using the Heap sort algorithm.

LLD - Design IRCTC - actors, data functions and data members, basic java oops concepts, a problem on concurrency. If there is one ticked available and more than 1 passenger are trying to book seat how will you design your system for such problem

You are given a string S which represents a number. You have to find the smallest number strictly greater than the given number which contains the same set of digits as of the original number i.e the frequency of each digit from 0 to 9 should be exactly the same as in the original number.

For example:

If the given string is 56789, then the next greater number is 56798. Note that although 56790 is also greater than the given number it contains 1 '0' which is not in the original number and also it does not contain the digit '8'.

Note:

The given string is non-empty.

If the answer does not exist, then return -1.

The given number does not contain any leading zeros.