Re: [algogeeks] Re: is it possible to detect the first repeating number in a 2-D array (n X n) in O(n) time ?
Ya sorry abt that my algo is wrong! On Tue, Jul 19, 2011 at 3:35 PM, Bhanu Kishore wrote: > @Venkat. That algorithm doesnt work actually.Try for 9,8,1. At 1 , it > becomes 0. > > -- > 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. > -- Cheers, Vicky -- 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: is it possible to detect the first repeating number in a 2-D array (n X n) in O(n) time ?
@Dumanshu: i know you have given a good explanation but i have never done parallel computing.. could you illustrate a bit more especially about the n+1th process.. On Tue, Jul 19, 2011 at 3:35 PM, Bhanu Kishore wrote: > @Venkat. That algorithm doesnt work actually.Try for 9,8,1. At 1 , it > becomes 0. > > -- > 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: is it possible to detect the first repeating number in a 2-D array (n X n) in O(n) time ?
@Venkat. That algorithm doesnt work actually.Try for 9,8,1. At 1 , it becomes 0. -- 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] Re: is it possible to detect the first repeating number in a 2-D array (n X n) in O(n) time ?
doing xor of all elements in array[][] should work. you start from a[0] [0] to a[0][n] then a[1][0] .. when the xor value bcomz 0 then the corresponding value in arr[i][j] is the first repeated element in the array. though this code will have two loops and seem as O(n2) it will terminate once it finds the first repeated no. hope my algo works. comments plz On Jul 19, 2:14 am, Dumanshu wrote: > You have to use parallel computing to find the first repeating number > in O(n) time if theres nothing special about the 2-D array > Use n +1 processes, n processes to scan each row and 1 process to scan > the rows last and next rows first element to check for repetition. > Each process uses hash table to find the first non repeating number. > When we have the results from all the processes, do O(n) scanning, and > output the result for minimum row which wud be the first repetition. > > On Jul 18, 10:42 pm, snehi jain wrote: > > > > > > > > > this question was asked in an interview. > > > Regards > > Snehi -- 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] Re: is it possible to detect the first repeating number in a 2-D array (n X n) in O(n) time ?
You have to use parallel computing to find the first repeating number in O(n) time if theres nothing special about the 2-D array Use n +1 processes, n processes to scan each row and 1 process to scan the rows last and next rows first element to check for repetition. Each process uses hash table to find the first non repeating number. When we have the results from all the processes, do O(n) scanning, and output the result for minimum row which wud be the first repetition. On Jul 18, 10:42 pm, snehi jain wrote: > this question was asked in an interview. > > Regards > Snehi -- 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.
