Question: Amazon, Recently Asked Questions in IIT-H , 11th November, 2022
0
Entering edit mode
ADD COMMENTlink 20 days ago Rohit • 190 • updated 17 days ago Lokesh 230
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
ADD COMMENTlink 18 days ago Ujjwal Srivastava 160
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) >=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) >=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) >=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<int> 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<arr.size()-1){

        index++;

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

        // for 10 sec
        while(arr[sec_10_i] <= arr[index] - 10) sec_10_i++;
        if(index-sec_10_i >= 20) continue;

        // for 1 min
        while(arr[min_i] <= arr[index] - 60) min_i++;
        if(index-min_i >= 60) continue;

        ans++;

    }
    return arr.size()-ans;
}
ADD COMMENTlink 17 days ago Lokesh 230

Login before adding your answer.

Similar Posts
Loading Similar Posts