Find Majority Element in an Array

By | | , ,
Leave a comment

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.

→

First Non Repeating Character in a Stream of Characters

By | | , ,
Leave a comment

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’.

→