Re: [algogeeks] Re: Microsoft interview question
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when I
read your solution attempt: What do you do with negative elements? What is
the -12th prime number? How do you deal with overflow in the cases where
you have a lot of large prime numbers and the product exceeds your native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array b
elements
if product is equal then b is a permutation of a
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
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.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
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: Microsoft interview question
U are checking if the sum is same or not.. which can be same even if the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when I
read your solution attempt: What do you do with negative elements? What is
the -12th prime number? How do you deal with overflow in the cases where
you have a lot of large prime numbers and the product exceeds your native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array b
elements
if product is equal then b is a permutation of a
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
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.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
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: storing URL's
question is more of like asking which data structure is suitable for implementing DNS server like functionality ? On Sat, May 19, 2012 at 10:46 PM, Gene gene.ress...@gmail.com wrote: This question has no answer. Every good student of computer science will know that you choose a data structure based on the _operations_ that must be performed on it: insert, lookup and what flavors of lookup, delete, etc.. So if an interviewer uses this question, he or she is probably trying to get you discuss this. So the right _response_ (not an answer) is What will you be _doing_ with these URLs? An example: Suppose you take Varun's approach and build a tree. Then it turns out the operation is Count the URLs for .png files. Well, the tree is no help here. You have to search the whole thing. On May 15, 11:50 am, atul anand atul.87fri...@gmail.com wrote: Given a file which contain millions of URL's. which data structure would you use for storing these URL's . data structure used should store and fetch data in efficient manner. -- 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: Microsoft interview question
@piyush :
your solution will fail for the case
a={5,1,1}
b={3,3,1}
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when I
read your solution attempt: What do you do with negative elements? What is
the -12th prime number? How do you deal with overflow in the cases where
you have a lot of large prime numbers and the product exceeds your native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array b
elements
if product is equal then b is a permutation of a
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
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.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
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] Microsoft interview question
it can be done by doing set of operation on the data. 1) check sum of the square of arr1 = arr2 2) sum of elements of arr1=arr2 3) xoring elements of arr1 and arr2 == 0 if all 3 condition are successful then..permutation found. On Sun, May 20, 2012 at 12:59 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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] Microsoft interview question
@atul:- why we require 1st condition(check sum of the square of arr1 = arr2) ?? On Sun, May 20, 2012 at 1:10 PM, atul anand atul.87fri...@gmail.com wrote: it can be done by doing set of operation on the data. 1) check sum of the square of arr1 = arr2 2) sum of elements of arr1=arr2 3) xoring elements of arr1 and arr2 == 0 if all 3 condition are successful then..permutation found. On Sun, May 20, 2012 at 12:59 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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. -- *DARPAN BAWEJA* *3rd year, I.T* *MNNIT Allahabad* -- 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: Microsoft interview question
Piyush. I think we can use your logic. But You should check the product also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations
of each other.
Space = O(1)
Time=O(n)
I think this should work. Please correct me if you find mistakes.
On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote:
U are checking if the sum is same or not.. which can be same even if the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when I
read your solution attempt: What do you do with negative elements? What
is
the -12th prime number? How do you deal with overflow in the cases where
you have a lot of large prime numbers and the product exceeds your native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array b
elements
if product is equal then b is a permutation of a
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
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.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
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.
--
*
*
*Kalyanasundaram N*
*BE 2nd year, CSE*
*College of Engineering Guindy,*
*Chennai-600025*
*
*
--
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: Microsoft interview question
@Piyush: Try this i/p 8,0,0 ; 2,6,0-- Ur algo aint adequate..
On Sat, May 19, 2012 at 11:24 PM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when I
read your solution attempt: What do you do with negative elements? What is
the -12th prime number? How do you deal with overflow in the cases where
you have a lot of large prime numbers and the product exceeds your native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] .. th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with array b
elements
if product is equal then b is a permutation of a
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
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.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
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: Interview Question based on histogram
Navin , your reply is correct. On Sat, May 19, 2012 at 10:36 PM, Gene gene.ress...@gmail.com wrote: The problem is not so clear, so you must make some assumptions to gat an answer. Since we have water, we have to envision the histogram in 3d. Then assume that the distance between histogram bars is 1 and bar i has height H[i], 0=iN, zero width and unit depth, and the base plane is at zero. Water is held in the pockets between bars. Then the pocket between H[i] and H[i+1] holds min(H[i],H[i+1]). To get the total, just sum these for 0 = i N-1 . On May 17, 1:57 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Imagine that you have an histogram stored in an array. Now imagine that you can pour water on top of your histogram. Describe an algorithm that computes the amount of water that remains trapped among the columns of the graph. Clearly on the edges the water would fall off. Use the language or the pseudocode you prefer. -- Thanks Regards Nikhil Agarwal B.Tech. in Computer Science Engineering National Institute Of Technology, Durgapur,Indiahttp://tech-nikk.blogspot.comhttp:// beta.freshersworld.com/communities/nitd -- 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. -- Thanks Regards Nikhil Agarwal B.Tech. in Computer Science Engineering National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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: Partition the array with equal average
@ prem... can U submit the code...for all Subsets of the particular array with O(n^2). thanks.. On Sun, May 20, 2012 at 1:11 AM, abhijeet srivastva nwaab.abhij...@gmail.com wrote: This is a subset sum problem. You have to find a subset of elements of array whose sum is x/2, where x is sum of all the elements of the array. On Sat, May 19, 2012 at 2:07 PM, payal gupta gpt.pa...@gmail.com wrote: this wont work out as we need to partition the elements to get the average of the two parts to be equal and not the sum of the two parts.. On Fri, May 18, 2012 at 11:57 PM, Ramindar Singh ramin...@gmail.comwrote: Not sure if i am correct but still be very close. 1. Intial Array is A with n elements 2. Sort the Array's in descending order 3. take 2 more arrays B and C in which u keep the partition 4. pull the one element from A to B and keep keep track of the sum's in both the arrays B C 5. Try to reach the sum in B by pulling the elements from A 6. Continue till all the n elements are partitioned. 7. If in the end still some difference is there b/w B and C, it can be settled by exchanging the elements among them as they both would be sorted. hope this helps... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BRRM2sjulSEJ. 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. -- Regards, GAURAV CHAWLA +919992635751 +919654127192 -- 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: Algo for Search in a 2D Matrix
@ashish: ya m sorry.. i didnt read the quest properly, it was for any given
number..
On Fri, May 18, 2012 at 11:37 AM, Ashish Goel ashg...@gmail.com wrote:
Anika, what you are talking about is finding a specific element, not the
kth largest or smallest element, can you give a walk through with an
example in case i have understood you incorrectly
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 17, 2012 at 3:33 PM, Anika Jain anika.jai...@gmail.comwrote:
there's a solution of O(log n) where 2D matrix has n rows and n columns.
Apply binary search for the search on the diagonal. when you are left with
just one element after the search apply binary search within that elements
row and its column. you will get the element. O(log n+log n+log n). so
O(log n).
On Wed, May 16, 2012 at 6:36 PM, Prem Krishna Chettri hprem...@gmail.com
wrote:
Well I hv got Something running in my mind buy ofcse need some cornor
case tuning.
If we take sqrt() of the number (say K) than we can avoid looking
into sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally
means that the final solution is possible in constant time (the time
independent of k or matrix values), which ofcourse can go upto O(n) in
worst case where N is the Matrix of N Rows and 1 Column as we cannot use
the intelligence of sqrt function to corner the value.
Its seems okei logically to remove those rows and columns as we are
certain that they are sorted in both ways and avoid unnecessary time
looking for the place where it won't belong.
Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1)k and
now keep on adding the value to sqrt(k)+1 till U reach k and get corner
that element.
I guess it works..
On Wed, May 16, 2012 at 1:17 PM, Ashish Goel ashg...@gmail.com wrote:
Vikas, can you suggest the logic of this also? I am a bit unclear on
how the 2D arr is being used as a heap and how recursion is used to solve
this
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Oct 13, 2011 at 11:37 PM, vikas vikas.rastogi2...@gmail.comwrote:
@Sunny, good catch, k X k approach wont work
lets try to use matrix itself as heap
heapify(int cr, int cc, int Nr, int Nc){
mr = cr; mc = cc;
if(cr+1 Nr)
mr = cr+1 mc = cc;
if(cc + 1 Nc min A[cc+1][cr])
mr = cr; mc = cc+1;
if(A[cr][cc] A[mr][mc]){
swap(A[cr][cc] ,A[mr][mc]);
heapify(mr, mc, Nr, Nc);
}
extract_min(){
swap(A[0][0], A[hr][hc]);
if(hc 0) hc--;
else if(hr 0){
hr --;
hc = N;
}
if(hr | hc)
heapify(0, 0, hr, hc);
}
}
On Oct 13, 12:18 pm, sunny agrawal sunny816.i...@gmail.com wrote:
Nopes
Still it does not ensure that duplicates will not be there in the
priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other
than heap,
which stores that which (i+1,j) are already there in the heap map
can also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
i could not understand the Order Analysis of the solution ..is it k*(lg
n)(lg m) or k*lg(mn)
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, May 20, 2012 at 11:15 PM, Anika Jain anika.jai...@gmail.com wrote:
@ashish: ya m sorry.. i didnt read the quest properly, it was for any
given number..
On Fri, May 18, 2012 at 11:37 AM, Ashish Goel ashg...@gmail.com wrote:
Anika, what you are talking about is finding a specific element, not the
kth largest or smallest element, can you give a walk through with an
example in case i have understood you incorrectly
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 17, 2012 at 3:33 PM, Anika Jain anika.jai...@gmail.comwrote:
there's a solution of O(log n) where 2D matrix has n rows and n columns.
Apply binary search for the search on the diagonal. when you are left with
just one element after the search apply binary search within that elements
row and its column. you will get the element. O(log n+log n+log n). so
O(log n).
On Wed, May 16, 2012 at 6:36 PM, Prem Krishna Chettri
hprem...@gmail.com wrote:
Well I hv got Something running in my mind buy ofcse need some cornor
case tuning.
If we take sqrt() of the number (say K) than we can avoid looking
into sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally
means that the final solution is possible in constant time (the time
independent of k or matrix values), which ofcourse can go upto O(n) in
worst case where N is the Matrix of N Rows and 1 Column as we cannot use
the intelligence of sqrt function to corner the value.
Its seems okei logically to remove those rows and columns as we are
certain that they are sorted in both ways and avoid unnecessary time
looking for the place where it won't belong.
Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1)k and
now keep on adding the value to sqrt(k)+1 till U reach k and get corner
that element.
I guess it works..
On Wed, May 16, 2012 at 1:17 PM, Ashish Goel ashg...@gmail.com wrote:
Vikas, can you suggest the logic of this also? I am a bit unclear on
how the 2D arr is being used as a heap and how recursion is used to solve
this
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Oct 13, 2011 at 11:37 PM, vikas
vikas.rastogi2...@gmail.comwrote:
@Sunny, good catch, k X k approach wont work
lets try to use matrix itself as heap
heapify(int cr, int cc, int Nr, int Nc){
mr = cr; mc = cc;
if(cr+1 Nr)
mr = cr+1 mc = cc;
if(cc + 1 Nc min A[cc+1][cr])
mr = cr; mc = cc+1;
if(A[cr][cc] A[mr][mc]){
swap(A[cr][cc] ,A[mr][mc]);
heapify(mr, mc, Nr, Nc);
}
extract_min(){
swap(A[0][0], A[hr][hc]);
if(hc 0) hc--;
else if(hr 0){
hr --;
hc = N;
}
if(hr | hc)
heapify(0, 0, hr, hc);
}
}
On Oct 13, 12:18 pm, sunny agrawal sunny816.i...@gmail.com wrote:
Nopes
Still it does not ensure that duplicates will not be there in the
priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other
than heap,
which stores that which (i+1,j) are already there in the heap map
can also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: [algogeeks] Print longest string duplicated M times
soln pls
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, May 20, 2012 at 5:49 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
I can give you a dynamic programming approach in O(n^2) and O(n) space .
On Tue, May 15, 2012 at 12:22 PM, Ashish Goel ashg...@gmail.com wrote:
I am unclear about the answer provided by Programming Pearls on the
question. What this does is to find longest string whose beginning is
separated by exactly M chars.
The original question is to find the longest string duplicated M times. Any
ideas on the approach for this? I could think of having a suffix tree with
each node keeping a count to keep track of while insertion how many times
this node was passed while going down
#include stdlib.h
#include string.h
#include stdio.h
int pstrcmp(char **p, char **q)
{ return strcmp(*p, *q); }
int comlen(char *p, char *q)
{int i = 0;
while (*p (*p++ == *q++))
i++;
return i;
}
#define M 1
#define MAXN 500
char c[MAXN], *a[MAXN];
int main()
{ int i, ch, n = 0, maxi, maxlen = -1;
while ((ch = getchar()) != EOF) {
a[n] = c[n];
c[n++] = ch;
}
c[n] = 0;
qsort(a, n, sizeof(char *), pstrcmp);
for (i = 0; i n-M; i++)
if (comlen(a[i], a[i+M]) maxlen) {
maxlen = comlen(a[i], a[i+M]);
maxi = i;
}
printf(%.*s\n, maxlen, a[maxi]);
return 0;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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,
Jalaj Jaiswal
Software Developer,
Adobe Systems
+91-9019947895
*
*
FACEBOOK http://www.facebook.com/jalaj.jaiswal89
LINKEDINhttp://www.linkedin.com/profile/view?id=34803280trk=tab_pro
--
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.
