Re: [algogeeks] Re: Google Q
On Sat, May 14, 2011 at 12:55 PM, pacific :-) pacific4...@gmail.com wrote:
Will not a balanced binary tree do the job ? if we will pick the root each
time for the median.
You cannot do it with a vanilla balanced binary tree.
But you can, if you use an augmented tree in the following sense - In
each node of the tree, store the number of nodes in the subtree rooted
at that node.
So , for eg,
- the root node will store N where N is the total number of nodes in the tree,
- number stored in left child of root + number stored in right child
of root = N - 1
Then, to find the element appearing at the N/2th position in an
inorder walk (i.e. the median) is given by Find(root, N/2) where Find
is defined like so -
Node* Find(Node* ptr, int position)
{
int ptrpos = ptr-left-numchildren + 1;
if(ptrpos == position) return ptr;
else if(ptrpos position) return Find(ptr-left, position);
else return Find(ptr-right, position - ptrpos);
}
On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:
@Ashish: The idea is to keep two heaps, a max-heap of the smallest
half of the elements and a min-heap of the largest elements. You
insert incoming elements into the appropriate heap. If the result is
that the number of elements in the two heaps differs by more than 1,
then you move the top element from the longer heap into the other one,
thereby equalzing the number of elements. Thus, inserting an element
is an O(log n) operation. To get the median, it is the top element of
the longer heap, or, if the heaps are of equal length, it is the
average of the two top elements. This is O(1).
Dave
On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
not clear, can u elaborate..
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal
agr.bhav...@gmail.comwrote:
This problem can be solved using 2 heaps and the median can always be
accessed in O(1) time ,the first node.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards,
chinna.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] first fit bin packing
Not sure what you are suggesting. If you bring to the root which has capacity to hold then it looks like you are disturbing the order of the bins. On Sat, May 14, 2011 at 1:34 PM, pacific :-) pacific4...@gmail.com wrote: i think we can use heaps for this problem..bring to the root which has capacity to hold and pick the root each time. If the root cannot accomodate then no other node will be able to accomodate. On Sat, May 14, 2011 at 1:26 AM, MK stardust...@gmail.com wrote: Consider the first fit strategy for online bin packing. So if you have N bins numbered 1, 2, 3..N and you are given value V, you scan them from left to right and insert V into the first bin that currently has enough capacity. In the naieve case, N insertions will take O(N^2) time. How can this be done in NlogN time? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] first fit bin packing
Consider the first fit strategy for online bin packing. So if you have N bins numbered 1, 2, 3..N and you are given value V, you scan them from left to right and insert V into the first bin that currently has enough capacity. In the naieve case, N insertions will take O(N^2) time. How can this be done in NlogN time? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding subarray
Let there be n elements v1, v2, v3 .. vn
Let S(i,k) mean - Sum k exists in a subset of {v1, v2, v3, ... vi}
At any given time, if solution has not yet been found then :
S(i,k) = S(i-1,k-vi) + vi or no solution exists
We need to find S(n,k)
So in a systematic fashion, solve S(1,1), S(1,2), S(1,3) ... S(1,k) ,
S(2,1), S(2,2), S(2,3), S(2,4) .. S(2,k) , ... S(n,1), S(n,2) ..
S(n,k)
On Wed, Mar 30, 2011 at 2:46 AM, Subhransu
subhransu.panigr...@gmail.com wrote:
set of integers in an array X that the sum equals a given number N
Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3}
Lets say the number 5 which can be formed in the following manner 5= 2 + 3
(the values from array). If there is no match it has to return
invalid numbers.
We also have to see the complexity of the solution.
I thought of one approach but not sure if there is more approach where the
complexity will be minimal.
Lets say sort the array and now take number and find the closest number for
that.
Then in a recursion manner search for another( Lets say number '5', it
search the list and found closest match
will be 3. Then recursively search for 3 now where closest match is 2)
Any algo with better complexity will be appreciated.
Subhransu Panigrahi
Email: subhransu.panigr...@gmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Coding Round
2) Design a DS that would do Push(),Pop(), and GetMax() elements at complexity O(1) Are you sure you remember this correctly? This would give you a way of sorting in O(1). Thanks.. On Thu, Mar 24, 2011 at 12:09 AM, balaji a peshwa.bal...@gmail.com wrote: The main thing they are testing is Problem Solving and the Algorithm Designing ability. Coding Ability is only next. If you have good knowledge in Data Structures and good Problem Solving skills with coding ability you can easily crack through the interview. This is what i infered from my experience. On Thu, Mar 24, 2011 at 12:33 AM, kunal srivastav kunal.shrivas...@gmail.com wrote: hi people, could someone tell me in detail what all things to prepare for amazon including the resources to consult for the same?? it would be really helpful On Thu, Mar 24, 2011 at 12:11 AM, Akash Mukherjee akash...@gmail.com wrote: kul man...wud appreciate if u cud post your question On Wed, Mar 23, 2011 at 11:28 PM, balaji a peshwa.bal...@gmail.com wrote: hi i got till the third round of technical interview out of the four rounds and got eliminated in third round.anyways thnx for ur support dude :-) On Tue, Mar 22, 2011 at 12:51 PM, balaji a peshwa.bal...@gmail.com wrote: Thnx :-) I am from SSN College of Engineering,Chennai l On Tue, Mar 22, 2011 at 12:28 PM, Akash Mukherjee akash...@gmail.com wrote: u r welcome :), nd all the best for ur test.btw, which clg?? On Tue, Mar 22, 2011 at 11:45 AM, guru peshwa.bal...@gmail.com wrote: Thank you very much for the info friendAnd sure will give u a treat :-) On Mar 22, 11:02 am, Akash Mukherjee akash...@gmail.com wrote: hey, dis is what i was told by a friend working @ amazon - Sometimes they do go to the level of the subject basics like OS or DS but you should be able to tackle these if you had studied well. No separate prep is needed. Few Favs DS Algos ( i should get treat for revealing this.;)... ) 1) All Trees (Binary for sure) 2) Graphs 3) Sorting Algos 4) Heaps Let us C ... though clichéd gives a good insight. If you can find time. can u tell a bit more about your profile?? fresher?? On Tue, Mar 22, 2011 at 11:20 AM, guru peshwa.bal...@gmail.com wrote: Hi geeks, tomorrow i am having Amazon.com's Coding round followed by Interview...pls suggest some tips to help me out... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- A.Balaji -- A.Balaji -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- thezeitgeistmovement.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- A.Balaji -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to
Re: [algogeeks] Application N-ary Tree..Important Question As Well
Why is unlock O(log(n)) - Shouldn't it be just O(1) ?
templateint N
struct Node
{
bool isLocked_;
Node *parent_;
Node *children_[N];
};
bool isLocked(NodeN *node)
{
return node-isLocked_;
}
bool visitor(NodeN* node)
{
if(node-isLocked_) return true;
for(int i = 0; i N; ++i){
if(children_[i] visitor(children_[i])) return true;
}
return false;
}
bool lock(NodeN *node)
{
if(!node) return false;
if(node-isLocked_) return true;
//Is any ancestor locked?
NodeN *n = node;
while(n-parent_){
if(n-parent_-isLocked_) return false;
n = node-parent_;
}
//Is any of the children locked?
if(visitor(node)) return false;
//Proceed to lock
node-isLocked_ = true;
return true;
}
void unlock(NodeN* node)
{
node_-isLocked_ = false;
}
---
On Fri, Mar 18, 2011 at 8:32 AM, DIPANKAR DUTTA dutta.dipanka...@gmail.com
wrote:
this is something like Multiple granularity locking protocol in DBMS...
On Fri, Mar 18, 2011 at 5:43 PM, bittu shashank7andr...@gmail.com wrote:
Given an n-ary tree of resources arranged hierarchically. A process
needs to lock a resource node in order to use it. But a node cannot be
locked if any of its descendant or ancestor is locked. You are
supposed to:
- write the structure of node
- write codes for
* Islock()- returns true if a given node is locked and false if it
is not
* Lock()- locks the given node if possible and updates lock
information
* Unlock()- unlocks the node and updates information.
Codes should be :
* Islock –O(1)
* Lock()- O(log n)
* unLock()- O(log n)
Thanks Regards
Shashank
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
DIPANKAR DUTTA
M-TECH,Computer Science Engg.
EC Dept,IIT ROORKEE
Uttarakhand , India – 247667
---
website:http://people.iitr.ernet.in/shp/09535009/Website/index.html
ph no-09045809987
Lab: 286454
email:dipan...@iitr.ernet.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Coding Round
Actually, you probably mean that GetMax() does not remove it from the DS? Sorry for the hasty conclusion. On Thu, Mar 24, 2011 at 12:11 AM, MK stardust...@gmail.com wrote: 2) Design a DS that would do Push(),Pop(), and GetMax() elements at complexity O(1) Are you sure you remember this correctly? This would give you a way of sorting in O(1). Thanks.. On Thu, Mar 24, 2011 at 12:09 AM, balaji a peshwa.bal...@gmail.com wrote: The main thing they are testing is Problem Solving and the Algorithm Designing ability. Coding Ability is only next. If you have good knowledge in Data Structures and good Problem Solving skills with coding ability you can easily crack through the interview. This is what i infered from my experience. On Thu, Mar 24, 2011 at 12:33 AM, kunal srivastav kunal.shrivas...@gmail.com wrote: hi people, could someone tell me in detail what all things to prepare for amazon including the resources to consult for the same?? it would be really helpful On Thu, Mar 24, 2011 at 12:11 AM, Akash Mukherjee akash...@gmail.com wrote: kul man...wud appreciate if u cud post your question On Wed, Mar 23, 2011 at 11:28 PM, balaji a peshwa.bal...@gmail.com wrote: hi i got till the third round of technical interview out of the four rounds and got eliminated in third round.anyways thnx for ur support dude :-) On Tue, Mar 22, 2011 at 12:51 PM, balaji a peshwa.bal...@gmail.com wrote: Thnx :-) I am from SSN College of Engineering,Chennai l On Tue, Mar 22, 2011 at 12:28 PM, Akash Mukherjee akash...@gmail.com wrote: u r welcome :), nd all the best for ur test.btw, which clg?? On Tue, Mar 22, 2011 at 11:45 AM, guru peshwa.bal...@gmail.com wrote: Thank you very much for the info friendAnd sure will give u a treat :-) On Mar 22, 11:02 am, Akash Mukherjee akash...@gmail.com wrote: hey, dis is what i was told by a friend working @ amazon - Sometimes they do go to the level of the subject basics like OS or DS but you should be able to tackle these if you had studied well. No separate prep is needed. Few Favs DS Algos ( i should get treat for revealing this.;)... ) 1) All Trees (Binary for sure) 2) Graphs 3) Sorting Algos 4) Heaps Let us C ... though clichéd gives a good insight. If you can find time. can u tell a bit more about your profile?? fresher?? On Tue, Mar 22, 2011 at 11:20 AM, guru peshwa.bal...@gmail.com wrote: Hi geeks, tomorrow i am having Amazon.com's Coding round followed by Interview...pls suggest some tips to help me out... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- A.Balaji -- A.Balaji -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- thezeitgeistmovement.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- A.Balaji -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks
