Urik's twin Cookie Monster (dead now)
BAN USERThe map i -> (a+id) is bijective (because it is degree 1 linear map)
So this reduces to the problem of finding the missing element in the sorted array
0 1 2 ... (n-1) <== we only have to discuss this problem hereon
So the method above we're replying to is roughly equal to scanning left to right until we find an element that doesn't match it's index.
But there is a better way, because checking any random index gets us this information:
1) If number _does_ match index, then everything upto that index is "correct", so the problem must be to the right
2) If number does not match index, then something that happened before to the left (or at that point) has an issue
So:
a , a+1d , a+2d , ... , a+(n-1)d and finding missing element looks daunting, but it is reducible (in both ways) to above problem on {0, 1, ..., n-1}
I may be missing something, since the original question is, as usual for careercup standards, was rush typed to save the original poster 30seconds to 1 min. of precious time.
^^^undefined is me
- Urik's twin Cookie Monster (dead now) October 28, 2013No clue what the specific question is. Sounds like a specific arrangement of rectangles, but then there is "n" there too. Sounds like the points are discrete (well for a computer related question it would have to be).
In general:
If we have a set of rectangles (defined with two corner points), to find the area they puncture seems like a tough problem (for me at least) to code in 45 min. (since I have to derive an idea first).
I don't know any well known algorithm off the top of my head, but I know how someone would integrate such areas in math assuming first continuous variables:
1) Integrate the punctured area using Fubini's theorem (iterated integral).
-------------------------------------------------------------------------------------------------
So we either integrate moving left to right on x-axis (or alternatively, move on y-axis).
This reduces the problem to essentially summing up inner 1D integrals.
Something like:
Double Integral{over area}
={using Fubini's theorem, using to do integral over x on outside}
Integral{from leftmost x to rightmost} of Integral{ something we call G(x) }*deltax
G(x) is "sort of" the intersection area of the line at x with the region.
We just need to know the intersection of the vertical line at position x with all the rectangles (so this reduces to 1D union of intervals problem).
To convert this problem to the integer (discrete case), we get:
Area =
SUM(x from leftmost to rightmost) of G(x)*(1) , where deltax = 1
where G(x) refers to union of intervals that intersected the rectangles AT BOTH x-1 and x (because deltax = 1).
I think we can keep updating G(x) with a D.S. and keep adding and removing rectangles into question.
I am rambling but it all boils down to converting double iterated interval to the discrete case (on paper it will make sense).
2) Calculate 2D Double Integral with Green's Theorem
-------------------------------------------------------------------------
Another way to do a 2D double integral is to use Green's theorem instead of Fubini's theorem. To do this, we need to find the sort of "concave" hull of all the corners and intersection points of the rectangles. So basically, all the relevant points in your "punctured" area.
Then we can use green's theorem to go "around" the "relevant" points in the proper order and find the area (we have to do this for the multiple region case which are not necessarily simply connected).
I am not sure if anyone really uses Green's theorem for such problems, if not someone see if it's a slick way and write a paper on it.
No clue what the specific question is. Sounds like a specific arrangement of rectangles, but then there is "n" there too. Sounds like the points are discrete (well for a computer related question it would have to be).
In general:
If we have a set of rectangles (defined with two corner points), to find the area they puncture seems like a tough problem (for me at least) to code in 45 min. (since I have to derive an idea first).
I don't know any well known algorithm off the top of my head, but I know how someone would integrate such areas in math assuming first continuous variables:
1) Integrate the punctured area using Fubini's theorem (iterated integral).
-------------------------------------------------------------------------------------------------
So we either integrate moving left to right on x-axis (or alternatively, move on y-axis).
This reduces the problem to essentially summing up inner 1D integrals.
Something like:
Double Integral{over area}
={using Fubini's theorem, using to do integral over x on outside}
Integral{from leftmost x to rightmost} of Integral{ something we call G(x) }*deltax
G(x) is "sort of" the intersection area of the line at x with the region.
We just need to know the intersection of the vertical line at position x with all the rectangles (so this reduces to 1D union of intervals problem).
To convert this problem to the integer (discrete case), we get:
Area =
SUM(x from leftmost to rightmost) of G(x)*(1) , where deltax = 1
where G(x) refers to union of intervals that intersected the rectangles AT BOTH x-1 and x (because deltax = 1).
I think we can keep updating G(x) with a D.S. and keep adding and removing rectangles into question.
I am rambling but it all boils down to converting double iterated interval to the discrete case (on paper it will make sense).
2) Calculate 2D Double Integral with Green's Theorem
-------------------------------------------------------------------------
Another way to do a 2D double integral is to use Green's theorem instead of Fubini's theorem. To do this, we need to find the sort of "concave" hull of all the corners and intersection points of the rectangles. So basically, all the relevant points in your "punctured" area.
Then we can use green's theorem to go "around" the "relevant" points in the proper order and find the area (we have to do this for the multiple region case which are not necessarily simply connected).
I am not sure if anyone really uses Green's theorem for such problems, if not someone see if it's a slick way and write a paper on it.
Pardon? Are you sure we can create a thread without invoking a system call into Kernel at some point?
fork is a linux/unix system library function to create a new process identical to the calling one
Are you sure spawn means create new thread, instead of fork+exec ?
"pthread_create" creates a new thread on unix/linux
both pthread_create and fork call "clone" on linux (they both require the linux kernel's intervention)
@mit
You see a lot of 'could' and 'should' but I see not one.
I was suggestion improves very concretely.
You can start with the middle if statement.
Then go onto realizing that log_2 is related to pow(2, ) so no need to undo each other.
Then go onto repeating things at the top and bottom of a body of a loop.
Good luck.
Or we can loop from left to right until we find a difference double any other difference.
- Urik's twin Cookie Monster (dead now) October 27, 2013@Anon, Swapnil is right. You aren't propagating truth value up the tree.
bool isValidBST(struct node *root)
{
static struct node *prev = NULL;
if(root==NULL) return true;
if(!isValidBST(root->left) || (prev && root->data<=prev->data)) return false;
prev = root;
return isValidBST(root->right);
}
@Swapnil, Check above please.
- Urik's twin Cookie Monster (dead now) October 27, 2013@micvog, try it on paper
- Urik's twin Cookie Monster (dead now) October 27, 2013@mithya, sorry but the code is not slick.
{All complexities are w.r.t. total value of number}
you seem to be using floating point log function (then using ceil around it), and then using some sort of pow function (floating point?)
and you do each twice inside a loop, at start and end... this is a clear sign that there is redundancy
We can find "the highest set bit" in upper bound log(log(n)) time which will replace your code segments that look like
int NumBits = CEILING(log N);
int NextN = N - pow(2, NumBits)
Then in the middle of your loop you have this
if(NextN == 0)
{
// this means, the number is power of 2, just find trailing 0s and return max
if(NumBits > max)
max = NumBits;
return max;
}
Can you make due without this? Even if you keep this, why do you need to set max then return?
And then at the end of the loop, you repeat the whole "find highest set bit" log/pow statements.
Please try writing a slick for or while loop to replace this.
I rarely downvote, but I am going to downvote this.
The code is inefficiency and a bit messy.
The idea used therein can be done way more efficiency with much cleaner code.
In fact, some of the statements used in the code are not necessary (redundancies exist).
Repgladysloweg, Brokerage clerk at Bell Markets
I am Gladys from Defiance city . I am working as a Brokerage clerk with tasks associated with securities such as ...
If the question is posted in a rush, we answer in a rush (make our own interpretation and solve our own interpretation of the problem). Fair game I think.
- Urik's twin Cookie Monster (dead now) October 28, 2013