[algogeeks] Amazon Job openings

[immanuel kingston]

Hi all,

I am a hiring manager at Amazon. We are hiring for SDE and Applied Science
roles in my team. Please send a short note about yourself, the role you
wish to apply for and your updated CV.

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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CACOkDGfuoUubqU6TKrb%3DehEA6sHMwE8S-_a_7Qj2S8V7iz9HVw%40mail.gmail.com.

[algogeeks] amazon interview

[Deependra pratap singh]

Hi all,
I've interviews for SDE-1 in amazon bangalore  this weekend. Can any one
tell me the recent questions they are focusing on ? or if anyone have the
recent experience with them please share it.

Thanks

-- 
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 Hiring SDE-Is, SDE-IIs, SDM and QAE-1

[Abhijeet Srivastva]

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

[algogeeks] Amazon Hiring SDE-Is, SDE-IIs, SDM and QAE-1

[immanuel kingston]

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.

Re: [algogeeks] Amazon problem

[bharat b]

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 wrote:

> sorry.. pls ignore the above post.. that doesn't work..
>
>
> On Wed, Jun 19, 2013 at 10:5
> 5 PM, bharat b  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  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

[bharat b]

sorry.. pls ignore the above post.. that doesn't work..


On Wed, Jun 19, 2013 at 10:5
5 PM, bharat b  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  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

[bharat b]

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  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.

[algogeeks] Amazon problem

[Jai Shri Ram]

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.

Re: [algogeeks] Amazon interview Questions

[sourabh jain]

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  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 wrote:
>
>> Can u clear Round3 --- Qstn-3. the language is not cleared
>>
>>
>> On Wed, Jun 5, 2013 at 1:52 PM, sourabh jain  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 (i>>  if(ar[i]+ar[j]==k) {printpairs; i++; j++;}
>>>  else if(ar[i])+ar[j] >>  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, *$*  wrote:
>>>
 these are for which position? and experience?


 On Thu, May 2, 2013 at 9:27 PM, Guneesh  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.

Re: [algogeeks] Amazon interview Questions

[sourabh jain]

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  wrote:

> Can u clear Round3 --- Qstn-3. the language is not cleared
>
>
> On Wed, Jun 5, 2013 at 1:52 PM, sourabh jain  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 (i>  if(ar[i]+ar[j]==k) {printpairs; i++; j++;}
>>  else if(ar[i])+ar[j] >  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, *$*  wrote:
>>
>>> these are for which position? and experience?
>>>
>>>
>>> On Thu, May 2, 2013 at 9:27 PM, Guneesh  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)ispre

Re: [algogeeks] Amazon interview Questions

[Ravi Ranjan]

Can u clear Round3 --- Qstn-3. the language is not cleared


On Wed, Jun 5, 2013 at 1:52 PM, sourabh jain  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 (i  if(ar[i]+ar[j]==k) {printpairs; i++; j++;}
>  else if(ar[i])+ar[j]   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, *$*  wrote:
>
>> these are for which position? and experience?
>>
>>
>> On Thu, May 2, 2013 at 9:27 PM, Guneesh  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
>>
>> --

Re: [algogeeks] Amazon interview Questions

[sourabh jain]

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 (ik) 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, *$*  wrote:

> these are for which position? and experience?
>
>
> On Thu, May 2, 2013 at 9:27 PM, Guneesh  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 stop rece

Re: [algogeeks] Amazon interview Questions

[*$*]

these are for which position? and experience?


On Thu, May 2, 2013 at 9:27 PM, Guneesh  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 interview Questions

[bharat b]

Can any one give some points on Round 3 : 1st and 3rd question ?

On Thu, May 2, 2013 at 9:27 PM, Guneesh  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 f2f round question ..

[Avi Dullu]

My bad, I wrote "out degree" where I should have written "in degree".
My proposal:
Topological Sort  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  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  wrote:
>
>>
>> On Sat, May 11, 2013 at 10:29 AM, Aman Jain  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  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 ..

[MAC]

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  wrote:

>
> On Sat, May 11, 2013 at 10:29 AM, Aman Jain  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  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 ..

[Avi Dullu]

On Sat, May 11, 2013 at 10:29 AM, Aman Jain  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  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 ..

[Karthikeyan V.B]

@atul anand :  got it thanks for pointing it out



On Mon, May 13, 2013 at 12:19 AM, atul anand wrote:

> @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  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 
> > 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  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 
> >> 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  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 ..

[atul anand]

@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  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 
> 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  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 
>> 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  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 ..

[Karthikeyan V.B]

@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  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  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 
> 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  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 ..

[atul anand]

@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  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  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  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 ..

[Karthikeyan V.B]

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  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  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 f2f round question ..

[Aman Jain]

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  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.

[algogeeks] amazon f2f round question ..

[MAC]

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.

[algogeeks] Amazon interview Questions

[Guneesh]

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.

Re: [algogeeks] Amazon interview question

[Richard Reed]

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 wrote:

>  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;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.

[algogeeks] Amazon interview question

[rahul sharma]

 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;ihttps://groups.google.com/groups/opt_out.

Re: [algogeeks] Amazon interview Question

[Pralay Biswas]

@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  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  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 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 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 
> 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
> >  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 

Re: [algogeeks] Amazon interview Question

[rashmi i]

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  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 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  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 
 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
 >  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] Amazon Interview Questions

[Pratik Mehta]

Hi All,
I need ur help in solving few questions.

Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC BEHIND 
IT and it's DEEP EXPLANATION IF POSSIBLE?*


*
*

*a. Kadane’s Algo.*

*
*

*b. Linked-list intersection point.*

*
[A tree with only parent pointer, how to find LCA?]
*

*

*

*
c. Design a stack which can perform findMax in O(1).
*

*

*

*d. Set of stocks for each day have been given. Need to find the days on 
which I buy and sell share to earn max profit, alongwith finding the max 
profit.*


*
e. Find top k searched elements from a continuous stream of data.
*

*

*

*f. Given a linked-list and 2 integers k & m. Reverse the linked-list till 
k elements and then traverse till m elements and repeat.*

*Write production quality code.*

*
*

*g. An array of elements have been given. Find for each element, first max 
element to its right.*

*
*

*h. Boundary traversal of a tree. Write the code.*


Please help me out...

Thanks in advance...

Thanks & Regards,
Pratik Mayur Mehta.

-- 
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 jain]

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 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  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  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
>>> >  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

[Sadhan Sood]

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  pair of  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  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  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
>>  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  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
>>> >  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

[Pralay Biswas]

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 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  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  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
>>> >  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

[bharat b]

@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  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  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
>> >  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

[sourabh jain]

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  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
> >  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

[kumar ankit]

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  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
> >  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

[Nishant Pandey]

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  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  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
>> >  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

[Pralay Biswas]

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 wrote:

> 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  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
>> >  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

[Pralay Biswas]

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  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
> >  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]

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  >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 > 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 
>>> > 
>>> 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
>>> > > 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 .
>>> >> 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 .
>>> > 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 .
>>> 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 .
>> 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...@googl

Re: [algogeeks] Amazon interview Question

[bharat b]

@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  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  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
>> >  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

[Srikar]

*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  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
> >  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 singh gaur]

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  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
>  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.

Re: [algogeeks] Amazon interview Question

[kumar ankit]

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

[Guneesh Paul Singh]

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

[Guneesh Paul Singh]

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.

[algogeeks] Amazon interview Question

[navneet singh gaur]

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.

Re: [algogeeks] Amazon Onsite

[bharat b]

can any one give me anexample which takes worst case of this problem

On Mon, Mar 26, 2012 at 1:56 PM, Arpit Sood  wrote:

> @ankur +1
> correct algo, can be done in just one pass.
>
> On Mon, Oct 24, 2011 at 11:03 PM, Ankur Garg  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 
>>> wrote:
>>>
 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  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.
>

[algogeeks] Amazon Job openings

[sahil madaan]

Hi all,

There are multiple openings for SDE1 and SDE2 for Amazon hyderabad and
Bangalore location. Interested candidates please send your resume to
sahilmadaann...@gmail.com

Thanks
sahil

-- 

Re: [algogeeks] Amazon Dynamic Programming problem

[siva]

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  >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

[vamshi palakurti]

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 wrote:

>
> how is winning going to decided
>
> On Sat, Jan 12, 2013 at 6:33 PM, siva  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

[Raunak Gupta]

how is winning going to decided

On Sat, Jan 12, 2013 at 6:33 PM, siva  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) ?
>
> --
>
>
>

-- 

[algogeeks] Amazon Dynamic Programming problem

[siva]

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

[Anurag Gupta]

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.

-- 

[algogeeks] Amazon interview Question

[tapan rathi]

 For a given number, find the next greatest number which is just greater 
than previous one and made up of same digits. 

-- 

Re: [algogeeks] amazon question

[bharat b]

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 wrote:

> 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  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

[bharat b]

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  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.

[algogeeks] amazon question

[saket]

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.

Re: [algogeeks] amazon Interview

[pankajsingh]

@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 Interview

[atul anand]

but how to solve this problem for with n-dimension ??

On Sun, Aug 26, 2012 at 6:47 PM, atul anand  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  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 >
> 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
> >> > >
> >>
> >> > wrote:
> >> >
> >> >> its a LIS problem.
> >> >>
> >> >> need to think for n-dimension...
> >> >>
> >> >> On 8/26/12, Ravi Ranjan > 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.com.
> >>
> >> >> > To unsubscribe from this group, send email to
> >> >> > algogeeks+...@googlegroups.com .
> >> >> > For more options, visit this group at
> >> >> > http://groups.google.com/group/algogeeks?hl=en.
> >> >> >
> >> >> >
> >> >>
> >> >> --
> >> >> You received this message because you are subscribed to the Google
> >> Groups
> >> >> "Algorithm Geeks" group.
> >> >> To post to this group, send email to
> >> >> algo...@googlegroups.com.
> >>
> >> >> To unsubscribe from this group, send email to
> >> >> algogeeks+...@googlegroups.com .
> >> >> For more options, visit this group at
> >> >> http://groups.google.com/group/algogeeks?hl=en.
> >> >>
> >> >>
> >> >
> >> >
> >> > --
> >> >
> >> > --
> >> >
> >> > ‘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.com.
> >>
> >> > To unsubscribe from this group, send email to
> >> > algogeeks+...@googlegroups.com .
> >> > For more options, visit this group at
> >> > http://groups.google.com/group/algogeeks?hl=en.
> >> >
> >> >
> >>
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To 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

[Mind Boggler]

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  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

[atul anand]

@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  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 > 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
>> > >
>>
>> > wrote:
>> >
>> >> its a LIS problem.
>> >>
>> >> need to think for n-dimension...
>> >>
>> >> On 8/26/12, Ravi Ranjan > 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.com.
>>
>> >> > To unsubscribe from this group, send email to
>> >> > algogeeks+...@googlegroups.com .
>> >> > For more options, visit this group at
>> >> > http://groups.google.com/group/algogeeks?hl=en.
>> >> >
>> >> >
>> >>
>> >> --
>> >> You received this message because you are subscribed to the Google
>> Groups
>> >> "Algorithm Geeks" group.
>> >> To post to this group, send email to
>> >> algo...@googlegroups.com.
>>
>> >> To unsubscribe from this group, send email to
>> >> algogeeks+...@googlegroups.com .
>> >> For more options, visit this group at
>> >> http://groups.google.com/group/algogeeks?hl=en.
>> >>
>> >>
>> >
>> >
>> > --
>> >
>> > --
>> >
>> > ‘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.com.
>>
>> > To unsubscribe from this group, send email to
>> > algogeeks+...@googlegroups.com .
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>> >
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To 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 Interview

[Dave]

@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 > 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 
> > > 
>
> > wrote: 
> > 
> >> its a LIS problem. 
> >> 
> >> need to think for n-dimension... 
> >> 
> >> On 8/26/12, Ravi Ranjan > 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.com. 
>
> >> > To unsubscribe from this group, send email to 
> >> > algogeeks+...@googlegroups.com . 
> >> > For more options, visit this group at 
> >> > http://groups.google.com/group/algogeeks?hl=en. 
> >> > 
> >> > 
> >> 
> >> -- 
> >> You received this message because you are subscribed to the Google 
> Groups 
> >> "Algorithm Geeks" group. 
> >> To post to this group, send email to 
> >> algo...@googlegroups.com. 
>
> >> To unsubscribe from this group, send email to 
> >> algogeeks+...@googlegroups.com . 
> >> For more options, visit this group at 
> >> http://groups.google.com/group/algogeeks?hl=en. 
> >> 
> >> 
> > 
> > 
> > -- 
> > 
> > -- 
> > 
> > ‘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.com. 
>
> > To unsubscribe from this group, send email to 
> > algogeeks+...@googlegroups.com . 
> > For more options, visit this group at 
> > http://groups.google.com/group/algogeeks?hl=en. 
> > 
> > 
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To 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

[atul anand]

@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  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 
> wrote:
>
>> its a LIS problem.
>>
>> need to think for n-dimension...
>>
>> On 8/26/12, Ravi Ranjan  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

[Kailash Bagaria]

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  wrote:

> its a LIS problem.
>
> need to think for n-dimension...
>
> On 8/26/12, Ravi Ranjan  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

[atul anand]

its a LIS problem.

need to think for n-dimension...

On 8/26/12, Ravi Ranjan  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 Q

[Navin Kumar]

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  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.

[algogeeks] amazon Interview

[Ravi Ranjan]

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.

[algogeeks] Amazon Q

[Ashish Goel]

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.

[algogeeks] Amazon Online Test

[nick]

Hi All,

Has anyone appeared for the online test of amazon recently??
 if(yes){
 Please share with us :)
 }
 

-- 
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/-/xuD9M8vmV74J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] AMAZON: given col id, print col name in excel

[Ashish Goel]

Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab,
aac aax, aaz, aba, abc... (Its same as excel column names). Given an
integer (n), generate n-th string from the above sequence.

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.

Re: [algogeeks] amazon online test question

[vaibhav shukla]

yeah... i got that... just shared with algogeeks ;)
questions were somewhat easy

On Sun, Aug 5, 2012 at 7:25 PM, Prem Krishna Chettri wrote:

> 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 wrote:
>
>> 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 online test question

[Prem Krishna Chettri]

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 wrote:

> 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.

[algogeeks] amazon online test question

[vaibhav shukla]

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.

Re: [algogeeks] Amazon CodeSprint

[Prem Krishna Chettri]

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  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.

[algogeeks] Amazon CodeSprint

[Navin Kumar]

 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.

Re: [algogeeks] [Amazon]

[SHOBHIT GUPTA]

Sorry , I've tried but BS will not work here .

On Tue, Jul 24, 2012 at 9:17 PM, algo bard  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 
>>>
>>> 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 .
 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.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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]

@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 
>>
>> 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 > > 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 .
>>> 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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Amazon support engineer

[rahul sharma]

Guys i am having amazon support engg. test tonyt...90 min 27 questions
mcq...plz tell how to prepare and wats dis profyl???reply asap..and sory
for posting it in algogeeks as i need quick response.waiting for +ve
response soon...
thnx

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] [amazon]: calculating resistance

[Navin Kumar]

Given a Circuit (with resistors), we need to calculate the total 
resistance. Input will be like AB-5ohm, BC-6ohm, BC-10ohm, BC-20 ohm, CD-5 
ohm. BC has been repeated twice implying they are in parallel. "Write a 
program by implementing efficient data structure for storing and 
calculating the total 
resistance."

-- 
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/-/q1AxlJQBmGEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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]

[neelpulse(Jadavpur University)]

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 
> 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+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]

[SHOBHIT GUPTA]

@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  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 
> 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+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]

[algo bard]

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 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+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] [Amazon]

[Sakshi Agrawal]

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.

[algogeeks] [Amazon] : constructing fully binary tree

[Navin Kumar]

Given Preorder and postorder traversals of a tree. Device an algorithm to 
constuct a fully binary tree from these traversals.

-- 
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/-/fx4LY5IUFT8J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Amazon Interview Question

[algo bard]

Given an array of integers where some numbers repeat once, some numbers
repeat twice and only one number repeats thrice, how do you find the number
that gets repeated 3 times?

Does this problem have an O(n) time and O(1) space solution?
No hashmaps please!

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[Decipher]

@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
>
>
> vector prefix;
> prefix[0]=NULL;
> prefixCount =1;
> for (int i=0;i   for (int j=0;j for (int k=0; 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  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.
>> vector prefix;
>> prefix[0]=NULL;
>> prefixCount =1;
>> for (int i=0;i>   for (int j=0;j> for (int k=0; 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  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

[Bhupendra Dubey]

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  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 
> wrote:
>
>> 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  wrote:
>>
>>> Q4
>>>
>>>
>>> vector prefix;
>>> prefix[0]=NULL;
>>> prefixCount =1;
>>> for (int i=0;i>>   for (int j=0;j>> for (int k=0; 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  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.
 vector prefix;
 prefix[0]=NULL;
 prefixCount =1;
 for (int i=0;i>>>   for (int j=0;j>>> for (int k=0; 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 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.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[a g]

 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 wrote:

> 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  wrote:
>
>> Q4
>>
>>
>> vector prefix;
>> prefix[0]=NULL;
>> prefixCount =1;
>> for (int i=0;i>   for (int j=0;j> for (int k=0; 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  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.
>>> vector prefix;
>>> prefix[0]=NULL;
>>> prefixCount =1;
>>> for (int i=0;i>>   for (int j=0;j>> for (int k=0; 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 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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[Bhupendra Dubey]

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 wrote:

> 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 
> wrote:
>
>> 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  wrote:
>>
>>> Q4
>>>
>>>
>>> vector prefix;
>>> prefix[0]=NULL;
>>> prefixCount =1;
>>> for (int i=0;i>>   for (int j=0;j>> for (int k=0; 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  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.
 vector prefix;
 prefix[0]=NULL;
 prefixCount =1;
 for (int i=0;i>>>   for (int j=0;j>>> for (int k=0; 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 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
>>
>>
>>
>
>
> --
> 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

[Bhupendra Dubey]

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 wrote:

> 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  wrote:
>
>> Q4
>>
>>
>> vector prefix;
>> prefix[0]=NULL;
>> prefixCount =1;
>> for (int i=0;i>   for (int j=0;j> for (int k=0; 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  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.
>>> vector prefix;
>>> prefix[0]=NULL;
>>> prefixCount =1;
>>> for (int i=0;i>>   for (int j=0;j>> for (int k=0; 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 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
>
>
>


-- 
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

[Bhupendra Dubey]

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  wrote:

> Q4
>
>
> vector prefix;
> prefix[0]=NULL;
> prefixCount =1;
> for (int i=0;i   for (int j=0;j for (int k=0; 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  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.
>> vector prefix;
>> prefix[0]=NULL;
>> prefixCount =1;
>> for (int i=0;i>   for (int j=0;j> for (int k=0; 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  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

[Ashish Goel]

Q4


vector prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;i 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.
> vector prefix;
> prefix[0]=NULL;
> prefixCount =1;
> for (int i=0;i   for (int j=0;j for (int k=0; 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  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

[Ashish Goel]

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  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.
> vector prefix;
> prefix[0]=NULL;
> prefixCount =1;
> for (int i=0;i   for (int j=0;j for (int k=0; 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  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

[Ashish Goel]

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.
vector prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;i 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

[adarsh kumar]

Have answered inline:
Q1) Given a newspaper and a set of ‘l’ words, give an efficient
algorithm to find the ‘l’ words in the newspaper.

Trivial hash-dictionary search operation. Takes O(m*l), where m=length
of maximum length word in the set l.

Q2) Find the next higher number in set of permutations of a given number.

Sorting and just returning next element, takes O(nlogn).
Hashing takes O(n). Just iterate through the list, and as and when you
encounter a number, check if its a permuation of the given number. If
yes, update min(a variable thats used to keep track of the minimum
found upto that element), else just pass that element simply. Finally,
return min.

Q3) Given preorder of a BST, find if each non-leaf node has just one
child or not. To be done in linear time.

If the word non-leaf node is strictly considered, the root should also
be included. Thus, traverse the given preorder of the BST, and in case
any violation happens, the answer is no, otherwise yes. Violation
meaning, if you pass a node that is less than the root(which will
subsequently be updated to the current node as you iterate through the
loop), you should never encounter a value that is greater than the
root(or, again, any subsequent node encountered).


On 7/4/12, Decipher  wrote:
> Q1) Given a newspaper and a set of ‘l’ words, give an efficient algorithm
> to find the ‘l’ words in the newspaper.
>
> Q2) Find the next higher number in set of permutations of a given number.
>
> Q3) Given preorder of a BST, find if each non-leaf node has just one child
> or not. To be done in linear time.
>
> Q4) Given a dictionary of words, two APIs
> Is_word(string)
> Is_prefix(string)
> And a NxN matrix with each postion consisting of a character. If from any
> position (i,j) you can move
> in any of the four directions, find out the all the valid words that can be
>
> formed in the matrix.
> (looping is not allowed, i.e. for forming a word position if you start from
>
> (i,j) and move to (i-1,j) then
> from this position you cannot go back to (i,j))
>
> Q5) Given that there are n players and each one of them has played exactly
> one game with every
> other player. Also given is an API that tells whether player ‘a’ won or
> lost to player ‘b’, where ‘a’ and
> ‘b’ could be any of the players. Arrange the n players in a length n array
> such that player at position
> ‘i’ has won from player at ‘i+1’ and lost to player at ‘i-1’.
>
> --
> 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/-/LzG-OrtjDmoJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Amazon Interview Question

[Decipher]

Q1) Given a newspaper and a set of ‘l’ words, give an efficient algorithm 
to find the ‘l’ words in the newspaper.

Q2) Find the next higher number in set of permutations of a given number.

Q3) Given preorder of a BST, find if each non-leaf node has just one child 
or not. To be done in linear time.

Q4) Given a dictionary of words, two APIs
Is_word(string)
Is_prefix(string)
And a NxN matrix with each postion consisting of a character. If from any 
position (i,j) you can move 
in any of the four directions, find out the all the valid words that can be 
formed in the matrix.
(looping is not allowed, i.e. for forming a word position if you start from 
(i,j) and move to (i-1,j) then 
from this position you cannot go back to (i,j))

Q5) Given that there are n players and each one of them has played exactly 
one game with every 
other player. Also given is an API that tells whether player ‘a’ won or 
lost to player ‘b’, where ‘a’ and 
‘b’ could be any of the players. Arrange the n players in a length n array 
such that player at position 
‘i’ has won from player at ‘i+1’ and lost to player at ‘i-1’.

-- 
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/-/LzG-OrtjDmoJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[atul anand]

http://www.leetcode.com/2010/11/finding-minimum-window-in-s-which.html

On 6/25/12, Navin Kumar  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.

[algogeeks] [amazon ] Finding Sub segment

[Navin Kumar]

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.

Re: [algogeeks] Amazon Interview Question

[megha agrawal]

Hashmap can be used for effective retreival..

On Thu, Jun 14, 2012 at 4:23 PM, Mohit Rathi  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 wrote:
>
>> example pls...
>>
>> On Thu, Jun 14, 2012 at 1:01 PM, Mohit Rathi 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.
>>
>
>
>
> --
> 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.