Re: [algogeeks] Amazon Hiring SDE-Is, SDE-IIs, SDM and QAE-1
Hi Immanuel, Please find attached resume and process it for mentioned opening. Regarding, Abhijeet Srivastva 09871147025 On Sun, Jul 27, 2014 at 8:27 PM, immanuel kingston kingston.imman...@gmail.com wrote: There are openings in my team for SDE-Is, SDE-IIs, SDM and QAE-1. Please send me resumes if you or your friends are interested in any of these roles. Thanks, Kingston -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. Abhijeet__Srivastva.doc Description: MS-Word document
Re: [algogeeks] Amazon problem
If I understood the problem, the following works fine.
if(A[i][j] == 'o' and it is not and edge element) {
if(A[i][j] is surrounded by either 'x' or 'o') {
A[i][j] = 'x';
}
}
On Mon, Jun 10, 2013 at 8:38 PM, Jai Shri Ram del7...@gmail.com wrote:
Given a 2D board containing 'X' and 'O', capture all regions surrounded
by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded
region .
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Amazon problem
sorry.. pls ignore the above post.. that doesn't work..
On Wed, Jun 19, 2013 at 10:5
5 PM, bharat b bagana.bharatku...@gmail.com wrote:
If I understood the problem, the following works fine.
if(A[i][j] == 'o' and it is not and edge element) {
if(A[i][j] is surrounded by either 'x' or 'o') {
A[i][j] = 'x';
}
}
On Mon, Jun 10, 2013 at 8:38 PM, Jai Shri Ram del7...@gmail.com wrote:
Given a 2D board containing 'X' and 'O', capture all regions surrounded
by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded
region .
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Amazon problem
Start BFS from a position which is 'o'. the neighbour elements are as
defined in the question. Mark neighbour as 'Z' if it is not a boundary and
either 'x' or 'o', else *failure*. If there is no more for the considered
connected component *and if it is* *success*, then mark all 'Z's to 'x'. Do
this till we parse the whole matrix.
Now traverse the whole matrix and mark all 'Z's to 'o'.
On Wed, Jun 19, 2013 at 10:56 PM, bharat b bagana.bharatku...@gmail.comwrote:
sorry.. pls ignore the above post.. that doesn't work..
On Wed, Jun 19, 2013 at 10:5
5 PM, bharat b bagana.bharatku...@gmail.com wrote:
If I understood the problem, the following works fine.
if(A[i][j] == 'o' and it is not and edge element) {
if(A[i][j] is surrounded by either 'x' or 'o') {
A[i][j] = 'x';
}
}
On Mon, Jun 10, 2013 at 8:38 PM, Jai Shri Ram del7...@gmail.com wrote:
Given a 2D board containing 'X' and 'O', capture all regions surrounded
by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded
region .
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Amazon interview Questions
Round 1 :
Q2: given BST is not correct.
correct BST passing this condition will be 7
/
5
/
3
\
4
in this case the root element of given BST will be the largest if left
child exist or will be the smallest if right child exist.
so you just need to start checking the last value of given post order.
eg: in this case
post order will be 4 3 5 7
here last value is 7 so it is greatest among all so left nde exist.
next is 5 which is largest of remaining so left node exist for this
next is 3 which is smallest of remaining so 4 will come on right node.
On Wed, Jun 5, 2013 at 5:14 PM, Ravi Ranjan ravi.cool2...@gmail.com wrote:
Can u clear Round3 --- Qstn-3. the language is not cleared
On Wed, Jun 5, 2013 at 1:52 PM, sourabh jain wsour...@gmail.com wrote:
Round 1:
1.Design a Data Structure supporting 3 queries a)push b)pop c) find
minimum
Ans : Do it using Two Stacks . in first stack use it as normal stack.
second stack use it to find minimun as the value inserted is greater than
the top ignore it else push it. if pop operation happens and the value
popped is equal to the top(s2) then pop(s2).
time complexity push : O(1) , pop O(1) , find Minimum O(1)
2.Given post order of a BST find whether each node of the tree(except
leaf) has only 1 child or not.
eg5
\
7
/
3
/
2
is correct as each node has only 1 child.
Round 2:
1.Given a sorted array a and a sum k print all pairs of indexes i and
j such that a[i]+a[j]=k.
put one pointer at index 0 and 2nd at length(ar)-1.
while (ij){
if(ar[i]+ar[j]==k) {printpairs; i++; j++;}
else if(ar[i])+ar[j] k) i++;
else if(ar[i])+ar[j] k) j--;
}
2.Given a matrix that is row and column wise sorted give an algo for
finding count of the total no of -ve nos.
start from (0,n) move towards right if found +ve and increment count of
positive in row. else move down .
Round 3:
1.Given a matrix consisting of nos you can print the max length of
sequence possible where in a sequence each consecutive nos have a diff
of +1 or -1.
eg 3 5 7 3
4 5 8 1
6 4 5 2
here sequence is 3
4 5
4 5
*you can do it using recursion *
2.Give a data structure that supports following queries a)insert
b)delete c)ispresent d)print all elements
*BST's ... , if insertionorder needs to be maintained then linked list;*
3.Given a infinite supply of n cylinders where each cylinder is
specified by weight of 02,weight of n2,total weight ,
now u need some minimum quantity of o2 and n2 by selecting
cylinders and your aim is make it so that u have min total weight.
output the minimum total weight .
Round 4:
1.Given 2 sorted arrays find there median
.http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
2.Consider column of ms excel the start with A,BZ,AA
Now u r given column no u need to print its name
*Ans : Same as number system problem with base 26*
3.Given 2 arrays.Imagine you are making bst from each array.u need to
tell whether 2 bsts will be identical or not without actually
constructing the tree.
eg 1 2 3
1 3 2
will construct the same tree
On Mon, Jun 3, 2013 at 10:52 PM, *$* gopi.komand...@gmail.com wrote:
these are for which position? and experience?
On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote:
Round 1:
1.Design a Data Structure supporting 3 queries a)push b)pop c) find
minimum
2.Given post order of a BST find whether each node of the tree(except
leaf) has only 1 child or not.
eg5
\
7
/
3
/
2
is correct as each node has only 1 child.
Round 2:
1.Given a sorted array a and a sum k print all pairs of indexes i and
j such that a[i]+a[j]=k.
2.Given a matrix that is row and column wise sorted give an algo for
finding count of the total no of -ve nos.
Round 3:
1.Given a matrix consisting of nos you can print the max length of
sequence possible where in a sequence each consecutive nos have a diff
of +1 or -1.
eg 3 5 7 3
4 5 8 1
6 4 5 2
here sequence is 3
4 5
4 5
2.Give a data structure that supports following queries a)insert
b)delete c)ispresent d)print all elements
3.Given a infinite supply of n cylinders where each cylinder is
specified by weight of 02,weight of n2,total weight ,
now u need some minimum quantity of o2 and n2 by selecting
cylinders
Re: [algogeeks] Amazon interview Questions
Hi ravi ,
I think he is trying to find the longest possible increasing chain in
matrix .
he needs to start traversing from first row choosing columns one by one and
move in all direction. but he needs to maintain the already visited nodes.
On Thu, Jun 6, 2013 at 12:07 AM, sourabh jain wsour...@gmail.com wrote:
Round 1 :
Q2: given BST is not correct.
correct BST passing this condition will be 7
/
5
/
3
\
4
in this case the root element of given BST will be the largest if left
child exist or will be the smallest if right child exist.
so you just need to start checking the last value of given post order.
eg: in this case
post order will be 4 3 5 7
here last value is 7 so it is greatest among all so left nde exist.
next is 5 which is largest of remaining so left node exist for this
next is 3 which is smallest of remaining so 4 will come on right node.
On Wed, Jun 5, 2013 at 5:14 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote:
Can u clear Round3 --- Qstn-3. the language is not cleared
On Wed, Jun 5, 2013 at 1:52 PM, sourabh jain wsour...@gmail.com wrote:
Round 1:
1.Design a Data Structure supporting 3 queries a)push b)pop c) find
minimum
Ans : Do it using Two Stacks . in first stack use it as normal stack.
second stack use it to find minimun as the value inserted is greater than
the top ignore it else push it. if pop operation happens and the value
popped is equal to the top(s2) then pop(s2).
time complexity push : O(1) , pop O(1) , find Minimum O(1)
2.Given post order of a BST find whether each node of the tree(except
leaf) has only 1 child or not.
eg5
\
7
/
3
/
2
is correct as each node has only 1 child.
Round 2:
1.Given a sorted array a and a sum k print all pairs of indexes i and
j such that a[i]+a[j]=k.
put one pointer at index 0 and 2nd at length(ar)-1.
while (ij){
if(ar[i]+ar[j]==k) {printpairs; i++; j++;}
else if(ar[i])+ar[j] k) i++;
else if(ar[i])+ar[j] k) j--;
}
2.Given a matrix that is row and column wise sorted give an algo for
finding count of the total no of -ve nos.
start from (0,n) move towards right if found +ve and increment count of
positive in row. else move down .
Round 3:
1.Given a matrix consisting of nos you can print the max length of
sequence possible where in a sequence each consecutive nos have a diff
of +1 or -1.
eg 3 5 7 3
4 5 8 1
6 4 5 2
here sequence is 3
4 5
4 5
*you can do it using recursion *
2.Give a data structure that supports following queries a)insert
b)delete c)ispresent d)print all elements
*BST's ... , if insertionorder needs to be maintained then linked list;*
3.Given a infinite supply of n cylinders where each cylinder is
specified by weight of 02,weight of n2,total weight ,
now u need some minimum quantity of o2 and n2 by selecting
cylinders and your aim is make it so that u have min total weight.
output the minimum total weight .
Round 4:
1.Given 2 sorted arrays find there median
.http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
2.Consider column of ms excel the start with A,BZ,AA
Now u r given column no u need to print its name
*Ans : Same as number system problem with base 26*
3.Given 2 arrays.Imagine you are making bst from each array.u need to
tell whether 2 bsts will be identical or not without actually
constructing the tree.
eg 1 2 3
1 3 2
will construct the same tree
On Mon, Jun 3, 2013 at 10:52 PM, *$* gopi.komand...@gmail.com wrote:
these are for which position? and experience?
On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote:
Round 1:
1.Design a Data Structure supporting 3 queries a)push b)pop c) find
minimum
2.Given post order of a BST find whether each node of the tree(except
leaf) has only 1 child or not.
eg5
\
7
/
3
/
2
is correct as each node has only 1 child.
Round 2:
1.Given a sorted array a and a sum k print all pairs of indexes i and
j such that a[i]+a[j]=k.
2.Given a matrix that is row and column wise sorted give an algo for
finding count of the total no of -ve nos.
Round 3:
1.Given a matrix consisting of nos you can print the max length of
sequence possible where in a sequence each consecutive nos have a diff
of +1 or -1.
eg 3 5 7 3
4 5 8 1
6 4 5 2
here sequence is 3
4 5
Re: [algogeeks] Amazon interview Questions
Round 1:
1.Design a Data Structure supporting 3 queries a)push b)pop c) find
minimum
Ans : Do it using Two Stacks . in first stack use it as normal stack.
second stack use it to find minimun as the value inserted is greater than
the top ignore it else push it. if pop operation happens and the value
popped is equal to the top(s2) then pop(s2).
time complexity push : O(1) , pop O(1) , find Minimum O(1)
2.Given post order of a BST find whether each node of the tree(except
leaf) has only 1 child or not.
eg5
\
7
/
3
/
2
is correct as each node has only 1 child.
Round 2:
1.Given a sorted array a and a sum k print all pairs of indexes i and
j such that a[i]+a[j]=k.
put one pointer at index 0 and 2nd at length(ar)-1.
while (ij){
if(ar[i]+ar[j]==k) {printpairs; i++; j++;}
else if(ar[i])+ar[j] k) i++;
else if(ar[i])+ar[j] k) j--;
}
2.Given a matrix that is row and column wise sorted give an algo for
finding count of the total no of -ve nos.
start from (0,n) move towards right if found +ve and increment count of
positive in row. else move down .
Round 3:
1.Given a matrix consisting of nos you can print the max length of
sequence possible where in a sequence each consecutive nos have a diff
of +1 or -1.
eg 3 5 7 3
4 5 8 1
6 4 5 2
here sequence is 3
4 5
4 5
*you can do it using recursion *
2.Give a data structure that supports following queries a)insert
b)delete c)ispresent d)print all elements
*BST's ... , if insertionorder needs to be maintained then linked list;*
3.Given a infinite supply of n cylinders where each cylinder is
specified by weight of 02,weight of n2,total weight ,
now u need some minimum quantity of o2 and n2 by selecting
cylinders and your aim is make it so that u have min total weight.
output the minimum total weight .
Round 4:
1.Given 2 sorted arrays find there median
.http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
2.Consider column of ms excel the start with A,BZ,AA
Now u r given column no u need to print its name
*Ans : Same as number system problem with base 26*
3.Given 2 arrays.Imagine you are making bst from each array.u need to
tell whether 2 bsts will be identical or not without actually
constructing the tree.
eg 1 2 3
1 3 2
will construct the same tree
On Mon, Jun 3, 2013 at 10:52 PM, *$* gopi.komand...@gmail.com wrote:
these are for which position? and experience?
On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote:
Round 1:
1.Design a Data Structure supporting 3 queries a)push b)pop c) find
minimum
2.Given post order of a BST find whether each node of the tree(except
leaf) has only 1 child or not.
eg5
\
7
/
3
/
2
is correct as each node has only 1 child.
Round 2:
1.Given a sorted array a and a sum k print all pairs of indexes i and
j such that a[i]+a[j]=k.
2.Given a matrix that is row and column wise sorted give an algo for
finding count of the total no of -ve nos.
Round 3:
1.Given a matrix consisting of nos you can print the max length of
sequence possible where in a sequence each consecutive nos have a diff
of +1 or -1.
eg 3 5 7 3
4 5 8 1
6 4 5 2
here sequence is 3
4 5
4 5
2.Give a data structure that supports following queries a)insert
b)delete c)ispresent d)print all elements
3.Given a infinite supply of n cylinders where each cylinder is
specified by weight of 02,weight of n2,total weight ,
now u need some minimum quantity of o2 and n2 by selecting
cylinders and your aim is make it so that u have min total weight.
output the minimum total weight .
Round 4:
1.Given 2 sorted arrays find there median.
2.Consider column of ms excel the start with A,BZ,AA
Now u r given column no u need to print its name
3.Given 2 arrays.Imagine you are making bst from each array.u need to
tell whether 2 bsts will be identical or not without actually
constructing the tree.
eg 1 2 3
1 3 2
will construct the same tree
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
Thx,
--Gopi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
Regards,
Sourabh Kumar Jain
+91-8971547841
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and
Re: [algogeeks] Amazon interview Questions
Can u clear Round3 --- Qstn-3. the language is not cleared
On Wed, Jun 5, 2013 at 1:52 PM, sourabh jain wsour...@gmail.com wrote:
Round 1:
1.Design a Data Structure supporting 3 queries a)push b)pop c) find
minimum
Ans : Do it using Two Stacks . in first stack use it as normal stack.
second stack use it to find minimun as the value inserted is greater than
the top ignore it else push it. if pop operation happens and the value
popped is equal to the top(s2) then pop(s2).
time complexity push : O(1) , pop O(1) , find Minimum O(1)
2.Given post order of a BST find whether each node of the tree(except
leaf) has only 1 child or not.
eg5
\
7
/
3
/
2
is correct as each node has only 1 child.
Round 2:
1.Given a sorted array a and a sum k print all pairs of indexes i and
j such that a[i]+a[j]=k.
put one pointer at index 0 and 2nd at length(ar)-1.
while (ij){
if(ar[i]+ar[j]==k) {printpairs; i++; j++;}
else if(ar[i])+ar[j] k) i++;
else if(ar[i])+ar[j] k) j--;
}
2.Given a matrix that is row and column wise sorted give an algo for
finding count of the total no of -ve nos.
start from (0,n) move towards right if found +ve and increment count of
positive in row. else move down .
Round 3:
1.Given a matrix consisting of nos you can print the max length of
sequence possible where in a sequence each consecutive nos have a diff
of +1 or -1.
eg 3 5 7 3
4 5 8 1
6 4 5 2
here sequence is 3
4 5
4 5
*you can do it using recursion *
2.Give a data structure that supports following queries a)insert
b)delete c)ispresent d)print all elements
*BST's ... , if insertionorder needs to be maintained then linked list;*
3.Given a infinite supply of n cylinders where each cylinder is
specified by weight of 02,weight of n2,total weight ,
now u need some minimum quantity of o2 and n2 by selecting
cylinders and your aim is make it so that u have min total weight.
output the minimum total weight .
Round 4:
1.Given 2 sorted arrays find there median
.http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
2.Consider column of ms excel the start with A,BZ,AA
Now u r given column no u need to print its name
*Ans : Same as number system problem with base 26*
3.Given 2 arrays.Imagine you are making bst from each array.u need to
tell whether 2 bsts will be identical or not without actually
constructing the tree.
eg 1 2 3
1 3 2
will construct the same tree
On Mon, Jun 3, 2013 at 10:52 PM, *$* gopi.komand...@gmail.com wrote:
these are for which position? and experience?
On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote:
Round 1:
1.Design a Data Structure supporting 3 queries a)push b)pop c) find
minimum
2.Given post order of a BST find whether each node of the tree(except
leaf) has only 1 child or not.
eg5
\
7
/
3
/
2
is correct as each node has only 1 child.
Round 2:
1.Given a sorted array a and a sum k print all pairs of indexes i and
j such that a[i]+a[j]=k.
2.Given a matrix that is row and column wise sorted give an algo for
finding count of the total no of -ve nos.
Round 3:
1.Given a matrix consisting of nos you can print the max length of
sequence possible where in a sequence each consecutive nos have a diff
of +1 or -1.
eg 3 5 7 3
4 5 8 1
6 4 5 2
here sequence is 3
4 5
4 5
2.Give a data structure that supports following queries a)insert
b)delete c)ispresent d)print all elements
3.Given a infinite supply of n cylinders where each cylinder is
specified by weight of 02,weight of n2,total weight ,
now u need some minimum quantity of o2 and n2 by selecting
cylinders and your aim is make it so that u have min total weight.
output the minimum total weight .
Round 4:
1.Given 2 sorted arrays find there median.
2.Consider column of ms excel the start with A,BZ,AA
Now u r given column no u need to print its name
3.Given 2 arrays.Imagine you are making bst from each array.u need to
tell whether 2 bsts will be identical or not without actually
constructing the tree.
eg 1 2 3
1 3 2
will construct the same tree
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
Thx,
--Gopi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to
Re: [algogeeks] Amazon interview Questions
Can any one give some points on Round 3 : 1st and 3rd question ? On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote: Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5 4 5 2.Give a data structure that supports following queries a)insert b)delete c)ispresent d)print all elements 3.Given a infinite supply of n cylinders where each cylinder is specified by weight of 02,weight of n2,total weight , now u need some minimum quantity of o2 and n2 by selecting cylinders and your aim is make it so that u have min total weight. output the minimum total weight . Round 4: 1.Given 2 sorted arrays find there median. 2.Consider column of ms excel the start with A,BZ,AA Now u r given column no u need to print its name 3.Given 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree. eg 1 2 3 1 3 2 will construct the same tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Amazon interview Questions
these are for which position? and experience? On Thu, May 2, 2013 at 9:27 PM, Guneesh gunees...@gmail.com wrote: Round 1: 1.Design a Data Structure supporting 3 queries a)push b)pop c) find minimum 2.Given post order of a BST find whether each node of the tree(except leaf) has only 1 child or not. eg5 \ 7 / 3 / 2 is correct as each node has only 1 child. Round 2: 1.Given a sorted array a and a sum k print all pairs of indexes i and j such that a[i]+a[j]=k. 2.Given a matrix that is row and column wise sorted give an algo for finding count of the total no of -ve nos. Round 3: 1.Given a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1. eg 3 5 7 3 4 5 8 1 6 4 5 2 here sequence is 3 4 5 4 5 2.Give a data structure that supports following queries a)insert b)delete c)ispresent d)print all elements 3.Given a infinite supply of n cylinders where each cylinder is specified by weight of 02,weight of n2,total weight , now u need some minimum quantity of o2 and n2 by selecting cylinders and your aim is make it so that u have min total weight. output the minimum total weight . Round 4: 1.Given 2 sorted arrays find there median. 2.Consider column of ms excel the start with A,BZ,AA Now u r given column no u need to print its name 3.Given 2 arrays.Imagine you are making bst from each array.u need to tell whether 2 bsts will be identical or not without actually constructing the tree. eg 1 2 3 1 3 2 will construct the same tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Thx, --Gopi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
kindly explain visualizing a balanced BST as a graph and unable to underdstand your point thanks --mac On Fri, May 24, 2013 at 6:04 AM, Avi Dullu avi.du...@gmail.com wrote: On Sat, May 11, 2013 at 10:29 AM, Aman Jain pureama...@gmail.com wrote: 2. from this no*de u*, again apply* dfs* to find longest distant node from this node.Let us say that node is v. Small doubt about the solution. Consider this graph a - b - c - d You randomly choose vertex 'b' and do a DFS. Your u will be vertex 'd'. Then you do DFS from d, but its out degree is 0. So your DFS ends at 'd' itself and you report the solution as b-c-d. But the solution is a-b-c-d. What did I miss? My proposal: Topological Sort http://en.wikipedia.org/wiki/Topological_sorting the graph and keep removing the nodes from vertices which have out degree of 0 (given the DAG, there will always be atleast one such vertex). Rest is self explanatory :) Veni Vedi Slumber ! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
My bad, I wrote out degree where I should have written in degree. My proposal: Topological Sort http://en.wikipedia.org/wiki/Topological_sorting the graph and keep removing the nodes from vertices which have in degree of 0 (given the DAG, there will always be at least one such vertex). For a BST, since just root has an in degree of 0, start by removing the 2 out nodes from it. Now you will have 2 vertices with in degree as 0, repeat this for each of them. The last vertex which will be left i.e. the one without any out degree will be one end of your solution and the root will be the other. Essentially, for a BST this problem is equal to finding the depth of the tree. Also I made a blunder by assuming the graph is directed (DAG). The question does not say graph is directed or undirected. This approach will work for DAG. For undirected, convert the graph in to a directed graph first and then start with the vertices whose in degree is 1. Veni Vedi Slumber ! On Fri, May 24, 2013 at 6:19 AM, MAC macatad...@gmail.com wrote: kindly explain visualizing a balanced BST as a graph and unable to underdstand your point thanks --mac On Fri, May 24, 2013 at 6:04 AM, Avi Dullu avi.du...@gmail.com wrote: On Sat, May 11, 2013 at 10:29 AM, Aman Jain pureama...@gmail.com wrote: 2. from this no*de u*, again apply* dfs* to find longest distant node from this node.Let us say that node is v. Small doubt about the solution. Consider this graph a - b - c - d You randomly choose vertex 'b' and do a DFS. Your u will be vertex 'd'. Then you do DFS from d, but its out degree is 0. So your DFS ends at 'd' itself and you report the solution as b-c-d. But the solution is a-b-c-d. What did I miss? My proposal: Topological Sort http://en.wikipedia.org/wiki/Topological_sorting the graph and keep removing the nodes from vertices which have out degree of 0 (given the DAG, there will always be atleast one such vertex). Rest is self explanatory :) Veni Vedi Slumber ! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
On Sat, May 11, 2013 at 10:29 AM, Aman Jain pureama...@gmail.com wrote: 2. from this no*de u*, again apply* dfs* to find longest distant node from this node.Let us say that node is v. Small doubt about the solution. Consider this graph a - b - c - d You randomly choose vertex 'b' and do a DFS. Your u will be vertex 'd'. Then you do DFS from d, but its out degree is 0. So your DFS ends at 'd' itself and you report the solution as b-c-d. But the solution is a-b-c-d. What did I miss? My proposal: Topological Sort http://en.wikipedia.org/wiki/Topological_sorting the graph and keep removing the nodes from vertices which have out degree of 0 (given the DAG, there will always be atleast one such vertex). Rest is self explanatory :) Veni Vedi Slumber ! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
@atul anand : got it thanks for pointing it out
On Mon, May 13, 2013 at 12:19 AM, atul anand atul.87fri...@gmail.comwrote:
@Karthikeyan : Given graph is directed and does not carry edge
weight.So you cannot use pris/kruskal algo to convert them to
tree.Even if you tweak prism/krukal algo to form a tree , you can
never guarantee that each node will have only 2 child , it can have
more than 2 children.So your terminology of using t-.left and t-right
wont work here.nevertheless it will fail for simple cases mentioned
below :-
given graph :-
(a)-(b)
(a)-(c)
(b)-(c)
output should be (a) - (b) -(c)
now to convert into tree as you have mentioned above you have to
remove edge (b)-(c).
so output will be (a)-(b) or (a)-(c)
which is wrong.
On 5/12/13, Karthikeyan V.B kartmu...@gmail.com wrote:
@atul anand : acyclic graph can be converted to a tree using prim/kruskal
or by finding an appropriate node that can act like the root of a tree
On Sun, May 12, 2013 at 5:55 PM, atul anand atul.87fri...@gmail.com
wrote:
@karthikeyan : It is an acyclic graph not a binary tree. your solution
will work if given graph is a binary tree.
problem can be solved using dfs as suggested above
On 5/11/13, Karthikeyan V.B kartmu...@gmail.com wrote:
Since it is an acyclic graph, find the appropriate node that can be
the
root of this tree.
Now apply the logic to find the diameter of the tree here, which finds
the
longest path in the graph as follows:
int diameter(Tree * t) { if (t == 0) return 0; int lheight =
height(tree-left); int rheight = height(tree-right); int ldiameter =
diameter(tree-left); int rdiameter = diameter(tree-right); return
max(lheight + rheight + 1, max(ldiameter,rdiameter)); }
int height(Tree * t)
{
if (t == 0)
{ return 0; } else { return 1 + max(height(t-left),height(t-right));
}
}
On Sat, May 11, 2013 at 10:59 PM, Aman Jain pureama...@gmail.com
wrote:
In a connected and acyclic graph,that is a tree, we can apply this
approach
1. apply *dfs *on any random node and find the longest distant node
from
this node.Let us say this node i*s u*.
2. from this no*de u*, again apply* dfs* to find longest distant node
from this node.Let us say that node is v.
(u,v) is the required pair of nodes.
On Sat, May 11, 2013 at 7:16 PM, MAC macatad...@gmail.com wrote:
Given an acyclic graph. Give an algorithm to find the pair of nodes
which
has the maximum distance between them, i.e. the maximum number of
edges
in
between them
any suggestion ?
thanks
--mac
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
@karthikeyan : It is an acyclic graph not a binary tree. your solution
will work if given graph is a binary tree.
problem can be solved using dfs as suggested above
On 5/11/13, Karthikeyan V.B kartmu...@gmail.com wrote:
Since it is an acyclic graph, find the appropriate node that can be the
root of this tree.
Now apply the logic to find the diameter of the tree here, which finds the
longest path in the graph as follows:
int diameter(Tree * t) { if (t == 0) return 0; int lheight =
height(tree-left); int rheight = height(tree-right); int ldiameter =
diameter(tree-left); int rdiameter = diameter(tree-right); return
max(lheight + rheight + 1, max(ldiameter,rdiameter)); }
int height(Tree * t)
{
if (t == 0)
{ return 0; } else { return 1 + max(height(t-left),height(t-right)); } }
On Sat, May 11, 2013 at 10:59 PM, Aman Jain pureama...@gmail.com wrote:
In a connected and acyclic graph,that is a tree, we can apply this
approach
1. apply *dfs *on any random node and find the longest distant node from
this node.Let us say this node i*s u*.
2. from this no*de u*, again apply* dfs* to find longest distant node
from this node.Let us say that node is v.
(u,v) is the required pair of nodes.
On Sat, May 11, 2013 at 7:16 PM, MAC macatad...@gmail.com wrote:
Given an acyclic graph. Give an algorithm to find the pair of nodes
which
has the maximum distance between them, i.e. the maximum number of edges
in
between them
any suggestion ?
thanks
--mac
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
@atul anand : acyclic graph can be converted to a tree using prim/kruskal
or by finding an appropriate node that can act like the root of a tree
On Sun, May 12, 2013 at 5:55 PM, atul anand atul.87fri...@gmail.com wrote:
@karthikeyan : It is an acyclic graph not a binary tree. your solution
will work if given graph is a binary tree.
problem can be solved using dfs as suggested above
On 5/11/13, Karthikeyan V.B kartmu...@gmail.com wrote:
Since it is an acyclic graph, find the appropriate node that can be the
root of this tree.
Now apply the logic to find the diameter of the tree here, which finds
the
longest path in the graph as follows:
int diameter(Tree * t) { if (t == 0) return 0; int lheight =
height(tree-left); int rheight = height(tree-right); int ldiameter =
diameter(tree-left); int rdiameter = diameter(tree-right); return
max(lheight + rheight + 1, max(ldiameter,rdiameter)); }
int height(Tree * t)
{
if (t == 0)
{ return 0; } else { return 1 + max(height(t-left),height(t-right)); }
}
On Sat, May 11, 2013 at 10:59 PM, Aman Jain pureama...@gmail.com
wrote:
In a connected and acyclic graph,that is a tree, we can apply this
approach
1. apply *dfs *on any random node and find the longest distant node from
this node.Let us say this node i*s u*.
2. from this no*de u*, again apply* dfs* to find longest distant node
from this node.Let us say that node is v.
(u,v) is the required pair of nodes.
On Sat, May 11, 2013 at 7:16 PM, MAC macatad...@gmail.com wrote:
Given an acyclic graph. Give an algorithm to find the pair of nodes
which
has the maximum distance between them, i.e. the maximum number of edges
in
between them
any suggestion ?
thanks
--mac
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
@Karthikeyan : Given graph is directed and does not carry edge
weight.So you cannot use pris/kruskal algo to convert them to
tree.Even if you tweak prism/krukal algo to form a tree , you can
never guarantee that each node will have only 2 child , it can have
more than 2 children.So your terminology of using t-.left and t-right
wont work here.nevertheless it will fail for simple cases mentioned
below :-
given graph :-
(a)-(b)
(a)-(c)
(b)-(c)
output should be (a) - (b) -(c)
now to convert into tree as you have mentioned above you have to
remove edge (b)-(c).
so output will be (a)-(b) or (a)-(c)
which is wrong.
On 5/12/13, Karthikeyan V.B kartmu...@gmail.com wrote:
@atul anand : acyclic graph can be converted to a tree using prim/kruskal
or by finding an appropriate node that can act like the root of a tree
On Sun, May 12, 2013 at 5:55 PM, atul anand atul.87fri...@gmail.com
wrote:
@karthikeyan : It is an acyclic graph not a binary tree. your solution
will work if given graph is a binary tree.
problem can be solved using dfs as suggested above
On 5/11/13, Karthikeyan V.B kartmu...@gmail.com wrote:
Since it is an acyclic graph, find the appropriate node that can be the
root of this tree.
Now apply the logic to find the diameter of the tree here, which finds
the
longest path in the graph as follows:
int diameter(Tree * t) { if (t == 0) return 0; int lheight =
height(tree-left); int rheight = height(tree-right); int ldiameter =
diameter(tree-left); int rdiameter = diameter(tree-right); return
max(lheight + rheight + 1, max(ldiameter,rdiameter)); }
int height(Tree * t)
{
if (t == 0)
{ return 0; } else { return 1 + max(height(t-left),height(t-right));
}
}
On Sat, May 11, 2013 at 10:59 PM, Aman Jain pureama...@gmail.com
wrote:
In a connected and acyclic graph,that is a tree, we can apply this
approach
1. apply *dfs *on any random node and find the longest distant node
from
this node.Let us say this node i*s u*.
2. from this no*de u*, again apply* dfs* to find longest distant node
from this node.Let us say that node is v.
(u,v) is the required pair of nodes.
On Sat, May 11, 2013 at 7:16 PM, MAC macatad...@gmail.com wrote:
Given an acyclic graph. Give an algorithm to find the pair of nodes
which
has the maximum distance between them, i.e. the maximum number of
edges
in
between them
any suggestion ?
thanks
--mac
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
In a connected and acyclic graph,that is a tree, we can apply this approach 1. apply *dfs *on any random node and find the longest distant node from this node.Let us say this node i*s u*. 2. from this no*de u*, again apply* dfs* to find longest distant node from this node.Let us say that node is v. (u,v) is the required pair of nodes. On Sat, May 11, 2013 at 7:16 PM, MAC macatad...@gmail.com wrote: Given an acyclic graph. Give an algorithm to find the pair of nodes which has the maximum distance between them, i.e. the maximum number of edges in between them any suggestion ? thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
Since it is an acyclic graph, find the appropriate node that can be the
root of this tree.
Now apply the logic to find the diameter of the tree here, which finds the
longest path in the graph as follows:
int diameter(Tree * t) { if (t == 0) return 0; int lheight =
height(tree-left); int rheight = height(tree-right); int ldiameter =
diameter(tree-left); int rdiameter = diameter(tree-right); return
max(lheight + rheight + 1, max(ldiameter,rdiameter)); }
int height(Tree * t)
{
if (t == 0)
{ return 0; } else { return 1 + max(height(t-left),height(t-right)); } }
On Sat, May 11, 2013 at 10:59 PM, Aman Jain pureama...@gmail.com wrote:
In a connected and acyclic graph,that is a tree, we can apply this approach
1. apply *dfs *on any random node and find the longest distant node from
this node.Let us say this node i*s u*.
2. from this no*de u*, again apply* dfs* to find longest distant node
from this node.Let us say that node is v.
(u,v) is the required pair of nodes.
On Sat, May 11, 2013 at 7:16 PM, MAC macatad...@gmail.com wrote:
Given an acyclic graph. Give an algorithm to find the pair of nodes which
has the maximum distance between them, i.e. the maximum number of edges in
between them
any suggestion ?
thanks
--mac
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Amazon interview question
Your solution fails for a number of reasons:
1. If your array is size 1 or 0.
2. The last digit in the array is found by arr[n-1] - [n-2] not
arr[i+1]-arr[i]
3. Recursion here creates unnecessary overheard
How many times are you calling abc? Draw the recursion tree.
On Tue, Apr 9, 2013 at 11:29 AM, rahul sharma rahul23111...@gmail.comwrote:
A = {5, 3, 8, 9, 16}
After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
Given an array, return sum after n iterations
my sol/
void abc(int arr[],n)
{
for(i=0;in;i++)
arr[i]=arr[i+1]-arr[i];
abc(arr,n-1);
}
I wana ask that the complexity is o(n) or o(n)2..as loop is executed n
times..say n is 10...so fxn is called 10 timesi.e 10 n..and ignoring n
it comes out to be...n..but if we implemeted with 2 loops then
complexity is n2 ...and both sol are taking same no of iterations...please
tell whether complexity is n or n2 for above codeif it is n2 then how???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
@Rashmi: I did not get your approach. I do not get emails from the group just in case you have posted a solution :( What do you mean by keeping a count? Also, are you using a hashmap? If yes, whats ur K,V? #Pralay On Tue, Feb 12, 2013 at 10:00 AM, rashmi i rash...@gmail.com wrote: Hey Pralay, Sorry, if I have missed any point.Why would we need to map the frequencies when the second problem can be solved by simply keeping a count and comparing the index values that have been already mapped. On Fri, Feb 8, 2013 at 11:19 AM, sourabh jain wsour...@gmail.com wrote: One solution for the 2nd question can be LinkedHashMap (linked list + hashmap) . Store the integer in linked list in the order of occurrence in stream and make an entry in hashmap on first occurence. Delete the integer entry from linked list on 2nd occurence and replace the reference with some special value so for 3rd time no need to touch the linked list. while printing the result print first k integers from linked list. On Fri, Feb 8, 2013 at 9:46 AM, bharat b bagana.bharatku...@gmail.comwrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.comwrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- R@$!-! DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS. -- You received this
Re: [algogeeks] Amazon interview Question
Guys, Why can't we simply use a hashset for both the questions. hash the arr[i] and the frequencies in the hash map in the first pass. Then iterate over the array to find the first arr[i] whose freq is 1 in the hash map. For second part, keep a count and find the kth element in the array whose freq in the hashmap is 1. *Pralay MS-Comp Sci* *Univ of California* On Thu, Feb 7, 2013 at 8:16 PM, bharat b bagana.bharatku...@gmail.comwrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.com wrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
first problem can be solved using a fixed sized array if we know the range of numbers or a hash table with an appropriate hash function and it is O(N) for time and space as some solutions above already mentioned this. for the second problem, I don't think heap is the right data structure which is only good for getting min(max) element in logN time. A possible solution would be to use a combination of linked list and a hash table. For every incoming number num(i) of the stream, check if the number exists in the hash table and: 1. if it does not exist, add an entry in hash table and insert a node in linked list. HashTbl row is key,val pair of num,Node* where Node* points to the corresponding node entry in the linked list. linked list node should contain pointer(index) to the corresponding HashTblRow. It is like hash table entry pointing to corresponding node in the list and list node pointing to hash table entry.O(1) adding to hash table and list. 2. if it does exist, delete the node from hash table and find the list node address, and delete it from the list. O(1) operation To find the k-th unique number: just walk the list, O(k) On Thu, Feb 7, 2013 at 11:16 PM, bharat b bagana.bharatku...@gmail.com wrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.com wrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
One solution for the 2nd question can be LinkedHashMap (linked list + hashmap) . Store the integer in linked list in the order of occurrence in stream and make an entry in hashmap on first occurence. Delete the integer entry from linked list on 2nd occurence and replace the reference with some special value so for 3rd time no need to touch the linked list. while printing the result print first k integers from linked list. On Fri, Feb 8, 2013 at 9:46 AM, bharat b bagana.bharatku...@gmail.comwrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.com wrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
Hey Pralay, Sorry, if I have missed any point.Why would we need to map the frequencies when the second problem can be solved by simply keeping a count and comparing the index values that have been already mapped. On Fri, Feb 8, 2013 at 11:19 AM, sourabh jain wsour...@gmail.com wrote: One solution for the 2nd question can be LinkedHashMap (linked list + hashmap) . Store the integer in linked list in the order of occurrence in stream and make an entry in hashmap on first occurence. Delete the integer entry from linked list on 2nd occurence and replace the reference with some special value so for 3rd time no need to touch the linked list. while printing the result print first k integers from linked list. On Fri, Feb 8, 2013 at 9:46 AM, bharat b bagana.bharatku...@gmail.comwrote: @sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.com wrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- R@$!-! DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
was trying to do something clever. Knew it couldnt be that simple. Missed some cases. I still feel with some hacks and handling some special cases this approach would work. But considering it still takes O(n) time I am not thrilled. I am still ok with my algo taking Space for time. But probably not the other way unless there are some special constraints. Hashtable it is. Srikar On Thursday, February 7, 2013 12:35:21 PM UTC+5:30, bharat wrote: @srikar : approach2 is wrong. ex: [1, 5, 7, 66, 7, 1, 77] first window [1,5,7] all are unique.oops On Wed, Feb 6, 2013 at 11:31 PM, Srikar srika...@gmail.com javascript:wrote: *APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet@gmail.com javascript: wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.an...@gmail.comjavascript: wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet@gmail.com javascript: wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
I guess the part 1 can be solved in O(n) time and space both. Here is my
approach.
Assume: Array given is arr[] = {2,3,1,2,3,2,4,1,5,6}
1. Given an array, scan thru it, element by element and hash it on a
hashmap with key as the arr[i] as the key and i+1 as the index.
2. There would be two cases
a) arr[i] is already there in the hash map, if so, check if the
hashmap.get(arr[i]) is a negative or not. If it is negative , do nothing.
If its is not negative, negate it.
b) arr[i] is a new element, in such a case, hash key as arr[i] and i+1
as the value.
3. Scan thru the value set, the key corresponding to minimum of positive
values is the answer.
Example.
For {2,3,1,2,3,2,4,1, 5,6}
2 = not seen, hash 2,1 (arr[i], i+1)
3 = not seen, hash 3, 2
1 = not seen, hash 1,3
2 = seen - is the value corresponding to key 2 negative = No. So negate
it- hash entry now becomes 2,-1
3 = similar to above - Hash entry is 3,-2
2 = seen, is the value negative = yes, do nothing
4 = not seen, hash 4,8
1 = seen, is the value corresponding to key 1 -ve? No, negate it, hashentry
= 1,-3
5 = not seen, hash 5,10
6= not seen, hash 6,11
Hasmap ready. Whats the value set (the values only) ? -1,-2,-3,8,10,11
Whats the *least minimum of positive values*? 8
Whats the key corresponding to value 8? Its 4.
*4 is the first unique number!*
Please let me know if you need the code, shall send you ova :)
Cheers,
*Pralay*
*MS,Comp Sci, *
*University of California, Irvine*
On Tue, Feb 5, 2013 at 8:30 PM, navneet singh gaur
navneet.singhg...@gmail.com wrote:
nice algo ankit, so it will be nlogn using O (n) space only. What abt
2nd Q., which have a big online stream.
On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote:
For 1:
i think you can use sorting, sort the array and keep the indices of the
numbers in the sorted list.
Now traverse the sorted list and in the sorted list you need to find the
unique number with the
minimum index which is easy to find.
Eg: Array:5 3 1 2 4 1 4
Indices: 0 1 2 3 4 5 6
After sorting : Array:1 1 2 3 4 4 5
Indices: 2 5 3 1 4 6 1
Now you can see the unique number with lowest index is 3(index=1). So ,
you
have your answer.
On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur
navneet.singhg...@gmail.com wrote:
1. Given a array,find a first unique integer.
2. Integers are coming as online stream,have to find a kth unique
integer
till now.
For 1.
Even we cannot use sorting for solving this as if we sort it than our
first number which is non-repetitive changes.
The best I am able to do is nlogn using a space of O( n ).
For 2. No idea
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
Kumar Ankit
Senior Undergraduate
Department of Computer Engineering
Institute of Technology
Banaras Hindu University
Varanasi
Ph: +91 9473629892
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
navneet singh gaur
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
Navneet, For 2nd problem, i need a clarification, whether the Kth number is wrt mathematical ordering of numbers or the kth number is wrt to the order in which the number are input ? On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
what would happen of the input is like this : 5, 5, 66, 66, 7, 1, 1, 77,7 i think in this case the moment window reaches to point (66,7,1) it will take 7 as unique number but that too window will not move any futhur , but 7 is not unique . Please comment if i misunderstood ur explanation . On Wed, Feb 6, 2013 at 11:31 PM, Srikar srikar2...@gmail.com wrote: *APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
Also, for the part two of the question, you can simply go in for the *kth
largest positive index *in the same hashmap (described earlier for part 1).
That solves the part two of the problem :)
Hth,
*Pralay Biswas*
*MS,Comp Sci, *
*University of California, Irvine*
On Tue, Feb 5, 2013 at 8:46 PM, Pralay Biswas pralaybiswas2...@gmail.comwrote:
I guess the part 1 can be solved in O(n) time and space both. Here is my
approach.
Assume: Array given is arr[] = {2,3,1,2,3,2,4,1,5,6}
1. Given an array, scan thru it, element by element and hash it on a
hashmap with key as the arr[i] as the key and i+1 as the index.
2. There would be two cases
a) arr[i] is already there in the hash map, if so, check if the
hashmap.get(arr[i]) is a negative or not. If it is negative , do nothing.
If its is not negative, negate it.
b) arr[i] is a new element, in such a case, hash key as arr[i] and i+1
as the value.
3. Scan thru the value set, the key corresponding to minimum of positive
values is the answer.
Example.
For {2,3,1,2,3,2,4,1, 5,6}
2 = not seen, hash 2,1 (arr[i], i+1)
3 = not seen, hash 3, 2
1 = not seen, hash 1,3
2 = seen - is the value corresponding to key 2 negative = No. So negate
it- hash entry now becomes 2,-1
3 = similar to above - Hash entry is 3,-2
2 = seen, is the value negative = yes, do nothing
4 = not seen, hash 4,8
1 = seen, is the value corresponding to key 1 -ve? No, negate it,
hashentry = 1,-3
5 = not seen, hash 5,10
6= not seen, hash 6,11
Hasmap ready. Whats the value set (the values only) ? -1,-2,-3,8,10,11
Whats the *least minimum of positive values*? 8
Whats the key corresponding to value 8? Its 4.
*4 is the first unique number!*
Please let me know if you need the code, shall send you ova :)
Cheers,
*Pralay*
*MS,Comp Sci, *
*University of California, Irvine*
On Tue, Feb 5, 2013 at 8:30 PM, navneet singh gaur
navneet.singhg...@gmail.com wrote:
nice algo ankit, so it will be nlogn using O (n) space only. What abt
2nd Q., which have a big online stream.
On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote:
For 1:
i think you can use sorting, sort the array and keep the indices of the
numbers in the sorted list.
Now traverse the sorted list and in the sorted list you need to find
the
unique number with the
minimum index which is easy to find.
Eg: Array:5 3 1 2 4 1 4
Indices: 0 1 2 3 4 5 6
After sorting : Array:1 1 2 3 4 4 5
Indices: 2 5 3 1 4 6 1
Now you can see the unique number with lowest index is 3(index=1). So ,
you
have your answer.
On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur
navneet.singhg...@gmail.com wrote:
1. Given a array,find a first unique integer.
2. Integers are coming as online stream,have to find a kth unique
integer
till now.
For 1.
Even we cannot use sorting for solving this as if we sort it than our
first number which is non-repetitive changes.
The best I am able to do is nlogn using a space of O( n ).
For 2. No idea
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
Kumar Ankit
Senior Undergraduate
Department of Computer Engineering
Institute of Technology
Banaras Hindu University
Varanasi
Ph: +91 9473629892
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
navneet singh gaur
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
@sourabh : how do u find whether the element in stream gets repeated in heap.-- O(n) time...totally its O(nk) algo .. If we maintain max-heap with BST property on index, then it would be O(nlogk). On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain wsour...@gmail.com wrote: for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it. On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
*APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
@srikar : approach2 is wrong. ex: [1, 5, 7, 66, 7, 1, 77] first window [1,5,7] all are unique.oops On Wed, Feb 6, 2013 at 11:31 PM, Srikar srikar2...@gmail.com wrote: *APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
in above algo primary index is no of times that value is repeated till now -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
I can think of an o(n^2) algo for 2n question Make a heap formed acctoring to two indexes 1.Primary -value 2.Secondary - index Now for each new incoming value first search in head if exist inc its index else make a new node -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon Onsite
can any one give me anexample which takes worst case of this problem On Mon, Mar 26, 2012 at 1:56 PM, Arpit Sood soodfi...@gmail.com wrote: @ankur +1 correct algo, can be done in just one pass. On Mon, Oct 24, 2011 at 11:03 PM, Ankur Garg ankurga...@gmail.com wrote: I think this can be solved like this . Start from the first petrol pump i.e first point in the circle . Now if the petrol finishes befor reaching the second petrol pump that means we chose the incorrect point . So , choose second petrol pump now. If u reach third, fill ur tanker and move to 4th . Now if before 4th we again run out of petrol that means our choice was incorrect . Start from 4th and so on .. If u reach the starting point again this is the choice we need to make ..and thats the answer . Programatically , it can be thought of Kadane Algo ..(seems to me ..not sure of algo) but I think this way we just make at most 2 pass (in case the petrol pump of choice is just before the first point ) . Please comment in case you think its right/wrong Regards Ankur On Mon, Oct 24, 2011 at 10:15 PM, ravindra patel ravindra.it...@gmail.com wrote: @Nitin, excellent algo. if S 0 j = i-1 return 0 // I believe this mean there is no solution, you might want to return -1. Thanks, - Ravindra On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg nitin.garg.i...@gmail.comwrote: Lets say the Amount of petrol is Pi and distance to next petrol pump is Di for ith petrol pump. start from i=1, j=1 S =0 while (i=n) S += Pj - Dj; if S = 0 j = i-1 return i if S 0 j = i-1 return 0 else if S = 0 j++ mod n; else if S 0 j ++ mod n, i = j , S = 0; return 0 it will traverse atmost twice, and hence O(n). no extra space required. On Mon, Oct 24, 2011 at 4:06 AM, Aniket aniket...@gmail.com wrote: Suppose there is a circle. You have five points on that circle. Each point corresponds to a petrol pump. You are given two sets of data. 1. The amount of petrol that petrol pump will give. 2. Distance from that petrol pump to the next petrol pump. (Assume for 1 lit Petrol the truck will go 1 km) Now calculate the first point from where a truck will be able to complete the circle. (The truck will stop at each petrol pump and it has infinite capacity). Give o(n) solution. You may use o(n) extra space. -- 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. -- 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, Arpit Sood -- 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] Amazon Dynamic Programming problem
how is winning going to decided On Sat, Jan 12, 2013 at 6:33 PM, siva sivavikne...@gmail.com wrote: consider there are N balls in a basket. 2 players play the turns alternatively ..AT each turn,the player can take 1 or 2 balls from the basket. the first player starts the game.. Both the players play optimally. i) Given N,tell whether the 1st player win or loss ? ii) If player 1 wins, how many balls he should take at this first turn(1 or 2) ? -- --
Re: [algogeeks] Amazon Dynamic Programming problem
Are we supposed to assume that every ball played is a hit? Or should we consider a hit or a fail case?? On Sat, Jan 12, 2013 at 7:12 PM, Raunak Gupta raunak.gupt...@gmail.comwrote: how is winning going to decided On Sat, Jan 12, 2013 at 6:33 PM, siva sivavikne...@gmail.com wrote: consider there are N balls in a basket. 2 players play the turns alternatively ..AT each turn,the player can take 1 or 2 balls from the basket. the first player starts the game.. Both the players play optimally. i) Given N,tell whether the 1st player win or loss ? ii) If player 1 wins, how many balls he should take at this first turn(1 or 2) ? -- -- --
Re: [algogeeks] Amazon Dynamic Programming problem
The player who plays the last turn and finishes the game wins ... I think the approach would be similar to this .. http://www.spoj.com/problems/TWENDS/ .. @vamshi .. Can't get your question? .. what you refer to hit or fail case in picking up a ball?.. At the end any of the 2 players can win On Saturday, 12 January 2013 19:12:19 UTC+5:30, raunak wrote: how is winning going to decided On Sat, Jan 12, 2013 at 6:33 PM, siva sivavi...@gmail.com javascript:wrote: consider there are N balls in a basket. 2 players play the turns alternatively ..AT each turn,the player can take 1 or 2 balls from the basket. the first player starts the game.. Both the players play optimally. i) Given N,tell whether the 1st player win or loss ? ii) If player 1 wins, how many balls he should take at this first turn(1 or 2) ? -- --
Re: [algogeeks] Amazon interview Question
loop from the end of given number till you get a digit less than the previously scanned digit.Let the index of that number be 'i' . if index = -1,then the given number is the largest one else do the following 1) swap the digit at the index i with the digit just greater than it in the scanned portion 2) sort the remaining scanned digits after index i. Ex:- let the given number be 51432 the digit '1' is the first digit less that its previously scanned digit '4' thus, we swap 2 which is the smallest greater digit the '1' in scanned portion to get 52431 and the we sort the remaining digits after the index to get 52134. --
Re: [algogeeks] amazon question
we can represent in 3-D array .. what type of elements are those .. is there any special kind of formation among elements for searching? we have to think about searching based on the criteria .. On Tue, Oct 23, 2012 at 3:34 PM, saket narayan.shiv...@gmail.com wrote: We have a long chain of cuboids in all the six directions (six faces). One start node is given and one end node is given. Give a data structure to represent this also search for the given node from start node. -- 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/-/5GuOVuTne4cJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] amazon question
If the requirement is only searching in 3-D .. there is a famous data structure K-D tree. On Tue, Oct 23, 2012 at 5:54 PM, bharat b bagana.bharatku...@gmail.comwrote: we can represent in 3-D array .. what type of elements are those .. is there any special kind of formation among elements for searching? we have to think about searching based on the criteria .. On Tue, Oct 23, 2012 at 3:34 PM, saket narayan.shiv...@gmail.com wrote: We have a long chain of cuboids in all the six directions (six faces). One start node is given and one end node is given. Give a data structure to represent this also search for the given node from start node. -- 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/-/5GuOVuTne4cJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] amazon Interview
@atul-I think This Should work for n dimension- complexity O(n^no.of dimesions) :- have N-dimension check for which Tile can contain which Tile.i.e (3,3,4) can contain (2,3,4) . Now 1.Take the titles which cannot contain any-other tile set no-of tile if it is base =1; 2.now take tiles which can contain 1 tile only.This tile will contain any of tiles in 1. case ..it cannot be other title..since other tile can contain tiles=1 which means it shud contain =2..which is not true. set with base value=(if it exist)1+1=2; 3.similarly for other Tiles..in increasing order check maximum tile it can contain.. correct me if wrong...complexity is high but its due to no.of dimesion..for n=2 its simply O(n^2).. -- 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] Amazon Q
Q1 Solution: . we can use doubly linked list with hash to implement all the
operation in O(1).
By keeping track of head and tail pointer we can do enqueue and dequeue in
O(1) time.
In hash we will keep track of each element present in linked list(queue).
With node value as a hash key and address of node as a value. So for
searching we can do it in O(1).
For deleting an element we will directly take address of that value from
hash and delete it. O(1) time.
Q2. /*my code will return NULL if not palindrome and head if it is
palindrome */
count = totalnode/2;
//odd = 0 if totalnode is even else 1
struct node *checkPalindrome(struct node *head, int count)
{
struct node *temp;
if(count == 0) {
if(odd head-next) return head-next;
else return head;
}
if(count 0)
temp = checkPalindrome(head-next, count - 1);
if(temp (temp-data == head-data ) !temp-next)
return head;
else if (temp (temp-data == head-data ))
return temp-next;
else return NULL;
}
On Sun, Aug 26, 2012 at 12:41 AM, Ashish Goel ashg...@gmail.com wrote:
Q1. Design a data structure for the following operations:
I.Enqueue
II. Dequeue
III. Delete a given number(if it is present in the queue,
else do nothing)
IV. isNumberPresent
All these operations should take O(1) time.
Q2. Check if a linked list (each char is a node) is palindrome,
recursively.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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] amazon Interview
its a LIS problem. need to think for n-dimension... On 8/26/12, Ravi Ranjan ravi.cool2...@gmail.com wrote: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs and for general n-dimesions -- 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] amazon Interview
Yeah Atul is right.
Here is my solution:--
1) first rearrange the dimensions of slabs i.e. put bigger dimension in y
and smaller dimenson in x (rotate the slab)
2) then arrange all slabs in increasing order of x dimension
3) and then find the longest increasing sub-sequence based on y
dimension..
Ex:- (2,5),(5,1),(1,3),(1,2),(6,1)
Step-1= (2,5),(1,5),(1,3),(1,2),(1,6)
Step-2= (1,2),(1,3),(1,5),(1,6),(2,5)
Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR (1,2),(1,3),(1,5),(2,5) }
Correct me if i wrong...
On Sun, Aug 26, 2012 at 3:54 PM, atul anand atul.87fri...@gmail.com wrote:
its a LIS problem.
need to think for n-dimension...
On 8/26/12, Ravi Ranjan ravi.cool2...@gmail.com wrote:
You are given many slabs each with a length and a breadth. A slab i can
be
put on slab j if both dimensions of i are less than that of j. In this
similar manner, you can keep on putting slabs on each other. Find the
maximum stack possible which you can create out of the given slabs
and for general n-dimesions
--
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.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
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] amazon Interview
@kailash : you can simply find area of each slab area=x*y ,,,store it;
then just run LIS on this area.
On 8/26/12, Kailash Bagaria kbkailashbaga...@gmail.com wrote:
Yeah Atul is right.
Here is my solution:--
1) first rearrange the dimensions of slabs i.e. put bigger dimension in y
and smaller dimenson in x (rotate the slab)
2) then arrange all slabs in increasing order of x dimension
3) and then find the longest increasing sub-sequence based on y
dimension..
Ex:- (2,5),(5,1),(1,3),(1,2),(6,1)
Step-1= (2,5),(1,5),(1,3),(1,2),(1,6)
Step-2= (1,2),(1,3),(1,5),(1,6),(2,5)
Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR (1,2),(1,3),(1,5),(2,5)
}
Correct me if i wrong...
On Sun, Aug 26, 2012 at 3:54 PM, atul anand atul.87fri...@gmail.com
wrote:
its a LIS problem.
need to think for n-dimension...
On 8/26/12, Ravi Ranjan ravi.cool2...@gmail.com wrote:
You are given many slabs each with a length and a breadth. A slab i can
be
put on slab j if both dimensions of i are less than that of j. In this
similar manner, you can keep on putting slabs on each other. Find the
maximum stack possible which you can create out of the given slabs
and for general n-dimesions
--
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.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
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] amazon Interview
@Atul007: No, because a (1,4) tile will not fit on a (2,3) tile.
Dave
On Sunday, August 26, 2012 7:45:27 AM UTC-5, atul007 wrote:
@kailash : you can simply find area of each slab area=x*y ,,,store it;
then just run LIS on this area.
On 8/26/12, Kailash Bagaria kbkailas...@gmail.com javascript: wrote:
Yeah Atul is right.
Here is my solution:--
1) first rearrange the dimensions of slabs i.e. put bigger dimension in
y
and smaller dimenson in x (rotate the slab)
2) then arrange all slabs in increasing order of x dimension
3) and then find the longest increasing sub-sequence based on y
dimension..
Ex:- (2,5),(5,1),(1,3),(1,2),(6,1)
Step-1= (2,5),(1,5),(1,3),(1,2),(1,6)
Step-2= (1,2),(1,3),(1,5),(1,6),(2,5)
Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR
(1,2),(1,3),(1,5),(2,5)
}
Correct me if i wrong...
On Sun, Aug 26, 2012 at 3:54 PM, atul anand
atul.8...@gmail.comjavascript:
wrote:
its a LIS problem.
need to think for n-dimension...
On 8/26/12, Ravi Ranjan ravi.c...@gmail.com javascript: wrote:
You are given many slabs each with a length and a breadth. A slab i
can
be
put on slab j if both dimensions of i are less than that of j. In
this
similar manner, you can keep on putting slabs on each other. Find the
maximum stack possible which you can create out of the given slabs
and for general n-dimesions
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/ABJAgG77YhkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] amazon Interview
@dave : correct..
i guess this will work :-
sort in decreasing area.
then run LIS such that for i j , length( i ) length( j ) width(
i ) width( j )
On 8/26/12, Dave dave_and_da...@juno.com wrote:
@Atul007: No, because a (1,4) tile will not fit on a (2,3) tile.
Dave
On Sunday, August 26, 2012 7:45:27 AM UTC-5, atul007 wrote:
@kailash : you can simply find area of each slab area=x*y ,,,store it;
then just run LIS on this area.
On 8/26/12, Kailash Bagaria kbkailas...@gmail.com javascript: wrote:
Yeah Atul is right.
Here is my solution:--
1) first rearrange the dimensions of slabs i.e. put bigger dimension in
y
and smaller dimenson in x (rotate the slab)
2) then arrange all slabs in increasing order of x dimension
3) and then find the longest increasing sub-sequence based on y
dimension..
Ex:- (2,5),(5,1),(1,3),(1,2),(6,1)
Step-1= (2,5),(1,5),(1,3),(1,2),(1,6)
Step-2= (1,2),(1,3),(1,5),(1,6),(2,5)
Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR
(1,2),(1,3),(1,5),(2,5)
}
Correct me if i wrong...
On Sun, Aug 26, 2012 at 3:54 PM, atul anand
atul.8...@gmail.comjavascript:
wrote:
its a LIS problem.
need to think for n-dimension...
On 8/26/12, Ravi Ranjan ravi.c...@gmail.com javascript: wrote:
You are given many slabs each with a length and a breadth. A slab i
can
be
put on slab j if both dimensions of i are less than that of j. In
this
similar manner, you can keep on putting slabs on each other. Find the
maximum stack possible which you can create out of the given slabs
and for general n-dimesions
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/ABJAgG77YhkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Amazon Q
Q2) get to n/2 nodes Reverse link list after n/2 nodes Now check from 1st node and n/2 node for equality Can make the checking for equality function recursive Sent from my iPhone 4 On 26-Aug-2012, at 12:41 AM, Ashish Goel ashg...@gmail.com wrote: Q1. Design a data structure for the following operations: I.Enqueue II. Dequeue III. Delete a given number(if it is present in the queue, else do nothing) IV. isNumberPresent All these operations should take O(1) time. Q2. Check if a linked list (each char is a node) is palindrome, recursively. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] amazon Interview
but how to solve this problem for with n-dimension ??
On Sun, Aug 26, 2012 at 6:47 PM, atul anand atul.87fri...@gmail.com wrote:
@dave : correct..
i guess this will work :-
sort in decreasing area.
then run LIS such that for i j , length( i ) length( j ) width(
i ) width( j )
On 8/26/12, Dave dave_and_da...@juno.com wrote:
@Atul007: No, because a (1,4) tile will not fit on a (2,3) tile.
Dave
On Sunday, August 26, 2012 7:45:27 AM UTC-5, atul007 wrote:
@kailash : you can simply find area of each slab area=x*y ,,,store it;
then just run LIS on this area.
On 8/26/12, Kailash Bagaria kbkailas...@gmail.com javascript:
wrote:
Yeah Atul is right.
Here is my solution:--
1) first rearrange the dimensions of slabs i.e. put bigger dimension
in
y
and smaller dimenson in x (rotate the slab)
2) then arrange all slabs in increasing order of x dimension
3) and then find the longest increasing sub-sequence based on y
dimension..
Ex:- (2,5),(5,1),(1,3),(1,2),(6,1)
Step-1= (2,5),(1,5),(1,3),(1,2),(1,6)
Step-2= (1,2),(1,3),(1,5),(1,6),(2,5)
Step-3= LIS=4 { (1,2),(1,3),(1,5),(1,6) OR
(1,2),(1,3),(1,5),(2,5)
}
Correct me if i wrong...
On Sun, Aug 26, 2012 at 3:54 PM, atul anand
atul.8...@gmail.comjavascript:
wrote:
its a LIS problem.
need to think for n-dimension...
On 8/26/12, Ravi Ranjan ravi.c...@gmail.com javascript: wrote:
You are given many slabs each with a length and a breadth. A slab i
can
be
put on slab j if both dimensions of i are less than that of j. In
this
similar manner, you can keep on putting slabs on each other. Find
the
maximum stack possible which you can create out of the given slabs
and for general n-dimesions
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--
‘Kailash Bagaria’
B-tech 4th year
Computer Science Engineering
Indian Institute of Technology, Roorkee
Roorkee, India (247667)
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algo...@googlegroups.comjavascript:.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/ABJAgG77YhkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] amazon online test question
Wow.. You got this question... Lucky Fellow so easy.. I remember SISO
asking such question long back.. its way below Amazon Standard...
Basically they want to make Sure U understand the question.. Implementation
is jst a copy of the content of the current SLL Node and rewiring the rest.
On Sun, Aug 5, 2012 at 6:39 PM, vaibhav shukla vaibhav200...@gmail.comwrote:
Given a singly linked list with a random pointer pointing to any node(can
be even null).
Create a clone of the list.
node structure can be :
struct node {
struct node *next;
struct node *random;
int value;
}
The next pointer points to next node in the list while random pointer may
point to anywhere.
We have to Clone the list.
--
best wishes!!
Vaibhav
--
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] amazon online test question
yeah... i got that... just shared with algogeeks ;)
questions were somewhat easy
On Sun, Aug 5, 2012 at 7:25 PM, Prem Krishna Chettri hprem...@gmail.comwrote:
Wow.. You got this question... Lucky Fellow so easy.. I remember SISO
asking such question long back.. its way below Amazon Standard...
Basically they want to make Sure U understand the question..
Implementation is jst a copy of the content of the current SLL Node and
rewiring the rest.
On Sun, Aug 5, 2012 at 6:39 PM, vaibhav shukla vaibhav200...@gmail.comwrote:
Given a singly linked list with a random pointer pointing to any node(can
be even null).
Create a clone of the list.
node structure can be :
struct node {
struct node *next;
struct node *random;
int value;
}
The next pointer points to next node in the list while random pointer may
point to anywhere.
We have to Clone the list.
--
best wishes!!
Vaibhav
--
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.
--
best wishes!!
Vaibhav
--
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] Amazon CodeSprint
Well, I donoo the TO cost Impact on this question. If we need to get the solution within the given interview time , we can go for the permutation approach.. i.e permute all the operators and calculate. But the T(O) and S(O) is seriously jeopardize. Anyone got better ones?? On Sat, Aug 4, 2012 at 8:03 PM, Navin Kumar navin.nit...@gmail.com wrote: Given the array of digits, you have to calculate the least positive integer value of the expression that could *NOT *have been received by you. The binary operators possible are *, +, -, / and brackets possible are ( and ). Note that / is an integer division i.e. 9/5 = 1. For ex- 6 6 4 4 the answer is 18 1 = 6 /6 + 4-4 2 = 6/6 + 4/4 3 = 6 +( 6/4) -4 4 = (6+6+4) / 4 …….. 18 cannot be formed -- 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/-/cxnY9WEACTIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] [Amazon]
@Shobhit: Can you give me a few hints on implementing a BS on the 2D?
@neelpulse: That's what I said. A 2D array *might* be a probable candidate.
In your example, the first 2d satisfies the criteria...so we check it --
Not found -- Reject -- Move on to next probable candidate.
On Sat, Jul 21, 2012 at 5:14 PM, neelpulse(Jadavpur University)
neelpu...@gmail.com wrote:
May be I am missing a few details. But Consider this 3D array:
{
{
{1,2},
{7,8} // First 2D array
},
{
{3,4},
{9,10}
}
}
If you search for 3 then your search in first step will give first 2D
which actually does not contain 3. As per my interpretation of the problem,
my array is holding the preconditions.
On Friday, 20 July 2012 16:25:49 UTC+5:30, algo bard wrote:
Compare the element with the first([0][0]) and the last
element([n-1][n-1]) of each 2D array to pin down the 2D array it *might* be
present in.
After that you can follow this approach : http://www.geeksforgeeks.org/*
*archives/11337 http://www.geeksforgeeks.org/archives/11337
If it's not present in that 2D, move on and search for the next target 2D.
The Probable 2D target set will be given by :
arr[i][0][0]=element=arr[i][**n-1][n-1].
Reject the 2Ds which don't follow this condition.
TC: O(n^2)
Though, I think an O(n) approach must exist for this problem.
On Fri, Jul 20, 2012 at 11:24 AM, Sakshi Agrawal sweetsaksh...@gmail.com
wrote:
How will you search an element in sorted 3D Array ? ( Sorted in all the
3 directions )
--
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 group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/UKYO8gE0s08J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] [Amazon]
Sorry , I've tried but BS will not work here .
On Tue, Jul 24, 2012 at 9:17 PM, algo bard algo.b...@gmail.com wrote:
@Shobhit: Can you give me a few hints on implementing a BS on the 2D?
@neelpulse: That's what I said. A 2D array *might* be a probable
candidate. In your example, the first 2d satisfies the criteria...so we
check it -- Not found -- Reject -- Move on to next probable candidate.
On Sat, Jul 21, 2012 at 5:14 PM, neelpulse(Jadavpur University)
neelpu...@gmail.com wrote:
May be I am missing a few details. But Consider this 3D array:
{
{
{1,2},
{7,8} // First 2D array
},
{
{3,4},
{9,10}
}
}
If you search for 3 then your search in first step will give first 2D
which actually does not contain 3. As per my interpretation of the problem,
my array is holding the preconditions.
On Friday, 20 July 2012 16:25:49 UTC+5:30, algo bard wrote:
Compare the element with the first([0][0]) and the last
element([n-1][n-1]) of each 2D array to pin down the 2D array it *might* be
present in.
After that you can follow this approach : http://www.geeksforgeeks.org/
**archives/11337 http://www.geeksforgeeks.org/archives/11337
If it's not present in that 2D, move on and search for the next target
2D.
The Probable 2D target set will be given by :
arr[i][0][0]=element=arr[i][**n-1][n-1].
Reject the 2Ds which don't follow this condition.
TC: O(n^2)
Though, I think an O(n) approach must exist for this problem.
On Fri, Jul 20, 2012 at 11:24 AM, Sakshi Agrawal
sweetsaksh...@gmail.com wrote:
How will you search an element in sorted 3D Array ? ( Sorted in all
the 3 directions )
--
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 group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/UKYO8gE0s08J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] [Amazon]
May be I am missing a few details. But Consider this 3D array:
{
{
{1,2},
{7,8} // First 2D array
},
{
{3,4},
{9,10}
}
}
If you search for 3 then your search in first step will give first 2D which
actually does not contain 3. As per my interpretation of the problem, my
array is holding the preconditions.
On Friday, 20 July 2012 16:25:49 UTC+5:30, algo bard wrote:
Compare the element with the first([0][0]) and the last
element([n-1][n-1]) of each 2D array to pin down the 2D array it *might* be
present in.
After that you can follow this approach :
http://www.geeksforgeeks.org/archives/11337
If it's not present in that 2D, move on and search for the next target 2D.
The Probable 2D target set will be given by :
arr[i][0][0]=element=arr[i][n-1][n-1].
Reject the 2Ds which don't follow this condition.
TC: O(n^2)
Though, I think an O(n) approach must exist for this problem.
On Fri, Jul 20, 2012 at 11:24 AM, Sakshi Agrawal
sweetsaksh...@gmail.comwrote:
How will you search an element in sorted 3D Array ? ( Sorted in all the
3 directions )
--
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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/UKYO8gE0s08J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] [Amazon]
Compare the element with the first([0][0]) and the last element([n-1][n-1]) of each 2D array to pin down the 2D array it *might* be present in. After that you can follow this approach : http://www.geeksforgeeks.org/archives/11337 If it's not present in that 2D, move on and search for the next target 2D. The Probable 2D target set will be given by : arr[i][0][0]=element=arr[i][n-1][n-1]. Reject the 2Ds which don't follow this condition. TC: O(n^2) Though, I think an O(n) approach must exist for this problem. On Fri, Jul 20, 2012 at 11:24 AM, Sakshi Agrawal sweetsaksh...@gmail.comwrote: How will you search an element in sorted 3D Array ? ( Sorted in all the 3 directions ) -- 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] [Amazon]
@algo bard : Why dont you use binary search in your first step (while comparing first and last element of 2d array) On Fri, Jul 20, 2012 at 4:25 PM, algo bard algo.b...@gmail.com wrote: Compare the element with the first([0][0]) and the last element([n-1][n-1]) of each 2D array to pin down the 2D array it *might* be present in. After that you can follow this approach : http://www.geeksforgeeks.org/archives/11337 If it's not present in that 2D, move on and search for the next target 2D. The Probable 2D target set will be given by : arr[i][0][0]=element=arr[i][n-1][n-1]. Reject the 2Ds which don't follow this condition. TC: O(n^2) Though, I think an O(n) approach must exist for this problem. On Fri, Jul 20, 2012 at 11:24 AM, Sakshi Agrawal sweetsaksh...@gmail.comwrote: How will you search an element in sorted 3D Array ? ( Sorted in all the 3 directions ) -- 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] Amazon Interview Question
@ashgoel - Could you please explain what exactly are you doing here ?
On Wednesday, 4 July 2012 16:16:38 UTC+5:30, ashgoel wrote:
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote:
Find the next higher number in set of permutations of a given number
--
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/-/Q7xtXJj8lVIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Amazon Interview Question
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote:
Find the next higher number in set of permutations of a given number
--
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] Amazon Interview Question
Q5 is sorting problem
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote:
Find the next higher number in set of permutations of a given number
--
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] Amazon Interview Question
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote:
Find the next higher number in set of permutations of a given number
--
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] Amazon Interview Question
Consider trees:
1 3
2 3 2
1
pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't
satisfy the criteria . So I don't think it can be determined.
On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote:
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote:
Find the next higher number in set of permutations of a given number
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks regards
Bhupendra
--
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] Amazon Interview Question
1. For first question trie of given word will be best option.
Space complexity O(total length of words) (worst case)
Time complexity O(T) . T length of input text (Newspaper)
2. consider it to be a 4 digit number ABCD . Find maximum Most
significant digit say it is C , and out of these nos find maximum value of
next digit say A and so on . Suppose Final no. is CADB
Now next highest permutation will be the no. just greater than this and
made of these digits . This is easy.
On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote:
Consider trees:
1 3
2 3 2
1
pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't
satisfy the criteria . So I don't think it can be determined.
On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote:
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote:
Find the next higher number in set of permutations of a given number
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks regards
Bhupendra
--
Thanks regards
Bhupendra
--
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] Amazon Interview Question
For question 5.
Even this doesn't seems right
Consider this scenario
Match b/w Winner
a vs b a
a vs c c
b vs c b
What will be order ?? acb or bca
On Wed, Jul 4, 2012 at 5:38 PM, Bhupendra Dubey bhupendra@gmail.comwrote:
1. For first question trie of given word will be best option.
Space complexity O(total length of words) (worst case)
Time complexity O(T) . T length of input text (Newspaper)
2. consider it to be a 4 digit number ABCD . Find maximum Most
significant digit say it is C , and out of these nos find maximum value of
next digit say A and so on . Suppose Final no. is CADB
Now next highest permutation will be the no. just greater than this and
made of these digits . This is easy.
On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey
bhupendra@gmail.comwrote:
Consider trees:
1 3
2 3 2
1
pre order traversal is same still (1 , 2 ,3) even though ist tree
doesn't satisfy the criteria . So I don't think it can be determined.
On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote:
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote:
Find the next higher number in set of permutations of a given number
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks regards
Bhupendra
--
Thanks regards
Bhupendra
--
Thanks regards
Bhupendra
--
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] Amazon Interview Question
1
2 3 is not a BST and its pre-order traversal is 1 2 3, pre
order of other is 3 2 1 .
On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote:
Consider trees:
1 3
2 3 2
1
pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't
satisfy the criteria . So I don't think it can be determined.
On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote:
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote:
Find the next higher number in set of permutations of a given number
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks regards
Bhupendra
--
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] Amazon Interview Question
Sorry i typed wrongly
tree is
2
1 3
preorder traversal is 123 and same for other tree as well. Please check !
On Wed, Jul 4, 2012 at 5:24 PM, a g ag20071...@gmail.com wrote:
1
2 3 is not a BST and its pre-order traversal is 1 2 3, pre
order of other is 3 2 1 .
On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey
bhupendra@gmail.comwrote:
Consider trees:
1 3
2 3 2
1
pre order traversal is same still (1 , 2 ,3) even though ist tree
doesn't satisfy the criteria . So I don't think it can be determined.
On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote:
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote:
Find the next higher number in set of permutations of a given number
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks regards
Bhupendra
--
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.
--
Thanks regards
Bhupendra
--
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] [amazon ] Finding Sub segment
http://www.leetcode.com/2010/11/finding-minimum-window-in-s-which.html On 6/25/12, Navin Kumar algorithm.i...@gmail.com wrote: please provide some good data structure to solve this problem: http://www.careercup.com/question?id=14062676 -- 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/-/WZiRDVnMKQYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Amazon Interview Question
example pls... On Thu, Jun 14, 2012 at 1:01 PM, Mohit Rathi mohit08...@iiitd.ac.in wrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1,* *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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. -- Utsav Sharma, NIT Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Interview Question
arr1 = [abc,xyz,lmn,def] arr2 = [3,6,2,8] if user enters xyz then 6 will be printed else if xyz doesn't exist in arr1 then ask for a number and add them in respective arrays(name in arr1 and number in arr2). Hope it helps On Thu, Jun 14, 2012 at 3:58 PM, utsav sharma utsav.sharm...@gmail.comwrote: example pls... On Thu, Jun 14, 2012 at 1:01 PM, Mohit Rathi mohit08...@iiitd.ac.inwrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1,* *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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. -- Utsav Sharma, NIT Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mohit Rathi 4th year, B.Tech (IT) IIIT-Delhi -- 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] Amazon Interview Question
it can be done using map in c++ On Thu, Jun 14, 2012 at 4:23 PM, Mohit Rathi mohit08...@iiitd.ac.in wrote: arr1 = [abc,xyz,lmn,def] arr2 = [3,6,2,8] if user enters xyz then 6 will be printed else if xyz doesn't exist in arr1 then ask for a number and add them in respective arrays(name in arr1 and number in arr2). Hope it helps On Thu, Jun 14, 2012 at 3:58 PM, utsav sharma utsav.sharm...@gmail.comwrote: example pls... On Thu, Jun 14, 2012 at 1:01 PM, Mohit Rathi mohit08...@iiitd.ac.inwrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1, * *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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. -- Utsav Sharma, NIT Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mohit Rathi 4th year, B.Tech (IT) IIIT-Delhi -- 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. -- Utsav Sharma, NIT Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Interview Question
Since the size of array is very less I think Hashmap is the best. Use name as the hash key and number as its value. On Thursday, June 14, 2012 6:46:34 PM UTC+5:30, utsav sharma wrote: it can be done using map in c++ On Thu, Jun 14, 2012 at 4:23 PM, Mohit Rathi mohit08...@iiitd.ac.inwrote: arr1 = [abc,xyz,lmn,def] arr2 = [3,6,2,8] if user enters xyz then 6 will be printed else if xyz doesn't exist in arr1 then ask for a number and add them in respective arrays(name in arr1 and number in arr2). Hope it helps On Thu, Jun 14, 2012 at 3:58 PM, utsav sharma utsav.sharm...@gmail.comwrote: example pls... On Thu, Jun 14, 2012 at 1:01 PM, Mohit Rathi mohit08...@iiitd.ac.inwrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1, * *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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. -- Utsav Sharma, NIT Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mohit Rathi 4th year, B.Tech (IT) IIIT-Delhi -- 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. -- Utsav Sharma, NIT Allahabad -- 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/-/wF1ZUNLZV4UJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Amazon Interview Question
Hashmap can be used for effective retreival.. On Thu, Jun 14, 2012 at 4:23 PM, Mohit Rathi mohit08...@iiitd.ac.in wrote: arr1 = [abc,xyz,lmn,def] arr2 = [3,6,2,8] if user enters xyz then 6 will be printed else if xyz doesn't exist in arr1 then ask for a number and add them in respective arrays(name in arr1 and number in arr2). Hope it helps On Thu, Jun 14, 2012 at 3:58 PM, utsav sharma utsav.sharm...@gmail.comwrote: example pls... On Thu, Jun 14, 2012 at 1:01 PM, Mohit Rathi mohit08...@iiitd.ac.inwrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1, * *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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. -- Utsav Sharma, NIT Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mohit Rathi 4th year, B.Tech (IT) IIIT-Delhi -- 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] [amazon]: dutch national flag algorithm
Let array contains 3 types of elements R,G,B. Now, if we place all the R elements from the left and B elements from the right then G elements will automatically be between the two. Thus we only have to keep indexes for the R and B elements inserted till now and update their positions accordingly to the current array element we are accessing. -- 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] [amazon]: dutch national flag algorithm
it can be solved in o(n) , keep one pointer at start and another pointer at the last , traverse the string if u get R swap it at the start position and then increament it , if u get B swap it with last pointer pointing to last position .and then decrement it . in this way all things will come in place . On Sat, Jun 9, 2012 at 11:36 PM, Navin Kumar algorithm.i...@gmail.comwrote: Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's. Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity. You can only traverse the array once. -- 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/-/54GHWSwHHw8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- 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] [amazon]: dutch national flag algorithm
Just use the counting sort and keep the counts in variables int R, int G, int B. Traverse the array and increment each respective variable (R or G or B) as soon as you encounter upon it. Once finished, you will have all the counts of frequencies stored in those three variables. Now, start traversing the array of counts (R, G, B) and fill the original array with data. Space O(1), time O(N) Rgds, Ashot Madatyan From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On Behalf Of Nishant Pandey Sent: Saturday, June 09, 2012 10:16 PM To: algogeeks@googlegroups.com Subject: Re: [algogeeks] [amazon]: dutch national flag algorithm it can be solved in o(n) , keep one pointer at start and another pointer at the last , traverse the string if u get R swap it at the start position and then increament it , if u get B swap it with last pointer pointing to last position .and then decrement it . in this way all things will come in place . On Sat, Jun 9, 2012 at 11:36 PM, Navin Kumar algorithm.i...@gmail.com wrote: Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's. Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity. You can only traverse the array once. -- 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/-/54GHWSwHHw8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Nishant Pandey | Specialist Tools Development | npandey mailto:gvib...@google.com @google.com | +91-9911258345 -- 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] [amazon]: dutch national flag algorithm
int low,mid,high;
low = mid = 0;
high = (int)(sizeof(arr)/sizeof(arr[0]))-1;
/*
According to Dutch national flag problem there are three types of
quantities in an array and we have to combine these elements together
but in a certain order
Let the elements in the array are in the form 0,1,2 then these elements in
an array should appear in order 0 then 1 then 2
( low to middle-1 ) - elements having 0 as a number
(middle to high-1 ) - 1 as a number
( high to arr - size) - 2 as a number
/
n = high;
for ( int i = 0; i = n; i++ ) {
if ( arr[mid] == 0 ) {
swap(arr[low],arr[mid]);
low++;
mid++;
}
else if ( arr[mid] == 2 ) {
swap(arr[mid],arr[high]);
high--;
}
else {
mid++;
}
}
--
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] [amazon]: dutch national flag algorithm
@Ashot: You can traverse array one time. In your case you are traversing
twice. First for counting occurrence of R , G and B then again traversing
for assigning values. But constraints is that you have to traverse only
once.
On Sun, Jun 10, 2012 at 5:13 PM, Akshat Sapra sapraaks...@gmail.com wrote:
int low,mid,high;
low = mid = 0;
high = (int)(sizeof(arr)/sizeof(arr[0]))-1;
/*
According to Dutch national flag problem there are three types of
quantities in an array and we have to combine these elements together
but in a certain order
Let the elements in the array are in the form 0,1,2 then these elements in
an array should appear in order 0 then 1 then 2
( low to middle-1 ) - elements having 0 as a number
(middle to high-1 ) - 1 as a number
( high to arr - size) - 2 as a number
/
n = high;
for ( int i = 0; i = n; i++ ) {
if ( arr[mid] == 0 ) {
swap(arr[low],arr[mid]);
low++;
mid++;
}
else if ( arr[mid] == 2 ) {
swap(arr[mid],arr[high]);
high--;
}
else {
mid++;
}
}
--
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] [amazon]: dutch national flag algorithm
sorry for the above post , there was careless mistake of mine. The code
will be
[code]
int low,mid,high;
low = mid = 0;
high = (int)(sizeof(arr)/sizeof(arr[0]))-1;
/*
According to Dutch national flag problem there are three types of
quantities in an array and we have to combine these elements together
but in a certain order
Let the elements in the array are in the form 0,1,2 then these elements in
an array should appear in order 0 then 1 then 2
( low to middle-1 ) - elements having 0 as a number
(middle to high-1 ) - 1 as a number
( high to arr - size) - 2 as a number
/
n = high;
while ( mid = high ) {
if ( arr[mid] == 0 ) {
swap(arr[low],arr[mid]);
low++;
mid++;
}
else if ( arr[mid] == 2 ) {
swap(arr[mid],arr[high]);
high--;
}
else {
mid++;
}
}
[/code]
--
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] Amazon : Find popular cost
Here, we can use hashmap and use an extra variable max_till_now that will
keep track of maximum element occured to us till now while updating.
Time complexity of solution will be O(n)
max_till_now = 0;
for ( int i = 0; i arr.size(); i++ ) {
hashmap[arr[i]] += 1;
if ( hashmap[arr[i]] max_till_now ) max_till_now =
hashmap[arr[i]];
}
print(max_till_now);
--
Akshat Sapra
Under Graduation(B.Tech)
IIIT-Allahabad(Amethi Campus)
*--*
sapraaks...@gmail.com
akshatsapr...@gmail.com
rit20009008@ rit20009...@gmail.comiiita.ac.in
--
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] [amazon]: dutch national flag algorithm
http://www.geeksforgeeks.org/archives/8133 -- 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] amazon interview questions
can be done with O(n^2) time complexity.. can it be done with O(n) complexity ??? On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote: given a string tell wether it is valid or not. string is valid if there is no substring which have the same substring following it. these strings are not valid:- stringstring,geek123123rt, abcadabcad,strngstingstrngsting -- 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] Amazon : exponentiation(x,n)
i assumed the numbers are positive..
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Fri, Jun 1, 2012 at 1:19 AM, Dave dave_and_da...@juno.com wrote:
@Amol: You've chosen to use -1 as an error return. But -1 is the correct
response if b = -1 and e is odd. Furthermore, isn't the inequality in the
if(prevresult) statement backwards. E.g., if b = 2 and e = 3, then the
code returns -1. Even reversing the inequality doesn't fix the problem when
b = -2 and e = 3, for which the correct response is -8, without overflow.
Dave
On Thursday, May 31, 2012 2:04:24 AM UTC-5, Amol Sharma wrote:
for checking overflow you can check the value after and before the
multiplication..if value after multiplication is less then there is
overflow for sure
now code will look like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
int prev;
while( e 1 )
{
prev=b;
b = (b * b);
if(bprev)
return -1; //OVERFLOW
e = 1;
if( e 1 )
{
prev=result;
result = (result * b);
if(prevresult)
return -1; //OVERFLOW
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 12:07 PM, Ashish Goel ashg...@gmail.com wrote:
the return type is int, hence when xpowern becomes bigger than INT_MAX,
it should throw an exception.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 11:59 AM, Amol Sharma amolsharm...@gmail.comwrote:
i didn't got your problem where is the overflow.. ??
btw i will do the same like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
while( e 1 )
{
b = ((long long int)b * b);
e = 1;
if( e 1 )
result = ((long long int)result * b);
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 9:54 AM, Ashish Goel ashg...@gmail.com wrote:
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be
written as x*xE when odd or xE otherwise.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+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 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 group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/UuSiE5US8SkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Amazon : exponentiation(x,n)
the return type is int, hence when xpowern becomes bigger than INT_MAX, it
should throw an exception.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 11:59 AM, Amol Sharma amolsharm...@gmail.comwrote:
i didn't got your problem where is the overflow.. ??
btw i will do the same like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
while( e 1 )
{
b = ((long long int)b * b);
e = 1;
if( e 1 )
result = ((long long int)result * b);
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 9:54 AM, Ashish Goel ashg...@gmail.com wrote:
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be written
as x*xE when odd or xE otherwise.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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] Amazon : exponentiation(x,n)
for checking overflow you can check the value after and before the
multiplication..if value after multiplication is less then there is
overflow for sure
now code will look like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
int prev;
while( e 1 )
{
prev=b;
b = (b * b);
if(bprev)
return -1; //OVERFLOW
e = 1;
if( e 1 )
{
prev=result;
result = (result * b);
if(prevresult)
return -1; //OVERFLOW
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 12:07 PM, Ashish Goel ashg...@gmail.com wrote:
the return type is int, hence when xpowern becomes bigger than INT_MAX, it
should throw an exception.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 11:59 AM, Amol Sharma amolsharm...@gmail.comwrote:
i didn't got your problem where is the overflow.. ??
btw i will do the same like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
while( e 1 )
{
b = ((long long int)b * b);
e = 1;
if( e 1 )
result = ((long long int)result * b);
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 9:54 AM, Ashish Goel ashg...@gmail.com wrote:
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be written
as x*xE when odd or xE otherwise.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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] Amazon : Find popular cost
here find popular post means to find most repeated costso we can use combination of max-heap and hashtable. hashtable is required to keep track for distinct cost. so if cost is not present in hashtable then add it to the hashtable and then add it to the Max-heap with counter value =1...then hepify. next time we find that cost in hashtable then we just need to increment counter of that cost in heap and thne hepify.At any point of time ...element at the top is the element with popular cost. On 5/31/12, g4ur4v gauravyadav1...@gmail.com wrote: How to find popular cost of the books, say book1 $10 book2 $20 book3 $40 book4 $50 book5 $10 book6 $20 http://www.careercup.com/question?id=13720752 -- 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] Amazon : exponentiation(x,n)
@Amol: You've chosen to use -1 as an error return. But -1 is the correct
response if b = -1 and e is odd. Furthermore, isn't the inequality in the
if(prevresult) statement backwards. E.g., if b = 2 and e = 3, then the
code returns -1. Even reversing the inequality doesn't fix the problem when
b = -2 and e = 3, for which the correct response is -8, without overflow.
Dave
On Thursday, May 31, 2012 2:04:24 AM UTC-5, Amol Sharma wrote:
for checking overflow you can check the value after and before the
multiplication..if value after multiplication is less then there is
overflow for sure
now code will look like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
int prev;
while( e 1 )
{
prev=b;
b = (b * b);
if(bprev)
return -1; //OVERFLOW
e = 1;
if( e 1 )
{
prev=result;
result = (result * b);
if(prevresult)
return -1; //OVERFLOW
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 12:07 PM, Ashish Goel ashg...@gmail.com wrote:
the return type is int, hence when xpowern becomes bigger than INT_MAX,
it should throw an exception.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 11:59 AM, Amol Sharma amolsharm...@gmail.comwrote:
i didn't got your problem where is the overflow.. ??
btw i will do the same like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
while( e 1 )
{
b = ((long long int)b * b);
e = 1;
if( e 1 )
result = ((long long int)result * b);
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 9:54 AM, Ashish Goel ashg...@gmail.com wrote:
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be written
as x*xE when odd or xE otherwise.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/UuSiE5US8SkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] amazon
here is a nice explanation for the problem
http://stackoverflow.com/questions/5131497/given-a-string-and-permutation-of-the-string-find-the-index-of-this-permuted-st
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Tue, May 29, 2012 at 3:37 PM, rahul patil
rahul.deshmukhpa...@gmail.comwrote:
Here is a constant time formula, LetterRankInSortedString is index of
alphabate if all characters in string are sorted lexographically starting
from 1.
Index = 0;
For(i=0; i LengthOfString; i++)
{
Letter = string[i];
Index + = (LetterRankInSortedString(Letter) - 1) *
(TotalPermutationsPossible/ (LengthOfString-i));
}
On Mon, May 28, 2012 at 12:26 AM, saurabh agrawal saurabh...@gmail.comwrote:
@atul:
i dont agree that baa should come once or twice is arguable.
It definitely have to be one time only..
we are supposed to get all lexicographic combinations (which implicitly
means no two strings will be same..)
On Mon, May 28, 2012 at 12:23 AM, atul anand atul.87fri...@gmail.comwrote:
@saurabh : i kinda assumed that string will not contain
repeated character. reason being if string has repeated character , say in
your case baa then baa will be repeated
twice hence it would be difficult to justify the output for this
input answer could be say 2 or 3 or both are correct.
On Mon, May 28, 2012 at 12:16 AM, saurabh agrawal
saurabh...@gmail.comwrote:
@atul:
if i have understood ..
ur solution will break when the string has repeated characters.
e.g. for baa
On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
sorry it was treeset Here is the code..
public class asd1 {
public static TreeSetString t = new TreeSetString();
public static int j = 0;
public static void main(String args[]) {
String s= edcba;
permute(, s);
System.out.println(t.toString());
int length=t.size();
String[] arr=(String[]) t.toArray(new String[length]);
for(int i =0;ilength;i++)
{
System.out.println(arr[i]);
if(arr[i].equals(s)){
System.out.println(i+1);
break;
}
}
}
public static void permute(String st, String chars) {
if (chars.length() = 1)
t.add(st+chars);
else
for (int i = 0; i chars.length(); i++) {
try {
String newString = chars.substring(0,
i)
+ chars.substring(i +
1);
permute(st + chars.charAt(i),
newString);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
Java has something call treeMap. it stores strings lexographically..
u can always do permutations and store them in a treeMap. and get the
rank
then... just the idea.. will post the solution once i am done.. what do u
guys think.abt the idea???
On Tue, May 22, 2012 at 9:46 AM, atul anand
atul.87fri...@gmail.comwrote:
actually we can think of above approach as follows :-
input : cabd
sort(input) = abcd
find first element of the input i.e 'c' in the sorted form i.e abcd
'c' is at found_index=3 ( index starting from 1 )
so permutaion stating from 'c' will come after
temp_rank=(found_index - start_index) * (total_lentgh - 1) !
now after temp_rank we know that permutation starting with 'c' will
come.
so to find out the exact index sort(input-1) i.e removing 1st
character ('c') from the input(cadb) we will get abd
now permute string abd and compare with input - 1 character i.e
(abd).
and keep inc the counter , if match is found then you have to add
this counter to temp_rank.
so for the input = cabd
temp_rank = (3 - 1) * (4-1) !
= 2 * 3!
= 12
counter found c = 1;
rank = 12 + c = 13
but i dont think this would be good solution as be have to permute
string and then compare at last...yes we did some optimization.
i was wondering if instead of permuting at the end , we can
calculate minimum number of swaps required to convert input - 1 to
sorted
input -1 (removing 1st character )using edit distance ...will this
work??
.
On Mon, May 21, 2012 at 11:33 PM, atul anand
atul.87fri...@gmail.com wrote:
consider string input = cabd
now sort this string = abcd
now search 1st character from original string(cabd) in sorted
string abcd... index found = 3 (index starting from 1 )
now you can arrange left elements from found index i.e index-1
elements in (index-1) ! and right elements from found index in
(lastIndex -
index)! before character 'c'
Re: [algogeeks] amazon
nice explanation..
On 30 May 2012 06:05, Amol Sharma amolsharm...@gmail.com wrote:
here is a nice explanation for the problem
http://stackoverflow.com/questions/5131497/given-a-string-and-permutation-of-the-string-find-the-index-of-this-permuted-st
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Tue, May 29, 2012 at 3:37 PM, rahul patil
rahul.deshmukhpa...@gmail.com wrote:
Here is a constant time formula, LetterRankInSortedString is index of
alphabate if all characters in string are sorted lexographically starting
from 1.
Index = 0;
For(i=0; i LengthOfString; i++)
{
Letter = string[i];
Index + = (LetterRankInSortedString(Letter) - 1) *
(TotalPermutationsPossible/ (LengthOfString-i));
}
On Mon, May 28, 2012 at 12:26 AM, saurabh agrawal
saurabh...@gmail.comwrote:
@atul:
i dont agree that baa should come once or twice is arguable.
It definitely have to be one time only..
we are supposed to get all lexicographic combinations (which implicitly
means no two strings will be same..)
On Mon, May 28, 2012 at 12:23 AM, atul anand atul.87fri...@gmail.comwrote:
@saurabh : i kinda assumed that string will not contain
repeated character. reason being if string has repeated character , say in
your case baa then baa will be repeated
twice hence it would be difficult to justify the output for this
input answer could be say 2 or 3 or both are correct.
On Mon, May 28, 2012 at 12:16 AM, saurabh agrawal saurabh...@gmail.com
wrote:
@atul:
if i have understood ..
ur solution will break when the string has repeated characters.
e.g. for baa
On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
sorry it was treeset Here is the code..
public class asd1 {
public static TreeSetString t = new TreeSetString();
public static int j = 0;
public static void main(String args[]) {
String s= edcba;
permute(, s);
System.out.println(t.toString());
int length=t.size();
String[] arr=(String[]) t.toArray(new String[length]);
for(int i =0;ilength;i++)
{
System.out.println(arr[i]);
if(arr[i].equals(s)){
System.out.println(i+1);
break;
}
}
}
public static void permute(String st, String chars) {
if (chars.length() = 1)
t.add(st+chars);
else
for (int i = 0; i chars.length(); i++) {
try {
String newString = chars.substring(0,
i)
+ chars.substring(i +
1);
permute(st + chars.charAt(i),
newString);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
Java has something call treeMap. it stores strings lexographically..
u can always do permutations and store them in a treeMap. and get the
rank
then... just the idea.. will post the solution once i am done.. what do
u
guys think.abt the idea???
On Tue, May 22, 2012 at 9:46 AM, atul anand atul.87fri...@gmail.com
wrote:
actually we can think of above approach as follows :-
input : cabd
sort(input) = abcd
find first element of the input i.e 'c' in the sorted form i.e abcd
'c' is at found_index=3 ( index starting from 1 )
so permutaion stating from 'c' will come after
temp_rank=(found_index - start_index) * (total_lentgh - 1) !
now after temp_rank we know that permutation starting with 'c' will
come.
so to find out the exact index sort(input-1) i.e removing 1st
character ('c') from the input(cadb) we will get abd
now permute string abd and compare with input - 1 character i.e
(abd).
and keep inc the counter , if match is found then you have to add
this counter to temp_rank.
so for the input = cabd
temp_rank = (3 - 1) * (4-1) !
= 2 * 3!
= 12
counter found c = 1;
rank = 12 + c = 13
but i dont think this would be good solution as be have to permute
string and then compare at last...yes we did some optimization.
i was wondering if instead of permuting at the end , we can
calculate minimum number of swaps required to convert input - 1 to
sorted
input -1 (removing 1st character )using edit distance ...will this
work??
.
On Mon, May 21, 2012 at 11:33 PM, atul anand
atul.87fri...@gmail.com wrote:
consider string input = cabd
now sort this string = abcd
now search 1st character from original string(cabd) in sorted
string abcd... index found = 3 (index starting from 1 )
now you can arrange left elements from found index i.e index-1
Re: [algogeeks] amazon
Here is a constant time formula, LetterRankInSortedString is index of
alphabate if all characters in string are sorted lexographically starting
from 1.
Index = 0;
For(i=0; i LengthOfString; i++)
{
Letter = string[i];
Index + = (LetterRankInSortedString(Letter) - 1) *
(TotalPermutationsPossible/ (LengthOfString-i));
}
On Mon, May 28, 2012 at 12:26 AM, saurabh agrawal saurabh...@gmail.comwrote:
@atul:
i dont agree that baa should come once or twice is arguable.
It definitely have to be one time only..
we are supposed to get all lexicographic combinations (which implicitly
means no two strings will be same..)
On Mon, May 28, 2012 at 12:23 AM, atul anand atul.87fri...@gmail.comwrote:
@saurabh : i kinda assumed that string will not contain
repeated character. reason being if string has repeated character , say in
your case baa then baa will be repeated
twice hence it would be difficult to justify the output for this
input answer could be say 2 or 3 or both are correct.
On Mon, May 28, 2012 at 12:16 AM, saurabh agrawal
saurabh...@gmail.comwrote:
@atul:
if i have understood ..
ur solution will break when the string has repeated characters.
e.g. for baa
On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
sorry it was treeset Here is the code..
public class asd1 {
public static TreeSetString t = new TreeSetString();
public static int j = 0;
public static void main(String args[]) {
String s= edcba;
permute(, s);
System.out.println(t.toString());
int length=t.size();
String[] arr=(String[]) t.toArray(new String[length]);
for(int i =0;ilength;i++)
{
System.out.println(arr[i]);
if(arr[i].equals(s)){
System.out.println(i+1);
break;
}
}
}
public static void permute(String st, String chars) {
if (chars.length() = 1)
t.add(st+chars);
else
for (int i = 0; i chars.length(); i++) {
try {
String newString = chars.substring(0, i)
+ chars.substring(i +
1);
permute(st + chars.charAt(i),
newString);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
Java has something call treeMap. it stores strings lexographically.. u
can always do permutations and store them in a treeMap. and get the rank
then... just the idea.. will post the solution once i am done.. what do u
guys think.abt the idea???
On Tue, May 22, 2012 at 9:46 AM, atul anand
atul.87fri...@gmail.comwrote:
actually we can think of above approach as follows :-
input : cabd
sort(input) = abcd
find first element of the input i.e 'c' in the sorted form i.e abcd
'c' is at found_index=3 ( index starting from 1 )
so permutaion stating from 'c' will come after temp_rank=(found_index
- start_index) * (total_lentgh - 1) !
now after temp_rank we know that permutation starting with 'c' will
come.
so to find out the exact index sort(input-1) i.e removing 1st
character ('c') from the input(cadb) we will get abd
now permute string abd and compare with input - 1 character i.e
(abd).
and keep inc the counter , if match is found then you have to add
this counter to temp_rank.
so for the input = cabd
temp_rank = (3 - 1) * (4-1) !
= 2 * 3!
= 12
counter found c = 1;
rank = 12 + c = 13
but i dont think this would be good solution as be have to permute
string and then compare at last...yes we did some optimization.
i was wondering if instead of permuting at the end , we can calculate
minimum number of swaps required to convert input - 1 to sorted input -1
(removing 1st character )using edit distance ...will this work?? .
On Mon, May 21, 2012 at 11:33 PM, atul anand atul.87fri...@gmail.com
wrote:
consider string input = cabd
now sort this string = abcd
now search 1st character from original string(cabd) in sorted
string abcd... index found = 3 (index starting from 1 )
now you can arrange left elements from found index i.e index-1
elements in (index-1) ! and right elements from found index in
(lastIndex -
index)! before character 'c' occurs at index 0. similarly find for other
characters and at the end subtract it from n! (n = length of the string
)
to find rank
On Mon, May 21, 2012 at 11:02 PM, rahul venkat
rahul911...@gmail.com wrote:
Given a string. Tell its rank among all its permutations sorted
lexicographically.
--
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] amazon
@atul:
if i have understood ..
ur solution will break when the string has repeated characters.
e.g. for baa
On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
sorry it was treeset Here is the code..
public class asd1 {
public static TreeSetString t = new TreeSetString();
public static int j = 0;
public static void main(String args[]) {
String s= edcba;
permute(, s);
System.out.println(t.toString());
int length=t.size();
String[] arr=(String[]) t.toArray(new String[length]);
for(int i =0;ilength;i++)
{
System.out.println(arr[i]);
if(arr[i].equals(s)){
System.out.println(i+1);
break;
}
}
}
public static void permute(String st, String chars) {
if (chars.length() = 1)
t.add(st+chars);
else
for (int i = 0; i chars.length(); i++) {
try {
String newString = chars.substring(0, i)
+ chars.substring(i + 1);
permute(st + chars.charAt(i), newString);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
Java has something call treeMap. it stores strings lexographically.. u
can always do permutations and store them in a treeMap. and get the rank
then... just the idea.. will post the solution once i am done.. what do u
guys think.abt the idea???
On Tue, May 22, 2012 at 9:46 AM, atul anand atul.87fri...@gmail.comwrote:
actually we can think of above approach as follows :-
input : cabd
sort(input) = abcd
find first element of the input i.e 'c' in the sorted form i.e abcd
'c' is at found_index=3 ( index starting from 1 )
so permutaion stating from 'c' will come after temp_rank=(found_index -
start_index) * (total_lentgh - 1) !
now after temp_rank we know that permutation starting with 'c' will come.
so to find out the exact index sort(input-1) i.e removing 1st character
('c') from the input(cadb) we will get abd
now permute string abd and compare with input - 1 character i.e (abd).
and keep inc the counter , if match is found then you have to add this
counter to temp_rank.
so for the input = cabd
temp_rank = (3 - 1) * (4-1) !
= 2 * 3!
= 12
counter found c = 1;
rank = 12 + c = 13
but i dont think this would be good solution as be have to permute
string and then compare at last...yes we did some optimization.
i was wondering if instead of permuting at the end , we can calculate
minimum number of swaps required to convert input - 1 to sorted input -1
(removing 1st character )using edit distance ...will this work?? .
On Mon, May 21, 2012 at 11:33 PM, atul anand atul.87fri...@gmail.comwrote:
consider string input = cabd
now sort this string = abcd
now search 1st character from original string(cabd) in sorted string
abcd... index found = 3 (index starting from 1 )
now you can arrange left elements from found index i.e index-1 elements
in (index-1) ! and right elements from found index in (lastIndex - index)!
before character 'c' occurs at index 0. similarly find for other characters
and at the end subtract it from n! (n = length of the string ) to find rank
On Mon, May 21, 2012 at 11:02 PM, rahul venkat
rahul911...@gmail.comwrote:
Given a string. Tell its rank among all its permutations sorted
lexicographically.
--
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
Re: [algogeeks] amazon
@saurabh : i kinda assumed that string will not contain repeated character.
reason being if string has repeated character , say in your case baa then
baa will be repeated
twice hence it would be difficult to justify the output for this input
answer could be say 2 or 3 or both are correct.
On Mon, May 28, 2012 at 12:16 AM, saurabh agrawal saurabh...@gmail.comwrote:
@atul:
if i have understood ..
ur solution will break when the string has repeated characters.
e.g. for baa
On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
sorry it was treeset Here is the code..
public class asd1 {
public static TreeSetString t = new TreeSetString();
public static int j = 0;
public static void main(String args[]) {
String s= edcba;
permute(, s);
System.out.println(t.toString());
int length=t.size();
String[] arr=(String[]) t.toArray(new String[length]);
for(int i =0;ilength;i++)
{
System.out.println(arr[i]);
if(arr[i].equals(s)){
System.out.println(i+1);
break;
}
}
}
public static void permute(String st, String chars) {
if (chars.length() = 1)
t.add(st+chars);
else
for (int i = 0; i chars.length(); i++) {
try {
String newString = chars.substring(0, i)
+ chars.substring(i + 1);
permute(st + chars.charAt(i), newString);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
Java has something call treeMap. it stores strings lexographically.. u
can always do permutations and store them in a treeMap. and get the rank
then... just the idea.. will post the solution once i am done.. what do u
guys think.abt the idea???
On Tue, May 22, 2012 at 9:46 AM, atul anand atul.87fri...@gmail.comwrote:
actually we can think of above approach as follows :-
input : cabd
sort(input) = abcd
find first element of the input i.e 'c' in the sorted form i.e abcd
'c' is at found_index=3 ( index starting from 1 )
so permutaion stating from 'c' will come after temp_rank=(found_index -
start_index) * (total_lentgh - 1) !
now after temp_rank we know that permutation starting with 'c' will
come.
so to find out the exact index sort(input-1) i.e removing 1st
character ('c') from the input(cadb) we will get abd
now permute string abd and compare with input - 1 character i.e (abd).
and keep inc the counter , if match is found then you have to add this
counter to temp_rank.
so for the input = cabd
temp_rank = (3 - 1) * (4-1) !
= 2 * 3!
= 12
counter found c = 1;
rank = 12 + c = 13
but i dont think this would be good solution as be have to permute
string and then compare at last...yes we did some optimization.
i was wondering if instead of permuting at the end , we can calculate
minimum number of swaps required to convert input - 1 to sorted input -1
(removing 1st character )using edit distance ...will this work?? .
On Mon, May 21, 2012 at 11:33 PM, atul anand
atul.87fri...@gmail.comwrote:
consider string input = cabd
now sort this string = abcd
now search 1st character from original string(cabd) in sorted string
abcd... index found = 3 (index starting from 1 )
now you can arrange left elements from found index i.e index-1
elements in (index-1) ! and right elements from found index in (lastIndex
-
index)! before character 'c' occurs at index 0. similarly find for other
characters and at the end subtract it from n! (n = length of the string )
to find rank
On Mon, May 21, 2012 at 11:02 PM, rahul venkat
rahul911...@gmail.comwrote:
Given a string. Tell its rank among all its permutations sorted
lexicographically.
--
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
Re: [algogeeks] amazon
@atul:
i dont agree that baa should come once or twice is arguable.
It definitely have to be one time only..
we are supposed to get all lexicographic combinations (which implicitly
means no two strings will be same..)
On Mon, May 28, 2012 at 12:23 AM, atul anand atul.87fri...@gmail.comwrote:
@saurabh : i kinda assumed that string will not contain
repeated character. reason being if string has repeated character , say in
your case baa then baa will be repeated
twice hence it would be difficult to justify the output for this input
answer could be say 2 or 3 or both are correct.
On Mon, May 28, 2012 at 12:16 AM, saurabh agrawal saurabh...@gmail.comwrote:
@atul:
if i have understood ..
ur solution will break when the string has repeated characters.
e.g. for baa
On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
sorry it was treeset Here is the code..
public class asd1 {
public static TreeSetString t = new TreeSetString();
public static int j = 0;
public static void main(String args[]) {
String s= edcba;
permute(, s);
System.out.println(t.toString());
int length=t.size();
String[] arr=(String[]) t.toArray(new String[length]);
for(int i =0;ilength;i++)
{
System.out.println(arr[i]);
if(arr[i].equals(s)){
System.out.println(i+1);
break;
}
}
}
public static void permute(String st, String chars) {
if (chars.length() = 1)
t.add(st+chars);
else
for (int i = 0; i chars.length(); i++) {
try {
String newString = chars.substring(0, i)
+ chars.substring(i + 1);
permute(st + chars.charAt(i), newString);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
Java has something call treeMap. it stores strings lexographically.. u
can always do permutations and store them in a treeMap. and get the rank
then... just the idea.. will post the solution once i am done.. what do u
guys think.abt the idea???
On Tue, May 22, 2012 at 9:46 AM, atul anand atul.87fri...@gmail.comwrote:
actually we can think of above approach as follows :-
input : cabd
sort(input) = abcd
find first element of the input i.e 'c' in the sorted form i.e abcd
'c' is at found_index=3 ( index starting from 1 )
so permutaion stating from 'c' will come after temp_rank=(found_index
- start_index) * (total_lentgh - 1) !
now after temp_rank we know that permutation starting with 'c' will
come.
so to find out the exact index sort(input-1) i.e removing 1st
character ('c') from the input(cadb) we will get abd
now permute string abd and compare with input - 1 character i.e
(abd).
and keep inc the counter , if match is found then you have to add this
counter to temp_rank.
so for the input = cabd
temp_rank = (3 - 1) * (4-1) !
= 2 * 3!
= 12
counter found c = 1;
rank = 12 + c = 13
but i dont think this would be good solution as be have to permute
string and then compare at last...yes we did some optimization.
i was wondering if instead of permuting at the end , we can calculate
minimum number of swaps required to convert input - 1 to sorted input -1
(removing 1st character )using edit distance ...will this work?? .
On Mon, May 21, 2012 at 11:33 PM, atul anand
atul.87fri...@gmail.comwrote:
consider string input = cabd
now sort this string = abcd
now search 1st character from original string(cabd) in sorted string
abcd... index found = 3 (index starting from 1 )
now you can arrange left elements from found index i.e index-1
elements in (index-1) ! and right elements from found index in
(lastIndex -
index)! before character 'c' occurs at index 0. similarly find for other
characters and at the end subtract it from n! (n = length of the string )
to find rank
On Mon, May 21, 2012 at 11:02 PM, rahul venkat rahul911...@gmail.com
wrote:
Given a string. Tell its rank among all its permutations sorted
lexicographically.
--
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
Re: [algogeeks] Amazon Q: Implement an algorithm to do wild card string matching
match(*input , *pattern)
if(*pat == 0)
return true;
if('?' == *pat)
return match(input+1,pat+1) || match(input,pat+1)
if('*' == *pat)
return match(input+1,pat) || match(input,pat+1)
if(*text == *pat)
return match(input+1,pat+1)
return 0;
take care of base cases..
On Sat, May 26, 2012 at 2:16 PM, Ashish Goel ashg...@gmail.com wrote:
Implement an algorithm to do wild card string matching
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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] Amazon Q: Implement an algorithm to do wild card string matching
typo error above resolved :-
match(*input , *pattern)
if(*pat == 0)
return true;
if('?' == *pat)
return match(input+1,pat+1) || match(input,pat+1)
if('*' == *pat)
return match(input+1,pat) || match(input,pat+1)
if(*input == *pat)
return match(input+1,pat+1)
return 0;
On Sat, May 26, 2012 at 2:39 PM, atul anand atul.87fri...@gmail.com wrote:
match(*input , *pattern)
if(*pat == 0)
return true;
if('?' == *pat)
return match(input+1,pat+1) || match(input,pat+1)
if('*' == *pat)
return match(input+1,pat) || match(input,pat+1)
if(*text == *pat)
return match(input+1,pat+1)
return 0;
take care of base cases..
On Sat, May 26, 2012 at 2:16 PM, Ashish Goel ashg...@gmail.com wrote:
Implement an algorithm to do wild card string matching
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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] Amazon interview question
array of bits? if the current integer is present set the bit if else make it zero, searching, insertion and deletion all in O(1) time. On Thu, May 24, 2012 at 4:15 PM, rishabh shukla rockrishabh.mn...@gmail.com wrote: Suggest a data structure for storing million trillion numbers efficiently in very less space. Means space complexity should be as less as possible -- Rishabh Shukla B.Tech Final Year MNNIT Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] Amazon interview question
What is the purpose of these numbers, if the idea is to manage a free pool, then probably 10-ary-tree is the solution. May be Tiger Tree Hash a better answer where it is tree to say level 7 and then for rest three digits it become hash table. This way, the chunks can be kept on different machines too. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, May 24, 2012 at 4:51 PM, Aman Raj amanka...@gmail.com wrote: array of bits? if the current integer is present set the bit if else make it zero, searching, insertion and deletion all in O(1) time. On Thu, May 24, 2012 at 4:15 PM, rishabh shukla rockrishabh.mn...@gmail.com wrote: Suggest a data structure for storing million trillion numbers efficiently in very less space. Means space complexity should be as less as possible -- Rishabh Shukla B.Tech Final Year MNNIT Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.
