Hash Map Assignments
1. Most Frequent Element
You have been given an array of elements. You need to return the most frequent
element. In case of more than one element having the same highest frequency, return
the smallest of those elements.
Input Format:
The first line contains an integer n denoting the number of elements in the array.
The second line contains n space-separated integers denoting the elements of the
array.
Output Format:
Print the most frequent element. In case of a tie, print the smallest element among
those with the highest frequency.
Sample Input 1:
9
5 5 5 6 6 6 7 7 8
Sample Output 1:
Constraints:
(1 <=arr.size <=10^5)
(1 <=arr[i] <=10^9)
Note:The function should return the result, and the driver code will handle printing the
output.
class Solution {
public int MostFrequent(int[] arr) {
//Write your code here
}
}
2. Hashmap Implementation
Given an array of integers, your task is to implement a map that stores each number
and its frequency, and then return it.
Input Format:
The first line contains an integer n denoting the number of elements in the array.
The second line contains n space-separated integers denoting the elements of the
array.
Output Format:
Return each number with its frequency in sorted form.
Sample Input 1:
6
1 2 4 1 3 3
Sample Output 1:
[1,2] [2,1] [3,2] [4,1]
Constraints:
(1 <=arr.size<= 10^5)
(1 <=arr[i] <=10^9)
Note:The function should return the result, and the driver code will handle printing the
output. Sorting and formatting of the map is handled by driver code. You do not need to
sort and convert the map to an array in the function.
class Solution {
public Map<Integer, Integer> mapImplementation(int[] arr, int n) {
//Write your code here
}
}
3. Berlogging: The Quest for Victory
In the card game popular in Berland known as "Berlogging," the winner is determined by
a set of rules. If, by the end of the game, only one player has the highest number of
points, they emerge victorious. However, if multiple players share the maximum points,
the situation becomes more complex. Throughout the game, players gain or lose points
during each round.
The points accumulated by each player are recorded in the format "name score," where
"name" represents the player's name and "score" denotes the points gained or lost in
that round, expressed as an integer. Negative scores indicate losses. In cases where
multiple players have the same maximum points (let's call it "m") at the game's
conclusion, the winner is the one who reached at least m points first. Initially, all players
start with 0 points, and it's guaranteed that at least one player will have a positive point
total by the game's end.
Input Format:
The first line contains an integer n (1 ≤ n ≤ 1000), which represents the
number of rounds played.
The next n lines each contain the information about a round in the format "name
score".
Output Format:
Print the name of the winner.
Sample Input 1:
3
mike 3
andrew 5
mike 2
Sample Output 1:
andrew
Explanation 1:
Given the breakdown of the game rounds:
Round 1: mike 3: Mike's score becomes 3.
Round 2: andrew 5: Andrew's score becomes 5.
Round 3: mike 2: Mike's score increases to 5.
At the end of the game:
Mike and Andrew both have the highest score of 5 points. According to the tie-
breaking rule, the winner is the player who reached the maximum score (m = 5)
first. In this case:
Mike reaches 5 points first in Round 3.
Andrew reaches 5 points in Round 2.
Therefore, the correct winner is Andrew, as he achieved the highest score of 5 points
first.
Sample Input 2:
4
alice 10
bob 5
alice -3
bob 10
Sample Output 2:
bob
Explanation 2:
Given the breakdown of the game rounds:
Round 1: alice 10: Alice's score becomes 10.
Round 2: bob 5: Bob's score becomes 5.
Round 3: alice -3: Alice's score becomes 7.
Round 4: bob 10: Bob's score becomes 15.
Bob reaches the highest score of 15 first, so Bob is the winner.
Constraints
(1 <= n <= 1000)
(1 <= name.length <= 32)
(-1000 <= score <= 1000)
Note:The function should return the result, and the driver code will handle printing the
output.
/*class Pair<K, V> {
private K key;
private V value;
// Constructor to initialize a Pair with key and value
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
// Getter method for key
public K getKey() {
return key;
}
// Getter method for value
public V getValue() {
return value;
}
}*/
class Solution {
public String winner(List<Pair<String, Integer>> input, int N) {
}
}
4. Number of subarrays with given sum
Given an array of integers nums and an integer k, your task is to devise an efficient
algorithm that determines the number of subarrays within the given array, where the
sum of elements in each subarray is exactly equal to the given value k.
Note: A subarray is defined as a continuous and non-empty sequence of elements
extracted from the original array.
Input Format:
The first line contains two integers n and k, where n is the number of elements in the
array and k is the target sum.
The second line contains n space-separated integers denoting the elements of the
array.
Output Format: Print the number of subarrays where the sum of elements is equal to k.
Sample Input 1:
5 10
10 1 4 2 3
Sample Output 1:
Explanation 1:
We have two such subarrays where the sum of elements is equal to 10 and they are
{10} and {4, 2, 3, 1}.
Sample Input 2:
6 6
-4 4 3 3 8 -2
Sample Output 2:
Explanation 2:
There are in total 3 subarrays whose sum is equal to 6 and they are {-4, 4, 3, 3}, {3,
3}, and {8, -2}.
Constraints:
(1 <=nums.length <=2 * 10^4)
(-1000 <=nums[i] <=1000)
(1 <=k <=10^7)
Note: The function should return the result, and the driver code will handle printing the
output.
class Solution {
public int findSubarraySum(int[] arr, int n, int sum) {
//Write your code here
}
}
5. Longest Subarray with Equal Number of
0s and 1s
You are given a binary array nums containing only 0s and 1s. You have to find the
length of the longest contiguous subarray with an equal number of 0s and 1s.
Input Format:
The first line contains a single integer n (the size of the array).
The second line contains n integers representing the elements of the array nums,
where each element is either 0 or 1.
Output Format:
Output a single integer, the length of the longest balanced subarray with equal numbers
of 0s and 1s.
Example:
Example 1:
Input:
3
0 1 0
Output:
Explanation:
[0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Example 2:
Input:
7
0 1 1 0 1 1 0
Output:
Explanation:
[0, 1, 1, 0] is the longest contiguous subarray with an equal number of 0 and
1.
Constraints:
1 <= nums.length <= 10^5
nums[i] is either 0 or 1.
Note:The function should return the result.
class Solution {
public int findMaxLength(int[] nums) {
//Write your code here
}
}
