hirajhil
BAN USER- 3of 3 votes
AnswersYou have a lists with integers. Find all the pairs of numbers that sum less than or equal to to a particular number k. The list contains minimum 5 Million number.
- hirajhil in United States
(I provided a n^2logn solution but they may be looking forward to having a better answer).| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm
It's just a buffering problem like online streaming. The time required to generate unique ids may be more than per request time. So if we know request rate we can learn what is the gap, and how many unique ids required to fillup that gap. Then we can use a buffer to make generate unique ids ahead, and give ids from that buffer, at the same time we continue generating ids and storing on buffer.
- hirajhil January 29, 2014just XOR the bit positions, if its a 0 then we have a successful predictions. You can have two byte arrays in java. Initially all are zero and after that for each number of tournaments shift 1 to the number to the left and make an AND and test that corresponding bit.
- hirajhil January 29, 2014I have a solution O(n^2) though for a larger number of rectangles it may not work.
simply add a boundary check whether a particular point falls in that boundary.
boolean boundary(Rec r,point p)
{
if(p.x>=r.p1.x &&p.x<=r.p2.x&&p.y<=r.p1.y&&p.y>=r.p3.y)return true;
return false;
}
now for each rectangle save them in a list while saving just check whether any of them falls within the boundary of any other in the already existing list.
the boundary check is an O(1) operation and for each element t we are checking (t-1) elements. O(n^2) operations.
here is the algorithm
switch means making 0 to 1 and 1 to zero
for next highest
------------------------
switch the lowest bit with value 0 (let it be position n) and the lowest 1 on the right side of the switched 0.
then just minimize the rest of the bits after position n.
for next lowest
---------------------
switch the highest 0 (let the position be n) and the left 1. now maximize all the bits after nth position.
minimize
---------------
switch the highest 1 (let it be position n) and lowest 0. continue to do so after n until no such is possible.
maximize
-------------
switch the highest 0 (let it be position n) and lowest 1. continue to do so after n until no such is possible.
can anyone put an efficient c or java code with this algorithm?
if we convert it to some binary string we can manipulate string easily.
just like
Integer.toBinaryString(int i)
but if anyone knows to do it by bit maniulation please share.
- hirajhil January 26, 2014there is no need to use the stack, just push the nested element between current node and next node. something like,
tempNode=curnode->nextNode;
curNode->nextNode=curNode->nestedNode;
curNode->nextNode=tempNode;
btw I assumed that the linked list will not need to be the same after print. otherwise we always can use a single node entry as a exchange space instead of a stack. It will be initialized with null.
exchangeNode=null;
then in the iterator
whenever we wanna print a value
if(!exchangeNode!=NULL)
{
new_copy_of_exchangeNode=copy(exchangeNode);
exchangeNode=NULL;
return new_copy_of_exchangeNode;
}
else
{
exchangeNode=curNode->nestedNode;
tempNode=curNode;
curNode=curNode->next;
return tempNode;
}
there is no need to use the stack, just push the nested element between current node and next node. something like,
tempNode=curnode->nextNode;
curNode->nextNode=curNode->nestedNode;
curNode->nextNode=tempNode;
btw I assumed that the linked list will not need to be the same after print. otherwise we always can use a single node entry as a exchange space instead of a stack. It will be initialized with null.
exchangeNode=null;
then in the iterator
whenever we wanna print a value
if(!exchangeNode!=NULL)
{
new_copy_of_exchangeNode=copy(exchangeNode);
exchangeNode=NULL;
return new_copy_of_exchangeNode;
}
else
{
exchangeNode=curNode->nestedNode;
tempNode=curNode;
curNode=curNode->next;
return tempNode;
}
we just have to find whether the left hand side string of * is a prefix and right hand size is a suffix. then we will need to find whether suffix.length + prefix.length < original_string.length or not. If * also allows blank characters we even will not need this check.
we have to assume that blank "" character is always a prefix and suffix.
Repamyfreynold, abc at ADP
Hi Everyone, I'm Ammy. I love to build props...everything from a casket to pneumatic monsters.My current pet ...
Reptaniajclover, Analyst at Amdocs
Hi, I am Tania from Tuckahoe USA, I am working as a Public relations representative in Gamble-Skogmo company. I like ...
Replarrymmapp, Android test engineer at Software AG
Hello, I am name and I live in a city, USA. I am a professional's Podiatric doctor. I am ...
Repmyershllims, abc at ASAPInfosystemsPvtLtd
Hiii, I am Myers and I am from Elizabeth. I am working as a Product designer designing most things I ...
Repnicolealove786, Apple Phone Number available 24/7 for our Customers at Argus
I am Nicole from Beverly Hills, CA. I am working as a manager in Liberty Wealth Planner company. I also ...
this will work only for quadruples that include arr[0], this will fail in a test like 2,4,1, 600,4
- hirajhil October 16, 2014