Re: [algogeeks] Re: Amazon Interview Question
Counting sort does not run in O(1) space though. Optimally it will run in O(K) space, where A is an array of integer numbers and K = max(A) - min(A) On Saturday, February 9, 2013 9:52:01 PM UTC-5, Mohanabalan wrote: can use counting sort On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santosh...@gmail.comjavascript: wrote: If we can retrieve ith prime efficiently, we can do the following... 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime 2.check if (prod% (ith_prime * ith_prime )==0) then return i; else prod=prod*ith_prime; 3.repeat it till end On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: Given an array of integers where some numbers repeat once, some numbers repeat twice and only one number repeats thrice, how do you find the number that gets repeated 3 times? Does this problem have an O(n) time and O(1) space solution? No hashmaps please! -- 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/-/TSPSKlD0FDsJ. To post to this group, send email to algo...@googlegroups.comjavascript: . To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Find the number of islands/connected components
Let's take the worst case, where the matrix is filled with ones.
Say that it takes S nanoseconds to scan one location, and D
nanoseconds to visit a location with DFS.
We have to scan all locations in the matrix. That is row*col scans,
which takes S*row*col ns.
At the first location we will start a DFS which will visit all of the
matrix locations. In the process it will mark them all as visited.
That will take D*row*col ns.
From then on, all of the locations are marked as visited, so we don't
do any more DFS.
Total time: S*row*col + D*row*col = (S+D)*(row*col)
But S and D are constants, so the complexity is O(row*col).
Don
On Apr 26, 8:19 am, rahul sharma rahul23111...@gmail.com wrote:
got the islands...but first we scan each element then also dfs for them if
all are 1..then how it can be o(row*col)...plz explain me complexity ofr
this
On Fri, Apr 26, 2013 at 2:07 PM, atul anand atul.87fri...@gmail.com wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*
},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
above different set of color represent different island.Simple DFS is used
to find all the island
On Fri, Apr 26, 2013 at 3:11 AM, Don dondod...@gmail.com wrote:
The complexity is still O(ROWS*COLS) because each location in the
matrix will be visited once by the loop and once by DFS. Once a
location has been visited by DFS, it is marked as visited and can't be
visited again.
Don
On Apr 25, 5:11 pm, rahul sharma rahul23111...@gmail.com wrote:
What will be complexity if all elements in matrix are 1..
when first dfs will call then all matrix will be scanned setting each
element to visited...
then again loop contiues to scan all the elements..plz explain
On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma rahul23111...@gmail.com
wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
Can anybody eplain how there are 5 islands in above matrix..thnx in
advance
source:-http://www.geeksforgeeks.org/find-number-of-islands/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visithttps://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visithttps://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Amazon Interview Question
A bit vector is basically just a sequence of bits such as a word or even an
array of words. Here is an example...
int x = 5; // 32 bit word size on Intel IA-32 Architecture In C
programming language.
A variable in C will be either located in a register in memory or in Main
Memory. You can even have bit vector data structures
reside on the hard disk. It just looks like this
10010101010010101...
If I'm interpreting the solution properly you will index into the bit
vector based on the number found in the array A that is
for j = 1... A.size
currentNumber = A[j] // The jth array element
bitVector[currentNumber] = ~ bitVector[currentNumber] ; // Toggle the
currentNumber bit
end for
Although this is a big memory save, you're still not using constant memory
because the size of your memory is dependent on the size of a word let's
say k
In worst case the space complexity will be 2*2^k = O(2^(K+1))
On Wednesday, April 3, 2013 9:58:23 AM UTC-8, ashekhar007 wrote:
hi sourab please explain what bit vector1 and bit vector 2 really are can
you give an example please?
On Saturday, February 16, 2013 11:20:59 PM UTC+5:30, sourabh wrote:
you can solve this problem using bitvector/bitset.
first scan :
scan the array set the bit on odd occurrence and unset on even or
0 occurrence.
second scan :
shift all the odd occurring elements in beginning of array and even
towards end.
third scan : till end of odd occurring elements.
take another bit vector
on first occurence :if bit is set in bv1 then unset it and set it in bv2.
on second occurence : if bv1 is not set and bv2 is set then these are the
array elements occuring 3rd time.
On Wed, Feb 13, 2013 at 9:27 PM, prakhar singh prakhars...@gmail.comwrote:
Yes, thats a valid point Don.
Thats what i meant when i wrote //is that correct? in the comments on
the array line in code.
int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct?
On Wed, Feb 13, 2013 at 9:09 PM, Don dond...@gmail.com wrote:
The xor approach only works if there are no values which occur only
once. But the problem statement indicates that some numbers occur
once, some occur twice, and one occurs three times. So you will end up
with prod equal to the xor of all of the values which occur once or
three times. Put that in your input array and you'll find that you
don't get the desired output.
I don't know of a solution better than sorting and scanning the array.
Don
On Feb 12, 3:14 pm, prakhar singh prakharsngh.1...@gmail.com wrote:
#includestdio.h
int main()
{
int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct?
int prod=a[0];int i;
for(i=1;i(int)sizeof(a)/sizeof(a[0]);i++)
{
prod ^= a[i];
}
printf(%d\n,prod); //outputs 3, algorithm works as Sachin
described
it;
}
On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
sachinchital...@gmail.comwrote:
use ex-or operation for all array elements..
a^a=0
a^a^a=a
On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B
mohanabala...@gmail.comwrote:
can use counting sort
On Sun, Jul 15, 2012 at 6:37 PM, santosh thota
santoshthot...@gmail.comwrote:
If we can retrieve ith prime efficiently, we can do the
following...
1.maintain a prod=1, start from 1st element, say a[0]=n find n th
prime
2.check if (prod% (ith_prime * ith_prime )==0) then return i;
else prod=prod*ith_prime;
3.repeat it till end
On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
Given an array of integers where some numbers repeat once, some
numbers
repeat twice and only one number repeats thrice, how do you find
the number
that gets repeated 3 times?
Does this problem have an O(n) time and O(1) space solution?
No hashmaps please!
--
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/-/TSPSKlD0FDsJ.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+...@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 unsubscribe from this group and stop receiving emails from it,
send an
email to algogeeks+...@googlegroups.com.
For more options, visithttps://groups.google.com/groups/opt_out.
--
Regards,
Sachin Chitale
Application Engineer SCJP, SCWCD
Contact# : +91 8086284349, 9892159511
Oracle Corporation
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send an
email to algogeeks+...@googlegroups.com.
For more options,
