zyfo2
BAN USER- 0of 0 votes
Answersc = ‘a’
- zyfo2 in United States
w = “apple”
c covers w, iff w contains c.
c_set = {‘a’, ‘b’, ‘c’, ‘g’}
w_set = {‘apple’, ‘ibm’, ‘cisco’, ‘google’}
c_set covers w_set, iff every w in w_set is covered by some c in c_set.
Given c_set and w_set, Whether w_set is covered by c_set?
Follow up: if w_set is fixed say a book, how to determine whether a c_set covers this w_set?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures
if it means the max number in a certain interval, then can be done by sorting on the left point, then binary search the right point in the list, and keep the end position for each interval in an array, so in one pass we'll get the result. time complexity o(nlgn) space o(n)
if it means the interval which overlaps most number of intervals, we need sort twice. one is by the left point, the other on the right point. similar idea, just count twice to get each interval's overlapping number. still nlgn
below is the typical dp. and time complexity should be O(n*amount)
int tmp;
int dp[]=new int[amount+1];
for(int s=0;s<amount+1;s++)
for(int i=0;i<quantities.length;i++){
if(s>=quantities[i]) tmp=dp[s-quantities[i]]+price[i];
if(i==0) dp[s]=tmp;
else dp[s]=Math.min(tmp,dp[s]);
}
return dp[amount];
this is similar to the box problem, which asks for putting bigger box under smaller boxes and returning the max height from a list of boxes
use one integer as bit vector to represent the current word
pseudo code:
int maxlength(int bitvector){
max=0;
for(word: list){
if(word contains the previous bit vector){
update the bit vector
if(maxlength(bitvector)>max) update max;}
}
besides use memorizing to reduce duplicates
well, I believe this is a mutation of longest common substring problem.
so given string a, use dp to find the common longest substring of a and itself. but we need to ignore those max values where i==j in dp[i][j]. time complexity still O(length^2)
or surely you can use trie
use a new matrix sum[row][column][2] which represents the sum of left 1s and top 1s
say
1,1,0,1,0
0,1,1,1,0
1,1,1,0,1
1,0,1,1,0
you'll have a new matrix sum[0][0]={1,1} sum[0][1]={2,1}, etc
so you can check from bottom right to top left of this matrix to get the each rectangle's area, and each element will be visited once, which has time complexity O(row*column).
I didn't mean you need to generate all the sequence. instead, you can base on this fact to calculate the bit. say 14, 14-9=5, it means the fifth digit of the two-digit number. 5/2=2, 5%2=1;
so it's the 1st digit of 10+2.
check the code below
public static int res(int x){
int count=2,base=90;
if(x<10) return x;
x-=10;
while(x>=base*count){
x=x-base*count;
count++;
base*=10;}
int res=x/count+base/9;
int s=count-x%count-1;
int bit=(res/((Double)Math.pow(10,s)).intValue())%10;
return bit;
}
my solution won't change the array itself but it still needs O(n) space and run in O(nlogn)
so the idea is to make use of the sorted order of the birth date.
first pass check every death date and binary search in the birth date
say {1,4,2,7,5,8,9,10}
int live[n]
first death date 6,you will find it's larger than 2 but less than 5
then live[2]--;
second death 7,larger than 5, less than 9
then live[3]--;
third death less than 9
live[3]--
then in second pass, live[i]=live[i-1]+live[i]+1;
you'll find the max number
@eugene.yarovoi Ok, I'm not saying there's only one best solution. And I like discussions as long as they are trying to achieve better time and space complexity than the best we know till now. I just mean in the time complexity, the queue solution is the best one, which is O(n) and the best we can do. If your solution runs in O(n), I will say it's also the best we can do. Why don't you post your O(n) time with O(sqrt(windowSize)) space solution? It's surely better in the overall time and space complexity.
- zyfo2 February 03, 2013@S.Abakumoff all right. my bad. I missed the correct solution.
@eugene.yarovoi well, I mean for a typical problem like this, the best one is to use the queue, which I believe is most interveiwers expect. ok, if we don't have O(k) memory, I guess the only way is to compare in every window, which is rarely possible for a interview problem.
if the subtree doesn't require containing all the subnodes
int no=0,max=-1;
node largest;
node largest(node root,int min,int max){
if(root==null){ no=0; return null;}
node l=largest(root.left,min,root.data);
node x=new node(root);
int tmp=no;
x.left=l;
x.right=largest(root.right,root.data,max);
if(root.data<max&&root.data>min){
no=tmp+no+1;
if(no>max) largest=x;
return x;}
no=0;
return null;
}
bottom up recursion
int min,max,no,tempmin,tempmax,largestno=-1;
node largest;
int largest(node root){
if(root==null) return 0;
int l=largest(root.left);
if(l!=-1&&l!=0){ tempmin=min;if(root.data<=max) return -1;}
else if(l==0) tempmin=root.data;
else return -1;
int r=largest(root.right);
if(r!=-1&&r!=0){ tempmax=max;if(root.data>=min) return -1;}
else if(r==0) tempmax=root.data;
else return -1;
min=tempmin;
max=tempmax;
no=1+l+r;
if(no>largestno) largest=root;
return no;
}
I think you can first retrieve two pairs of points with the same distance in the hashtable which contain four distinct points, say ab, cd and their distance is 1. then you just check whether distance of ac, ad, bc, bd are all 1/sqrt(2). so the worst case will be n(n-1)/2 if the values with key==1 has n pairs of points.
- zyfo2 January 31, 2013
I also suspect we can do it in nlgn. like secondary sort
- zyfo2 February 26, 2013sort the R set on the basis of x1,x2,y1,y2 (x1<x2&&y1<y2)which are the edges of rectangle.
to find each point in it, binary search on basis of x, y basically, if x>x2, right=mid-1; else if x<x1 left= mid +1; else {
if y<y1, left=mid+1; else if x>y2 right=mid-1; else return it!}