tanmaydatta's blog

By tanmaydatta, history, 3 years ago, In English

I am not able to comment on blog: https://codeforces.com/blog/entry/68138

I am not even able to message to the user.

Let me know if someone else is also having some issues. Thanks

Full text and comments »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By tanmaydatta, history, 6 years ago, In English

I recently gave a hiring test and was stuck on a particular problem. The problem is as follows:

You are given an array A of N elements and Q queries of the form L,R.

For every query find the first missing positive integer in the range A[L],A[L+1],A[L+2] ...... A[R].

N <= 10^6

Q <= 10^6

1<= A[i] <= 10^9

I know how to find the first missing positive in O(N) but don't know how to handle multiple queries in less time. Any help would be appreciated. Thanks

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +47
  • Vote: I do not like it