Vincent.Y.Guo
BAN USER- 0of 0 votes
AnswersWithin a 2D space, there is a batch of points(no duplicate) in the region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide the region to 2 parts with half points in each .the input will be an array of points and the length of the array.
- Vincent.Y.Guo
struct point{
int x;
int y;
};
input : struct point * points, int length| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm
Yes, that would be helpful.
- Vincent.Y.Guo March 18, 2010void bitreverse(int * arr,int len)
{
int length = len >> 1;
int i=0;
while(i<length)
{
arr[i] = arr[i]^arr[len-i-1];
arr[len-i-1] = arr[len-i-1] ^ arr[i];
arr[i] = arr[i] ^ arr[len-i-1];
i++;
}
}
O(n)
I don't think that would work .
- Vincent.Y.Guo March 10, 2010Actually, I think you can understand this question in another way, which the distance between the most nearest a and b <= distance or not
bool findABWithinDis(string s, char a, char b,int distance)
{
char c;
int firstPos = -1;
if((s.size()>1 )&& (distance < s.size()-2))
{
for(int i=0;i<s.size();i++)
{
if((firstPos > -1)&&(s[i]==c)&&(i-firstPos <=distance))
{
return true;
}
if(s[i] == a)
{
c = b;
firstPos = i;
}
else if(s[i] == b)
{
c = a;
firstPos = i;
}
}
}
return false;
}
and it is O(n).
it means every access to the variable declared by volatile keyword should read the memory address of the variable .
- Vincent.Y.Guo March 06, 2010
what if all points are in the same slope
- Vincent.Y.Guo March 22, 2010