SDE - Intern

Ninja is given a binary search tree and an integer. Now he is given a particular key in the tree and returns its ceil value. Can you help Ninja solve the problem?

Note:

Ceil of an integer is the closest integer greater than or equal to a given number.
For example:
arr[] = {1, 2, 5, 7, 8, 9}, key = 3.
The closest integer greater than 3 in the given array is 5. So, its ceil value in the given array is 5.

Given a Binary Search Tree (BST) and a range [min, max], remove all keys which are outside the given range. The modified tree should also be BST.

A palindrome string is one that reads the same backward as well as forward.

You are given a string 'str'.

Find the minimum number of characters needed to insert in 'str' to make it a palindromic string.

Example :

Input: 'str' = "abca"

Output: 1

Explanation:
If we insert the character ‘b’ after ‘c’, we get the string "abcba", which is a palindromic string. Please note that there are also other ways possible.

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 are given a Singly Linked List of integers. You need to reverse the Linked List by changing the links between nodes.

Note :

You do not need to print anything, just return the head of the reversed linked list. 

You have to implement the pop function of Max Priority Queue and implement using a heap.

Functions :

a) push(int x) : 'x' has to be inserted in the priority queue. This has been implemented already

b) pop() : return the maximum element in the priority queue, if priority queue is empty then return '-1'.

Example:

We perform the following operations on an empty priority queue:

When operation push(5) is performed, we insert 1 in the priority queue.

When operation push(2) is performed, we insert 2 in the priority queue. 

When operation pop() is performed, we remove the maximum element from the priority queue and print which is 5.

When operation push(3) is performed, we insert 1 in the priority queue.

When operation pop() is performed, we remove the maximum element from the priority queue and print which is 3.

Ninja has to implement an ‘AVL_TREE’ from scratch.

He is given ‘N’ values, representing the values of nodes to be inserted. Ninja has to insert these values into the ‘AVL_TREE’ and return its root after inserting all the nodes.

Note: An ‘AVL_TREE’ is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

For example:

You are given a string 'str' of length 'N'.

Your task is to return the longest palindromic substring. If there are multiple strings, return any.

A substring is a contiguous segment of a string.

For example :

str = "ababc"

The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome. 

There is another palindromic substring of length 3 is "bab". Since starting index of "aba" is less than "bab", so "aba" is the answer.

How do we measure forty-five minutes using two identical wires, each of which takes an hour to burn? We have matchsticks with us. The wires burn non-uniformly. So, for example, the two halves of wire might burn in 10 minutes and 50 minutes respectively.

Questions related to virtual memory and cache implementation.

For a given string(str), remove all the consecutive duplicate characters.

Example:

Input String: "aaaa"
Expected Output: "a"

Input String: "aabbbcc"
Expected Output: "abc"

You are given an array A of length N consisting of positive integers. Your task is to print the maximum subsequence sum such that no three consecutive elements are taken from array A.

Note:

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements

Given a string 'S' of length 'L', return the length of the longest substring without repeating characters.

Example:

Suppose given input is "abacb", then the length of the longest substring without repeating characters will be 3 ("acb").

How many rectangles and squared are there in a chessboard.
 

Design a class of shapes
Some basic OOPs questions, singleton design patterns , cons & des calling seq , dangling objects/pointers , Diamond problem