So this blog will be dedicated to all the questions asked in technical rounds of competitive programming. These questions are like bible/gita for programmers you should be aware of these concepts because the solution can be given using hashing only. I would suggest solve these problems using hashing concepts.
Problems are below:
1. Count Non-Repeated Elements
Hashing is very useful to keep track of the frequency of the elements in a list.
You are given an array of integers. You need to print the count of non-repeated elements in the array.
Example 1:
Input:
10
1 1 2 2 3 3 4 5 6 7
Output:
4
Explanation:
4, 5, 6 and 7 are the
elements with frequency 1 and rest
elements are repeated so the number
of non-repeated elements are 4.
2. Print Non-Repeated Elements
Hashing is very useful to keep track of the frequency of the elements in a list.
You are given an array of integers. You need to print the non-repeated elements as they appear in the array.
Example 1:
Input:
n = 10
arr[] = {1,1,2,2,3,3,4,5,6,7}
Output: 4 5 6 7
Explanation: 4, 5, 6 and 7 are the only
elements which is having only 1
frequency and hence, Non-repeating.
3.First Repeating Element
Given an array arr[] of size n, find the first repeating element. The element should occurs more than once and the index of its first occurrence should be the smallest.
Example 1:
Input:
n = 7
arr[] = {1, 5, 3, 4, 3, 5, 6}
Output: 2
Explanation:
5 is appearing twice and
its first appearence is at index 2
which is less than 3 whose first
occuring index is 3.
4.Intersection of two arrays
Given two arrays a[] and b[] respectively of size n and m, the task is to print the count of elements in the intersection (or common elements) of the two arrays.
For this question, the intersection of two arrays can be defined as the set containing distinct common elements between the two arrays.
Example 1:
Input:
n = 5, m = 3
a[] = {89, 24, 75, 11, 23}
b[] = {89, 2, 4}
Output: 1
Explanation:
89 is the only element
in the intersection of two arrays.
5.Union of two arrays
Given two arrays a[] and b[] of size n and m respectively. The task is to find union between these two arrays.
Union of the two arrays can be defined as the set containing distinct elements from both the arrays. If there are repetitions, then only one occurrence of element should be printed in the union.
Example 1:
Input:
5 3
1 2 3 4 5
1 2 3
Output:
5
Explanation:
1, 2, 3, 4 and 5 are the
elements which comes in the union set
of both arrays. So count is 5.
6.Check if two arrays are equal or not
This problem is part of GFG SDE Sheet. Click here to view more.
Given two arrays A and B of equal size N, the task is to find if given arrays are equal or not. Two arrays are said to be equal if both of them contain same set of elements, arrangements (or permutation) of elements may be different though.
Note : If there are repetitions, then counts of repeated elements must also be same for two array to be equal.
Example 1:
Input:
N = 5
A[] = {1,2,5,4,0}
B[] = {2,4,5,0,1}
Output: 1
Explanation: Both the array can be
rearranged to {0,1,2,4,5}
7.Subarray with 0 sum
Given an array of positive and negative numbers. Find if there is a subarray (of size at-least one) with 0 sum.
Example 1:
Input:
5
4 2 -3 1 6
Output:
Yes
Explanation:
2, -3, 1 is the subarray
with sum 0.
8.Winner of an election
Given an array of names (consisting of lowercase characters) of candidates in an election. A candidate name in array represents a vote casted to the candidate. Print the name of candidate that received Max votes. If there is tie, print lexicographically smaller name.
Example 1:
Input:
n = 13
Votes[] = {john,johnny,jackie,johnny,john
jackie,jamie,jamie,john,johnny,jamie,
johnny,john}
Output: john 4
Explanation: john has 4 votes casted for
him, but so does johny. john is
lexicographically smaller, so we print
john and the votes he received.
9.Subarray range with given sum
Given an unsorted array of integers and a sum. The task is to count the number of subarray which adds to the given sum.
Example 1:
Input:
n = 5
arr[] = {10,2,-2,-20,10}
sum = -10
Output: 3
Explanation: Subarrays with sum -10 are:
[10, 2, -2, -20], [2, -2, -20, 10] and
[-20, 10].
10.Positive Negative Pair
Given an array of distinct integers, find all the pairs having both negative and positive values of a number in the array.
Example 1:
Input:
n = 8
arr[] = {1,3,6,-2,-1,-3,2,7}
Output: -1 1 -3 3 -2 2
Explanation: 1, 3 and 2 are present
pairwise positive and negative. 6 and
7 have no pair.
11.Zero Sum Subarrays
You are given an array arr[] of size n. Find the total count of sub-arrays having their sum equal to 0.
Example 1:
Input:
n = 6
arr[] = {0,0,5,5,0,0}
Output: 6
Explanation: The 6 subarrays are
[0], [0], [0], [0], [0,0], and [0,0].
12.Subarrays with equal 1s and 0s
Given an array containing 0s and 1s. Find the number of subarrays having equal number of 0s and 1s.
Example 1:
Input:
n = 7
A[] = {1,0,0,1,0,1,1}
Output: 8
Explanation: The index range for the 8
sub-arrays are: (0, 1), (2, 3), (0, 3), (3, 4),
(4, 5) ,(2, 5), (0, 5), (1, 6)
13.Sort an array according to the other
This problem is part of GFG SDE Sheet. Click here to view more.
Given two integer arrays A1[ ] and A2[ ] of size N and M respectively. Sort the first array A1[ ] such that all the relative positions of the elements in the first array are the same as the elements in the second array A2[ ].
See example for better understanding.
Note: If elements are repeated in the second array, consider their first occurance only.
Example 1:
Input:
N = 11
M = 4
A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}
A2[] = {2, 1, 8, 3}
Output:
2 2 1 1 8 8 3 5 6 7 9
Explanation: Array elements of A1[] are
sorted according to A2[]. So 2 comes first
then 1 comes, then comes 8, then finally 3
comes, now we append remaining elements in
sorted order.
14. Sorting Elements of an Array by Frequency
Medium Accuracy: 47.44% Submissions: 32039 Points: 4
Given an array of integers, sort the array according to frequency of elements. That is elements that have higher frequency come first. If frequencies of two elements are same, then smaller number comes first.
Example 1:
Input:
N = 5
A[] = {5,5,4,6,4}
Output: 4 4 5 5 6
Explanation: The highest frequency here is
2. Both 5 and 4 have that frequency. Now
since the frequencies are same then
smallerelement comes first. So 4 4 comes
firstthen comes 5 5. Finally comes 6.
The output is 4 4 5 5 6.
Note : if you are able to solve these problems then consider your self good for Hashing.
No comments:
Post a Comment