Analyst

Given an integer ‘N’ representing the number of pairs of parentheses, Find all the possible combinations of balanced parentheses with the given number of pairs of parentheses.

Note :

Conditions for valid parentheses:
1. All open brackets must be closed by the closing brackets.

2. Open brackets must be closed in the correct order.

For Example :

()()()() is a valid parentheses.
)()()( is not a valid parentheses.

Write a program to do basic string compression. For a character which is consecutively repeated more than once, replace consecutive duplicate occurrences with the count of repetitions.

Example:

If a string has 'x' repeated 5 times, replace this "xxxxx" with "x5".
The string is compressed only when the repeated character count is more than 1.

Note:

Consecutive count of every character in the input string is less than or equal to 9. You are not required to print anything. It has already been taken care of. Just implement the given function and return the compressed string.

You have been given an integer array/list(ARR) of size N that contains only integers, 0 and 1. Write a function to sort this array/list. Think of a solution which scans the array/list only once and don't require use of an extra array/list.

Note:

You need to change in the given array/list itself. Hence, no need to return or print anything. 

Ninja is now bored with numbers and is now playing with characters but hates when he gets repeated characters. Ninja is provided a string, and he wants to return the first unique character in the string.The string will contain characters only from the English alphabet set, i.e., ('A' - 'Z') and ('a' - 'z'). If there is no non-repeating character, print the first character of the string. If there is no non-repeating character, return the first character of the string.

Bubble Sort is one of the sorting algorithms that works by repeatedly swapping the adjacent elements of the array if they are not in sorted order.

You are given an unsorted array consisting of N non-negative integers. Your task is to sort the array in non-decreasing order using the Bubble Sort algorithm.

For Example:

Bubble Sort implementation for the given array:  {6,2,8,4,10} is shown below :-

You are given an n-ary tree consisting of ‘N’ nodes. Your task is to return the maximum sum of the path from the root to the leaf node.

For example:

For the given tree:

The path 1 -> 3 -> 7 produces the maximum i.e, 11.

You have been given a Binary Tree of integers. You are supposed to return the level order traversal of the given tree.

For example:

For the given binary tree

The level order traversal will be {1,2,3,4,5,6,7}.

Given a string ‘str’ and a string ‘pat’. The string s has some wildcard characters i.e ‘?’ and ‘*’.

If any character is a ‘?’ we can replace that character with any other character. 

If a character is a * we can replace * with any sequence of characters including the empty sequence.  

Your task is to determine if it is possible that we can make ‘str' = 'pat’ using appropriate conversions in ‘str’.

For example:

Let str = “abc?" and pat= “abcd”

We return true as ‘?’ can be replaced with ‘d’ and this makes ‘str’ and ‘pat’ same.

You are Harshad Mehta’s friend. He told you the price of a particular stock for the next ‘n’ days.

You are given an array ‘prices’ which such that ‘prices[i]’ denotes the price of the stock on the ith day.

You don't want to do more than 2 transactions. Find the maximum profit that you can earn from these transactions.

Note

1. Buying a stock and then selling it is called one transaction.

2. You are not allowed to do multiple transactions at the same time. This means you have to sell the stock before buying it again. 

Example:

Input: ‘n’ = 7, ‘prices’ = [3, 3, 5, 0, 3, 1, 4].

Output: 6

Explanation: 
The maximum profit can be earned by:
Transaction 1: Buying the stock on day 4 (price 0) and then selling it on day 5 (price 3). 
Transaction 2: Buying the stock on day 6 (price 1) and then selling it on day 6 (price 4).
Total profit earned will be (3 - 0) + ( 4 - 1) = 6. 

There are 9 boxes and 36 balls. Can we arrange odd number of balls in every box?

Given an array/list ‘ARR' of size ‘N’, the task is to generate a Complete Binary Tree in such a way that the sum of the non-leaf nodes is minimum, whereas values of the leaf node correspond to the array elements in an In-order Traversal of the tree and value of each non-leaf node corresponds to the product of the largest leaf value in the left sub-tree and right sub-tree.

Example:

Let's say we have an 'ARR' = {1, 2, 3, 4}, so the possible complete 
binary trees will be:
   4                                                          12                      
  /  \                                                       /  \
 1   8                                                      6    4
     / \                                                   /  \
   2   12                                                  2   3   
        /  \                                              /  \
        3   4                                             1   2
  Sum of non-leaf nodes  = 24                    Sum of non-leaf nodes = 20
  So the required answer you have to return is 20.

All the oops concepts were asked. All the collection frameworks were asked and asked me to explain how hashmap works(algorithm). Thread questions were asked and I have no work experience in multi threading and I told the interviewer same and he didn't ask any from multi threading.