Find Majority Element in an Array

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.

Insert Delete GetRandom o(1) Solution

In this problem, We have to design a data structure that supports Insert, Delete, and GetRandom in average O(1) time.

OR

Design a data structure that supports insert, delete, and getRandom in constant time O(1).

insert(value): Inserts an item value to the set if it’s not present.

remove(value): Removes an item value from the set if present.

getRandom(): Returns a random element from current set of elements. Each element must have the same probability of being returned.

Remove Duplicates from Unsorted Array

Given an unsorted array of integers. Write a code to remove duplicates from unsorted array.

For example:

Input   :{5, 1, 2, 6, 4, 4, 5}
Output :{5, 1, 2, 6, 4}

In this example, 4 and 5 appear multiple times in an input array.

In the output, All the duplicates are removed and we have printed only distinct elements of an array.