SDE - 1

Suppose we are given an empty string “inputString”. We have to convert this “inputString” into a “Beautiful String”

We can perform any number of operations on “inputString” to convert it to “Beautiful String”.

Operation :

You have to insert “abc” to “inputString” in every operation.
If “inputString” is empty just insert “abc” in “inputString”
If “inputString” is not empty, you can insert “abc” in any position in “inputString” in such a way that:
1. “ LEFT PORTION OF “inputString” ” + “ abc ” + “ RIGHT PORTION OF “inputString” ” = “Beautiful String”.
2. “ LEFT PORTION OF “inputString” ” maybe EMPTY OR “a” OR “ab” OR “abc”.
3. “ LEFT PORTION OF “inputString” ” maybe EMPTY OR “c” OR “bc” OR “abc”.

Your task is to find whether the given string “inputString” is a “Beautiful String”, or not.

Note :

The given string "inputString" cannot be empty.

Your house is located at the origin of a 2-D plane. You have 'N' neighbours who live at 'N' different points on the plane. You want to visit exactly 'K' different neighbours who live closest to your house, you are given a 2 - D matrix 'POINTS'. So, find out the coordinates of the neighbours you are going to visit. The answer is guaranteed to be unique.

Note:

The distance between two points on a plane is the Euclidean Distance.

For Example:

If N = 2, K = 1 and the points are {2,3}, {-1, 2}.

Then the distance of the first point from the origin is sqrt((2 - 0) ^ 2 + (3 - 0) ^ 2) = sqrt(13).

The distance of the second point from the origin is sqrt((-1 - 0) ^ 2 + (2 - 0) ^ 2) = sqrt(5).

Follow Up:

Can you solve this in O(N log K) time complexity?

You are given a string ‘str’ of size ‘N’. Your task is to remove consecutive duplicates from this string recursively.

For example:

If the input string is ‘str’ = ”aazbbby”, then your output will be “azby”.
Note that we are just removing adjacent duplicates.

You are given a sorted array 'ARR' and a number 'X'. Your task is to count the number of occurrences of 'X' in 'ARR'.

Note :

1. If 'X' is not found in the array, return 0.
2. The given array is sorted in non-decreasing order.

You have been given a Binary Tree of 'N' nodes, where the nodes have integer values. Your task is to print the zigzag traversal of the given tree.

Note:

In zigzag order, level 1 is printed from left to right fashion, level 2 is printed from right to left. and level 3 is printed from left to right again, and so on…..

For example:

For the given binary tree

The zigzag  traversal is [1, 4, 3, 5, 2, 7, 6]

For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increasing order.

Strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.

For example:

[1, 2, 3, 4] is a strictly increasing array, while [2, 1, 4, 3] is not.

There are ‘N’ people at a party. Each person has been assigned a unique id between 0 to 'N' - 1(both inclusive). A celebrity is a person who is known to everyone but does not know anyone at the party.

Given a helper function ‘knows(A, B)’, It will returns "true" if the person having id ‘A’ know the person having id ‘B’ in the party, "false" otherwise. Your task is to find out the celebrity at the party. Print the id of the celebrity, if there is no celebrity at the party then print -1.

Note:

1. The helper function ‘knows’ is already implemented for you.
2. ‘knows(A, B)’ returns "false", if A doesn't know B.
3. You should not implement helper function ‘knows’, or speculate about its implementation.
4. You should minimize the number of calls to function ‘knows(A, B)’.
5. There are at least 2 people at the party.
6. At most one celebrity will exist.

You are given an array 'ARR' of N integers. Each integer represents the height of a balloon. So, there are N balloons lined up.

Your aim is to destroy all these balloons. Now, a balloon can only be destroyed if the player shoots its head. So, to do the needful, he/ she shoots an arrow from the left to the right side of the platform, from an arbitrary height he/she chooses. The arrow moves from left to right, at a chosen height ARR[i] until it finds a balloon. The moment when an arrow touches a balloon, the balloon gets destroyed and disappears and the arrow continues its way from left to right at a height decreased by 1. Therefore, if the arrow was moving at height ARR[i], after destroying the balloon it travels at height ARR[i]-1. The player wins this game if he destroys all the balloons in minimum arrows.

You have to return the minimum arrows required to complete the task.