Re: [algogeeks] Re: MS interview
@all .. i suggested him the hashing method... but was not convinced... he might be expecting something else.. something like tries.. etc.. @ Karthikeyan Muthu... can u explain it in detail with some ex ... On Thu, Aug 23, 2012 at 11:28 PM, Karthikeyan Muthu keyankarthi1...@gmail.com wrote: i would suggest using tires data structure, basically a n-nary tree to store the dictionary. Entire algo is as follows: 1) Create a trie http://en.wikipedia.org/wiki/Trie representing the dictionary. 2) create a aux array for the search key. as count [ key[i] ] ++; 3) Start a recursion from the root of the trie and pick a path if (count [ path ] 0 ) 3rd step ensures that we traverse only those valid paths (ie valid words, this would reduce n! checking of all combinations). On Thu, Aug 23, 2012 at 8:23 PM, Ashish Goel ashg...@gmail.com wrote: yes, that is correct. O(mn) to form multimap and then O(m) to tell all anagram groups Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Aug 23, 2012 at 5:11 PM, kings dns.bhar...@gmail.com wrote: Dear GC, The efficient data structure in my opinion is Hash Table. 1. For a given word in the dictionary we need to form an anagram dictionary i.e. take a given word sort it which forms the key for the hashtable , then start forming the different anagrams for that word and insert it into the hash table with the corresponding key. 2. Once the hash table is ready for the given word sort it find the key and print all the anagarams i.e. values associated to that key. we will get all the anagrams for a given word. Coming to time complexity... sorting of a word can be done in a O(nlogn). building of anagram will take O(n). hash complexity O(n) worst case. so total time complexity is O(nlogn) for whole execrcise. Thanks Bhargava On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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/-/ySPUSvS0Sh0J. 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.
[algogeeks] Re: MS interview
Dear GC, The efficient data structure in my opinion is Hash Table. 1. For a given word in the dictionary we need to form an anagram dictionary i.e. take a given word sort it which forms the key for the hashtable , then start forming the different anagrams for that word and insert it into the hash table with the corresponding key. 2. Once the hash table is ready for the given word sort it find the key and print all the anagarams i.e. values associated to that key. we will get all the anagrams for a given word. Coming to time complexity... sorting of a word can be done in a O(nlogn). building of anagram will take O(n). hash complexity O(n) worst case. so total time complexity is O(nlogn) for whole execrcise. Thanks Bhargava On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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/-/ySPUSvS0Sh0J. 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: MS interview
yes, that is correct. O(mn) to form multimap and then O(m) to tell all anagram groups Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Aug 23, 2012 at 5:11 PM, kings dns.bhar...@gmail.com wrote: Dear GC, The efficient data structure in my opinion is Hash Table. 1. For a given word in the dictionary we need to form an anagram dictionary i.e. take a given word sort it which forms the key for the hashtable , then start forming the different anagrams for that word and insert it into the hash table with the corresponding key. 2. Once the hash table is ready for the given word sort it find the key and print all the anagarams i.e. values associated to that key. we will get all the anagrams for a given word. Coming to time complexity... sorting of a word can be done in a O(nlogn). building of anagram will take O(n). hash complexity O(n) worst case. so total time complexity is O(nlogn) for whole execrcise. Thanks Bhargava On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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/-/ySPUSvS0Sh0J. 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: MS interview
i would suggest using tires data structure, basically a n-nary tree to store the dictionary. Entire algo is as follows: 1) Create a trie http://en.wikipedia.org/wiki/Trie representing the dictionary. 2) create a aux array for the search key. as count [ key[i] ] ++; 3) Start a recursion from the root of the trie and pick a path if (count [ path ] 0 ) 3rd step ensures that we traverse only those valid paths (ie valid words, this would reduce n! checking of all combinations). On Thu, Aug 23, 2012 at 8:23 PM, Ashish Goel ashg...@gmail.com wrote: yes, that is correct. O(mn) to form multimap and then O(m) to tell all anagram groups Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Aug 23, 2012 at 5:11 PM, kings dns.bhar...@gmail.com wrote: Dear GC, The efficient data structure in my opinion is Hash Table. 1. For a given word in the dictionary we need to form an anagram dictionary i.e. take a given word sort it which forms the key for the hashtable , then start forming the different anagrams for that word and insert it into the hash table with the corresponding key. 2. Once the hash table is ready for the given word sort it find the key and print all the anagarams i.e. values associated to that key. we will get all the anagrams for a given word. Coming to time complexity... sorting of a word can be done in a O(nlogn). building of anagram will take O(n). hash complexity O(n) worst case. so total time complexity is O(nlogn) for whole execrcise. Thanks Bhargava On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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/-/ySPUSvS0Sh0J. 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.
Re: [algogeeks] Re: MS Q
anybody have informaton regarding questions asked in written and interview of capillary technology for developer post please share at bhardwaj.ankit...@gmail.com thanks in advance. On 5/22/12, Navin.nitjsr navin.nit...@gmail.com wrote: If the matrix is 4-connected, we can use the same matrix. now we have to find the total number of connected components of a graph. consider 1 1 1 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 we can use bfs/dfs to mark the nodes as visited and thus total connected components can be counted. On Tuesday, 10 January 2012 07:09:46 UTC+5:30, ashgoel wrote: there is a matrix of 1 and 0 1 is a island and 0 is water 1-1 together makes one island calculate total no of islands Best Regards Ashish Goel Think positive and find fuel in failure -- 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/-/JiDXnyVHn4YJ. 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] Re: MS Question: Add two large numbers where the numbers are stored in an array format
- in general we use polynomial addition for the same. If the numbers are carrying some additional information as ( particular base or pattern) another mechanise can be designed On Tuesday, 26 June 2012 15:40:39 UTC+5:30, ashgoel wrote: 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/eBEuUWRASgwJ. 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: MS Question: Reverse stack using push, pop without any auxiliary data structure
In a stack, you can't access any element directly, except the top one.
On Mon, Jun 18, 2012 at 11:33 AM, Rituraj worstcod...@gmail.com wrote:
My iterative approach
/*code in c*/
#includestdio.h
int main()
{
int stack[]={1,2,3,4,5,6,7,8},top=7;//
int i,j,temp;
for(i=1;i=top;i++)
{
temp=stack[i];
for(j=i;j0;j--)
stack[j]=stack[j-1];
stack[0]=temp;
}
for(i=0;i=top;i++)
printf(%d ,stack[i] );
return 0;
}
/*
Rituraj
2nd Yr.
B.tech CSE
NIT -Trichy
--
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/-/n1OE58e8B7IJ.
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.
--
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology
--
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: MS Question: Reverse stack using push, pop without any auxiliary data structure
this is not a stack at all, u have just named it as a stack. for it to be a
stack u should access only the top most element at any point of time!!!
On Mon, Jun 18, 2012 at 11:33 AM, Rituraj worstcod...@gmail.com wrote:
My iterative approach
/*code in c*/
#includestdio.h
int main()
{
int stack[]={1,2,3,4,5,6,7,8},top=7;//
int i,j,temp;
for(i=1;i=top;i++)
{
temp=stack[i];
for(j=i;j0;j--)
stack[j]=stack[j-1];
stack[0]=temp;
}
for(i=0;i=top;i++)
printf(%d ,stack[i] );
return 0;
}
/*
Rituraj
2nd Yr.
B.tech CSE
NIT -Trichy
--
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/-/n1OE58e8B7IJ.
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.
--
Aditya Gupta
B.Tech III yr CSE
IITR
--
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: MS Question: Reverse stack using push, pop without any auxiliary data structure
I think there is a problem in this solution.
U r accessing stack elements from 1 to n in the outer loop. It is not
possible. 1st element cannot be accessed without popping first n-1 elements
out.
On Mon, Jun 18, 2012 at 11:33 AM, Rituraj worstcod...@gmail.com wrote:
My iterative approach
/*code in c*/
#includestdio.h
int main()
{
int stack[]={1,2,3,4,5,6,7,8},top=7;//
int i,j,temp;
for(i=1;i=top;i++)
{
temp=stack[i];
for(j=i;j0;j--)
stack[j]=stack[j-1];
stack[0]=temp;
}
for(i=0;i=top;i++)
printf(%d ,stack[i] );
return 0;
}
/*
Rituraj
2nd Yr.
B.tech CSE
NIT -Trichy
--
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/-/n1OE58e8B7IJ.
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: MS Question : find word in 2D array
1 search should in using KMP algo so that It can be seacrh in O(n) . let
function is int KMP(src,trget, searchDirection )
this kmpSearch funtion should be implemented is such a fashion that is
search in both direction.
3. assume that give 2d array name is array
const int row =1;
const int col =1;
const int dig =1;
for(i=0;iM;i++) //O(n^2)
{
KMP(array,target, row); //O(n)
KMP(array,target,col ); //O(n)
KMP(array,target, dig );//O(n)
}
result in O(n^2)
but still looking for better solution
--
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: MS Question : find word in 2D array
This can be done with a dfs to mark the path and a backtrack to construct the path or the word itself. -- 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: MS question : string compression
#include stdafx.h
#include iostream
using namespace std;
const int len = 20;
const int maxCount = 127;
int rle(char* pStr, int length, char* pNew) {
if (!pStr) return -1;
if (length 3) return -1;
int i = 0;
int k = 0;
char p1 = pStr[i++];
char p2 = pStr[i++];
char p3 = pStr[i++];
int pos=0;
int cCount = 0;
bool verbatim = false;
while ((p3) (ilength)) {
if (p1==p2) {
if (p2==p3) {
if (i == k+3) //no vRun
verbatim = false;//no vRun befor this cRun
if (verbatim)
{
int vEnd = (i-3)-k;;
pNew[pos++] = vEnd;
for (int t=k;tvEnd;t++) {
pNew[pos++]=pStr[t];
}
}
cCount++;
p1 = p2;
p2 = p3;/*not required*/
p3 = pStr[i++];
continue;
}
else { //run end or no run at all
if (cCount 0) { //a run
pNew[pos++] = -cCount; ///
pNew[pos++] = p2;
p1 = p3;
k = i-1; //p3's position
p2 = pStr[i++];
if (!p2) break;
p3 = pStr[i++];
cCount = 0;
}
else { /*aab */
verbatim = true;
p1 = p2;
p2 = p3;
p3 =pStr[i++];
}
}
}
else { //no run
verbatim = true;
p1 = p2;
p2 = p3;
p3 =pStr[i++];
}
}
//possible run or no run here
if (cCount0) {
pNew[pos++] = -cCount;
pNew[pos++] = p2;
} else {
if (klength) {
pNew[pos++] = length-k-1;
for (int t=k;tlength;t++) {
pNew[pos++]=pStr[t];
}
}
}
pNew[pos]='\0';
return 1;
}
void rleDecode(char *pEnc, char *pDec, char *pOrig)
{
int i = 0;
int pos =0;
int count ;
char character ;
do {
count = pEnc[i++];
if (count 0) {
count = 2-count;
character = pEnc[i++];
for (int j=0;jcount;j++)
pDec[pos++] = character;
}
else {
//pNew[pos++]=character;
for (int j=0;jcount;j++) {
pDec[pos++]=pEnc[i++];
}
}
}while (pEnc[i]);
pDec[pos]='\0';
for(int i=0;ilen;i++)
if (pOrig[i]!=pDec[i]) cout JERK, do it again!! (: endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
char *pStr = (char *)malloc(sizeof(char)*len);
pStr = abccdddijkk; //TRY more examples
char *pNew = (char *)malloc(sizeof(char)*len);
char *pDec = (char *)malloc(sizeof(char)*len);
//rleSimple(pStr,pNew);
rle(pStr,len,pNew);
rleDecode(pNew, pDec, pStr);
return 0;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jun 8, 2012 at 9:04 AM, Ashish Goel ashg...@gmail.com wrote:
The idea here is that there will be parts of the stream which actually
should not be compressed. For example abcdef as well as aa do not need any
compression. We need to compress only if 3 characters match because for
compressing two chars we will take up 2 chars so no compression benefit (:
So we need to keep a pos as a reference to say that here is the position
in the string i am processing now and do the compress(either verbatim or
real compress) when 3 same chars are found
eg
abcfdgffg: pos is 0 and at index 8 we get to know that there is a run,
so we should say 8-3+1=6 need to go verbatim so we write 6abcfdg and update
pos to index 6, and count to 1. Since now run flag is on, we continue till
we find a triplet mismatch(f==f but f!=g) which happens at g (index
12)implying an end to a run, therefore now count is 4, we would write 4f
implying 2+4 times of next char should be expanded. now again pos will be
set to 12, count to 0 and three same char check should re-begin. This will
for sure have 2 while loops and a bit comex, and i donot think this is what
the interviewer should expect one to code. Kindly note that if run is more
than max length, we need to tweak the writing part too.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Jun 7, 2012 at 7:05 PM, Navin Gupta navin.nit...@gmail.comwrote:
If abcdef is changed to a1b1c1d1e1f1,
then we need to allocate memory dynamically.
Because length is increased,I think this has no practical
implementation.As abcdef serves the same purpose.
On Sunday, 3 June 2012 09:36:25 UTC+5:30, utsav sharma wrote:
@ashish:-algo given in link wiil fail for abcdef
@navin:- output of abcdef should be 1a1b1c1d1e1f
On Sun, May 27, 2012 at 3:24 PM, Ashish Goel ashg...@gmail.com wrote:
Will fail for the sing having say 257characters all same
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, May 26, 2012 at 12:26 PM, Navin Gupta
navin.nit...@gmail.comwrote:
This is called Run-Length-Encoding (RLE) of a string.
Its purpose is to save space.So in case of abcdef,I think the output
needed is abcdef (1 is implicit).
The added benefit is it makes the solution in-place.
Approach:- (In-place and Linear Time)
Start from the left of string and PREVIOUS_CHAR = str[0]
move forward till u match the CURRENT_CHAR with PREVIOUS_CHAR and keep
count of PREVIOUS_CHAR
At any point if (PREVIOUS_CHAR!=CURRENT_CHAR)
put the count of prev_char next to the start position of the
previous character.
Below is the working code :-
void torle(char *str)
{ int i=0,j=0,k=0,cnt=1;
char cur_char=str[0],num[100];
while(str[j+1])
{
cnt=1;
while(str[j+1]==cur_char str[j]!='\0'){
Re: [algogeeks] Re: MS question : string compression
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jun 8, 2012 at 12:54 PM, Ashish Goel ashg...@gmail.com wrote:
#include stdafx.h
#include iostream
using namespace std;
const int len = 20;
const int maxCount = 127;
int rle(char* pStr, int length, char* pNew) {
if (!pStr) return -1;
if (length 3) return -1;
int i = 0;
int k = 0;
char p1 = pStr[i++];
char p2 = pStr[i++];
char p3 = pStr[i++];
int pos=0;
int cCount = 0;
bool verbatim = false;
while ((p3) (ilength)) {
if (p1==p2) {
if (p2==p3) {
if (i == k+3) //no vRun
verbatim = false;//no vRun befor this cRun
if (verbatim)
{
int vEnd = (i-3)-k;;
pNew[pos++] = vEnd;
for (int t=k;tvEnd;t++) {
pNew[pos++]=pStr[t];
}
}
cCount++;
if (cCount == maxCount) {
pNew[pos++] = -cCount; ///
pNew[pos++] = p3;
p1 = pStr[i++];
if (!p1) break;
k = 0;
p2 = pStr[i++];
if (!p2) break;
p3 = pStr[i++];
cCount = 0;
continue;
} else {
/*p1 = p2;
p2 = p3; //not required*/
p3 = pStr[i++];
}
}
else { //run end or no run at all
if (cCount 0) { //a run
pNew[pos++] = -cCount; ///
pNew[pos++] = p2;
p1 = p3;
k = i-1; //p3's position
p2 = pStr[i++];
if (!p2) break;
p3 = pStr[i++];
cCount = 0;
}
else { /*aab */
verbatim = true;
p1 = p2;
p2 = p3;
p3 =pStr[i++];
}
}
}
else { //no run
verbatim = true;
p1 = p2;
p2 = p3;
p3 =pStr[i++];
}
}
//possible run or no run here
if (cCount0) {
pNew[pos++] = -cCount;
pNew[pos++] = p2;
} else {
if (klength) {
pNew[pos++] = length-k-1;
for (int t=k;tlength;t++) {
pNew[pos++]=pStr[t];
}
}
}
pNew[pos]='\0';
return 1;
}
void rleDecode(char *pEnc, char *pDec, char *pOrig)
{
int i = 0;
int pos =0;
int count ;
char character ;
do {
count = pEnc[i++];
if (count 0) {
count = 2-count;
character = pEnc[i++];
for (int j=0;jcount;j++)
pDec[pos++] = character;
}
else {
//pNew[pos++]=character;
for (int j=0;jcount;j++) {
pDec[pos++]=pEnc[i++];
}
}
}while (pEnc[i]);
pDec[pos]='\0';
for(int i=0;ilen;i++)
if (pOrig[i]!=pDec[i]) cout JERK, do it again!! (: endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
char *pStr = (char *)malloc(sizeof(char)*len);
pStr = abccdddijkk; //TRY more examples
char *pNew = (char *)malloc(sizeof(char)*len);
char *pDec = (char *)malloc(sizeof(char)*len);
//rleSimple(pStr,pNew);
rle(pStr,len,pNew);
rleDecode(pNew, pDec, pStr);
return 0;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jun 8, 2012 at 9:04 AM, Ashish Goel ashg...@gmail.com wrote:
The idea here is that there will be parts of the stream which actually
should not be compressed. For example abcdef as well as aa do not need any
compression. We need to compress only if 3 characters match because for
compressing two chars we will take up 2 chars so no compression benefit (:
So we need to keep a pos as a reference to say that here is the position
in the string i am processing now and do the compress(either verbatim or
real compress) when 3 same chars are found
eg
abcfdgffg: pos is 0 and at index 8 we get to know that there is a
run, so we should say 8-3+1=6 need to go verbatim so we write 6abcfdg and
update pos to index 6, and count to 1. Since now run flag is on, we
continue till we find a triplet mismatch(f==f but f!=g) which happens at g
(index 12)implying an end to a run, therefore now count is 4, we would
write 4f implying 2+4 times of next char should be expanded. now again pos
will be set to 12, count to 0 and three same char check should re-begin.
This will for sure have 2 while loops and a bit comex, and i donot think
this is what the interviewer should expect one to code. Kindly note that if
run is more than max length, we need to tweak the writing part too.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Jun 7, 2012 at 7:05 PM, Navin Gupta navin.nit...@gmail.comwrote:
If abcdef is changed to a1b1c1d1e1f1,
then we need to allocate memory dynamically.
Because length is increased,I think this has no practical
implementation.As abcdef serves the same purpose.
On Sunday, 3 June 2012 09:36:25 UTC+5:30, utsav sharma wrote:
@ashish:-algo given in link wiil fail for abcdef
@navin:- output of abcdef should be 1a1b1c1d1e1f
On Sun, May 27, 2012 at 3:24 PM, Ashish Goel ashg...@gmail.com wrote:
Will fail for the sing having say 257characters all same
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, May 26, 2012 at 12:26 PM, Navin Gupta
navin.nit...@gmail.comwrote:
This is called Run-Length-Encoding (RLE) of a string.
Its purpose is to save space.So in case of abcdef,I think the output
needed is abcdef (1 is implicit).
The added benefit is it makes the solution in-place.
Approach:- (In-place and Linear
Re: [algogeeks] Re: MS question : string compression
The idea here is that there will be parts of the stream which actually
should not be compressed. For example abcdef as well as aa do not need any
compression. We need to compress only if 3 characters match because for
compressing two chars we will take up 2 chars so no compression benefit (:
So we need to keep a pos as a reference to say that here is the position in
the string i am processing now and do the compress(either verbatim or real
compress) when 3 same chars are found
eg
abcfdgffg: pos is 0 and at index 8 we get to know that there is a run,
so we should say 8-3+1=6 need to go verbatim so we write 6abcfdg and update
pos to index 6, and count to 1. Since now run flag is on, we continue till
we find a triplet mismatch(f==f but f!=g) which happens at g (index
12)implying an end to a run, therefore now count is 4, we would write 4f
implying 2+4 times of next char should be expanded. now again pos will be
set to 12, count to 0 and three same char check should re-begin. This will
for sure have 2 while loops and a bit comex, and i donot think this is what
the interviewer should expect one to code. Kindly note that if run is more
than max length, we need to tweak the writing part too.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Jun 7, 2012 at 7:05 PM, Navin Gupta navin.nit...@gmail.com wrote:
If abcdef is changed to a1b1c1d1e1f1,
then we need to allocate memory dynamically.
Because length is increased,I think this has no practical
implementation.As abcdef serves the same purpose.
On Sunday, 3 June 2012 09:36:25 UTC+5:30, utsav sharma wrote:
@ashish:-algo given in link wiil fail for abcdef
@navin:- output of abcdef should be 1a1b1c1d1e1f
On Sun, May 27, 2012 at 3:24 PM, Ashish Goel ashg...@gmail.com wrote:
Will fail for the sing having say 257characters all same
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, May 26, 2012 at 12:26 PM, Navin Gupta navin.nit...@gmail.comwrote:
This is called Run-Length-Encoding (RLE) of a string.
Its purpose is to save space.So in case of abcdef,I think the output
needed is abcdef (1 is implicit).
The added benefit is it makes the solution in-place.
Approach:- (In-place and Linear Time)
Start from the left of string and PREVIOUS_CHAR = str[0]
move forward till u match the CURRENT_CHAR with PREVIOUS_CHAR and keep
count of PREVIOUS_CHAR
At any point if (PREVIOUS_CHAR!=CURRENT_CHAR)
put the count of prev_char next to the start position of the
previous character.
Below is the working code :-
void torle(char *str)
{ int i=0,j=0,k=0,cnt=1;
char cur_char=str[0],num[100];
while(str[j+1])
{
cnt=1;
while(str[j+1]==cur_char str[j]!='\0'){
j++;
cnt++;
}
str[i++]=cur_char;
if( cnt9 ){
itoa(cnt,num);
k=0;
while(num[k]) str[i++]=num[k++];
}
else if( cnt1 cnt10 )
str[i++]= cnt+'0';
j++;
if(str[j]) cur_char=str[j];
}
if(i!=0){
if(cnt==1)
str[i++]=cur_char;
str[i]='\0';
}
}
On Saturday, 26 May 2012 04:32:35 UTC+5:30, utsav sharma wrote:
Implement a method to perform basic string compression using the
counts of repeated characters.(inplace)
eg:- input: aaabcdef
output:3a5b1c1d1e1f.
what should be my approach to this problem
if i calculate the size of array required to store the output string
and start from the last of the array then i wldn't get the right
answer of above input case.
and if start from front then i wldn't get the right answer of this
input case
eg:- input: abcdef
output: 1a1b1c1d1e1f
--
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/-/4LxWHEUJuK8Jhttps://groups.google.com/d/msg/algogeeks/-/4LxWHEUJuK8J
.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+unsubscribe@**
googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en 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+unsubscribe@**
googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
Re: [algogeeks] Re: MS: searching problem......help me out...
i think gene is correct in normal RAM it is impossible @abhishek you are talking about parallel algorithms but till this extent is not possible to implement in general computers.. @abhinav you was correct.. firsst we will have to make heap tree which is impossible in log(n) time... On Sun, Jun 3, 2012 at 11:23 PM, Gene gene.ress...@gmail.com wrote: Finding a given element in an unsorted list in less than O(n) time (with a normal RAM model of computation) is easy to prove impossible. On Jun 3, 11:01 am, abhinav gupta abhinav@gmail.com wrote: We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@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. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, India Mobile No: +91-8798049298, +91-9424738542 patlerahulku...@gmail.com rahulkumarpa...@yahoo.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.
[algogeeks] Re: MS: searching problem......help me out...
Finding a given element in an unsorted list in less than O(n) time (with a normal RAM model of computation) is easy to prove impossible. On Jun 3, 11:01 am, abhinav gupta abhinav@gmail.com wrote: We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@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.
Re: [algogeeks] Re: MS: searching problem......help me out...
finding element in an unsorted array and with no relationship b/w the elements would have lower bound - omega(n) ..boczz you need to traverse whole array atleast once to find that element. so obv it cant be done in log(n) time..think abt it. On Sun, Jun 3, 2012 at 11:23 PM, Gene gene.ress...@gmail.com wrote: Finding a given element in an unsorted list in less than O(n) time (with a normal RAM model of computation) is easy to prove impossible. On Jun 3, 11:01 am, abhinav gupta abhinav@gmail.com wrote: We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@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: MS question : string compression
Will fail for the sing having say 257characters all same
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, May 26, 2012 at 12:26 PM, Navin Gupta navin.nit...@gmail.comwrote:
This is called Run-Length-Encoding (RLE) of a string.
Its purpose is to save space.So in case of abcdef,I think the output
needed is abcdef (1 is implicit).
The added benefit is it makes the solution in-place.
Approach:- (In-place and Linear Time)
Start from the left of string and PREVIOUS_CHAR = str[0]
move forward till u match the CURRENT_CHAR with PREVIOUS_CHAR and keep
count of PREVIOUS_CHAR
At any point if (PREVIOUS_CHAR!=CURRENT_CHAR)
put the count of prev_char next to the start position of the previous
character.
Below is the working code :-
void torle(char *str)
{ int i=0,j=0,k=0,cnt=1;
char cur_char=str[0],num[100];
while(str[j+1])
{
cnt=1;
while(str[j+1]==cur_char str[j]!='\0'){
j++;
cnt++;
}
str[i++]=cur_char;
if( cnt9 ){
itoa(cnt,num);
k=0;
while(num[k]) str[i++]=num[k++];
}
else if( cnt1 cnt10 )
str[i++]= cnt+'0';
j++;
if(str[j]) cur_char=str[j];
}
if(i!=0){
if(cnt==1)
str[i++]=cur_char;
str[i]='\0';
}
}
On Saturday, 26 May 2012 04:32:35 UTC+5:30, utsav sharma wrote:
Implement a method to perform basic string compression using the counts
of repeated characters.(inplace)
eg:- input: aaabcdef
output:3a5b1c1d1e1f.
what should be my approach to this problem
if i calculate the size of array required to store the output string
and start from the last of the array then i wldn't get the right answer
of above input case.
and if start from front then i wldn't get the right answer of this input
case
eg:- input: abcdef
output: 1a1b1c1d1e1f
--
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/-/4LxWHEUJuK8J.
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: MS question : string compression
u forgot to do inplace and you have wrong conversion of count
On Sat, May 26, 2012 at 11:31 AM, Anchal Gupta anchal92gu...@gmail.comwrote:
hey, here is the function that do the compression and store the output
in an array op.
void str_comp(char *str)
{
int count=0,j=0,i;
char ch,op[100];
for(i=0;istrlen(str);)
{
ch = str[i];
while(str[i] == ch)
{ count++;
i++;
}
op[j] = count+48;
op[++j] = ch;
j++;
count=0;
}
coutinput : ;
for(i=0;istrlen(str);i++)
coutstr[i];
cout\n\noutput : ;
for(i=0;ij;i++)
coutop[i];
}
Best Regards
Anchal Gupta
USIT(GGSIPU), Delhi
+91-9015897983
--
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] Re: MS question : string compression
yeah i forgot inplace so to do that we simply add count and ch in str
input array instead of op.
btw whats wrong with count it give me right answer.
On May 26, 12:08 pm, Hassan Monfared hmonfa...@gmail.com wrote:
u forgot to do inplace and you have wrong conversion of count
On Sat, May 26, 2012 at 11:31 AM, Anchal Gupta anchal92gu...@gmail.comwrote:
hey, here is the function that do the compression and store the output
in an array op.
void str_comp(char *str)
{
int count=0,j=0,i;
char ch,op[100];
for(i=0;istrlen(str);)
{
ch = str[i];
while(str[i] == ch)
{ count++;
i++;
}
op[j] = count+48;
op[++j] = ch;
j++;
count=0;
}
coutinput : ;
for(i=0;istrlen(str);i++)
coutstr[i];
cout\n\noutput : ;
for(i=0;ij;i++)
coutop[i];
}
Best Regards
Anchal Gupta
USIT(GGSIPU), Delhi
+91-9015897983
--
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: MS question : string compression
1- try abb
On Sat, May 26, 2012 at 12:07 PM, Anchal Gupta anchal92gu...@gmail.comwrote:
yeah i forgot inplace so to do that we simply add count and ch in str
input array instead of op.
btw whats wrong with count it give me right answer.
On May 26, 12:08 pm, Hassan Monfared hmonfa...@gmail.com wrote:
u forgot to do inplace and you have wrong conversion of count
On Sat, May 26, 2012 at 11:31 AM, Anchal Gupta anchal92gu...@gmail.com
wrote:
hey, here is the function that do the compression and store the output
in an array op.
void str_comp(char *str)
{
int count=0,j=0,i;
char ch,op[100];
for(i=0;istrlen(str);)
{
ch = str[i];
while(str[i] == ch)
{ count++;
i++;
}
op[j] = count+48;
op[++j] = ch;
j++;
count=0;
}
coutinput : ;
for(i=0;istrlen(str);i++)
coutstr[i];
cout\n\noutput : ;
for(i=0;ij;i++)
coutop[i];
}
Best Regards
Anchal Gupta
USIT(GGSIPU), Delhi
+91-9015897983
--
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.
Re: [algogeeks] Re: MS question : string compression
http://michael.dipperstein.com/rle/index.html
and basic one is
http://www.fileformat.info/mirror/egff/ch09_03.htm
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, May 26, 2012 at 1:10 PM, Hassan Monfared hmonfa...@gmail.comwrote:
1- try abb
On Sat, May 26, 2012 at 12:07 PM, Anchal Gupta anchal92gu...@gmail.comwrote:
yeah i forgot inplace so to do that we simply add count and ch in str
input array instead of op.
btw whats wrong with count it give me right answer.
On May 26, 12:08 pm, Hassan Monfared hmonfa...@gmail.com wrote:
u forgot to do inplace and you have wrong conversion of count
On Sat, May 26, 2012 at 11:31 AM, Anchal Gupta anchal92gu...@gmail.com
wrote:
hey, here is the function that do the compression and store the output
in an array op.
void str_comp(char *str)
{
int count=0,j=0,i;
char ch,op[100];
for(i=0;istrlen(str);)
{
ch = str[i];
while(str[i] == ch)
{ count++;
i++;
}
op[j] = count+48;
op[++j] = ch;
j++;
count=0;
}
coutinput : ;
for(i=0;istrlen(str);i++)
coutstr[i];
cout\n\noutput : ;
for(i=0;ij;i++)
coutop[i];
}
Best Regards
Anchal Gupta
USIT(GGSIPU), Delhi
+91-9015897983
--
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.
--
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: MS question : string compression
This is called Run-Length-Encoding (RLE) of a string.
Its purpose is to save space.So in case of abcdef,I think the output needed
is abcdef (1 is implicit).
The added benefit is it makes the solution in-place.
Approach:- (In-place and Linear Time)
Start from the left of string and PREVIOUS_CHAR = str[0]
move forward till u match the CURRENT_CHAR with PREVIOUS_CHAR and keep
count of PREVIOUS_CHAR
At any point if (PREVIOUS_CHAR!=CURRENT_CHAR)
put the count of prev_char next to the start position of the previous
character.
Below is the working code :-
void torle(char *str)
{ int i=0,j=0,k=0,cnt=1;
char cur_char=str[0],num[100];
while(str[j+1])
{
cnt=1;
while(str[j+1]==cur_char str[j]!='\0'){
j++;
cnt++;
}
str[i++]=cur_char;
if( cnt9 ){
itoa(cnt,num);
k=0;
while(num[k]) str[i++]=num[k++];
}
else if( cnt1 cnt10 )
str[i++]= cnt+'0';
j++;
if(str[j]) cur_char=str[j];
}
if(i!=0){
if(cnt==1)
str[i++]=cur_char;
str[i]='\0';
}
}
On Saturday, 26 May 2012 04:32:35 UTC+5:30, utsav sharma wrote:
Implement a method to perform basic string compression using the counts of
repeated characters.(inplace)
eg:- input: aaabcdef
output:3a5b1c1d1e1f.
what should be my approach to this problem
if i calculate the size of array required to store the output string
and start from the last of the array then i wldn't get the right answer of
above input case.
and if start from front then i wldn't get the right answer of this input
case
eg:- input: abcdef
output: 1a1b1c1d1e1f
--
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/-/4LxWHEUJuK8J.
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: MS Q
If the matrix is 4-connected, we can use the same matrix. now we have to find the total number of connected components of a graph. consider 1 1 1 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 we can use bfs/dfs to mark the nodes as visited and thus total connected components can be counted. On Tuesday, 10 January 2012 07:09:46 UTC+5:30, ashgoel wrote: there is a matrix of 1 and 0 1 is a island and 0 is water 1-1 together makes one island calculate total no of islands Best Regards Ashish Goel Think positive and find fuel in failure -- 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/-/JiDXnyVHn4YJ. 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: MS QUESTION_LINKED LIST
using stack, the problem can be solved in O(n) time. here is the algo :- 1- push first node in stack. mark next node as current 2 - start from current element and check if the node on top of stack is smaller than current , then pop the node and make its next_largest pointer set to current. Do this until the stack is empty or the node on top of stack becomex greater than current. 3- If the node on top of stack is greater than current, push the current node on top of the stack. Move current to current-next 4 - Do this iteration for all nodes until current becomes NULL 5 - if stack is empty,we are done else pop each element of stack and make its next_largest point to NULL On Saturday, 24 March 2012 00:50:43 UTC+5:30, ATul SIngh wrote: Given a linked list with each node having two pointers : one pointing to next node other to null; how will u point the second pointer to next larger no. and return the pointer to smallest node -- ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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/-/RJYgDkGw6NsJ. 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: MS QUESTION_LINKED LIST
@Algo-Geek : this wont work , as requirement of the problem is different . even i misunderstood the problem and posted the algo above doing the same as you have mentioned , but question doesn't say next larger element on right side. It just ask for next larger element cud be on left or cud be on right. so solution is merge sort. On Thu, Mar 29, 2012 at 8:45 AM, Algo-Geek navin.nit...@gmail.com wrote: using stack, the problem can be solved in O(n) time. here is the algo :- 1- push first node in stack. mark next node as current 2 - start from current element and check if the node on top of stack is smaller than current , then pop the node and make its next_largest pointer set to current. Do this until the stack is empty or the node on top of stack becomex greater than current. 3- If the node on top of stack is greater than current, push the current node on top of the stack. Move current to current-next 4 - Do this iteration for all nodes until current becomes NULL 5 - if stack is empty,we are done else pop each element of stack and make its next_largest point to NULL On Saturday, 24 March 2012 00:50:43 UTC+5:30, ATul SIngh wrote: Given a linked list with each node having two pointers : one pointing to next node other to null; how will u point the second pointer to next larger no. and return the pointer to smallest node -- ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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/-/RJYgDkGw6NsJ. 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: MS QUESTION_LINKED LIST
@atul: we always need to point at the next larger node..so that is ruled out. On Sat, Mar 24, 2012 at 10:14 AM, Atul Singh atulsingh7...@gmail.comwrote: I couldn't understand the meaning of *return the pointer to smallest* Is it that that the pointer of largest node will point to smallest node. ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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: MS QUESTION_LINKED LIST
can anyone explain vividly how we can use merge sort here. thank you. On Sat, Mar 24, 2012 at 1:54 PM, Sambhavna Singh coolsambha...@gmail.comwrote: @atul: we always need to point at the next larger node..so that is ruled out. On Sat, Mar 24, 2012 at 10:14 AM, Atul Singh atulsingh7...@gmail.comwrote: I couldn't understand the meaning of *return the pointer to smallest* Is it that that the pointer of largest node will point to smallest node. ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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: MS QUESTION_LINKED LIST
@Atul: after u sort the list the head pointer will automatically point to
the smallest element so u actually return the head of the list.
@Sambhavna:
here is the Pseudoccode (More or less similar to, doing merge sort for
arrays):
Mersgesort(node ** list){
if( head==NULL or head- next == NULL) return;
//split the list into 2 halves (lets say *a and *b)
split(list, a , b);
//sort the two halves individually
mergesort(a);
mergesort(b);
//merge the two halves and return the smallest (first) element
*head = sortedMerge(a,b);
}
for merging u can use recursion:
Merge(node *a, node *b){
struct node *temp;
if (a== NULL ) return b;
if(b==NULL) return a;
if(a- data = b- data)
temp = a;
temp- next = Merge(a-next, b);
else
temp = b;
temp- next = Merge(a, b- next);
return;
}
On Sat, Mar 24, 2012 at 1:55 PM, Sambhavna Singh coolsambha...@gmail.comwrote:
can anyone explain vividly how we can use merge sort here. thank you.
On Sat, Mar 24, 2012 at 1:54 PM, Sambhavna Singh
coolsambha...@gmail.comwrote:
@atul: we always need to point at the next larger node..so that is ruled
out.
On Sat, Mar 24, 2012 at 10:14 AM, Atul Singh atulsingh7...@gmail.comwrote:
I couldn't understand the meaning of *return the pointer to smallest*
Is it that that the pointer of largest node will point to smallest node.
ATul Singh | Final Year | Computer Science Engineering | NIT
Jalandhar | 9530739855 |
--
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.
[algogeeks] Re: MS QUESTION_LINKED LIST
@Abhishek: What sorting algorithm are you going to use? On Mar 23, 3:02 pm, Abhishek Sharma jkabhishe...@gmail.com wrote: It is basically sorting the linked list. Do not change the first pointer of nodes and use the second pointer for sorting. return the pointer to the smallest element. That's it. On Sat, Mar 24, 2012 at 12:50 AM, Atul Singh atulsingh7...@gmail.comwrote: Given a linked list with each node having two pointers : one pointing to next node other to null; how will u point the second pointer to next larger no. and return the pointer to smallest node -- ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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.
[algogeeks] Re: MS QUESTION_LINKED LIST
A merge sort will be O(n*log n) and not use the extra memory required for a heap. Don On Mar 23, 3:11 pm, Ashish Goel ashg...@gmail.com wrote: actually, multimap can be avoided, each element of heap is key,value where key is the element and value is address and build heap on key. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Mar 24, 2012 at 1:40 AM, Ashish Goel ashg...@gmail.com wrote: don't know if i am complicating..assumption, build a multimap of values and the corresponding node address as well as a heap from the given nodes in first pass. now from minheap pick one by one and set the second pointer of previous picked min element to this element using multimap(remove from multimap in parallel while updating the second pointers). Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Mar 24, 2012 at 12:50 AM, Atul Singh atulsingh7...@gmail.comwrote: Given a linked list with each node having two pointers : one pointing to next node other to null; how will u point the second pointer to next larger no. and return the pointer to smallest node -- ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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.
Re: [algogeeks] Re: MS QUESTION_LINKED LIST
@don: inplace Mergesort can be used. Complexity would be O(nlogn). @Ashish: Heapsort is reliable but unstable and also, slower. On Sat, Mar 24, 2012 at 1:49 AM, Don dondod...@gmail.com wrote: A merge sort will be O(n*log n) and not use the extra memory required for a heap. Don On Mar 23, 3:11 pm, Ashish Goel ashg...@gmail.com wrote: actually, multimap can be avoided, each element of heap is key,value where key is the element and value is address and build heap on key. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Mar 24, 2012 at 1:40 AM, Ashish Goel ashg...@gmail.com wrote: don't know if i am complicating..assumption, build a multimap of values and the corresponding node address as well as a heap from the given nodes in first pass. now from minheap pick one by one and set the second pointer of previous picked min element to this element using multimap(remove from multimap in parallel while updating the second pointers). Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Mar 24, 2012 at 12:50 AM, Atul Singh atulsingh7...@gmail.com wrote: Given a linked list with each node having two pointers : one pointing to next node other to null; how will u point the second pointer to next larger no. and return the pointer to smallest node -- ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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. -- 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: MS QUESTION_LINKED LIST
I couldn't understand the meaning of *return the pointer to smallest* Is it that that the pointer of largest node will point to smallest node. ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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: MS Question -Reverse a Linked List in size of 2
struct node
{
int data;
struct node *link;
};
node* CreateNode(int val)
{
node* root = (node*)malloc(sizeof(struct node));
root-data = val;
root-link = NULL;
return root;
}
node* createList(int *arr, int n)
{
node * root = CreateNode(arr[0]);
node * temp = root;
for (int i =1; i n; ++i)
{
temp-link = CreateNode(arr[i]);
temp = temp-link;
}
return root;
}
void deleteList(node *root)
{
if(!root) return;
deleteList(root-link);
free(root);
}
void printList(node *root)
{
while(root)
{
printf(%d - , root-data);
root= root-link;
}
printf(NULL\n);
}
void reverseK(node *root, node **head, node **tail, int i, int K)
{
if(!root-link)
*head = root;
else
{
reverseK(root-link, head, tail, (i+1)%K, K);
if(i == K-1)
{
*tail = *head;
*head = root;
}
else
{
root-link-link= root;
if(i == 0) root-link = *tail;
}
}
}
node* reverseKSize(node *root, int K)
{
if(!root) return NULL;
node *head = NULL;
node *tail = NULL;
reverseK(root, head, tail, 0, K);
return head;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[11] = {1,2,3,4,5,6,7,8,9,10,11};
node* root = createList(a, 11);
printList(root);
root = reverseKSize(root, 2);
printList(root);
deleteList(root);
return 0;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 24, 2012 at 2:30 AM, Lucifer sourabhd2...@gmail.com wrote:
@above
attaching the file..
--
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/-/YW_phbT3me4J.
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: MS Question -Reverse a Linked List in size of 2
@Ashish : seems exactly similar to Lucifer code or you modified something
in his code ?? ...
On Tue, Jan 24, 2012 at 2:02 PM, Ashish Goel ashg...@gmail.com wrote:
struct node
{
int data;
struct node *link;
};
node* CreateNode(int val)
{
node* root = (node*)malloc(sizeof(struct node));
root-data = val;
root-link = NULL;
return root;
}
node* createList(int *arr, int n)
{
node * root = CreateNode(arr[0]);
node * temp = root;
for (int i =1; i n; ++i)
{
temp-link = CreateNode(arr[i]);
temp = temp-link;
}
return root;
}
void deleteList(node *root)
{
if(!root) return;
deleteList(root-link);
free(root);
}
void printList(node *root)
{
while(root)
{
printf(%d - , root-data);
root= root-link;
}
printf(NULL\n);
}
void reverseK(node *root, node **head, node **tail, int i, int K)
{
if(!root-link)
*head = root;
else
{
reverseK(root-link, head, tail, (i+1)%K, K);
if(i == K-1)
{
*tail = *head;
*head = root;
}
else
{
root-link-link= root;
if(i == 0) root-link = *tail;
}
}
}
node* reverseKSize(node *root, int K)
{
if(!root) return NULL;
node *head = NULL;
node *tail = NULL;
reverseK(root, head, tail, 0, K);
return head;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[11] = {1,2,3,4,5,6,7,8,9,10,11};
node* root = createList(a, 11);
printList(root);
root = reverseKSize(root, 2);
printList(root);
deleteList(root);
return 0;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 24, 2012 at 2:30 AM, Lucifer sourabhd2...@gmail.com wrote:
@above
attaching the file..
--
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/-/YW_phbT3me4J.
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.
Re: [algogeeks] Re: MS Question -Reverse a Linked List in size of 2
oh, a possible mistake from my side, ignore my mail please...
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 24, 2012 at 3:08 PM, atul anand atul.87fri...@gmail.com wrote:
@Ashish : seems exactly similar to Lucifer code or you modified something
in his code ?? ...
On Tue, Jan 24, 2012 at 2:02 PM, Ashish Goel ashg...@gmail.com wrote:
struct node
{
int data;
struct node *link;
};
node* CreateNode(int val)
{
node* root = (node*)malloc(sizeof(struct node));
root-data = val;
root-link = NULL;
return root;
}
node* createList(int *arr, int n)
{
node * root = CreateNode(arr[0]);
node * temp = root;
for (int i =1; i n; ++i)
{
temp-link = CreateNode(arr[i]);
temp = temp-link;
}
return root;
}
void deleteList(node *root)
{
if(!root) return;
deleteList(root-link);
free(root);
}
void printList(node *root)
{
while(root)
{
printf(%d - , root-data);
root= root-link;
}
printf(NULL\n);
}
void reverseK(node *root, node **head, node **tail, int i, int K)
{
if(!root-link)
*head = root;
else
{
reverseK(root-link, head, tail, (i+1)%K, K);
if(i == K-1)
{
*tail = *head;
*head = root;
}
else
{
root-link-link= root;
if(i == 0) root-link = *tail;
}
}
}
node* reverseKSize(node *root, int K)
{
if(!root) return NULL;
node *head = NULL;
node *tail = NULL;
reverseK(root, head, tail, 0, K);
return head;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[11] = {1,2,3,4,5,6,7,8,9,10,11};
node* root = createList(a, 11);
printList(root);
root = reverseKSize(root, 2);
printList(root);
deleteList(root);
return 0;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 24, 2012 at 2:30 AM, Lucifer sourabhd2...@gmail.com wrote:
@above
attaching the file..
--
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/-/YW_phbT3me4J.
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.
--
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: MS Question -Reverse a Linked List in size of 2
Steps: 1)Reverse the list ... 2)Now do the swap two nodes... consecutively... PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING -- 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: MS Q
Idea: 1)Take count =0; 2) make Outer loop ...and search for 1's . 3) Start ...searching for 1 consecutively... and make it ..0 untill all consecutive 1's becomes 0.. and then count++ 4) go to 1) untill all 1's finished.. count will give the total number of islands... PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING -- 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: MS Q
@Praveen : i have doubt in your algo...it seem it may fail for some cases... On Tue, Jan 24, 2012 at 5:59 PM, praveen raj praveen0...@gmail.com wrote: Idea: 1)Take count =0; 2) make Outer loop ...and search for 1's . 3) Start ...searching for 1 consecutively... and make it ..0 untill all consecutive 1's becomes 0.. and then count++ 4) go to 1) untill all 1's finished.. count will give the total number of islands... PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING -- 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: MS Q
name it. PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING On Wed, Jan 25, 2012 at 12:45 AM, atul anand atul.87fri...@gmail.comwrote: @Praveen : i have doubt in your algo...it seem it may fail for some cases... On Tue, Jan 24, 2012 at 5:59 PM, praveen raj praveen0...@gmail.comwrote: Idea: 1)Take count =0; 2) make Outer loop ...and search for 1's . 3) Start ...searching for 1 consecutively... and make it ..0 untill all consecutive 1's becomes 0.. and then count++ 4) go to 1) untill all 1's finished.. count will give the total number of islands... PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING -- 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.
Re: [algogeeks] Re: MS Q
@praveen : little more clarity required in your algoare you calling it recursively or moving row by row. On Tue, Jan 24, 2012 at 5:59 PM, praveen raj praveen0...@gmail.com wrote: Idea: 1)Take count =0; 2) make Outer loop ...and search for 1's . 3) Start ...searching for 1 consecutively... and make it ..0 untill all consecutive 1's becomes 0.. and then count++ 4) go to 1) untill all 1's finished.. count will give the total number of islands... PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING -- 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] Re: MS Question -Reverse a Linked List in size of 2
I just wrote a code which would work for any given size K.
I tested it with K = 1 till 7.
[ in the question asked above K=2]
Also, tested for corner cases..
If you guys are interested, then have a look at the code..
I have added few helper functions so that you can directly run the
code and use it for testing purposes as well..
Code is in the attached file..
On Jan 23, 11:34 pm, Dhaval Patel dhaval.pu...@gmail.com wrote:
struct node* revll(struct node* root)
{
return reverse(root,NULL);
}
struct node* reverse(struct node* head,struct node* prev)
{
struct node* temp1;
if(head-next==NULL)
{
head-next=prev;
return head;}
else
{
temp1=reverse(head-next,head);
head-next=prev;
return temp1;
}
}
--
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: MS Question -Reverse a Linked List in size of 2
@above
attaching the file..
--
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/-/YW_phbT3me4J.
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.
struct node
{
int data;
struct node *link;
};
node* CreateNode(int val)
{
node* root = (node*)malloc(sizeof(struct node));
root-data = val;
root-link = NULL;
return root;
}
node* createList(int *arr, int n)
{
node * root = CreateNode(arr[0]);
node * temp = root;
for (int i =1; i n; ++i)
{
temp-link = CreateNode(arr[i]);
temp = temp-link;
}
return root;
}
void deleteList(node *root)
{
if(!root) return;
deleteList(root-link);
free(root);
}
void printList(node *root)
{
while(root)
{
printf(%d - , root-data);
root= root-link;
}
printf(NULL\n);
}
void reverseK(node *root, node **head, node **tail, int i, int K)
{
if(!root-link)
*head = root;
else
{
reverseK(root-link, head, tail, (i+1)%K, K);
if(i == K-1)
{
*tail = *head;
*head = root;
}
else
{
root-link-link= root;
if(i == 0) root-link = *tail;
}
}
}
node* reverseKSize(node *root, int K)
{
if(!root) return NULL;
node *head = NULL;
node *tail = NULL;
reverseK(root, head, tail, 0, K);
return head;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[11] = {1,2,3,4,5,6,7,8,9,10,11};
node* root = createList(a, 11);
printList(root);
root = reverseKSize(root, 2);
printList(root);
deleteList(root);
return 0;
}
Re: [algogeeks] Re: MS Q
Here is my solution. Please have a look at it. Any kind of positive
criticism will be highly appreciated.
bool isConnected(int **space, int x, int y)
{
if (x == 0 y == 0)
{
return false;
}
if (y 0)
{
if (space[x][y-1] == 1)
return true;
}
if (x 0)
{
if (space[x-1][y] == 1)
return true;
}
if (x 0 y 0)
{
if (space[x-1][y-1] == 1)
return true;
}
if ((x-1 = 0)(y+1 sizeof(space)/sizeof(space[0][0])))
{
if (space[x-1][y+1] == 1)
return true;
}
return false;
}
int _tmain(int argc, _TCHAR* argv[])
{
int len = 4;
int breadth = 4;
int **space;
space = new int*[len];
for (int i = 0; i len; i++)
space[i] = new int[breadth];
space[0][0] = 1;
space[0][1] = 1;
space[0][2] = 0;
space[0][3] = 0;
space[1][0] = 1;
space[1][1] = 1;
space[1][2] = 0;
space[1][3] = 0;
space[2][0] = 0;
space[2][1] = 0;
space[2][2] = 0;
space[2][3] = 0;
space[3][0] = 0;
space[3][1] = 0;
space[3][2] = 1;
space[3][3] = 1;
int islands = 0;
for (int i = 0; i len; i++)
{
for (int j = 0; j breadth; j++)
if (isConnected(space, i, j) == false space[i][j] == 1)
islands++;
}
cout islandsendl;
int r = 0;
cin r;
return 0;
}
The function isConnected tells if an element at x,y on matrix (space) is
connected to an existing island or is it completely a new island.
The 2D array used in main function is only a test case. You can replace it
with anything you want. The nested loop in the main method iterates over
the whole array and gets the total number of islands that are present.
Anyway, nice question. I liked solving it :)
One more thing. Was it asked in phone interview or on-site interview?
On Wed, Jan 11, 2012 at 6:08 PM, Gene gene.ress...@gmail.com wrote:
The OP is not clear on how to handle diagonals. If adjacent 1's on the
diagonal are considered connected, then just add 4 more calls to
erase().
The standard terms are 4-connected and 8-connected. Both come up when
working with grid graphs or pixel matrices.
On Jan 10, 9:40 pm, surender sanke surend...@gmail.com wrote:
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com
wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column
wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com
wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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
Re: [algogeeks] Re: MS Q
this is the solution that i was referring to in the link i provided.
On the same lines there is another problem of rat in a maze .
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com
wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com
wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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] Re: MS Q
Part of the problem must be rules that specify how 1's can be
connected to form an island.
From the discussion, it looks like the rules are that a 1 must be
connected North, West, East, or South. This is called a 4-connected
grid.
Another possibility would be an 8-connected grid. This is probably
what you have in mind. In this case a 1 can be connected to another 1
North, Northeast, East, Southeast, South, Southwest, West, or
NorthWest. In the code I gave in a previous message, you'd just add 4
more erase() calls for the diagonal corners.
Since the OP never said which rule to use, you are not wrong. You're
just answering a different question than he/she had in mind. This is
a difficulty that often occurs when a question is asked imprecisely.
An excellent lesson to learn for anyone who wants to be a software
engineer...
On Jan 11, 1:28 am, Umer Farooq the.um...@gmail.com wrote:
I still don't get how are they two islands. As long as I have understood,
diagonals abridge the two islands into one. In this case, these two islands
are connected so they form one single island?
1 1 0 0
1 1 0 0
0 0 1 1
This can be either one single island. Or they are three island if a change
in direction makes a whole new island.
Can anyone please clear me the problem?
On Wed, Jan 11, 2012 at 10:24 AM, prakash y yprakash@gmail.com wrote:
I think atul/Ramakanth's approach will work fine, if we include one more
condition
for each arr[i][j]
if(arr[i][j]==1)
{
if (arr[i-1][j]==0 arr[i][j-1]==0 arr[i-1][j-1]==0)
count++;
else if (arr[i-1][j]==1 arr[i][j-1]==1 arr[i-1][j-1]==0)
count--;
}
On Wed, Jan 11, 2012 at 8:10 AM, surender sanke surend...@gmail.comwrote:
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com
wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column
wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com
wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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
[algogeeks] Re: MS Q
The OP is not clear on how to handle diagonals. If adjacent 1's on the
diagonal are considered connected, then just add 4 more calls to
erase().
The standard terms are 4-connected and 8-connected. Both come up when
working with grid graphs or pixel matrices.
On Jan 10, 9:40 pm, surender sanke surend...@gmail.com wrote:
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com
wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com
wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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] Re: MS Q
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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: MS Q
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com
wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com
wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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: MS Q
I think atul/Ramakanth's approach will work fine, if we include one more
condition
for each arr[i][j]
if(arr[i][j]==1)
{
if (arr[i-1][j]==0 arr[i][j-1]==0 arr[i-1][j-1]==0)
count++;
else if (arr[i-1][j]==1 arr[i][j-1]==1 arr[i-1][j-1]==0)
count--;
}
On Wed, Jan 11, 2012 at 8:10 AM, surender sanke surend...@gmail.com wrote:
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com
wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com
wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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.
Re: [algogeeks] Re: MS Q
@Umer : it has 1 island ashish made editing mistake before.
On Wed, Jan 11, 2012 at 11:58 AM, Umer Farooq the.um...@gmail.com wrote:
I still don't get how are they two islands. As long as I have understood,
diagonals abridge the two islands into one. In this case, these two islands
are connected so they form one single island?
1 1 0 0
1 1 0 0
0 0 1 1
This can be either one single island. Or they are three island if a change
in direction makes a whole new island.
Can anyone please clear me the problem?
On Wed, Jan 11, 2012 at 10:24 AM, prakash y yprakash@gmail.comwrote:
I think atul/Ramakanth's approach will work fine, if we include one more
condition
for each arr[i][j]
if(arr[i][j]==1)
{
if (arr[i-1][j]==0 arr[i][j-1]==0 arr[i-1][j-1]==0)
count++;
else if (arr[i-1][j]==1 arr[i][j-1]==1 arr[i-1][j-1]==0)
count--;
}
On Wed, Jan 11, 2012 at 8:10 AM, surender sanke surend...@gmail.comwrote:
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.com
wrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column
wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com
wrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
--
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.
--
Umer
--
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: MS test cases type Questions
there r lot of stuff for this in algogeeks.plz u all r requested to post these kind of quries on interview-street..i can tell u this last tym... for testing profyl questions will be : 1.u open word fyl and do wrk and save...what can be test cases that error can pccur. 2. u taking to frnd on phn..suddenly connection cut off...write for thta.. for devloper... 1. 2 server access same data from main data..hw to maintain integrity. no need to prrpare..these r general On Sun, Oct 9, 2011 at 1:42 AM, payal gupta gpt.pa...@gmail.com wrote: k... thanx...your info vud be of great help for me in future.. regards, PAYAL GUPTA, CSE 3RD YR NIT_B On Wed, Sep 14, 2011 at 11:38 PM, KK kunalkapadi...@gmail.com wrote: U must mention all the boundary cases, very large input cases, -ve nos and must throw appropriate exception while coding during interviews... Questions are not too hard in MS... just they dont want buggy code... even if u allocate memory.. u should take an if condition i.e. if (p ! = NULL)...and avoid such other silly mistakes... -- 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.
Re: [algogeeks] Re: MS test cases type Questions
k... thanx...your info vud be of great help for me in future.. regards, PAYAL GUPTA, CSE 3RD YR NIT_B On Wed, Sep 14, 2011 at 11:38 PM, KK kunalkapadi...@gmail.com wrote: U must mention all the boundary cases, very large input cases, -ve nos and must throw appropriate exception while coding during interviews... Questions are not too hard in MS... just they dont want buggy code... even if u allocate memory.. u should take an if condition i.e. if (p ! = NULL)...and avoid such other silly mistakes... -- 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] Re: MS question
@rahul sharma, i ran this code, it is producing wrong answer :| check it, http://codepad.org/THv1hJq1 anyone with correct solution? -- 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/-/26XU3UBqZ6EJ. 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: MS question
search archives :-/ On Mon, Oct 3, 2011 at 11:47 AM, pranav agrawal pranav.is.cool.agra...@gmail.com wrote: @rahul sharma, i ran this code, it is producing wrong answer :| check it, http://codepad.org/THv1hJq1 anyone with correct solution? -- 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/-/26XU3UBqZ6EJ. 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: MS question
yeah it is wrong..i have a solution but uses 0(n+m) space.i need it in 0(n*m) tymand o(1) space On Mon, Oct 3, 2011 at 11:55 AM, shady sinv...@gmail.com wrote: search archives :-/ On Mon, Oct 3, 2011 at 11:47 AM, pranav agrawal pranav.is.cool.agra...@gmail.com wrote: @rahul sharma, i ran this code, it is producing wrong answer :| check it, http://codepad.org/THv1hJq1 anyone with correct solution? -- 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/-/26XU3UBqZ6EJ. 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.
Re: [algogeeks] Re: MS question
keep two var row0 and col0 for checking if there is any 0 in row0flag /col0flag now walk over elements from 1,1 to n,m and set corresponding entry in 0th row /column if you hit a zero. now walk over zeroth column and rwo and set the complete row/col if a 0 is there in 0th row/col. after this based on row0flag/col0flag, set oth col/row values to 0. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Oct 3, 2011 at 12:08 PM, rahul sharma rahul23111...@gmail.comwrote: yeah it is wrong..i have a solution but uses 0(n+m) space.i need it in 0(n*m) tymand o(1) space On Mon, Oct 3, 2011 at 11:55 AM, shady sinv...@gmail.com wrote: search archives :-/ On Mon, Oct 3, 2011 at 11:47 AM, pranav agrawal pranav.is.cool.agra...@gmail.com wrote: @rahul sharma, i ran this code, it is producing wrong answer :| check it, http://codepad.org/THv1hJq1 anyone with correct solution? -- 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/-/26XU3UBqZ6EJ. 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. -- 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: MS question
@ashish can u give an xample.plz...i have read a lot archives ...but cant find in 0(1) spaceu using 2 var only...plz give xample...nended urgent.thnx On Tue, Oct 4, 2011 at 7:26 AM, Ashish Goel ashg...@gmail.com wrote: keep two var row0 and col0 for checking if there is any 0 in row0flag /col0flag now walk over elements from 1,1 to n,m and set corresponding entry in 0th row /column if you hit a zero. now walk over zeroth column and rwo and set the complete row/col if a 0 is there in 0th row/col. after this based on row0flag/col0flag, set oth col/row values to 0. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Oct 3, 2011 at 12:08 PM, rahul sharma rahul23111...@gmail.comwrote: yeah it is wrong..i have a solution but uses 0(n+m) space.i need it in 0(n*m) tymand o(1) space On Mon, Oct 3, 2011 at 11:55 AM, shady sinv...@gmail.com wrote: search archives :-/ On Mon, Oct 3, 2011 at 11:47 AM, pranav agrawal pranav.is.cool.agra...@gmail.com wrote: @rahul sharma, i ran this code, it is producing wrong answer :| check it, http://codepad.org/THv1hJq1 anyone with correct solution? -- 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/-/26XU3UBqZ6EJ. 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. -- 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: MS question
1 1 0 1
0 1 1 1
1 1 1 1
1 1 1 0
row0 is true
col0 is true
for (int i=1; in;i++)
for (int j=1;jm;j++)
if (a[i][j] == 0) {a[i][0]=0; a[0][j]=0;}
now after this
1 1 0 0
0 1 1 1
1 1 1 1
0 1 1 0
for (int i=1; in;i++)
if (a[i][0] ==0) for (int j=1; jm;j++) a[i][j]=0;
for (int j=1; im;j++)
if (a[0][j] ==0) for (int i=1; in;i++) a[i][j]=0;
after this
1 1 0 0
0 0 0 0
1 1 0 0
0 0 0 0
because of row0 and col0 vars
final output is
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Oct 4, 2011 at 7:49 AM, rahul sharma rahul23111...@gmail.comwrote:
@ashish can u give an xample.plz...i have read a lot archives ...but
cant find in 0(1) spaceu using 2 var only...plz give xample...nended
urgent.thnx
On Tue, Oct 4, 2011 at 7:26 AM, Ashish Goel ashg...@gmail.com wrote:
keep two var row0 and col0 for checking if there is any 0 in row0flag
/col0flag
now walk over elements from 1,1 to n,m and set corresponding entry in 0th
row /column if you hit a zero.
now walk over zeroth column and rwo and set the complete row/col if a 0 is
there in 0th row/col.
after this based on row0flag/col0flag, set oth col/row values to 0.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Oct 3, 2011 at 12:08 PM, rahul sharma rahul23111...@gmail.comwrote:
yeah it is wrong..i have a solution but uses 0(n+m) space.i need
it in 0(n*m) tymand o(1) space
On Mon, Oct 3, 2011 at 11:55 AM, shady sinv...@gmail.com wrote:
search archives :-/
On Mon, Oct 3, 2011 at 11:47 AM, pranav agrawal
pranav.is.cool.agra...@gmail.com wrote:
@rahul sharma, i ran this code, it is producing wrong answer :|
check it, http://codepad.org/THv1hJq1
anyone with correct solution?
--
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/-/26XU3UBqZ6EJ.
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.
--
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.
Re: [algogeeks] Re: MS question
row0 and col0 initilayy true coz we have 0 in 0 row???or these r default
values?
On Tue, Oct 4, 2011 at 8:07 AM, Ashish Goel ashg...@gmail.com wrote:
1 1 0 1
0 1 1 1
1 1 1 1
1 1 1 0
row0 is true
col0 is true
for (int i=1; in;i++)
for (int j=1;jm;j++)
if (a[i][j] == 0) {a[i][0]=0; a[0][j]=0;}
now after this
1 1 0 0
0 1 1 1
1 1 1 1
0 1 1 0
for (int i=1; in;i++)
if (a[i][0] ==0) for (int j=1; jm;j++) a[i][j]=0;
for (int j=1; im;j++)
if (a[0][j] ==0) for (int i=1; in;i++) a[i][j]=0;
after this
1 1 0 0
0 0 0 0
1 1 0 0
0 0 0 0
because of row0 and col0 vars
final output is
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Oct 4, 2011 at 7:49 AM, rahul sharma rahul23111...@gmail.comwrote:
@ashish can u give an xample.plz...i have read a lot archives ...but
cant find in 0(1) spaceu using 2 var only...plz give xample...nended
urgent.thnx
On Tue, Oct 4, 2011 at 7:26 AM, Ashish Goel ashg...@gmail.com wrote:
keep two var row0 and col0 for checking if there is any 0 in row0flag
/col0flag
now walk over elements from 1,1 to n,m and set corresponding entry in 0th
row /column if you hit a zero.
now walk over zeroth column and rwo and set the complete row/col if a 0
is there in 0th row/col.
after this based on row0flag/col0flag, set oth col/row values to 0.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Oct 3, 2011 at 12:08 PM, rahul sharma
rahul23111...@gmail.comwrote:
yeah it is wrong..i have a solution but uses 0(n+m) space.i need
it in 0(n*m) tymand o(1) space
On Mon, Oct 3, 2011 at 11:55 AM, shady sinv...@gmail.com wrote:
search archives :-/
On Mon, Oct 3, 2011 at 11:47 AM, pranav agrawal
pranav.is.cool.agra...@gmail.com wrote:
@rahul sharma, i ran this code, it is producing wrong answer :|
check it, http://codepad.org/THv1hJq1
anyone with correct solution?
--
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/-/26XU3UBqZ6EJ.
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.
--
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.
--
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: MS question
0 in 0th row as well as 0 in 0th col and hence true
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Oct 4, 2011 at 8:28 AM, rahul sharma rahul23111...@gmail.comwrote:
row0 and col0 initilayy true coz we have 0 in 0 row???or these r default
values?
On Tue, Oct 4, 2011 at 8:07 AM, Ashish Goel ashg...@gmail.com wrote:
1 1 0 1
0 1 1 1
1 1 1 1
1 1 1 0
row0 is true
col0 is true
for (int i=1; in;i++)
for (int j=1;jm;j++)
if (a[i][j] == 0) {a[i][0]=0; a[0][j]=0;}
now after this
1 1 0 0
0 1 1 1
1 1 1 1
0 1 1 0
for (int i=1; in;i++)
if (a[i][0] ==0) for (int j=1; jm;j++) a[i][j]=0;
for (int j=1; im;j++)
if (a[0][j] ==0) for (int i=1; in;i++) a[i][j]=0;
after this
1 1 0 0
0 0 0 0
1 1 0 0
0 0 0 0
because of row0 and col0 vars
final output is
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Oct 4, 2011 at 7:49 AM, rahul sharma rahul23111...@gmail.comwrote:
@ashish can u give an xample.plz...i have read a lot archives ...but
cant find in 0(1) spaceu using 2 var only...plz give xample...nended
urgent.thnx
On Tue, Oct 4, 2011 at 7:26 AM, Ashish Goel ashg...@gmail.com wrote:
keep two var row0 and col0 for checking if there is any 0 in row0flag
/col0flag
now walk over elements from 1,1 to n,m and set corresponding entry in
0th row /column if you hit a zero.
now walk over zeroth column and rwo and set the complete row/col if a 0
is there in 0th row/col.
after this based on row0flag/col0flag, set oth col/row values to 0.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Oct 3, 2011 at 12:08 PM, rahul sharma
rahul23111...@gmail.comwrote:
yeah it is wrong..i have a solution but uses 0(n+m) space.i
need it in 0(n*m) tymand o(1) space
On Mon, Oct 3, 2011 at 11:55 AM, shady sinv...@gmail.com wrote:
search archives :-/
On Mon, Oct 3, 2011 at 11:47 AM, pranav agrawal
pranav.is.cool.agra...@gmail.com wrote:
@rahul sharma, i ran this code, it is producing wrong answer :|
check it, http://codepad.org/THv1hJq1
anyone with correct solution?
--
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/-/26XU3UBqZ6EJ.
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.
--
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.
--
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,
Re: [algogeeks] Re: MS question
so we shoul d aslo add loop at the top to find only for firrst row and
column the initial values
On Tue, Oct 4, 2011 at 8:30 AM, Ashish Goel ashg...@gmail.com wrote:
0 in 0th row as well as 0 in 0th col and hence true
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Oct 4, 2011 at 8:28 AM, rahul sharma rahul23111...@gmail.comwrote:
row0 and col0 initilayy true coz we have 0 in 0 row???or these r default
values?
On Tue, Oct 4, 2011 at 8:07 AM, Ashish Goel ashg...@gmail.com wrote:
1 1 0 1
0 1 1 1
1 1 1 1
1 1 1 0
row0 is true
col0 is true
for (int i=1; in;i++)
for (int j=1;jm;j++)
if (a[i][j] == 0) {a[i][0]=0; a[0][j]=0;}
now after this
1 1 0 0
0 1 1 1
1 1 1 1
0 1 1 0
for (int i=1; in;i++)
if (a[i][0] ==0) for (int j=1; jm;j++) a[i][j]=0;
for (int j=1; im;j++)
if (a[0][j] ==0) for (int i=1; in;i++) a[i][j]=0;
after this
1 1 0 0
0 0 0 0
1 1 0 0
0 0 0 0
because of row0 and col0 vars
final output is
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Oct 4, 2011 at 7:49 AM, rahul sharma rahul23111...@gmail.comwrote:
@ashish can u give an xample.plz...i have read a lot archives ...but
cant find in 0(1) spaceu using 2 var only...plz give xample...nended
urgent.thnx
On Tue, Oct 4, 2011 at 7:26 AM, Ashish Goel ashg...@gmail.com wrote:
keep two var row0 and col0 for checking if there is any 0 in row0flag
/col0flag
now walk over elements from 1,1 to n,m and set corresponding entry in
0th row /column if you hit a zero.
now walk over zeroth column and rwo and set the complete row/col if a 0
is there in 0th row/col.
after this based on row0flag/col0flag, set oth col/row values to 0.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Oct 3, 2011 at 12:08 PM, rahul sharma rahul23111...@gmail.com
wrote:
yeah it is wrong..i have a solution but uses 0(n+m) space.i
need it in 0(n*m) tymand o(1) space
On Mon, Oct 3, 2011 at 11:55 AM, shady sinv...@gmail.com wrote:
search archives :-/
On Mon, Oct 3, 2011 at 11:47 AM, pranav agrawal
pranav.is.cool.agra...@gmail.com wrote:
@rahul sharma, i ran this code, it is producing wrong answer :|
check it, http://codepad.org/THv1hJq1
anyone with correct solution?
--
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/-/26XU3UBqZ6EJ.
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.
--
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.
--
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
Re: [algogeeks] Re: MS question
got it..thnx yr
On Tue, Oct 4, 2011 at 8:34 AM, rahul sharma rahul23111...@gmail.comwrote:
so we shoul d aslo add loop at the top to find only for firrst row and
column the initial values
On Tue, Oct 4, 2011 at 8:30 AM, Ashish Goel ashg...@gmail.com wrote:
0 in 0th row as well as 0 in 0th col and hence true
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Oct 4, 2011 at 8:28 AM, rahul sharma rahul23111...@gmail.comwrote:
row0 and col0 initilayy true coz we have 0 in 0 row???or these r default
values?
On Tue, Oct 4, 2011 at 8:07 AM, Ashish Goel ashg...@gmail.com wrote:
1 1 0 1
0 1 1 1
1 1 1 1
1 1 1 0
row0 is true
col0 is true
for (int i=1; in;i++)
for (int j=1;jm;j++)
if (a[i][j] == 0) {a[i][0]=0; a[0][j]=0;}
now after this
1 1 0 0
0 1 1 1
1 1 1 1
0 1 1 0
for (int i=1; in;i++)
if (a[i][0] ==0) for (int j=1; jm;j++) a[i][j]=0;
for (int j=1; im;j++)
if (a[0][j] ==0) for (int i=1; in;i++) a[i][j]=0;
after this
1 1 0 0
0 0 0 0
1 1 0 0
0 0 0 0
because of row0 and col0 vars
final output is
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Oct 4, 2011 at 7:49 AM, rahul sharma
rahul23111...@gmail.comwrote:
@ashish can u give an xample.plz...i have read a lot archives
...but cant find in 0(1) spaceu using 2 var only...plz give
xample...nended urgent.thnx
On Tue, Oct 4, 2011 at 7:26 AM, Ashish Goel ashg...@gmail.com wrote:
keep two var row0 and col0 for checking if there is any 0 in row0flag
/col0flag
now walk over elements from 1,1 to n,m and set corresponding entry in
0th row /column if you hit a zero.
now walk over zeroth column and rwo and set the complete row/col if a
0 is there in 0th row/col.
after this based on row0flag/col0flag, set oth col/row values to 0.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Oct 3, 2011 at 12:08 PM, rahul sharma
rahul23111...@gmail.com wrote:
yeah it is wrong..i have a solution but uses 0(n+m) space.i
need it in 0(n*m) tymand o(1) space
On Mon, Oct 3, 2011 at 11:55 AM, shady sinv...@gmail.com wrote:
search archives :-/
On Mon, Oct 3, 2011 at 11:47 AM, pranav agrawal
pranav.is.cool.agra...@gmail.com wrote:
@rahul sharma, i ran this code, it is producing wrong answer :|
check it, http://codepad.org/THv1hJq1
anyone with correct solution?
--
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/-/26XU3UBqZ6EJ.
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.
--
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.
--
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
[algogeeks] Re: MS WRITTEN TEST FOR INTERNS
pec, unversity of technology chandigarh On Oct 2, 10:46 pm, rahul sharma rahul23111...@gmail.com wrote: hey from which college r u??? On Sun, Oct 2, 2011 at 10:51 PM, gaurav kumar mailmea...@gmail.com wrote: there were 10 objective questions covering c,c++ and ds questions were on mainly memory allocation stack and heap ,etc output/error ; subjective part 1. compress the given string eg. aaabbcccaadee o/p = a3b2c3de2 2. u have to give the various test case and fault cases for a USB device such that when u connect that with a camera...photo viewer wizard should be activated when with a computer then file transfer wizard...etc etc -- 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: MS WRITTEN TEST FOR INTERNS
u r a 3rd year studentfor placement test is different??? On Sun, Oct 2, 2011 at 11:19 PM, gaurav kumar mailmea...@gmail.com wrote: pec, unversity of technology chandigarh On Oct 2, 10:46 pm, rahul sharma rahul23111...@gmail.com wrote: hey from which college r u??? On Sun, Oct 2, 2011 at 10:51 PM, gaurav kumar mailmea...@gmail.com wrote: there were 10 objective questions covering c,c++ and ds questions were on mainly memory allocation stack and heap ,etc output/error ; subjective part 1. compress the given string eg. aaabbcccaadee o/p = a3b2c3de2 2. u have to give the various test case and fault cases for a USB device such that when u connect that with a camera...photo viewer wizard should be activated when with a computer then file transfer wizard...etc etc -- 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.
Re: [algogeeks] Re: MS Question - Median of a BST without using extra space and in O(n)
*@all to median of BST time O(n) space O(1) (modified code of nitin to get median) medianBST*(node, n) int x = 0; *while* hasleftchild(node) *do* node = node.left *do* x++; if (x == n/2) return node-val; *if* (hasrightchild(node)) *then* node = node.right *while* hasleftchild(node) *do* node = node.left *else* *while* node.parent ≠ *null* *and* node == node.parent.right *do* node = node.parent node = node.parent *while* node ≠ *null* @dheeraj u U can get the number of elements by just traversing the who tree by above method -- 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: MS question
If you're given that it's a sparse matrix, then you must assume
storage is in a sparse matrix data structure to get time less than
O(mn).
In fact, if you assume the right data structure, then the operation
can take O(1) time.
For example if you say the structure is an array of sets of indices of
the 1's in each row (so that L(i) is a list that contains j if and
only if A(i,j) is a 1), then all you have to do is flip a bit saying
the representation has changed, i.e. lookups will work differently.
The old lookup is
A(i,j) = if L(i) contains j then 1 else 0.
The new lookup will be
A(i,j) = if L(i) is nonempty or L(j) contains i then 1 else 0
You'd probably want to store the sets in hash tables so that lookups
will remain O(1). Other choices might make more sense if A has special
structure.
On Sep 26, 6:41 pm, Ankur Garg ankurga...@gmail.com wrote:
Guys an Update ,
This has been asked in MS by me.. I suggested O(m*n) but they were looking
for a solution in nlogn ( n*n Sparse Matrix ) ..Any idea ...
This post was discussed earlier but every1 came with O(m*n) solution so
instead of cluttering it ..opened a new One ...
On Tue, Sep 27, 2011 at 3:06 AM, Gene gene.ress...@gmail.com wrote:
I assume we don't want to use extra storage.
So one way is this: Go over the matrix and mark the first row with a 1
and the first column with a 1 for each 1 you find. Because row and
column 1 are used for temporary storage in this manner, you must first
remember whether they contained a 1, then go ahead. With row and
column 1 holding the necessary marks, you can fill in all the rows and
columns except them. Finally you can fill in row and column 1 by
checking the saved values. It will look something like this.
row0has1 = 0;
for (j = 0; j n; j++) if (M(0,j)) { row0has1 = 1; break; }
col0has1 = 0;
for (i = 0; i n; i++) if (M(i,0)) { col0has1 = 1; break; }
for (i = 1; i m; i++)
for (j = 1; j n; j++)
if (M(i,j)) M(i,0) = M(0,j) = 1;
for (i = 1; i m; i++)
for (j = 1; j n; j++)
if (M(i,0) || M(0,j)) M(i, j) = 1;
if (row0has1)
for (j = 0; j n; j++) M(0,j) = 1;
if (col0has1)
for (i = 0; i n; i++) M(i,0) = 1;
Maybe there's a slicker way, but this is O(mn)
On Sep 26, 9:46 pm, Ankur Garg ankurga...@gmail.com wrote:
Saw this question in one of the algo communities.
Amazon telephonic interview question on Matrix
Input is a matrix of size n x m of 0's and 1's. eg:
1 0 0 1
0 0 1 0
0 0 0 0
If a location has 1; make all the elements of that row and column = 1. eg
1 1 1 1
1 1 1 1
1 0 1 1
Solution should be with Time complexity = O(n*m) and space complexity =
O(1)
--
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: MS question
Suppose matrix is
1 0 0 1
1 0 1 0
0 0 0 0
then we traverse the matrix for each 1 we found at a[i][j] , we will check
for i=i to irow and j=j to jcol if that contains any more 1
if it contains 1 in row then we don't make the whole row as 1..we ignore the
row and same will be for column
if it don't contains any other 1 after that (i,j) location then we make the
whole row as 1.. and same will be for column
i know this is not in O(mn) but i just want to check if my logic is correct
or not...because it can be used somewhere else...
.
On Tue, Sep 27, 2011 at 11:51 AM, Gene gene.ress...@gmail.com wrote:
If you're given that it's a sparse matrix, then you must assume
storage is in a sparse matrix data structure to get time less than
O(mn).
In fact, if you assume the right data structure, then the operation
can take O(1) time.
For example if you say the structure is an array of sets of indices of
the 1's in each row (so that L(i) is a list that contains j if and
only if A(i,j) is a 1), then all you have to do is flip a bit saying
the representation has changed, i.e. lookups will work differently.
The old lookup is
A(i,j) = if L(i) contains j then 1 else 0.
The new lookup will be
A(i,j) = if L(i) is nonempty or L(j) contains i then 1 else 0
You'd probably want to store the sets in hash tables so that lookups
will remain O(1). Other choices might make more sense if A has special
structure.
On Sep 26, 6:41 pm, Ankur Garg ankurga...@gmail.com wrote:
Guys an Update ,
This has been asked in MS by me.. I suggested O(m*n) but they were
looking
for a solution in nlogn ( n*n Sparse Matrix ) ..Any idea ...
This post was discussed earlier but every1 came with O(m*n) solution so
instead of cluttering it ..opened a new One ...
On Tue, Sep 27, 2011 at 3:06 AM, Gene gene.ress...@gmail.com wrote:
I assume we don't want to use extra storage.
So one way is this: Go over the matrix and mark the first row with a 1
and the first column with a 1 for each 1 you find. Because row and
column 1 are used for temporary storage in this manner, you must first
remember whether they contained a 1, then go ahead. With row and
column 1 holding the necessary marks, you can fill in all the rows and
columns except them. Finally you can fill in row and column 1 by
checking the saved values. It will look something like this.
row0has1 = 0;
for (j = 0; j n; j++) if (M(0,j)) { row0has1 = 1; break; }
col0has1 = 0;
for (i = 0; i n; i++) if (M(i,0)) { col0has1 = 1; break; }
for (i = 1; i m; i++)
for (j = 1; j n; j++)
if (M(i,j)) M(i,0) = M(0,j) = 1;
for (i = 1; i m; i++)
for (j = 1; j n; j++)
if (M(i,0) || M(0,j)) M(i, j) = 1;
if (row0has1)
for (j = 0; j n; j++) M(0,j) = 1;
if (col0has1)
for (i = 0; i n; i++) M(i,0) = 1;
Maybe there's a slicker way, but this is O(mn)
On Sep 26, 9:46 pm, Ankur Garg ankurga...@gmail.com wrote:
Saw this question in one of the algo communities.
Amazon telephonic interview question on Matrix
Input is a matrix of size n x m of 0's and 1's. eg:
1 0 0 1
0 0 1 0
0 0 0 0
If a location has 1; make all the elements of that row and column =
1. eg
1 1 1 1
1 1 1 1
1 0 1 1
Solution should be with Time complexity = O(n*m) and space complexity
=
O(1)
--
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.
[algogeeks] Re: MS Question - Median of a BST without using extra space and in O(n)
And you have to use the pointer-reversing trick to traverse the tree because you don't have space for a stack. On Sep 27, 4:52 am, anshu mishra anshumishra6...@gmail.com wrote: do the inorder traversal as soon as reached at n/2th element that will be median. -- 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: MS Question - Median of a BST without using extra space and in O(n)
This requires O(n) extra space.
On Sep 27, 7:43 am, anshu mishra anshumishra6...@gmail.com wrote:
int bstMedian(node *root, int n, int x)
{
if (node-left) return bstMedian(root-left, n, x);
x++;
if (x == n/2) return node-val;
if (node-right) return bstMedian(root-right, n, x);}
call bstMedian(root, n, 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.
Re: [algogeeks] Re: MS Question - Median of a BST without using extra space and in O(n)
its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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: MS Question - Median of a BST without using extra space and in O(n)
a simple one is rabit-tortoise method, and using stackless traversal, facing a lot of corner cases in coding this, can someone check this as well? On Sep 27, 6:41 pm, anshu mishra anshumishra6...@gmail.com wrote: its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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: MS Question - Median of a BST without using extra space and in O(n)
@anshu can middle element can be found if the no. of nodes are not given... On Tue, Sep 27, 2011 at 8:34 PM, vikas vikas.rastogi2...@gmail.com wrote: a simple one is rabit-tortoise method, and using stackless traversal, facing a lot of corner cases in coding this, can someone check this as well? On Sep 27, 6:41 pm, anshu mishra anshumishra6...@gmail.com wrote: its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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. -- *Dheeraj Sharma* -- 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: MS Question - Median of a BST without using extra space and in O(n)
Recursion also requires space, so the problem is how to traverse without extra space. Once this is done, nothing is left in the problem. Sanju :) On Tue, Sep 27, 2011 at 8:35 AM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: @anshu can middle element can be found if the no. of nodes are not given... On Tue, Sep 27, 2011 at 8:34 PM, vikas vikas.rastogi2...@gmail.comwrote: a simple one is rabit-tortoise method, and using stackless traversal, facing a lot of corner cases in coding this, can someone check this as well? On Sep 27, 6:41 pm, anshu mishra anshumishra6...@gmail.com wrote: its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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. -- *Dheeraj Sharma* -- 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: MS Question - Median of a BST without using extra space and in O(n)
Do inorder traversal, to find out the total no. of nodes. Next time, do the inorder traversal but keeping the count of nodes visited and stop when you visit n/2 nodes. Non recursive In-order Traversal - *inorder*(node) *while* hasleftchild(node) *do* node = node.left *do* visit(node) *if* (hasrightchild(node)) *then* node = node.right *while* hasleftchild(node) *do* node = node.left *else* *while* node.parent ≠ *null* *and* node == node.parent.right *do* node = node.parent node = node.parent *while* node ≠ *null* Source: Wikipedia On Tue, Sep 27, 2011 at 9:13 PM, Sanjay Rajpal srn...@gmail.com wrote: Recursion also requires space, so the problem is how to traverse without extra space. Once this is done, nothing is left in the problem. Sanju :) On Tue, Sep 27, 2011 at 8:35 AM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: @anshu can middle element can be found if the no. of nodes are not given... On Tue, Sep 27, 2011 at 8:34 PM, vikas vikas.rastogi2...@gmail.comwrote: a simple one is rabit-tortoise method, and using stackless traversal, facing a lot of corner cases in coding this, can someone check this as well? On Sep 27, 6:41 pm, anshu mishra anshumishra6...@gmail.com wrote: its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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. -- *Dheeraj Sharma* -- 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. -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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: MS Question - Median of a BST without using extra space and in O(n)
Since we are given pointer to root node, we can easily find the minimum element in the tree. This will be the first node in the inorder traversal, now use method to find the inorder successor of a each node. Do it iteratively. Complexity will be O(n log n) and O(n) if tree is skewed. Correct me if m wrong. Sanju :) On Tue, Sep 27, 2011 at 8:49 AM, Nitin Garg nitin.garg.i...@gmail.comwrote: Do inorder traversal, to find out the total no. of nodes. Next time, do the inorder traversal but keeping the count of nodes visited and stop when you visit n/2 nodes. Non recursive In-order Traversal - *inorder*(node) *while* hasleftchild(node) *do* node = node.left *do* visit(node) *if* (hasrightchild(node)) *then* node = node.right *while* hasleftchild(node) *do* node = node.left *else* *while* node.parent ≠ *null* *and* node == node.parent.right *do* node = node.parent node = node.parent *while* node ≠ *null* Source: Wikipedia On Tue, Sep 27, 2011 at 9:13 PM, Sanjay Rajpal srn...@gmail.com wrote: Recursion also requires space, so the problem is how to traverse without extra space. Once this is done, nothing is left in the problem. Sanju :) On Tue, Sep 27, 2011 at 8:35 AM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: @anshu can middle element can be found if the no. of nodes are not given... On Tue, Sep 27, 2011 at 8:34 PM, vikas vikas.rastogi2...@gmail.comwrote: a simple one is rabit-tortoise method, and using stackless traversal, facing a lot of corner cases in coding this, can someone check this as well? On Sep 27, 6:41 pm, anshu mishra anshumishra6...@gmail.com wrote: its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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. -- *Dheeraj Sharma* -- 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. -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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] Re: MS Question - Median of a BST without using extra space and in O(n)
morris Inorder traversal can do the task i think -- 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/-/TujHItNRKowJ. 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: MS question
I assume we don't want to use extra storage.
So one way is this: Go over the matrix and mark the first row with a 1
and the first column with a 1 for each 1 you find. Because row and
column 1 are used for temporary storage in this manner, you must first
remember whether they contained a 1, then go ahead. With row and
column 1 holding the necessary marks, you can fill in all the rows and
columns except them. Finally you can fill in row and column 1 by
checking the saved values. It will look something like this.
row0has1 = 0;
for (j = 0; j n; j++) if (M(0,j)) { row0has1 = 1; break; }
col0has1 = 0;
for (i = 0; i n; i++) if (M(i,0)) { col0has1 = 1; break; }
for (i = 1; i m; i++)
for (j = 1; j n; j++)
if (M(i,j)) M(i,0) = M(0,j) = 1;
for (i = 1; i m; i++)
for (j = 1; j n; j++)
if (M(i,0) || M(0,j)) M(i, j) = 1;
if (row0has1)
for (j = 0; j n; j++) M(0,j) = 1;
if (col0has1)
for (i = 0; i n; i++) M(i,0) = 1;
Maybe there's a slicker way, but this is O(mn)
On Sep 26, 9:46 pm, Ankur Garg ankurga...@gmail.com wrote:
Saw this question in one of the algo communities.
Amazon telephonic interview question on Matrix
Input is a matrix of size n x m of 0's and 1's. eg:
1 0 0 1
0 0 1 0
0 0 0 0
If a location has 1; make all the elements of that row and column = 1. eg
1 1 1 1
1 1 1 1
1 0 1 1
Solution should be with Time complexity = O(n*m) and space complexity = O(1)
--
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: MS question
Guys an Update ,
This has been asked in MS by me.. I suggested O(m*n) but they were looking
for a solution in nlogn ( n*n Sparse Matrix ) ..Any idea ...
This post was discussed earlier but every1 came with O(m*n) solution so
instead of cluttering it ..opened a new One ...
On Tue, Sep 27, 2011 at 3:06 AM, Gene gene.ress...@gmail.com wrote:
I assume we don't want to use extra storage.
So one way is this: Go over the matrix and mark the first row with a 1
and the first column with a 1 for each 1 you find. Because row and
column 1 are used for temporary storage in this manner, you must first
remember whether they contained a 1, then go ahead. With row and
column 1 holding the necessary marks, you can fill in all the rows and
columns except them. Finally you can fill in row and column 1 by
checking the saved values. It will look something like this.
row0has1 = 0;
for (j = 0; j n; j++) if (M(0,j)) { row0has1 = 1; break; }
col0has1 = 0;
for (i = 0; i n; i++) if (M(i,0)) { col0has1 = 1; break; }
for (i = 1; i m; i++)
for (j = 1; j n; j++)
if (M(i,j)) M(i,0) = M(0,j) = 1;
for (i = 1; i m; i++)
for (j = 1; j n; j++)
if (M(i,0) || M(0,j)) M(i, j) = 1;
if (row0has1)
for (j = 0; j n; j++) M(0,j) = 1;
if (col0has1)
for (i = 0; i n; i++) M(i,0) = 1;
Maybe there's a slicker way, but this is O(mn)
On Sep 26, 9:46 pm, Ankur Garg ankurga...@gmail.com wrote:
Saw this question in one of the algo communities.
Amazon telephonic interview question on Matrix
Input is a matrix of size n x m of 0's and 1's. eg:
1 0 0 1
0 0 1 0
0 0 0 0
If a location has 1; make all the elements of that row and column = 1. eg
1 1 1 1
1 1 1 1
1 0 1 1
Solution should be with Time complexity = O(n*m) and space complexity =
O(1)
--
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: MS test cases type Questions
dats f9...bt cud i get 2 knoe ...how bout answering 2 d perfectness...n if v cud practice dem from nywhere Regards, PAYAL GUPTA, CSE-3 rd yr, NIT-B On Tue, Sep 13, 2011 at 10:05 PM, Navneet navneetn...@gmail.com wrote: Basically test cases are asked for very general purpose software like a Notepad etc. Generally they want you to come up with as many as test cases as possible. On Sep 13, 7:15 pm, Akash Mukherjee akash...@gmail.com wrote: +1 On Mon, Sep 12, 2011 at 3:42 PM, pg@manit gpt.pa...@gmail.com wrote: Cud some 1 suggest me 4m how 2 practise test cases type of questions which usually cum in MS written Papers? thanx..in advance Regards, PAYAL GUPTA -- 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.
[algogeeks] Re: MS test cases type Questions
U must mention all the boundary cases, very large input cases, -ve nos and must throw appropriate exception while coding during interviews... Questions are not too hard in MS... just they dont want buggy code... even if u allocate memory.. u should take an if condition i.e. if (p ! = NULL)...and avoid such other silly mistakes... -- 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: MS test cases type Questions
Basically test cases are asked for very general purpose software like a Notepad etc. Generally they want you to come up with as many as test cases as possible. On Sep 13, 7:15 pm, Akash Mukherjee akash...@gmail.com wrote: +1 On Mon, Sep 12, 2011 at 3:42 PM, pg@manit gpt.pa...@gmail.com wrote: Cud some 1 suggest me 4m how 2 practise test cases type of questions which usually cum in MS written Papers? thanx..in advance Regards, PAYAL GUPTA -- 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] Re: MS Question
yep, trie needs to be built On Aug 24, 10:49 pm, Ankur Garg ankurga...@gmail.com wrote: It means when u call that func u get the next word in the document Regards Ankur On Wed, Aug 24, 2011 at 6:59 PM, vikas vikas.rastogi2...@gmail.com wrote: what do you mean by a function for finding the next word is given ? On Aug 22, 1:56 am, Ankur Garg ankurga...@gmail.com wrote: Question-- Given a document containing some words ...and a function for finding the next word is given .design a code which efficiently search the word and find occurrence of it in given document . -which data structure will be used? -write algorithm for implementing complexity? Guys any Ideas here .. I think tries can be used but can anyone explain/suggest/discuss proper implementation /technique to solve this problem Regards Ankur -- 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: MS Question
wat abt doing wid hashing? On Thu, Aug 25, 2011 at 3:55 PM, vikas vikas.rastogi2...@gmail.com wrote: yep, trie needs to be built On Aug 24, 10:49 pm, Ankur Garg ankurga...@gmail.com wrote: It means when u call that func u get the next word in the document Regards Ankur On Wed, Aug 24, 2011 at 6:59 PM, vikas vikas.rastogi2...@gmail.com wrote: what do you mean by a function for finding the next word is given ? On Aug 22, 1:56 am, Ankur Garg ankurga...@gmail.com wrote: Question-- Given a document containing some words ...and a function for finding the next word is given .design a code which efficiently search the word and find occurrence of it in given document . -which data structure will be used? -write algorithm for implementing complexity? Guys any Ideas here .. I think tries can be used but can anyone explain/suggest/discuss proper implementation /technique to solve this problem Regards Ankur -- 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.
Re: [algogeeks] Re: MS Question
ya why not hashing ? On Thu, Aug 25, 2011 at 3:31 PM, SANDEEP CHUGH sandeep.aa...@gmail.comwrote: wat abt doing wid hashing? On Thu, Aug 25, 2011 at 3:55 PM, vikas vikas.rastogi2...@gmail.comwrote: yep, trie needs to be built On Aug 24, 10:49 pm, Ankur Garg ankurga...@gmail.com wrote: It means when u call that func u get the next word in the document Regards Ankur On Wed, Aug 24, 2011 at 6:59 PM, vikas vikas.rastogi2...@gmail.com wrote: what do you mean by a function for finding the next word is given ? On Aug 22, 1:56 am, Ankur Garg ankurga...@gmail.com wrote: Question-- Given a document containing some words ...and a function for finding the next word is given .design a code which efficiently search the word and find occurrence of it in given document . -which data structure will be used? -write algorithm for implementing complexity? Guys any Ideas here .. I think tries can be used but can anyone explain/suggest/discuss proper implementation /technique to solve this problem Regards Ankur -- 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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: MS Question
how will we exactly implement hashtables in this? What will be appropriate keys? ?? -- 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: MS Question
for every word in the document , apply hash funtion.. store the string n its frequency too.. if we get the same word , then increment the frequency. after storing. whenver we want to search the word , searching in O(1) time , jst applying hash function again on the word to be searched .. correct me if i am wrong? On Thu, Aug 25, 2011 at 7:14 PM, Shrey Choudhary choudharyshre...@gmail.com wrote: how will we exactly implement hashtables in this? What will be appropriate keys? ?? -- 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] Re: MS Question
But it says finding the next word and also it's position of occurence. If we use frequency..won't position of occurence overlap? Am not sure whether I got the question right or not! -- 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: MS Question
no .. question says that there is a function that gives the next word in the document.. this means after hashing one word , we hav to go to another word ... for this going to next word in the document , we hav already provided wid a function.. nothing to do wid the occurence On Thu, Aug 25, 2011 at 7:30 PM, Shrey Choudhary choudharyshre...@gmail.com wrote: But it says finding the next word and also it's position of occurence. If we use frequency..won't position of occurence overlap? Am not sure whether I got the question right or not! -- 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] Re: MS Question
design a code which efficiently search the word and find occurrence of it in given document -- 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: MS Question
ohh sry my mistake .. got it On Thu, Aug 25, 2011 at 7:36 PM, Shrey Choudhary choudharyshre...@gmail.com wrote: design a code which efficiently search the word and find occurrence of it in given document -- 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: MS Question
@shrey but its not given in question that we have to return the position or the occurence in the document.. we hav to only the tell whether the word is in document.. read .design a code which efficiently search the word and find occurrence of it in given document . its nt given that return the position or something like that. isn't so ?? On Thu, Aug 25, 2011 at 7:38 PM, SANDEEP CHUGH sandeep.aa...@gmail.comwrote: ohh sry my mistake .. got it On Thu, Aug 25, 2011 at 7:36 PM, Shrey Choudhary choudharyshre...@gmail.com wrote: design a code which efficiently search the word and find occurrence of it in given document -- 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: MS Question
i made a boo boo -- 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: MS Question
what do you mean by a function for finding the next word is given ? On Aug 22, 1:56 am, Ankur Garg ankurga...@gmail.com wrote: Question-- Given a document containing some words ...and a function for finding the next word is given .design a code which efficiently search the word and find occurrence of it in given document . -which data structure will be used? -write algorithm for implementing complexity? Guys any Ideas here .. I think tries can be used but can anyone explain/suggest/discuss proper implementation /technique to solve this problem Regards Ankur -- 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: MS Question
It means when u call that func u get the next word in the document Regards Ankur On Wed, Aug 24, 2011 at 6:59 PM, vikas vikas.rastogi2...@gmail.com wrote: what do you mean by a function for finding the next word is given ? On Aug 22, 1:56 am, Ankur Garg ankurga...@gmail.com wrote: Question-- Given a document containing some words ...and a function for finding the next word is given .design a code which efficiently search the word and find occurrence of it in given document . -which data structure will be used? -write algorithm for implementing complexity? Guys any Ideas here .. I think tries can be used but can anyone explain/suggest/discuss proper implementation /technique to solve this problem Regards Ankur -- 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] Re: MS BRAINTEASR
it would take c days to take off all the hats On Aug 18, 3:51 pm, pg@manit gpt.pa...@gmail.com wrote: A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads (i.e., at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat. FOLLOW UP Prove that your solution is correct. -- 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: MS BRAINTEASR
hmm...suitable rply i suppose thanx...:):) REGARDS, PAYAL GUPTA On Thu, Aug 18, 2011 at 4:36 PM, DheerajSharma dheerajsharma1...@gmail.comwrote: it would take c days to take off all the hats On Aug 18, 3:51 pm, pg@manit gpt.pa...@gmail.com wrote: A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads (i.e., at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat. FOLLOW UP Prove that your solution is correct. -- 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] Re: MS BRAINTEASR
Case 1: when one person is wearing hat.The person wearing hat will see that no other is wearing hat.hence he must be wearing it.So she will take it off.hence one day Case 2: when two persons are wearing,first will think..that only second one is wearing..while second will think only first one is wearing.hence no one will go on first day. on the second day..when both will see the same thing..they will come to know..that they are also wearing hat..and making the second one confused ;) hence..they both will go and take off hat on second day. Case 3: first person sees hat on two others.(same for other two). no one will go on first day. On second day..same situation..bt this time the person is still unsure..wether she is wearing hat or not..bcoz case 2 can happen.. on third day..when same situation arises...they will come to know..that they are also wearing hat..hence..they will take it off on day 3. so on.. so on.. For C hats...C dayz... On Aug 18, 4:06 pm, DheerajSharma dheerajsharma1...@gmail.com wrote: it would take c days to take off all the hats On Aug 18, 3:51 pm, pg@manit gpt.pa...@gmail.com wrote: A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads (i.e., at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat. FOLLOW UP Prove that your solution is correct. -- 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: MS BRAINTEASR
ur welcume :) On Aug 18, 4:12 pm, payal gupta gpt.pa...@gmail.com wrote: hmm...suitable rply i suppose thanx...:):) REGARDS, PAYAL GUPTA On Thu, Aug 18, 2011 at 4:36 PM, DheerajSharma dheerajsharma1...@gmail.comwrote: it would take c days to take off all the hats On Aug 18, 3:51 pm, pg@manit gpt.pa...@gmail.com wrote: A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads (i.e., at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat. FOLLOW UP Prove that your solution is correct. -- 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] Re: MS BRAINTEASR
Time taken by one man only . As a person can do only at exactly mid night so , all have to do together only at midnight . On Aug 18, 3:51 pm, pg@manit gpt.pa...@gmail.com wrote: A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads (i.e., at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat. FOLLOW UP Prove that your solution is correct. -- 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.
