SDE - 1

You are given a linked list containing 'n' 'head' nodes, where every node in the linked list contains two pointers:

(1) ‘next’ which points to the next node in the list

(2) ‘child’ pointer to a linked list where the current node is the head.

Each of these child linked lists is in sorted order and connected by 'child' pointer.

Your task is to flatten this linked such that all nodes appear in a single layer or level in a 'sorted order'.

Input: Given linked list is:

Output:
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 12 → 20 → null.


Explanation:
The returned linked list should be in a sorted order. All the elements in this returned linked list are connected by 'child' pointers and 'next' pointers point to null.

You are given two strings S and X containing random characters. Your task is to find the smallest substring in S which contains all the characters present in X.

Example:

Let S = “abdd” and X = “bd”.

The windows in S which contain all the characters in X are: 'abdd', 'abd', 'bdd', 'bd'. 
Out of these, the smallest substring in S which contains all the characters present in X is 'bd'. 
All the other substring have a length larger than 'bd'.

You have been given two integers ‘N’ and ‘K’. Consider a set ‘X’ of all possible strings of ‘N’ number of digits such that all strings contain digits only in range 0 to ‘K’ inclusive.

For example, If ‘N’ is 2 and ‘K’ is ‘2’ then the set ‘X’ will be-

‘X’ = { 00, 01, 02, 10, 11, 12, 20, 21, 22 }.

Your task is to find a string of minimum possible length such that it contains all strings from set ‘X as any of its substring.

Note:

If there are more than one possible such strings, then you can output any of them.

You have been given a Binary Search Tree of integers. You are supposed to return the k-th (1-indexed) smallest element in the tree.

For example:

For the given binary search tree and k = 3

The 3rd smallest node is highlighted in yellow colour.