@piyush : O(n/2) is O(n) .
your approach is good , it will efficient than linear search.
On Sat, Dec 24, 2011 at 5:48 AM, Piyush Kansal piyush.kan...@gmail.comwrote:
Hey Ankur,
What is the order of time complexity we are looking for in this case. The
option which Dave suggested can
The thing is ..will it ascertain that the probability is equal
I am not sure how ur method guarantees that...
May be if you and Dave can explain the algo a bit better that wud be great .
regards
Ankur
On Sat, Dec 24, 2011 at 5:48 AM, Piyush Kansal piyush.kan...@gmail.comwrote:
Hey Ankur,
If you want to instant search a contact number of person from a phone
book.
one must be able to use any one of them to search(person name or
contact number).
for eg : given phone number as input it should return name of the
person
or
given name of the person as input it should return phone
TREE
On 24 December 2011 13:20, atul007 atul.87fri...@gmail.com wrote:
If you want to instant search a contact number of person from a phone
book.
one must be able to use any one of them to search(person name or
contact number).
for eg : given phone number as input it should return name
@Ankur: Since the list is of infinite length, equal probability of
selecting any given node is impossible. The probability distribution
must be such that
inf
sum p(i) = 1.
i = 0
I.e., the individual probabilities must form a convergent series, and
thus p(i) -- 0. But a uniform distribution has
@Atul007: Use a hash table. Enter the name and the number into the
table, or use separate hash tables for names and numbers. The data
associated with each is a pointer to the other.
Dave
On Dec 24, 1:50 am, atul007 atul.87fri...@gmail.com wrote:
If you want to instant search a contact number of
Consider an array of N integers. Find the longest contiguous subarray
so that the average of its elements is greater than a given number k
I know the general brute force solution in O(N^2). Is there any
efficient solution using extra space?
--
You received this message because you are
@dave :
using only one hastable will cause problem , if 2 person have same name
...right??
using 2 hashtable then:-
if say two person has same name , they will collide at same point on 2nd
hashtable.
so second hashtable must contain linked list implementation to contain
phone number of
http://groups.google.com/group/algogeeks/browse_thread/thread/ed7295fbe2009b2/54665b73e297d752?hl=enq=Sub-array+problemlnk=ol;
hope this link would help to find solution for the given problem.
On Sat, Dec 24, 2011 at 9:41 PM, top coder topcode...@gmail.com wrote:
Consider an array of N
Segregate even and odd psoitioned nodes in a linked list
Eg:
2-3-1-9-7-5
The output should be two separate lists
2-1-7
3-9-5
*My code is:*
void segregate(node* head)
{
int i=1;
node* sec=head-next;
node *odd=head,*even=head-next;
while(even)
{
if(i%2)
{
odd-next=even-next;
even-next=NULL;
how can one do frequency sort .
Suppose we have an integer array like
1,2,3,1,2,3,1,1,2,3,4,4,3,5,3
Then 1 is appearing 4 times
2 - 3
3- 5
4-2
5-1
Then if we sort by frequency we shud have this as result
5,4,4,2,2,2,1,1,1,1,3,3,3,3,3
How to do it
--
MinHeap with frequency of data is constructed, then sorting it.
But don't see with same frequency it maintains the order of the first
appeared element
Regards
Surender
On Sat, Dec 24, 2011 at 10:57 PM, Ankur Garg ankurga...@gmail.com wrote:
how can one do frequency sort .
Suppose we have an
because you are doing odd=odd-next; and even=even-next;
you will lose head pointers for the two linked list formed once you come
out of the loop.
void segregate(node* head)
{
node *temp,*odd,*even;
toggle=1;
if(head==NULL)
{
return;
}
odd=head;
first sort the given array , you will get
1,1,1,1,2,2,2,3,3,3,3,3,4,4,5
now count frequency of each number and insert it into min heap.
each node contain 2 variable.
1) frequency
2) number
now do extract min operation.
and expand , for eg:-
for node 5
frequency = 0
number =5;
write 5 to the
any better approach than O(N log N) time?
maintain a heap of nodes value, count
for each element, if already present increase the count. Else add the
elements.
Max-Heap -- fetch the node, print it count number of times, (time to
search in heap -- log N)
doing this for N elements.
--
You
15 matches
Mail list logo
