Question: Amazon, Recently Asked Questions in IIT-H , 11th November, 2022
0
Entering edit mode

# Question 2

2
Entering edit mode

## Question 1

Overview

• Given a string of lowercase English letters, return the index of the first occurrence of a unique character in the string using 1-based indexing.
• if the string does not contain any unique character return -1.

Solution

• Keep the frequency of each character in a frequency array.
• Now iterate from the start of the string, for each character check its frequency using the frequency array.
• If the frequency of a character is greater than 1, then move on to the next character in the string.
• Else if the frequency of a character is equal to 1, print the answer as the current index( using 1 -based indexing).
• If there is no character with frequency as 1 , the print the answer as -1
1
Entering edit mode

Question 2

`Overview`

• There are n requests given by their request times. There are 3 rules for taking a request to process
• Number of requests processed in any given second is at max `3.`
• Number of requests processed in any 10-second period is at max `20.`
• Number of requests processed in any 60-second period is at max `60.`
• if any processing request violates any of the rules the request is dropped
• We need to find the number of requests dropped.
• This is an implementation Problem

`Approach`

• Sort the requests times(it not sorted )
• Have 3 to two pointer
• Can keep a common right pointer, as it denotes the current index.
• let the time request at the current index `right` be `x`
• `left_1` pointer is for rule 1(1 sec).
• Denotes the index where a request of time `x` started.
• if `(right - left_1) &gt;=3` drop request at `right`
• `left_2` pointer is for rule 2(10 sec).
• Denotes the leftmost index whose request time is greater than `x-10`
• if `(right - left_2) &gt;=20` drop request at `right`
• `left_3` pointer is for rule 2(60 sec).
• Denotes the leftmost index whose request time is greater than `x-60`
• if `(right - left_3) &gt;=60` drop request at `right` -Have a count of non-dropped requests
• Return `arr.size()-count of non dropped requests`

`Complexity:`

• If initially given array is sorted, then `O(N)`
• Else `O(NLOGN)`

`Pseudocode:`

``````int solve(vector&lt;int&gt; arr){
sort(arr.begin(),arr.end());
int ans = 0,current_time=0;
int sec_i = 0,sec_10_i = 0,min_i = 0,index = 0;
while(index&lt;arr.size()-1){

index++;

// for 1 sec
if(arr[sec_i] == arr[index] &amp;&amp; index-sec_i &gt;=3) continue;
else sec_i = index;

// for 10 sec
while(arr[sec_10_i] &lt;= arr[index] - 10) sec_10_i++;
if(index-sec_10_i &gt;= 20) continue;

// for 1 min
while(arr[min_i] &lt;= arr[index] - 60) min_i++;
if(index-min_i &gt;= 60) continue;

ans++;

}
return arr.size()-ans;
}
``````