In this problem, we have given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Write a code to recover binary search tree without changing its structure.
The solution using O(n) space is pretty straight forward. Can you solve this problem using constant space?
Given an array of size n, Write a code to find majority element in an array.
What is Majority Element?
The majority element is the element that appears more than n/2 times where n is the size of an array.
NOTE: For this problem you can assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input : [3, 2, 3]
Output: 3
The size of the array is 3 and the element which occurs more than 1 is the majority element. So three is the output.
Example 2:
Input: [2, 2, 1, 1, 1, 2, 2]
Output: 2
The element 2 occurs more than 3 times. So, It is the majority element.
Find the first non-repeating character in a stream of characters.
Given a string A denoting a stream of lowercase alphabets. We have to write a code to make a new string B.
Here is the rule to form string B.
i) We have to find the first non-repeating character each time a character is inserted into the stream and append it at the end to B.
ii) If no non-repeating character is found then append ‘#’ at the end of B.
For example –
Example 1 –
Input = “abadbc”
Output = “aabbdd”
Explanation:
“a” – From the stream, the first character is a, So at this point, the first non-repeating character is ‘a’.
“ab” – When b comes, Still the first non-repeating character is ‘a’.
“aba” – This time the character is a. Character a is repeated twice so the first non repeating character is ‘b’
“abad” – When character d comes, the first non-repeating character is ‘b’.
“abadb” – When character b comes, its count is 2 now. So the first non-repeating character at this point is ‘d’.
“abadbc” – Next character is c. At this point, the first non-repeating character is ‘d’.