Task 1: Majority Element
You are given an array of integers @A. Write a script to find the majority element in the list, defined as an element that appears more than floor(size / 2) times. If no such element exists, return -1.
Example Output
Input: @A = (1, 2, 2, 3, 2, 4, 2)
Output: 2
Input: @A = (1, 3, 1, 2, 4, 5)
Output: -1
Logic
Compute the threshold floor(length / 2). Count the frequencies of each element in the array. If any element's count strictly exceeds the threshold, return that element immediately. If no element qualifies after traversing the list, return -1.
Perl Solution
ch-1.pl
sub get_majority_element ($arr) {
return -1 if !@$arr;
my %counts;
my $threshold = int( scalar(@$arr) / 2 );
for my $val (@$arr) {
$counts{$val}++;
return $val if $counts{$val} > $threshold;
}
return -1;
}
Python Solution
ch-1.py
def get_majority_element(arr: list[int]) -> int:
"""Return majority element appearing more than len(arr)//2 times, or -1."""
if not arr:
return -1
counts: dict[int, int] = {}
threshold = len(arr) // 2
for item in arr:
counts[item] = counts.get(item, 0) + 1
if counts[item] > threshold:
return item
return -1
Task 2: FNR Character
You are given a string $S. Write a script to print the series of first non-repeating characters (or # if none) dynamically as characters from the string are processed one by one.
Example Output
Input: $S = "ababc"
Output: "abb#c"
Input: $S = "xyzzyx"
Output: "xyzyx#"
Logic
Maintain a count dictionary and an ordered queue of characters that currently have an occurrence count of 1. As each character arrives, update its frequency count. If it is seen for the first time, append it to the queue; if seen again, remove it from the queue. At each step, the last element in the queue is the current first non-repeating character (or # if the queue is empty).
Perl Solution
ch-2.pl
sub get_fnr ($input) {
return '' if !defined $input || length($input) == 0;
my %fnr_count;
my @fnr_queue;
my $result = '';
for my $char ( split //, $input ) {
$fnr_count{$char}++;
if ( $fnr_count{$char} == 1 ) {
push @fnr_queue, $char;
}
else {
my $pos;
for my $i ( 0 .. $#fnr_queue ) {
if ( $fnr_queue[$i] eq $char ) {
$pos = $i;
last;
}
}
splice @fnr_queue, $pos, 1 if defined $pos;
}
$result .= @fnr_queue ? $fnr_queue[-1] : '#';
}
return $result;
}
Python Solution
ch-2.py
def get_fnr(in_str: str) -> str:
"""Find and return the FNR sequence for the given input string."""
fnr_count: dict[str, int] = {}
fnr_queue: list[str] = []
result = []
for char in in_str:
fnr_count[char] = fnr_count.get(char, 0) + 1
if fnr_count[char] == 1:
fnr_queue.append(char)
elif char in fnr_queue:
fnr_queue.remove(char)
result.append(fnr_queue[-1] if fnr_queue else "#")
return "".join(result)