In this post, we are going to solve Kth Occurrence Queries DSA Problem from JP Morgan Chase, Online Assessments conducted on 29th October,2022. Let’s have a look at the problem statement first and then try to solve the problem.
Kth Occurrence Queries DSA Problem Statement
There is an array of integers, arr, and an integer value
. For each element in another array of integers, query_values, return the 1-based index in arr of the query_values[i] occurrence of
. If
does not occur query_values[i] times, return -1 for that query.
Example
arr = [1, 2, 20, 8, 8, 1, 2, 5, 8, 0]
query_values = [100, 4, 2]
There is no 100th or 4th instance of
in arr. The 2nd occurrence is at index 5. Return [-1,-1, 5].
The first line contains
the number of elements in the array. The second line contains
elements separated by space denoting the array arr. The third line contains int
, the integer to search for. The fourth line contains an integer
denoting the length of the query array. The fifth line contains the
integers separated by space denoting query values that is the occurrence of
to find the index of.
int[q]: the index in arr or -1 for each query
10 1 2 4 5 8 8 9 0 9 8 8 3 1000000 2 3
-1 6 10
Problem Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
int x;
cin>>x;
vector<int> pos;
for(int i=0;i<n;i++){
if(a[i]==x){
pos.push_back(i+1);
}
}
int q;
cin>>q;
vector<int> ans;
while(q--){
int id;
cin>>id;
if(id>pos.size()){
ans.push_back(-1);
}
else{
ans.push_back(pos[id-1]);
}
}
for(auto v:ans)cout<<v<<' ';
cout<<'\n';
return 0;
}Problem Solution in Java
import java.util.*;
import java.io.*;
public class Main {
static FastReader in=new FastReader();
static final Random random=new Random();
static long mod=1000000007L;
static HashMap<String,Integer>map=new HashMap<>();
public static void main(String args[]) throws IOException {
int n=in.nextInt();
Map<Integer,Integer> m=new HashMap<>();
int arr[]=in.readintarray(n);
int x=in.nextInt();
int c=1;
for(int i=0;i<n;i++){
if(arr[i]==x){
m.put(c,i+1);
c++;
}
}
int p=in.nextInt();
for(int i=0;i<p;i++){
int t1=in.nextInt();
if(!m.containsKey(t1))System.out.print(-1+" ");
else System.out.print(m.get(t1)+" ");
}
}
static int max(int a, int b)
{
if(a<b)
return b;
return a;
}
static void ruffleSort(int[] a) {
int n=a.length;
for (int i=0; i<n; i++) {
int oi=random.nextInt(n), temp=a[oi];
a[oi]=a[i]; a[i]=temp;
}
Arrays.sort(a);
}
static < E > void print(E res)
{
System.out.println(res);
}
static int gcd(int a,int b)
{
if(b==0)
{
return a;
}
return gcd(b,a%b);
}
static int lcm(int a, int b)
{
return (a / gcd(a, b)) * b;
}
static int abs(int a)
{
if(a<0)
return -1*a;
return a;
}
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
int [] readintarray(int n) {
int res [] = new int [n];
for(int i = 0; i<n; i++)res[i] = nextInt();
return res;
}
long [] readlongarray(int n) {
long res [] = new long [n];
for(int i = 0; i<n; i++)res[i] = nextLong();
return res;
}
}
}