Thanks for all answers. It is very helpful. Here is another link I just found: http://stackoverflow.com/questions/26296624/orderstatisticonintervals
lian5
@lian5
Posts made by lian5

RE: A facebook question from careercup

Need a solution better than O(n^2) for an array related algorithm
I can only get O(n^2) solution for below question. Any better idea?
Given an array of integers you to find the range l (the starting
index) and r (the ending index) such that AND operation of largest two
elements in that range is maximum. For example: Input 8 4 3 1 Output 2
3 You have to print lexicographically smallest range. 
A facebook question from careercup
This is a question from careercup:
You are given a permutation arr[N]. E.g. arr[3] = {2, 1, 0} or arr[5] = {0,1,2,4,3};
Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, kth order statistic on slice [a:b] of arr.
E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it  get [0,1,5] and take kth element, that is  5.Implement request(a, b, k) function. You can preprocess input data, that is, assume there will be only one array and many request() calls.
Among the proposed solutions, I think the best is quickselect ( query time complex: O(ba), space complex: no extra space, preprocessing time complex: none)
I am confused by this questions since there seems no way to improve the query time complex by doing any preprocessing.
Anybody have any insight on how to use preprocessing to improve the query TC? Thanks.

Why my code of wildcard exceed time limit?
Below c# code for wildcard matching exceeds the time limit. Any idea?
public class Solution { public bool IsMatch(string s, string p) { if(s==null  p==null) return false; if(s.Length == 0 && p.Length == 0) return true; if(s.Length != 0 && p.Length == 0) return false; if(s.Length == 0) { for(int i=0; i<p.Length; ++i) { if(p[i] != '*') return false; }; return true; } if(s[0] == p[0]  p[0] == '?') return IsMatch(s.Substring(1), p.Substring(1)); if(p[0] == '*') { int i = 1; while(i<p.Length && p[i]=='*') i++; if(i== p.Length) return true; return IsMatch(s, p.Substring(i))  IsMatch(s.Substring(1), p.Substring(i))  IsMatch(s.Substring(1), p); } return false; } }
The test input is:
"babbbbaabababaabbababaababaabbaabababbaaababbababaaaaaabbabaaaabababbabbababbbaaaababbbabbbbbbbbbbaabbb"
"bbbabbababbbabababbbaaaabbbbba"