Fidelity Coding Questions and Answers
Sample Fidelity Coding Questions with Solutions
Here, on this page, you will get the sample Fidelity Coding Questions and Answers along with FAQ’s related to Recruitment Process, Eligibility Criteria and other insights on Job Profile offered by Fidelity.
Go through this page to get all the details related to Fidelity recruitment drive along with the coding questions asked in both online assessment and technical interview of the company.
Sample Fidelity Coding Questions and Answers
Question 1: Find the homeless
Problem Statement -: There are N Homeless people in the community and N houses in the community. It will be given in the array (people), the height of the person, and in the array house capacity of the house is given.
The government decided to give homes to people on the basis of the following conditions:
- Priority is given to the people from left to right of the array
- Each person is allotted to a house if and only if the capacity of the house is greater than or equal to the person’s height
- Nearby empty Houses are allotted to the person( starting from the extreme left)
You need to find the number of homeless people who have not been allotted any home if the government follows the above conditions. So that government will have an idea of how many people they need to allot homes for next time.
Constraints:
- 1 <= N <= 10^3
- 1 <= people[i] <= 10^5
- 1 <= house[i] <= 10^5
Input Format for Custom Testing:
- The first line contains an integer, N, denoting the number of people and number of houses.
- Each line i of the N subsequent lines (where 0 <= i <= N) contains an integer describing peoplei.
- Each line i of the N subsequent lines (where 0 <= i <= N) contains an integer describing housei.
Sample Test Cases
- Sample Input 1
3
4
2
7
3
5
10 - Sample Output 1
0 - Explanation
people=[4,2,7]
house=[3,5,10]
People[0] has more priority , from left to right order in houses 5 is the nearest one which fits for people[0]
people[1]=2 will fit in 3 which is nearer from left
people[2]=7 will fit in remaining house of capacity of 10
So no homeless people left so return 0
- Sample Input 2
3
3
8
5
1
9
4 - Sample Output 2
2 - Explanation
people=[3,8,5]
house=[1,9,4]
people[0]=3 can fit in 9 which is nearest from left in array house
people[1]=8 cannot fit in any home which is left (i.e, 1 and 4)
people[2]=5 cannot fit in any home which is left (i.e, 1 and 4)
So return 2,which is number of homeless people
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int people[n], house[n];
for(int i=0; i<n; i++) cin>>people[i];
for(int i=0; i<n; i++) cin>>house[i];
int count = 0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(people[i]<house[j]){
count+=1 ;
house[j]=-1;
break ;
}
}
}
cout<<n-count;
}
import java.util.*;
class Main
{
public static void main(String args[])
{
Scanner sc = new Scanner (System.in);
int n=sc.nextInt();
int people[]= new int[n];
int house[]= new int[n];
for(int i=0; i<n; i++)
people[i]=sc.nextInt();
for(int i=0; i<n; i++)
house[i]=sc.nextInt();
int count = 0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(people[i]<house[j]){
count+=1 ;
house[j]=-1;
break ;
}
}
}
System.out.println(n-count);
}
}
N=int(input())
people=[]
house=[]
#to read data of people and house arrays
for i in range(N): people.append(int(input()))
for i in range(N): house.append(int(input()))
count=0
for i in range(N):
for j in range(N):
if(people[i] < house[j]):
count+=1
house[j]=-1
break
print(N-count)
Question 2: Simple problem
Problem Statement :
Mr X is a teacher of maths. He came across a very simple problem. In the problem you have to arrange the numbers in an ascending order and calculate the total number of swaps required. The number of swaps must be minimum. But Mr X is busy with some other tasks and you being his favourite student , so he asks you to solve this problem.
Constraints:
1<=T<=100
1<=N<=100
1<=A[ ] <=1000
Examples
Input :
4
4 3 1 2
Output:
2
Explanation: Swap index 0 with 3 and 1 with 2 to form the sorted array {1, 2, 3, 4}.
Input :
5
1 5 4 3 2
Output :
2
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector < int > arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];
vector < pair < int, int >> ap(n);
for (int i = 0; i < n; i++) {
ap[i].first = arr[i];
ap[i].second = i;
}
sort(ap.begin(), ap.end());
vector < bool > v(n, false);
int ans = 0;
for (int i = 0; i < n; i++) { if (v[i] || ap[i].second == 1) continue; int cs = 0, j = i; while (!v[j]) { v[j] = 1; j = ap[j].second; cs++; } if (cs > 0) ans += cs - 1;
}
cout << ans;
}
import java.util.Scanner;
public class Main {
static int minimumSwaps(int[] arr) {
int count = 0;
int i = 0;
while (i < arr.length) {
if (arr[i] != i + 1) {
while (arr[i] != i + 1) {
int temp = 0;
temp = arr[arr[i] - 1];
arr[arr[i] - 1] = arr[i];
arr[i] = temp;
count++;
}
}
i++;
}
return count;
}
public static void main(String[] args) {
Scanner ss = new Scanner(System.in);
int n = ss.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = ss.nextInt();
}
System.out.println(minimumSwaps(arr));
}
}
n = int(input())
ar = list(map(int, input().split()))
arrpos = list(enumerate(ar))
arrpos.sort(key=lambda it: it[1])
vis = {k: False for k in range(n)}
ans = 0
for i in range(n):
if vis[i] or arrpos[i][0] == i:
continue
j = i
cycles = 0
while vis[j] == False:
vis[j] = True
cycles += 1
j = arrpos[j][0]
if cycles > 0:
ans += cycles - 1
print(ans)
Question 3: Queries for Count
The task is to determine the number of elements within a specified range in an unsorted array. Given an array of size n, the goal is to count the elements that fall between two given values, i and j, inclusively.
Examples:
Input:
Array: [1, 3, 3, 9, 10, 4]
Range 1: i = 1, j = 4
Range 2: i = 9, j = 12
Output:
For Range 1: 4
For Range 2: 2
Explanation:
In the first query, the numbers within the range 1 to 4 are 1, 3, 3, and 4.
In the second query, the numbers within the range 9 to 12 are 9 and 10.
#include<bits/stdc++.h>
using namespace std;
int findLowerIndex(int arr[], int n, int x) {
int low = 0, high = n - 1;
while (low <= high) { int mid = (low + high) / 2; if (arr[mid] >= x)
high = mid - 1;
else
low = mid + 1;
}
return low;
}
int findUpperIndex(int arr[], int n, int y) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] <= y)
low = mid + 1;
else
high = mid - 1;
}
return high;
}
int countElementsInRange(int arr[], int n, int x, int y) {
int count = 0;
count = findUpperIndex(arr, n, y) - findLowerIndex(arr, n, x) + 1;
return count;
}
int main() {
int arr[] = {1, 4, 4, 9, 10, 3};
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n);
int lowerRange = 1, upperRange = 4;
cout << countElementsInRange(arr, n, lowerRange, upperRange) << endl;
lowerRange = 9;
upperRange = 12;
cout << countElementsInRange(arr, n, lowerRange, upperRange) << endl;
return 0;
}
def find_lower_index(arr, x):
low, high = 0, len(arr) - 1
while low <= high: mid = (low + high) // 2 if arr[mid] >= x:
high = mid - 1
else:
low = mid + 1
return low
def find_upper_index(arr, y):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] <= y:
low = mid + 1
else:
high = mid - 1
return high
def count_elements_in_range(arr, x, y):
arr.sort()
lower_index = find_lower_index(arr, x)
upper_index = find_upper_index(arr, y)
count = upper_index - lower_index + 1
return count
arr = [1, 4, 4, 9, 10, 3]
lower_range = 1
upper_range = 4
print(count_elements_in_range(arr, lower_range, upper_range))
lower_range = 9
upper_range = 12
print(count_elements_in_range(arr, lower_range, upper_range))
import java.util.Arrays;
class Main {
static int findLowerIndex(int[] arr, int n, int x) {
int low = 0, high = n - 1;
while (low <= high) { int mid = (low + high) / 2; if (arr[mid] >= x)
high = mid - 1;
else
low = mid + 1;
}
return low;
}
static int findUpperIndex(int[] arr, int n, int y) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] <= y)
low = mid + 1;
else
high = mid - 1;
}
return high;
}
static int countElementsInRange(int[] arr, int n, int x, int y) {
int count = 0;
count = findUpperIndex(arr, n, y) - findLowerIndex(arr, n, x) + 1;
return count;
}
public static void main(String[] args) {
int[] arr = {1, 4, 4, 9, 10, 3};
int n = arr.length;
Arrays.sort(arr);
int lowerRange = 1, upperRange = 4;
System.out.println(countElementsInRange(arr, n, lowerRange, upperRange));
lowerRange = 9;
upperRange = 12;
System.out.println(countElementsInRange(arr, n, lowerRange, upperRange));
}
}
Question 4:
Rahul has an array a, consisting of n integers a1, a2, …, an. The boy cannot sit and do nothing, he decided to study an array. Rahul took a piece of paper and wrote out m integers l1, l2, …, lm (1 ≤ li ≤ n). For each number li he wants to know how many distinct numbers are staying on the positions li, li + 1, …, n. Formally, he want to find the number of distinct numbers among ali, ali + 1, …, an.?
Rahul wrote out the necessary array elements but the array was so large and the boy was so pressed for time. Help him, find the answer for the described question for each li.
Input
- The first line contains two integers n and m (1 ≤ n, m ≤ 105). The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 105) — the array elements.
- Next m lines contain integers l1, l2, …, lm. The i-th line contains integer li (1 ≤ li ≤ n).
Output
- Print m lines — on the i-th line print the answer to the number li.
Examples
- Input
10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10 - Output
6
6
6
6
6
5
4
3
2
1
n,m=map(int,input().split())
ar=list(map(int,input().split()))
a=set()
l=[0]*n
for i in range(n-1,-1,-1):
a.add(ar[i])
l[i]=len(a)
#print(l)
for i in range(m):
lx=int(input())
print(l[lx-1])
#include<bits/stdc++.h>
using namespace std;
int main ()
{
int n, m;
cin >> n >> m;
int a[n], b[m];
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
set < int >st;
int check[n] = { 0 };
for (int i = n - 1; i >= 0; i--)
{
st.insert (a[i]);
check[i] = st.size ();
}
for (int i = 0; i < m; i++)
cout << check[b[i] - 1] << endl;
return 0;
}
import java.util.*;
class Main
{
public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
int n = sc.nextInt ();
int m = sc.nextInt ();
int a[] = new int[n];
int l[] = new int[m];
for (int i = 0; i < n; i++)
a[i] = sc.nextInt ();
for (int j = 0; j < m; j++)
l[j] = sc.nextInt ();
int dp[] = new int[n];
HashSet < Integer > s = new HashSet < Integer > ();
for (int i = n - 1; i >= 0; i--)
{
s.add (a[i]);
dp[i] = s.size ();
}
for (int j = 0; j < m; j++)
System.out.println (dp[l[j] - 1]);
}
}
Question 5: Stepping Numbers
Problem Description :
Stepping Numbers are numbers in which the adjacent digits differ by 1. For example, 123, 545, and 98 are stepping numbers, while 321, 444, and 75 are not. The task is to find all stepping numbers in a given range [n, m].
- For example
- Range: [100, 500]
- Stepping Numbers: 101, 121, 123, 210, 212, 232, 234, 321, 323, 343, 345
- Explanation: The stepping numbers between 100 and 500 are 101, 121, 123, 210, 212, 232, 234, 321, 323, 343, and 345. These numbers have adjacent digits that differ by 1.
Write code to find out all the stepping numbers in the given range.
Input Format: First line contains two numbers N,M
Output Format: Print all the stepping numbers present in the range.
Constraints: 0 <= N < M <= 1,000,000,000
#include<bits/stdc++.h>
using namespace std;
void displaySteppingNumbers(int n, int m) {
queue q;
for (int i = 1; i <= 9; i++) { q.push(i); } while (!q.empty()) { int stepNum = q.front(); q.pop(); if (stepNum >= n && stepNum <= m) {
cout << stepNum << " "; } if (stepNum == 0 || stepNum > m) {
continue;
}
int lastDigit = stepNum % 10;
int stepNumA = stepNum * 10 + (lastDigit - 1);
int stepNumB = stepNum * 10 + (lastDigit + 1);
if (lastDigit == 0) {
q.push(stepNumB);
} else if (lastDigit == 9) {
q.push(stepNumA);
} else {
q.push(stepNumA);
q.push(stepNumB);
}
}
}
int main() {
int n, m;
cout << "Enter the range [n, m]: "; cin >> n >> m;
cout << "Stepping Numbers between " << n << " and " << m << ": ";
displaySteppingNumbers(n, m);
return 0;
}
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void displaySteppingNumbers(int n, int m) {
Queue queue = new LinkedList<>();
for (int i = 1; i <= 9; i++) { queue.add(i); } while (!queue.isEmpty()) { int stepNum = queue.poll(); if (stepNum >= n && stepNum <= m) { System.out.print(stepNum + " "); } if (stepNum == 0 || stepNum > m) {
continue;
}
int lastDigit = stepNum % 10;
int stepNumA = stepNum * 10 + (lastDigit - 1);
int stepNumB = stepNum * 10 + (lastDigit + 1);
if (lastDigit == 0) {
queue.add(stepNumB);
} else if (lastDigit == 9) {
queue.add(stepNumA);
} else {
queue.add(stepNumA);
queue.add(stepNumB);
}
}
}
public static void main(String[] args) {
int n = 0, m = 100;
System.out.print("Stepping Numbers between " + n + " and " + m + ": ");
displaySteppingNumbers(n, m);
}
}
def displaySteppingNumbers(n, m):
queue = []
for i in range(1, 10):
queue.append(i)
while queue:
stepNum = queue.pop(0)
if stepNum >= n and stepNum <= m: print(stepNum, end=' ') if stepNum == 0 or stepNum > m:
continue
lastDigit = stepNum % 10
stepNumA = stepNum * 10 + (lastDigit - 1)
stepNumB = stepNum * 10 + (lastDigit + 1)
if lastDigit == 0:
queue.append(stepNumB)
elif lastDigit == 9:
queue.append(stepNumA)
else:
queue.append(stepNumA)
queue.append(stepNumB)
n = 0
m = 100
print("Stepping Numbers between", n, "and", m, ": ", end='')
displaySteppingNumbers(n, m)
Question 6: Sort array after converting elements to their squares
Problem Description :
You are given an array of integers in non-decreasing order. Your task is to sort the array after converting each element to its square.
Write a function ‘sortArrayAfterSquaring’ that takes an array of integers as input and returns the sorted array after converting each element to its square.
- For example
- Input: [1, 2, 3, 4, 5]
- Output: [1, 4, 9, 16, 25]
- Explanation:
In this example, the input array is [1, 2, 3, 4, 5]. After squaring each element, we get [1, 4, 9, 16, 25]. The resulting array is then sorted in ascending order, which gives [1, 4, 9, 16, 25]. Finally, the sorted array is printed.
Input Format: Given an sorted array containing positive and negative numbers.
Output Format: Print the sorted array containing the squares of the numbers.
#include<bits/stdc++.h>
void squareSort(std::vector& arr) {
// Calculate squares of each element
for (int i = 0; i < arr.size(); i++) {
arr[i] = arr[i] * arr[i];
}
// Sort the array in ascending order
std::sort(arr.begin(), arr.end());
}
int main() {
std::vector arr = {4, 2, 1, 3, 5};
std::cout << "Original Array: ";
for (int i = 0; i < arr.size(); i++) {
std::cout << arr[i] << " ";
}
squareSort(arr);
std::cout << "\nSorted Array after Squaring: ";
for (int i = 0; i < arr.size(); i++) {
std::cout << arr[i] << " ";
}
return 0;
}
import java.util.Arrays;
public class Main {
public static void squareSort(int[] arr) {
// Calculate squares of each element
for (int i = 0; i < arr.length; i++) {
arr[i] = arr[i] * arr[i];
}
// Sort the array in ascending order
Arrays.sort(arr);
}
public static void main(String[] args) {
int[] arr = {4, 2, 1, 3, 5};
System.out.print("Original Array: ");
for (int num : arr) {
System.out.print(num + " ");
}
squareSort(arr);
System.out.print("\nSorted Array after Squaring: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
def square_sort(arr):
# Calculate squares of each element
arr = [num**2 for num in arr]
# Sort the list in ascending order
arr.sort()
return arr
arr = [4, 2, 1, 3, 5]
print("Original List:", arr)
arr_sorted = square_sort(arr)
print("Sorted List after Squaring:", arr_sorted)
Question 7: EMI Options
Problem Description
Question – : There are two banks – Bank A and Bank B. Their interest rates vary. You have received offers from both banks in terms of the annual rate of interest, tenure, and variations of the rate of interest over the entire tenure.You have to choose the offer which costs you least interest and reject the other. Do the computation and make a wise choice.
The loan repayment happens at a monthly frequency and Equated Monthly Installment (EMI) is calculated using the formula given below :
EMI = loanAmount * monthlyInterestRate / ( 1 – 1 / (1 + monthlyInterestRate)^(numberOfYears * 12))
Constraints:
- 1 <= P <= 1000000
- 1 <=T <= 50
- 1<= N1 <= 30
- 1<= N2 <= 30
Input Format:
- First line: P principal (Loan Amount)
- Second line: T Total Tenure (in years).
- Third Line: N1 is the number of slabs of interest rates for a given period by Bank A. First slab starts from the first year and the second slab starts from the end of the first slab and so on.
- Next N1 line will contain the interest rate and their period.
- After N1 lines we will receive N2 viz. the number of slabs offered by the second bank.
- Next N2 lines are the number of slabs of interest rates for a given period by Bank B. The first slab starts from the first year and the second slab starts from the end of the first slab and so on.
- The period and rate will be delimited by single white space.
Output Format: Your decision either Bank A or Bank B.
Explanation:
- Example 1
- Input
- 10000
- 20
- 3
- 5 9.5
- 10 9.6
- 5 8.5
- 3
- 10 6.9
- 5 8.5
- 5 7.9
- Output: Bank B
- Example 2
- Input
- 500000
- 26
- 3
- 13 9.5
- 3 6.9
- 10 5.6
- 3
- 14 8.5
- 6 7.4
- 6 9.6
- Output: Bank A
#include<bits/stdc++.h>
using namespace std;
int main()
{
double p,s,mi,sum,emi,bank[5],sq;
int y,n,k,i,yrs,l=0;
cin>>p;
cin>>y;
for(k=0;k<2;k++) { cin>>n;
sum=0;
for(i=0;i<n;i++) { cin>>yrs;
cin>>s;
mi=0;
sq=pow((1+s),yrs*12);
emi= (p*(s))/(1-1/sq);
sum= sum + emi;
}
bank[l++]=sum;
}
if(bank[0]<bank[1])
cout<<("Bank A");
else
cout<<("Bank B");
return 0;
}
Output 10000 20 3 5 9.5 10 9.6 5 8.5 3 10 6.9 5 8.5 5 7.9 Bank B
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); double p,s,mi,sum,emi,sq; int y,n,k,yrs,l=0; double[] bank = new double[5]; System.out.println("Enter the principal amount"); p = sc.nextDouble(); System.out.println("Enter tenature year"); y = sc.nextInt(); for (k = 0; k < 2; k++) { System.out.println("Enter the no of slabs"); n = sc.nextInt(); sum=0; for (int i = 0; i < n; i++) { System.out.println("Enter the period :"); yrs = sc.nextInt(); System.out.println("Enter the interest :"); s = sc.nextDouble(); mi=0; sq=Math.pow((1+s), yrs*12); emi=(p*(s))/(1-1/sq); sum=sum+emi; } bank[l++]=sum; } if(bank[0]<bank[1]) System.out.println("Bank A"); else System.out.println("Bank B"); } }
Output 10000 20 3 5 9.5 10 9.6 5 8.5 3 10 6.9 5 8.5 5 7.9 Bank B
bank = [] principal = int(input()) year = int(input() for i in range(0, 2): # 2 Banks installments = int(input()) sum = 0 for i in range(0, installments): time, roi = [float(i) for i in input().split()] square = pow((1+roi), time*12) emi = (principal*(roi)/(1-1/square)) sum = sum + emi bank.append(sum) if bank[0] < bank[1]: print("Bank A") else: print("Bank B")
Output: 10000 20 3 5 9.5 10 9.6 5 8.5 3 10 6.9 5 8.5 5 7.9 Bank B
Question 8: Nearest smaller Tower
Given an array representing the heights of towers, the task is to find, for each tower, the index of the nearest tower that is shorter than it.
The search for a shorter tower can be performed by looking to the left and right sides of each tower.
The following rules apply:
If there are two or more smaller towers at the same distance from the current tower, choose the tower with the smallest height.
If two towers have the same height, choose the one with the smaller index.
Example 1:
Input : Array: [1, 3, 2]
Output : Indexes: [-1, 0, 0]
Explanation:
For the tower at index 0, there is no tower shorter than it, so the output is -1.
For the tower at index 1 (height 3), there are two towers (heights 1 and 2) at the same distance. Following the rules, we choose the tower with the smallest height, which is at index 0.
For the tower at index 2 (height 2), the only tower shorter than it is at index 0.
Therefore, the final output is the array of indexes: [-1, 0, 0].
Example 2:
Input : Array : [4, 8, 3, 5, 3]
Output : Indexes: [2, 2, -1, 2, -1]
Explanation:
For the tower at index 0 (height 4), the nearest tower shorter than it is at index 2.
For the tower at index 1 (height 8), there are two towers (heights 4 and 3) at the same distance.
Following the rules, we choose the tower at index 2.
For the tower at index 2 (height 3), there is no tower shorter than it.
For the tower at index 3 (height 5), there are two towers (heights 3 and 3) at the same distance.
Following the rules, we choose the tower at index 2 because it has a smaller index.
For the tower at index 4 (height 3), there is no tower shorter than it.
Therefore, the final output is the array of indexes: [2, 2, -1, 2, -1].
#include<bits/stdc++.h>
class TowerFinder
{
public:
std::vector findNearestShorterTower(std::vector &towerHeights)
{
int n = towerHeights.size();
std::stack leftStack, rightStack;
std::vector result(n, -1);
for (int i = 0; i < n; i++) { while (!leftStack.empty() && towerHeights[leftStack.top()] >= towerHeights[i])
{
leftStack.pop();
}
if (!leftStack.empty())
{
result[i] = leftStack.top();
}
leftStack.push(i);
}
for (int i = n - 1; i >= 0; i--)
{
while (!rightStack.empty() && towerHeights[rightStack.top()] >= towerHeights[i])
{
rightStack.pop();
}
if (!rightStack.empty())
{
if (result[i] != -1)
{
if (std::abs(result[i] - i) == std::abs(rightStack.top() - i))
{
if (towerHeights[result[i]] > towerHeights[rightStack.top()])
result[i] = rightStack.top();
}
else if (std::abs(result[i] - i) > std::abs(rightStack.top() - i))
result[i] = rightStack.top();
}
else
result[i] = rightStack.top();
}
rightStack.push(i);
}
return result;
}
};
int main()
{
std::vector towerHeights = {4,8,3,5,3};
TowerFinder towerFinder;
std::vector nearestShorterTowers = towerFinder.findNearestShorterTower(towerHeights);
// Print the result
for (int i = 0; i < nearestShorterTowers.size(); i++)
{
std::cout << nearestShorterTowers[i] << " ";
}
std::cout << std::endl;
return 0;
}
class TowerFinder:
def find_nearest_shorter_tower(self, arr):
suff = []
n = len(arr)
find_suff = [0] * n # building suffix
for i in range(n - 1, -1, -1):
if len(suff) == 0:
find_suff[i] = -1
suff.append([arr[i], i])
else:
while suff:
if suff[-1][0] < arr[i]:
find_suff[i] = suff[-1][1]
break
suff.pop()
if len(suff) == 0:
find_suff[i] = -1
suff.append([arr[i], i])
pre = []
find_pre = [0] * n # building prefix
for i in range(n):
if len(pre) == 0:
find_pre[i] = -1
pre.append([arr[i], i])
else:
while pre:
if pre[-1][0] < arr[i]: find_pre[i] = pre[-1][1] break pre.pop() if len(pre) == 0: find_pre[i] = -1 pre.append([arr[i], i]) new = [0] * n # comparing both for i in range(n): if find_suff[i] == -1: new[i] = find_pre[i] continue if find_pre[i] == -1: new[i] = find_suff[i] continue if abs(find_suff[i] - i) == abs(find_pre[i] - i): if arr[find_suff[i]] >= arr[find_pre[i]]:
new[i] = find_pre[i]
else:
new[i] = find_suff[i]
elif abs(find_suff[i] - i) > abs(find_pre[i] - i):
new[i] = find_pre[i]
else:
new[i] = find_suff[i]
return new
# Test the code
tower_heights = [1, 3, 2]
tower_finder = TowerFinder()
nearest_shorter_towers = tower_finder.find_nearest_shorter_tower(tower_heights)
# Print the result
print(nearest_shorter_towers)
import java.util.*;
class Main {
public static int[] findNearestShorterTower(int[] towerHeights) {
int n = towerHeights.length;
Stack leftStack = new Stack<>();
Stack rightStack = new Stack<>();
int[] result = new int[n];
Arrays.fill(result, -1);
for (int i = 0; i < n; i++) { while (!leftStack.empty() && towerHeights[leftStack.peek()] >= towerHeights[i]) {
leftStack.pop();
}
if (!leftStack.empty()) {
result[i] = leftStack.peek();
}
leftStack.push(i);
}
for (int i = n - 1; i >= 0; i--) {
while (!rightStack.empty() && towerHeights[rightStack.peek()] >= towerHeights[i]) {
rightStack.pop();
}
if (!rightStack.empty()) {
if (result[i] != -1) {
if (Math.abs(result[i] - i) == Math.abs(rightStack.peek() - i)) {
if (towerHeights[result[i]] > towerHeights[rightStack.peek()]) {
result[i] = rightStack.peek();
}
} else if (Math.abs(result[i] - i) > Math.abs(rightStack.peek() - i)) {
result[i] = rightStack.peek();
}
} else {
result[i] = rightStack.peek();
}
}
rightStack.push(i);
}
return result;
}
public static void main(String[] args) {
int[] towerHeights = {4,8,3,5,3};
int[] nearestShorterTowers = findNearestShorterTower(towerHeights);
// Print the result
for (int i = 0; i < nearestShorterTowers.length; i++) {
System.out.print(nearestShorterTowers[i] + " ");
}
System.out.println();
}
}
Question 9: Match Substring After Replacement
Given two strings, s, and sub, along with a 2D character array mappings, we want to determine if it is possible to make the sub a substring of s by replacing characters according to the provided mappings. Each mapping consists of a pair [oldi, newi], indicating that we can replace the character oldi in sub with newi.
The replacement can be performed any number of times, but each character in sub can be replaced at most once.
We need to return true if it is possible to create sub as a substring of s using the given replacements, and false otherwise.
Example 1:
Input:
s = “fool3e7bar”
sub = “leet”
mappings = [[“e”,”3″],[“t”,”7″],[“t”,”8″]]
Output: True
Explanation:
We replace the first occurrence of ‘e’ in sub with ‘3’ and ‘t’ in sub with ‘7’, resulting in sub becoming “l3e7”. Now, “l3e7” is a substring of s, so we return true.
Example 2:
Input:
s = “fooleetbar”
sub = “f00l”
mappings = [[“o”,”0″]]
Output: False
Explanation:
The string “f00l” is not a substring of s, and no replacements can be made to create it. Additionally, we cannot replace ‘0’ with ‘o’, so it is not possible to create sub from s. Hence, we return false.
Example 3:
Input:
s = “Fool33tbaR”
sub = “leetd”
mappings = [[“e”,”3″],[“t”,”7″],[“t”,”8″],[“d”,”b”],[“p”,”b”]]
Output: True
Explanation:
We replace the first and second occurrences of ‘e’ in sub with ‘3’ and ‘d’ in sub with ‘b’, respectively. This transforms sub into “l33tb”, which is a substring of s. Therefore, we return true.
Constraints:
1 <= sub.length <= s.length <= 5000
0 <= mappings.length <= 1000
mappings[i].length == 2
oldi != newi
Both s and sub consist of uppercase and lowercase English letters and digits.
oldi and newi are either uppercase or lowercase English letters or digits.
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
vector compute_lps(string& s, unordered_map<char, unordered_set>& m) {
vector lps(s.size());
for (int i = 1, j = 0; i < s.size(); ++i) {
while (j && (s[i] != s[j] && m[s[i]].count(s[j]) == 0 && m[s[j]].count(s[i]) == 0))
j = max(0, lps[j] - 1);
j += s[i] == s[j] || m[s[i]].count(s[j]) || m[s[j]].count(s[i]);
lps[i] = j;
}
return lps;
}
bool matchReplacement(string s, string sub, vector<vector>& mappings) {
unordered_map<char, unordered_set> m;
for (auto& p : mappings)
m[p[0]].insert(p[1]);
auto lps = compute_lps(sub, m);
for (int i = 0, j = 0; i < s.size();) {
if (s[i] == sub[j] || m[sub[j]].count(s[i])) {
++i;
++j;
} else {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
if (j == sub.size())
return true;
}
return false;
}
};
int main() {
Solution solution;
// Example usage:
// string s = "fool3e7bar";
// string sub = "leet";
// vector<vector> mappings = {{'e','3'}, {'t','7'}, {'t','8'}};
// string s = "fooleetbar";
// string sub = "f00l";
// vector<vector> mappings = {{'o','0'}};
string s = "Fool33tbaR";
string sub = "leetd";
vector<vector> mappings = {{'e','3'}, {'t','7'}, {'t','8'}, {'d','b'}, {'p','b'}};
bool result = solution.matchReplacement(s, sub, mappings);
cout << boolalpha << result << endl; // Output: true
return 0;
}
class Solution:
def compute_lps(self, s, m):
lps = [0] * len(s)
j = 0
for i in range(1, len(s)):
while j > 0 and (s[i] != s[j] and (s[i] not in m or s[j] not in m[s[i]])):
j = lps[j - 1]
j += int(s[i] == s[j] or (s[i] in m and s[j] in m[s[i]]))
lps[i] = j
return lps
def matchReplacement(self, s, sub, mappings):
m = {}
for p in mappings:
if p[0] not in m:
m[p[0]] = set()
m[p[0]].add(p[1])
lps = self.compute_lps(sub, m)
i, j = 0, 0
while i < len(s):
if s[i] == sub[j] or (sub[j] in m and s[i] in m[sub[j]]):
i += 1
j += 1
else:
if j != 0:
j = lps[j - 1]
else:
i += 1
if j == len(sub):
return True
return False
solution = Solution()
# Example usage:
s = "fool3e7bar"
sub = "leet"
mappings = [['e', '3'], ['t', '7'], ['t', '8']]
# s = "fooleetbar"
# sub = "f00l"
# mappings = [['o', '0']]
# s = "Fool33tbaR"
# sub = "leetd"
# mappings = [['e', '3'], ['t', '7'], ['t', '8'], ['d', 'b'], ['p', 'b']]
result = solution.matchReplacement(s, sub, mappings)
print(result) # Output: True
class Main {
public boolean matchReplacement(String s, String sub, char[][] mappings) {
int m = sub.length(), n = s.length();
final int RANGE = 'z' - '0' + 1;
boolean[][] multiMap = new boolean[RANGE][RANGE];
for (char[] map : mappings) {
char from = map[0], to = map[1];
multiMap[from - '0'][to - '0'] = true;
}
// Now, we use a naive string matching algorithm
// This will run in O(mn) time.
for (int i = 0; i < n - m + 1; i++) {
int j = 0;
while (j < m) {
char sc = s.charAt(i + j), subc = sub.charAt(j);
if (sc != subc && !multiMap[subc - '0'][sc - '0'])
break;
j++;
}
if (j == m)
return true;
}
return false;
}
public static void main(String[] args) {
Main main = new Main();
// Example usage:
// String s = "fool3e7bar";
// String sub = "leet";
// char[][] mappings = { { 'e', '3' }, { 't', '7' }, { 't', '8' } };
// String s = "fooleetbar";
// String sub = "f00l";
// char[][] mappings = { { 'o', '0' } };
String s = "Fool33tbaR";
String sub = "leetd";
char[][] mappings = { { 'e', '3' }, { 't', '7' }, { 't', '8' }, { 'd', 'b' }, { 'p', 'b' } };
boolean result = main.matchReplacement(s, sub, mappings);
System.out.println(result); // Output: true
}
}
Question 10: Nearest smaller Tower
Given an array representing the heights of towers, the task is to find, for each tower, the index of the nearest tower that is shorter than it.
The search for a shorter tower can be performed by looking to the left and right sides of each tower.
The following rules apply:
If there are two or more smaller towers at the same distance from the current tower, choose the tower with the smallest height.
If two towers have the same height, choose the one with the smaller index.
Example 1:
Input : Array: [1, 3, 2]
Output : Indexes: [-1, 0, 0]
Explanation:
For the tower at index 0, there is no tower shorter than it, so the output is -1.
For the tower at index 1 (height 3), there are two towers (heights 1 and 2) at the same distance. Following the rules, we choose the tower with the smallest height, which is at index 0.
For the tower at index 2 (height 2), the only tower shorter than it is at index 0.
Therefore, the final output is the array of indexes: [-1, 0, 0].
Example 2:
Input : Array : [4, 8, 3, 5, 3]
Output : Indexes: [2, 2, -1, 2, -1]
Explanation:
For the tower at index 0 (height 4), the nearest tower shorter than it is at index 2.
For the tower at index 1 (height 8), there are two towers (heights 4 and 3) at the same distance.
Following the rules, we choose the tower at index 2.
For the tower at index 2 (height 3), there is no tower shorter than it.
For the tower at index 3 (height 5), there are two towers (heights 3 and 3) at the same distance.
Following the rules, we choose the tower at index 2 because it has a smaller index.
For the tower at index 4 (height 3), there is no tower shorter than it.
Therefore, the final output is the array of indexes: [2, 2, -1, 2, -1].
#include<bits/stdc++.h>
class TowerFinder
{
public:
std::vector findNearestShorterTower(std::vector &towerHeights)
{
int n = towerHeights.size();
std::stack leftStack, rightStack;
std::vector result(n, -1);
for (int i = 0; i < n; i++) { while (!leftStack.empty() && towerHeights[leftStack.top()] >= towerHeights[i])
{
leftStack.pop();
}
if (!leftStack.empty())
{
result[i] = leftStack.top();
}
leftStack.push(i);
}
for (int i = n - 1; i >= 0; i--)
{
while (!rightStack.empty() && towerHeights[rightStack.top()] >= towerHeights[i])
{
rightStack.pop();
}
if (!rightStack.empty())
{
if (result[i] != -1)
{
if (std::abs(result[i] - i) == std::abs(rightStack.top() - i))
{
if (towerHeights[result[i]] > towerHeights[rightStack.top()])
result[i] = rightStack.top();
}
else if (std::abs(result[i] - i) > std::abs(rightStack.top() - i))
result[i] = rightStack.top();
}
else
result[i] = rightStack.top();
}
rightStack.push(i);
}
return result;
}
};
int main()
{
std::vector towerHeights = {4,8,3,5,3};
TowerFinder towerFinder;
std::vector nearestShorterTowers = towerFinder.findNearestShorterTower(towerHeights);
// Print the result
for (int i = 0; i < nearestShorterTowers.size(); i++)
{
std::cout << nearestShorterTowers[i] << " ";
}
std::cout << std::endl;
return 0;
}
class TowerFinder:
def find_nearest_shorter_tower(self, arr):
suff = []
n = len(arr)
find_suff = [0] * n # building suffix
for i in range(n - 1, -1, -1):
if len(suff) == 0:
find_suff[i] = -1
suff.append([arr[i], i])
else:
while suff:
if suff[-1][0] < arr[i]:
find_suff[i] = suff[-1][1]
break
suff.pop()
if len(suff) == 0:
find_suff[i] = -1
suff.append([arr[i], i])
pre = []
find_pre = [0] * n # building prefix
for i in range(n):
if len(pre) == 0:
find_pre[i] = -1
pre.append([arr[i], i])
else:
while pre:
if pre[-1][0] < arr[i]: find_pre[i] = pre[-1][1] break pre.pop() if len(pre) == 0: find_pre[i] = -1 pre.append([arr[i], i]) new = [0] * n # comparing both for i in range(n): if find_suff[i] == -1: new[i] = find_pre[i] continue if find_pre[i] == -1: new[i] = find_suff[i] continue if abs(find_suff[i] - i) == abs(find_pre[i] - i): if arr[find_suff[i]] >= arr[find_pre[i]]:
new[i] = find_pre[i]
else:
new[i] = find_suff[i]
elif abs(find_suff[i] - i) > abs(find_pre[i] - i):
new[i] = find_pre[i]
else:
new[i] = find_suff[i]
return new
# Test the code
tower_heights = [1, 3, 2]
tower_finder = TowerFinder()
nearest_shorter_towers = tower_finder.find_nearest_shorter_tower(tower_heights)
# Print the result
print(nearest_shorter_towers)
import java.util.*;
class Main {
public static int[] findNearestShorterTower(int[] towerHeights) {
int n = towerHeights.length;
Stack leftStack = new Stack<>();
Stack rightStack = new Stack<>();
int[] result = new int[n];
Arrays.fill(result, -1);
for (int i = 0; i < n; i++) { while (!leftStack.empty() && towerHeights[leftStack.peek()] >= towerHeights[i]) {
leftStack.pop();
}
if (!leftStack.empty()) {
result[i] = leftStack.peek();
}
leftStack.push(i);
}
for (int i = n - 1; i >= 0; i--) {
while (!rightStack.empty() && towerHeights[rightStack.peek()] >= towerHeights[i]) {
rightStack.pop();
}
if (!rightStack.empty()) {
if (result[i] != -1) {
if (Math.abs(result[i] - i) == Math.abs(rightStack.peek() - i)) {
if (towerHeights[result[i]] > towerHeights[rightStack.peek()]) {
result[i] = rightStack.peek();
}
} else if (Math.abs(result[i] - i) > Math.abs(rightStack.peek() - i)) {
result[i] = rightStack.peek();
}
} else {
result[i] = rightStack.peek();
}
}
rightStack.push(i);
}
return result;
}
public static void main(String[] args) {
int[] towerHeights = {4,8,3,5,3};
int[] nearestShorterTowers = findNearestShorterTower(towerHeights);
// Print the result
for (int i = 0; i < nearestShorterTowers.length; i++) {
System.out.print(nearestShorterTowers[i] + " ");
}
System.out.println();
}
}
FAQs related to Fidelity Coding Questions and Answers
Question 1: How many rounds is a fidelity interview?
In Fidelity, 1 Technical Interview and 1 HR Interview is conducted to hire freshers.
Question 2: What is the Fidelity Recruitement Process ?
Fidelity Recruitment Process involves 3 steps: Online Assessement (Aptitude + Technical ) followed by Technical Interview and HR Interview.
Question 3: What is the eligibility criteria for Fidelity ?
- Course: BE/ B.Tech/MCA
- Score: Minimum 60% or 6.5 GPA and above in 10th,12th, Graduation and without any active backlogs.
