[algogeeks] MS Question -Reverse a Linked List in size of 2
Say LL is 1-2-3-4-5-6-7-8 Then u need to return 7-8-5-6-3-4-1-2 U cant swap the values U have to rearrange the ptr... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] MS Question -Reverse a Linked List in size of 2
wat if u have odd no of nodes On Tue, Jan 24, 2012 at 12:00 AM, atul anand atul.87fri...@gmail.comwrote: one simple way would be using stacks. push node,node-next; then pop() , and reversing the pointers. On Mon, Jan 23, 2012 at 11:46 PM, Ankur Garg ankurga...@gmail.com wrote: Say LL is 1-2-3-4-5-6-7-8 Then u need to return 7-8-5-6-3-4-1-2 U cant swap the values U have to rearrange the ptr... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] MS Question -Reverse a Linked List in size of 2
Well for odd cases its lile this
1 -2-3-4-5
4-5-2-3-1
Also u have to do this in single pass..U can use recursion though
On Tue, Jan 24, 2012 at 12:18 AM, Arun Vishwanathan
aaron.nar...@gmail.comwrote:
node *ptr =head;
//function call is reverse(head,NULL)
void reverse(node *ptr, node *follow)
{
if(ptr-next!=NULL ptr-next-next!=NULL)
reverse(ptr-next-next,ptr);
else
if(ptr-next!=NULL ptr-next-next==NULL)
{
ptr-next-next=follow;
head=ptr;
}
ptr-next-next=follow;
if(follow!=NULL)
follow-next-next=NULL;
}
@ankur: if odd number of nodes then maybe just ask interviewer how he
wants it to be and try including that case ;)
}
On Mon, Jan 23, 2012 at 10:32 AM, Ankur Garg ankurga...@gmail.com wrote:
wat if u have odd no of nodes
On Tue, Jan 24, 2012 at 12:00 AM, atul anand atul.87fri...@gmail.comwrote:
one simple way would be using stacks.
push node,node-next;
then pop() , and reversing the pointers.
On Mon, Jan 23, 2012 at 11:46 PM, Ankur Garg ankurga...@gmail.comwrote:
Say LL is
1-2-3-4-5-6-7-8
Then u need to return
7-8-5-6-3-4-1-2
U cant swap the values U have to rearrange the ptr...
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
--
People often say that motivation doesn't last. Well, neither does
bathing - that's why we recommend it daily.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Time Complexity Ques
Hello I was going through this link http://www.geeksforgeeks.org/archives/3187 Wonder what is the time complexity for this..?Can anyone explain Regards Ankur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MS Question
@Himanshu Nice idea..that shud do..but how do we code that ? regards Ankur On Sat, Jan 14, 2012 at 2:23 PM, payal gupta gpt.pa...@gmail.com wrote: @himanshu thnx..:) Regards, PAYAL GUPTA, 3rd YR ,CSE, NIT-BHOPAL. On Fri, Jan 13, 2012 at 9:42 PM, Himanshu Neema potential.himansh...@gmail.com wrote: Let a color below represent a single character in UTF-8 encoding , which means that each color can span multiple bytes , In example below I denote one byte by one english character . i.e. 'a' or 'b' or 'c' ,etc. below takes one byte : Let the string is : x abc def gh ij klmn now to reverse this UTF-8 encoded string in place in two steps : 1) reverse bytes of a multibyte character in place , after this step the string will look like : x cba fed hg ji nmlk 2) Now apply a normal string reversal algo , i.e , to swap first byte with last byte , swap second byte to second last byte .. and so on ... after this step the string will look like : klmn ij gh def abc x And look we have reversed an UTF-8 encoded string in place :) On Fri, Jan 13, 2012 at 11:13 AM, Supraja Jayakumar suprajasank...@gmail.com wrote: Hi Normal string will not work I think. Because it is avriable length encoding scheme. On Fri, Jan 13, 2012 at 11:11 AM, b.kisha...@gmail.com b.kisha...@gmail.com wrote: Is there anything called in-place reversal ?? UTF-8 is only encoding similar to ASCII but with a huge charecter set. So normal string reversal would work fine.. On Thu, Jan 12, 2012 at 2:02 AM, Ankur Garg ankurga...@gmail.comwrote: How to do this Write a function to reverse a UTF-8 encoded string in-place ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- U -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Linked list MS Q
XOR Linked Lists On Sat, Jan 14, 2012 at 7:06 PM, Ashish Goel ashg...@gmail.com wrote: design a linked list that has only one pointer per node yet can be traversed in forward or reverse direction. 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] sort 2D array
@Shady Rows are already sorted ... On Wed, Jan 11, 2012 at 1:53 PM, shady sinv...@gmail.com wrote: ^^ true, sort the rows and then a K-way merge. On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal sanjay.raj...@live.inwrote: I guess sort the array such that elements are sorted finally in such a way that if we print them row by row, the result is a sorted array. K-way merge can be useful. * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * On Tue, Jan 10, 2012 at 11:28 PM, prakash y yprakash@gmail.comwrote: sort the whole matrix in ascending array means? can you please explain ? On Wed, Jan 11, 2012 at 12:53 PM, atul anand atul.87fri...@gmail.comwrote: Given 2D array. The rows are sorted in ascending order and the colums are sorted in ascending order. We have to sort the whole matrix in ascending array. We cannot use 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] sort 2D array
If we use K merge I think the time complexity would be nm lognm I think we must try doing in O(m*n) On Wed, Jan 11, 2012 at 1:54 PM, Ankur Garg ankurga...@gmail.com wrote: @Shady Rows are already sorted ... On Wed, Jan 11, 2012 at 1:53 PM, shady sinv...@gmail.com wrote: ^^ true, sort the rows and then a K-way merge. On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal sanjay.raj...@live.inwrote: I guess sort the array such that elements are sorted finally in such a way that if we print them row by row, the result is a sorted array. K-way merge can be useful. * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * On Tue, Jan 10, 2012 at 11:28 PM, prakash y yprakash@gmail.comwrote: sort the whole matrix in ascending array means? can you please explain ? On Wed, Jan 11, 2012 at 12:53 PM, atul anand atul.87fri...@gmail.comwrote: Given 2D array. The rows are sorted in ascending order and the colums are sorted in ascending order. We have to sort the whole matrix in ascending array. We cannot use 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@Lucifer
I am not getting how u r working with heapifying each time ..
Initially the array is such that minimum value is ay (0,0) and and max at
index (m-1,n-1)
Now when u swap a value
Then u heapify i.e. make the prior arrangement again but that in turn will
lead to few swaps and so on...(Recursive)
Do you think it will be possible this way ?
Please correct me in case I got things wrong here
regards
Ankur
On Wed, Jan 11, 2012 at 5:07 PM, atul anand atul.87fri...@gmail.com wrote:
i have little doubt in complexity of proposed algo..
aren't we including complexity of heapifying each time. ??
On Wed, Jan 11, 2012 at 2:57 PM, Lucifer sourabhd2...@gmail.com wrote:
@dipit ..
Yup you are correct..
Say, no of rows = M and no. of cols = N,
Time complexity = sum over all i (1 to M} { N*(M+N-i) }
= M * N * (M + 2N - 1) /2
On Jan 11, 2:19 pm, Dipit Grover dipitgro...@gmail.com wrote:
@Lucifer : I came up with a similar algorithm as yours but I dont
understand your complexity analysis : sum over all i (1 to M} {
i*(M+N-i)} .
Shouldnt it be M * sum over all i(1 to N) {(M+N-i)} ? M= no of
columns, N= no of rows . Since we always have the min element at the 0th
column of the next row for each element of the current row.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] MS Question
How to do this Write a function to reverse a UTF-8 encoded string in-place ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] MS Q
Can you give an example Say matrix is 1 1 0 0 1 1 0 0 0 0 1 1 Has it got 3 islands i.e 1-1 be in same row or they can be column wise also i.e. 5 On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.com wrote: there is a matrix of 1 and 0 1 is a island and 0 is water 1-1 together makes one island calculate total no of islands Best Regards Ashish Goel Think positive and find fuel in failure -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding subarray
I think this wont work for cases with negetive nos
Ex
-2,8,-6
On Tue, Jan 10, 2012 at 6:51 AM, sravanreddy001 sravanreddy...@gmail.comwrote:
solution at this link:
http://ideone.com/ifVIv
for every position, (iteration)
maitain left, right for the sums,
keep adding elements towards the begenning to left, and towards the end to
right, (based on the conditions in the code)
Complexity: outer forloop : O(n)
inner while loop O(n)
total O(n^2) and O(1) space.
its currently printing all the position, center is included to the left
side,
Left : 3, Right: 9, Center: 6
this reads as.. sum(elements at 3,4,5,6) == sum(elements at 7,8,9)
let me know if it needs more explanantion.
for(int i=0;ilen;i++){
int left=0,right=0;
int p1 = i;
int p2 = i+1;
left = left + a[p1];
right = right + a[p2];
while(p1=0 p2 len){
if( left == right){
printf(Left : %d, Right: %d, Center: %d
\n,p1,p2,i);
break;
//return 0;
}
else if(left right p2 len-1){
p2++;
right = right+ a[p2];
}
else if(left right p1 0){
p1--;
left = left + a[p1];
}
else{
//printf(Left : %d, Right: %d, Center: %d
\n,p1,p2,i);
//printf(Not Possible\n);
break;
//return 0;
}
}
}
--
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/-/GoJEA73v8dcJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: check Similar array
What if we check these 2 conditions
XOR and sum of elements and sizeof array same
I cudnt find any counter example
Regards
Ankur
On Wed, Jan 4, 2012 at 6:53 PM, Karthikeyan V.B kartmu...@gmail.com wrote:
Hi,
Consider, arr1={1,2,3} and arr2={-1,-2,-3}
using sum of squares method sum(arr1) = 14 ans sum(arr2) = 14 (since
square of 1 and -1 is 1)
so it won work with this case
1.better take the square and negate it before adding
or
2.take sum of cubes
pls correct me if i'm wrong
Regards,
Karthikeyan
PSG TECH
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: check Similar array
sorry it shud be
sum of squares and xor and sumof elements
I think this shud work
Regards
Ankur
On Wed, Jan 4, 2012 at 9:52 PM, atul anand atul.87fri...@gmail.com wrote:
@ Karthikeyan :
sum of cubes fails:-
arr1={2,3,0,-3} = 4
arr2={1,1,1,1} = 4
On Wed, Jan 4, 2012 at 6:53 PM, Karthikeyan V.B kartmu...@gmail.comwrote:
Hi,
Consider, arr1={1,2,3} and arr2={-1,-2,-3}
using sum of squares method sum(arr1) = 14 ans sum(arr2) = 14 (since
square of 1 and -1 is 1)
so it won work with this case
1.better take the square and negate it before adding
or
2.take sum of cubes
pls correct me if i'm wrong
Regards,
Karthikeyan
PSG TECH
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Longest sequence of numbers with atmost diff K
I think this can be solved in NlogN using binary search
Here is the idea
We take a deque which stores the index of the array in increasing order
i.e. the index with minimum value is always on the front of the deque
Now when a new element comes we check with the front of this deque .
If the diff of the front element of the deque and a[i] =k that means it
can be part of the sequence . So we insert it into the correct position in
the deque using binary Search
If the diff is k then we know that with this element the sequence cant be
formed .So we update the maxLength to max(maxLen,deque.size())
And then remove all the elements from front of the deque till which diff
between front and a[i]=k
and keep on repeating the same process
We traverse the array once only and perform binary seach every time so
complexity nlogn
Ex array
2,1,8,12,10,15,13,25
I took deque as data structure so that I can insert and remove elements
from both ends and also access any in between element in O(1)
So Initially declare maxLen=INT_MIN
now 2 comes with index i=0
Since deque is empty we put its index - Deque - 0
Now next element is 1
We compare front of deque with 1 - 2-1 =1 .Its less than 7 so we insert it
into correct position in deque using Binary Search
Deque -1,0
Now 8 comes -Again 8-1 ==7 So we again put it in
Deque - 1,0,2
Now comes 12
Now 12-17 So it cant be part of Sequence . So we need to remove the
elements . The deque will always contain elements which can be part of the
sequence
Before removing we update the maxLen= max(INT_MIN,deque.size()) so it
becomes 3 for Now
And now we remove elements from start of the deque until deque.front()-12
=7
So deque becomes 2
Now insert 12 's index i.e 3 in correct position Deque - 2,3
Now comes 10 ..It will be part of the sequence So insert it in
Deque - 2,4,3
Now comes 15 .. Insert it as well
Dequeu- 2,4,3,5
13 comes
Dequeue- 2,4,3,6,5
Now comes 25
Update Max len=5 and start removing
Deque will only have 1 now
Now we are done with array
So we return 5
I wrote the code for this and it worked on few cases .I am sharing it below
, but I guess the idea is cleared as I stated above.
I dont think we can do better than NlogN here
Code -
void binary_search(int a[],dequeintindex,int low,int high,int i){
int mid;
dequeint::iterator it;
it=index.begin();
while(low=high){
mid=low+(high-low)/2;
if((mid==high || a[index[mid+1]]=a[i]) a[index[mid]]= a[i]){
index.insert(it+mid+1,i);
return;
}
else if((mid==low || a[index[mid-1]]=a[i]) a[index[mid]]= a[i] ){
if(mid==0){
index.insert(it,i);
return;
}else{
index.insert(it+mid-1,i);
return;
}
}
else if(a[index[mid]]= a[i])
low=mid+1;
else if( a[index[mid]]=a[i])
high=mid-1;
}
}
int FindMaxLength(int a[],int n,int k){
dequeintindex;
int len=INT_MIN;
int i,s;
index.push_back(0);
//length.push_back(0);
for(i=1;in;i++){
if(abs(a[i]-a[index.front()])k){
//binary_search(a,index,0,index.size()-1,i);
s=index.size();
len=max(len,s);
while( (!index.empty()) (abs(a[index.front()]-a[i])k))
index.pop_front();
}
if(index.empty())
index.push_back(i);
binary_search(a,index,0,index.size()-1,i);
}
s=index.size();
len=max(len,s);
return len;
}
On Tue, Jan 3, 2012 at 1:50 AM, Lucifer sourabhd2...@gmail.com wrote:
@ Optimization ... O(N).. single run O(n^2)
Basically in a single run we can calculate the maximum value using
praveen's logic..
Say, A[N] is the array of integers..
And X[N+1] stores the intermediate values for maximum size subarray...
int max = 0;
int strtind = -1;
int endind = -1;
for(int i =0; i= N; ++i)
X[i] = 0;
for (int i = 0; i N; ++i)
for (j = N; j 0; --j)
{
X[j] = ( abs(A[i] - A[j]) K ) ? 0 : 1+ min( X[j],
X[j-1] ) ;
if ( A[j] max)
{
max = A[j];
strtind = i - max + 1;
endind = j - 1;
}
}
On Jan 3, 12:57 am, Lucifer sourabhd2...@gmail.com wrote:
@above..
I m sorry,
A would be 1 2 3 4 5 ..
On Jan 3, 12:03 am, atul anand atul.87fri...@gmail.com wrote:
@praveen : i guess we can optimize the space to O(n);
if diff b/w two number is =K then A[i]=A[i-1]+1;
if condition fails temp_maxLen=A[i-1];
if(temp_maxlen maxLen)
{
maxLen=temp_maxlen;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
Re: [algogeeks] Re: Longest sequence of numbers with atmost diff K
@Lucifer
I checked with my code
The answer is coming out to be 4 ..So in this case its passing
Also the queue is containing the indexes in order of increasing values ..so
for curr min we need to only check the front of the queue.
Also I remove the elements of the queue till all the diff of elements in
the queue with the current element is =k
If queue is containing elements
say
i j k l m
Then yesit is possible that i j and i k... but a[i] is always less
than a[j] and a[k]...
So queue will always contain the correct elements I guess..
Like I said I have not done its testing with many cases .. But for this
case the answer is coming out correct
One correction to the code though
it should be
if(index.empty())
index.push_back(i);
else
binary_search(a,index,0,index.size()-1,i);
I missed the else part here..
In case you find anyother case it would be great .. I am sharing the source
codes .cpp file
If u find any case thats missing ..please tell me and I will also update in
case some case misses out
Thanks very much for looking into it :)
Thanks and Regards
Ankur
On Tue, Jan 3, 2012 at 3:26 AM, Lucifer sourabhd2...@gmail.com wrote:
@Ankur..
A : 2 4 6 8 1, diff is 6.
Looks like the answer acc. to ur code would be 5, but actually it
should be 4..
I m correct, then it can be fixed by looking at the front and back of
the queue and see whether the A[i] is actually the curr min or curr
max..
And then calculate the diff based on the above cond i.e either
abs(A[i] - Q.front()) or abs(A[i] - Q.back())
Also,
Taking the size of queue for calculating the max is incorrect, as the
queue might contain elements with lower indices that actually
shouldn't be considered for subarray calculation...
Say, Queue : i j k l m
Now, it is possible that i j and i k...
Hence, if u remove i and then calculate the next subarray it will also
take k into consideration which is incorrect..
The max length should be : Q.back - (i + 1) for the next iteration...
basically 'i+1' should be the start index...
Also, say when the queue looks like: k l m , this state is incorrect..
While removing elements u should also look for indices, if the current
start index is grater than Q.front then u should remove Q.front...
i.t for k l m..
current start index would be 'j+1' and as k j hence you should
remove it and loop over for further removals..
I all my observations are correct, then a couple of modifications will
rectify the code..
In case i m wrong.. then cheers :)
On Jan 3, 1:20 am, Lucifer sourabhd2...@gmail.com wrote:
@ Optimization ... O(N).. single run O(n^2)
Basically in a single run we can calculate the maximum value using
praveen's logic..
Say, A[N] is the array of integers..
And X[N+1] stores the intermediate values for maximum size subarray...
int max = 0;
int strtind = -1;
int endind = -1;
for(int i =0; i= N; ++i)
X[i] = 0;
for (int i = 0; i N; ++i)
for (j = N; j 0; --j)
{
X[j] = ( abs(A[i] - A[j]) K ) ? 0 : 1+ min( X[j],
X[j-1] ) ;
if ( A[j] max)
{
max = A[j];
strtind = i - max + 1;
endind = j - 1;
}
}
On Jan 3, 12:57 am, Lucifer sourabhd2...@gmail.com wrote:
@above..
I m sorry,
A would be 1 2 3 4 5 ..
On Jan 3, 12:03 am, atul anand atul.87fri...@gmail.com wrote:
@praveen : i guess we can optimize the space to O(n);
if diff b/w two number is =K then A[i]=A[i-1]+1;
if condition fails temp_maxLen=A[i-1];
if(temp_maxlen maxLen)
{
maxLen=temp_maxlen;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
#include iostream
#include queue
#includecstdlib
#includeclimits
using namespace std;
void binary_search(int a[],dequeintindex,int low,int high,int i){
int mid;
dequeint::iterator it;
it=index.begin();
while(low=high){
mid=low+(high-low)/2;
if((mid==high || a[index[mid+1]]=a[i]) a[index[mid]]= a[i]){
index.insert(it+mid+1,i);
return;
}
else if((mid==low || a[index[mid-1]]=a[i]) a[index[mid]]= a[i] ){
if(mid==0){
index.insert(it,i);
return;
}else{
index.insert(it+mid-1,i);
return;
}
}
else if(a[index[mid]]= a[i])
Re: [algogeeks] Re: Longest sequence of numbers with atmost diff K
@Lucifer
I checked again and saw a few flaws in my code . Please ignore my prev post
.. :P
1) I am always comparing with q.front() and taking the diff but I should
also do the same with q.back() as it might contain values which have diff
k . So yes , this is a bug
For this as you rightly pointed out we also need to compare with q.back()
So I modified my code accordingly
for(i=1;in;i++){
if(abs(a[i]-a[index.front()])k || abs(a[index.back()]-a[i])k ){
//binary_search(a,index,0,index.size()-1,i);
s=index.size();
couta[i] sendl;
len=max(len,s);
while( (!index.empty()) (abs(a[index.front()]-a[i])k))
index.pop_front();
while( (!index.empty()) (abs(a[index.back()]-a[i])k))
index.pop_back();
}
For the second part that you said , yes potentially if we use queue.size()
we can miss out on continuous part ..
Thanks for pointing these out
Regards
Ankur
On Tue, Jan 3, 2012 at 4:06 AM, Ankur Garg ankurga...@gmail.com wrote:
@Lucifer
I checked with my code
The answer is coming out to be 4 ..So in this case its passing
Also the queue is containing the indexes in order of increasing values
..so for curr min we need to only check the front of the queue.
Also I remove the elements of the queue till all the diff of elements in
the queue with the current element is =k
If queue is containing elements
say
i j k l m
Then yesit is possible that i j and i k... but a[i] is always
less than a[j] and a[k]...
So queue will always contain the correct elements I guess..
Like I said I have not done its testing with many cases .. But for this
case the answer is coming out correct
One correction to the code though
it should be
if(index.empty())
index.push_back(i);
else
binary_search(a,index,0,index.size()-1,i);
I missed the else part here..
In case you find anyother case it would be great .. I am sharing the
source codes .cpp file
If u find any case thats missing ..please tell me and I will also update
in case some case misses out
Thanks very much for looking into it :)
Thanks and Regards
Ankur
On Tue, Jan 3, 2012 at 3:26 AM, Lucifer sourabhd2...@gmail.com wrote:
@Ankur..
A : 2 4 6 8 1, diff is 6.
Looks like the answer acc. to ur code would be 5, but actually it
should be 4..
I m correct, then it can be fixed by looking at the front and back of
the queue and see whether the A[i] is actually the curr min or curr
max..
And then calculate the diff based on the above cond i.e either
abs(A[i] - Q.front()) or abs(A[i] - Q.back())
Also,
Taking the size of queue for calculating the max is incorrect, as the
queue might contain elements with lower indices that actually
shouldn't be considered for subarray calculation...
Say, Queue : i j k l m
Now, it is possible that i j and i k...
Hence, if u remove i and then calculate the next subarray it will also
take k into consideration which is incorrect..
The max length should be : Q.back - (i + 1) for the next iteration...
basically 'i+1' should be the start index...
Also, say when the queue looks like: k l m , this state is incorrect..
While removing elements u should also look for indices, if the current
start index is grater than Q.front then u should remove Q.front...
i.t for k l m..
current start index would be 'j+1' and as k j hence you should
remove it and loop over for further removals..
I all my observations are correct, then a couple of modifications will
rectify the code..
In case i m wrong.. then cheers :)
On Jan 3, 1:20 am, Lucifer sourabhd2...@gmail.com wrote:
@ Optimization ... O(N).. single run O(n^2)
Basically in a single run we can calculate the maximum value using
praveen's logic..
Say, A[N] is the array of integers..
And X[N+1] stores the intermediate values for maximum size subarray...
int max = 0;
int strtind = -1;
int endind = -1;
for(int i =0; i= N; ++i)
X[i] = 0;
for (int i = 0; i N; ++i)
for (j = N; j 0; --j)
{
X[j] = ( abs(A[i] - A[j]) K ) ? 0 : 1+ min( X[j],
X[j-1] ) ;
if ( A[j] max)
{
max = A[j];
strtind = i - max + 1;
endind = j - 1;
}
}
On Jan 3, 12:57 am, Lucifer sourabhd2...@gmail.com wrote:
@above..
I m sorry,
A would be 1 2 3 4 5 ..
On Jan 3, 12:03 am, atul anand atul.87fri...@gmail.com wrote:
@praveen : i guess we can optimize the space to O(n);
if diff b/w two number is =K then A[i]=A[i-1]+1;
if condition fails temp_maxLen=A[i-1];
if(temp_maxlen maxLen)
{
maxLen=temp_maxlen;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group
Re: [algogeeks] [Off-topic] Amdocs Interview Questions
Dude please ask these question on Interviewstreet group.. Your queries will be answered there Kindly adhere to the protocols of this group.. This may be one off thing but it can lead to start of interview queries.So please understand :) On Thu, Dec 29, 2011 at 12:35 AM, Jyoti Malik jyotimall...@gmail.comwrote: ooops sry i have no idea about that.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Frequency Sort Algo
@Atul..your solution is correct and would do the job but its complexity wud be nlogn . Any better way of solving it ? Regards Ankur On Sun, Dec 25, 2011 at 2:10 AM, sravanreddy001 sravanreddy...@gmail.comwrote: any better approach than O(N log N) time? maintain a heap of nodes value, count for each element, if already present increase the count. Else add the elements. Max-Heap -- fetch the node, print it count number of times, (time to search in heap -- log N) doing this for N elements. -- 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/-/rJMBHTFmv8IJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Frequency Sort Algo
fpr the nos with same frequency , the one having lower value shud come first For ex 3,1,1,3,1,3,2 Here 1 should come first so 2,1,1,1,3,3,3 On Sun, Dec 25, 2011 at 11:18 AM, top coder topcode...@gmail.com wrote: What about the case of the numbers having same frequency? Which one should come first? On Dec 24, 11:18 pm, atul anand atul.87fri...@gmail.com wrote: first sort the given array , you will get 1,1,1,1,2,2,2,3,3,3,3,3,4,4,5 now count frequency of each number and insert it into min heap. each node contain 2 variable. 1) frequency 2) number now do extract min operation. and expand , for eg:- for node 5 frequency = 0 number =5; write 5 to the given array for node 4 frequency = 2 number =4 write 4,4 to array. for node 2 frequency = 3 number =2 write 2,2,2 to the given array... On Sat, Dec 24, 2011 at 10:57 PM, Ankur Garg ankurga...@gmail.com wrote: how can one do frequency sort . Suppose we have an integer array like 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3 Then 1 is appearing 4 times 2 - 3 3- 5 4-2 5-1 Then if we sort by frequency we shud have this as result 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3 How to do it -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: How to solve this
The thing is ..will it ascertain that the probability is equal I am not sure how ur method guarantees that... May be if you and Dave can explain the algo a bit better that wud be great . regards Ankur On Sat, Dec 24, 2011 at 5:48 AM, Piyush Kansal piyush.kan...@gmail.comwrote: Hey Ankur, What is the order of time complexity we are looking for in this case. The option which Dave suggested can give us random node by traversing that many number of nodes from the head. That will be O(n). This can be further reduced to n/2 if we use two pointers, both of which will traverse two nodes at a time: 1. one pointing to first node (lets call it odd pointer) 2. other pointing to second node (lets call it even pointer) So, depending on the value returned by random number generator(even or odd), we can decide which pointer to pick. -- 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/-/N-5i9YH4AkYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Frequency Sort Algo
how can one do frequency sort . Suppose we have an integer array like 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3 Then 1 is appearing 4 times 2 - 3 3- 5 4-2 5-1 Then if we sort by frequency we shud have this as result 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3 How to do it -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] How to solve this
Suggest an algo with which u can find a random node in an infinitely long linked list -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Reverse n-Ary Tree and Return List of Leaf Nodes as Output - FYI Google MV
A better representation for a n-ary tree would be
struct node{
int data;
node* left;
node* sibling;
}
Like in a binary tree the second ptr points to its right child . Here it
points to its sibling.This one saves space and also We know in each level
we have how many nodes
@Shashank,
I think we can reverse the n-ary tree ,but again my doubt is what will be
leaf nodes then in that case , It seems it will be original root , so i was
confused . anyway , I will concentrate on reversing the tree only for now
based on ur definition.
Regards
Ankur
On Wed, Dec 21, 2011 at 1:08 PM, WgpShashank shashank7andr...@gmail.comwrote:
@atul,, yeah , but can you write some proper psuedo code/ Algorithm then
we can discus more about test cases.
Thanks
Shashank
--
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/-/VPZpHM8D_WcJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Reverse n-Ary Tree and Return List of Leaf Nodes as Output - FYI Google MV
Hey Shashank
Unfortunately I cudnt understand the problem
What do u mean by reversing the tree here :(..
On Tue, Dec 20, 2011 at 11:23 PM, WgpShashank shashank7andr...@gmail.comwrote:
here is my code
ListNode list=new LinkeListNode();
public ListNode reverseTreeandReturnListContainingAllLeafNOdes(Node n)
{
int i=0;
static int j=0;
if(n==null)
{
n=n.children[++j];
return null;
}
if(n.children[i]==null)
{
list.add(n);
return list;
}
list=reverseTreeandReturnListContainingAllLeafNOdes(n.children[i]);
n.children[i]=n;
return list;
}
may contains the bug ? any modification / suggestion will be appreciated
Thanks
Shashank
--
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/-/2puK42n-1yYJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Reverse n-Ary Tree and Return List of Leaf Nodes as Output - FYI Google MV
@Atul
Even i thought so..but then the definition of leaf node is that its a node
which doesnt have any children...then the answer is root of the original
tree so I got confused here :(
On Wed, Dec 21, 2011 at 12:20 AM, atul anand atul.87fri...@gmail.comwrote:
@ankur : for the given tree above instead of parent pointing to its child
, it would be child pointing to its parent after reversing
i guess thats wat he is trying to say.
On Tue, Dec 20, 2011 at 11:38 PM, Ankur Garg ankurga...@gmail.com wrote:
Hey Shashank
Unfortunately I cudnt understand the problem
What do u mean by reversing the tree here :(..
On Tue, Dec 20, 2011 at 11:23 PM, WgpShashank shashank7andr...@gmail.com
wrote:
here is my code
ListNode list=new LinkeListNode();
public ListNode reverseTreeandReturnListContainingAllLeafNOdes(Node n)
{
int i=0;
static int j=0;
if(n==null)
{
n=n.children[++j];
return null;
}
if(n.children[i]==null)
{
list.add(n);
return list;
}
list=reverseTreeandReturnListContainingAllLeafNOdes(n.children[i]);
n.children[i]=n;
return list;
}
may contains the bug ? any modification / suggestion will be appreciated
Thanks
Shashank
--
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/-/2puK42n-1yYJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Can anyone help me with this problem
Hi Can anyone help me with this question Code for Serializing and Deserializing a binary Tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] zig zag problem
a linear solution for this problem . although its more than O(n) but will
never be O(n*2)..used DP to solve it
space used -O(2n)
int ZigZagLength(vectorint a){
int n=a.size();
int DP[n][2];
DP[0][0]=1;
DP[0][1]=0;
DP[1][0]=2;
DP[1][1]=0;
int j;
for(int i=2;in;i++){
if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])==0){
DP[i][0]=DP[i-1][0];
DP[i][1]= i-1;
}
if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])0){
DP[i][0]=DP[i-1][0]+1;
DP[i][1]= i-1;
}
else{
j = DP[i-1][1];
while(j0){
if((a[i]-a[j])*(a[j]-a[DP[j][1]])0){
DP[i][0]=max(DP[j][0]+1,DP[i-1][0]);
if(DP[i][0]==DP[j][0]+1)
DP[i][1]=j ;
else
DP[i][1]= i-1;
break;
}else
j= DP[j][1];
}
if(j==0){
DP[i][0]=DP[i-1][0];
DP[i][1]=DP[i-1][1];
}
}
}
return DP[n-1][0];
}
On Sun, Dec 18, 2011 at 11:04 AM, atul anand atul.87fri...@gmail.comwrote:
complexity of this algo is O(n) ..I guess it is better than dynamic
programming approach which is O(n^2).
On Sat, Dec 17, 2011 at 6:28 PM, atul anand atul.87fri...@gmail.comwrote:
please see the algo and let me know if i am doing it wrong:-
toggle= arr[i+1] arr[i];
subseq=0;
for( i=0 ; ilen ;i++)
{
if ( toggle == 1)
{
if( arr[i+1] arr[i])
{
subseq=subseq+2;
}
toggle=0;
}
else
{
if(arr[i] arr[i+1])
{
subseq=subseq+2;
}
toggle=1;
}
}
print subseq;
On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta sangeeta15...@gmail.comwrote:
Problem Statement
A sequence of numbers is called a zig-zag sequence if the differences
between successive numbers strictly alternate between positive and
negative. The first difference (if one exists) may be either positive
or negative. A sequence with fewer than two elements is trivially a
zig-zag sequence.
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences
(6,-3,5,-7,3) are alternately positive and negative. In contrast,
1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because
its first two differences are positive and the second because its last
difference is zero.
Given a sequence of integers, sequence, return the length of the
longest subsequence of sequence that is a zig-zag sequence. A
subsequence is obtained by deleting some number of elements (possibly
zero) from the original sequence, leaving the remaining elements in
their original order
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] zig zag problem
@Atul ur solution is wrong
It seems u r comparing just the neighbouring elements .
The question is not to find the contiguous zig-zag sequence but longest
subsequence
Also even in case of contiguous sequence ur solution will not print the
correct length
like for 6 7 4 ur solution will print answer as 4 whereas in the answer
should be 3
Regards
Ankur
On Mon, Dec 19, 2011 at 1:16 AM, Ankur Garg ankurga...@gmail.com wrote:
a linear solution for this problem . although its more than O(n) but will
never be O(n*2)..used DP to solve it
space used -O(2n)
int ZigZagLength(vectorint a){
int n=a.size();
int DP[n][2];
DP[0][0]=1;
DP[0][1]=0;
DP[1][0]=2;
DP[1][1]=0;
int j;
for(int i=2;in;i++){
if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])==0){
DP[i][0]=DP[i-1][0];
DP[i][1]= i-1;
}
if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])0){
DP[i][0]=DP[i-1][0]+1;
DP[i][1]= i-1;
}
else{
j = DP[i-1][1];
while(j0){
if((a[i]-a[j])*(a[j]-a[DP[j][1]])0){
DP[i][0]=max(DP[j][0]+1,DP[i-1][0]);
if(DP[i][0]==DP[j][0]+1)
DP[i][1]=j ;
else
DP[i][1]= i-1;
break;
}else
j= DP[j][1];
}
if(j==0){
DP[i][0]=DP[i-1][0];
DP[i][1]=DP[i-1][1];
}
}
}
return DP[n-1][0];
}
On Sun, Dec 18, 2011 at 11:04 AM, atul anand atul.87fri...@gmail.comwrote:
complexity of this algo is O(n) ..I guess it is better than dynamic
programming approach which is O(n^2).
On Sat, Dec 17, 2011 at 6:28 PM, atul anand atul.87fri...@gmail.comwrote:
please see the algo and let me know if i am doing it wrong:-
toggle= arr[i+1] arr[i];
subseq=0;
for( i=0 ; ilen ;i++)
{
if ( toggle == 1)
{
if( arr[i+1] arr[i])
{
subseq=subseq+2;
}
toggle=0;
}
else
{
if(arr[i] arr[i+1])
{
subseq=subseq+2;
}
toggle=1;
}
}
print subseq;
On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta sangeeta15...@gmail.comwrote:
Problem Statement
A sequence of numbers is called a zig-zag sequence if the differences
between successive numbers strictly alternate between positive and
negative. The first difference (if one exists) may be either positive
or negative. A sequence with fewer than two elements is trivially a
zig-zag sequence.
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences
(6,-3,5,-7,3) are alternately positive and negative. In contrast,
1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because
its first two differences are positive and the second because its last
difference is zero.
Given a sequence of integers, sequence, return the length of the
longest subsequence of sequence that is a zig-zag sequence. A
subsequence is obtained by deleting some number of elements (possibly
zero) from the original sequence, leaving the remaining elements in
their original order
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] suggest algo
suggest algo to find k most frequently occuring numbers from a file of very large size containing numbers. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Interesting Liked List problem..Suggest Algo
Twisted linked list problem: Two linked lists merge at some node p,both the head pointers are given find the merging point under the following restrictions. 1. You should not traverse to the end any of the linked list. 2. Merge node p should be detected by the time you reach at most most k nodes from p. 3. Space should not exceed by k units. 4. No saving of nodes to hard discs. 5. No recursion. Regards Ankur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: find numbers if pair wise sums are given
Hi Topcoder. First of all you posted the wrong array . The array should be 4, 5, 10, 7, 12, 13 a+b a+c a+d b+cb+d c+d Now first calculate a+b+c+d which will be (sumofarray)/N-1 So here a+b+c+d = 17 Now take a[1] is a+c and a[N-1] = b+c subtracting them gives b-a = 2 a[0] is b+a=4 that gives b=3,a=1 Now u have a and b calculate c as a[1]-a=4 and d as9 . For this we traverse from a[1] to a[N-2] We calculate a and b because we know the order of sum of their elements(a+bis given and b's addition with rest elements are there in array) This will work in Linear Time Now lets take an example with 8 elements to let a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8 then N=8 and array is 3 4 5 6 7 8 9 5 6 7 8 9 10 7 8 9 10 11 9 10 11 12 11 12 13 13 14 15 Now by above logic first a+b+c+d+e+f+g+h = (sum)/7 = 252/7 = 36 Now a[1]=a+c = 4 and a[N-1] =a[7]=b+c=5 a[8]-a[1]= b-a=1 and a+b=a[0]=3 gives b=2 and a =1 Now we have a=1,b=2 So we traverse from a[1] to a[N-2] to calculate values c to h c= a[1]-a=4-1=3 d=a[2]-a=5-1=4 e=a[3]-a=6-1=5 similarly f=a[4]=6,g=a[5]=7 and h=a[6]=8 This will work in O(n) Regards Ankur On Thu, Dec 15, 2011 at 12:42 PM, WgpShashank shashank7andr...@gmail.comwrote: @all , a Naive Approach with Quadratic Time will be for each i=1 to n , check if i and a[i]-i makes given sum , so for each each number we will do the thus can achieve the solution ...i am just thinking about if we can do it linear time ..will post if able to do it :) Thanks Shashank CSe BIT Mesra -- 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/-/lF0kSVRUp5cJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: find numbers if pair wise sums are given
on above algo , there is no need to calculate sum of array so we can do it in O(N) and not O(n). On Fri, Dec 16, 2011 at 12:59 AM, Ankur Garg ankurga...@gmail.com wrote: Hi Topcoder. First of all you posted the wrong array . The array should be 4, 5, 10, 7, 12, 13 a+b a+c a+d b+cb+d c+d Now first calculate a+b+c+d which will be (sumofarray)/N-1 So here a+b+c+d = 17 Now take a[1] is a+c and a[N-1] = b+c subtracting them gives b-a = 2 a[0] is b+a=4 that gives b=3,a=1 Now u have a and b calculate c as a[1]-a=4 and d as9 . For this we traverse from a[1] to a[N-2] We calculate a and b because we know the order of sum of their elements(a+bis given and b's addition with rest elements are there in array) This will work in Linear Time Now lets take an example with 8 elements to let a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8 then N=8 and array is 3 4 5 6 7 8 9 5 6 7 8 9 10 7 8 9 10 11 9 10 11 12 11 12 13 13 14 15 Now by above logic first a+b+c+d+e+f+g+h = (sum)/7 = 252/7 = 36 Now a[1]=a+c = 4 and a[N-1] =a[7]=b+c=5 a[8]-a[1]= b-a=1 and a+b=a[0]=3 gives b=2 and a =1 Now we have a=1,b=2 So we traverse from a[1] to a[N-2] to calculate values c to h c= a[1]-a=4-1=3 d=a[2]-a=5-1=4 e=a[3]-a=6-1=5 similarly f=a[4]=6,g=a[5]=7 and h=a[6]=8 This will work in O(n) Regards Ankur On Thu, Dec 15, 2011 at 12:42 PM, WgpShashank shashank7andr...@gmail.comwrote: @all , a Naive Approach with Quadratic Time will be for each i=1 to n , check if i and a[i]-i makes given sum , so for each each number we will do the thus can achieve the solution ...i am just thinking about if we can do it linear time ..will post if able to do it :) Thanks Shashank CSe BIT Mesra -- 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/-/lF0kSVRUp5cJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: find numbers if pair wise sums are given
I saw this term non-decreasing order So we need to sort the numbers first..it will take nlogn . On Fri, Dec 16, 2011 at 1:12 AM, Ankur Garg ankurga...@gmail.com wrote: on above algo , there is no need to calculate sum of array so we can do it in O(N) and not O(n). On Fri, Dec 16, 2011 at 12:59 AM, Ankur Garg ankurga...@gmail.com wrote: Hi Topcoder. First of all you posted the wrong array . The array should be 4, 5, 10, 7, 12, 13 a+b a+c a+d b+cb+d c+d Now first calculate a+b+c+d which will be (sumofarray)/N-1 So here a+b+c+d = 17 Now take a[1] is a+c and a[N-1] = b+c subtracting them gives b-a = 2 a[0] is b+a=4 that gives b=3,a=1 Now u have a and b calculate c as a[1]-a=4 and d as9 . For this we traverse from a[1] to a[N-2] We calculate a and b because we know the order of sum of their elements(a+bis given and b's addition with rest elements are there in array) This will work in Linear Time Now lets take an example with 8 elements to let a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8 then N=8 and array is 3 4 5 6 7 8 9 5 6 7 8 9 10 7 8 9 10 11 9 10 11 12 11 12 13 13 14 15 Now by above logic first a+b+c+d+e+f+g+h = (sum)/7 = 252/7 = 36 Now a[1]=a+c = 4 and a[N-1] =a[7]=b+c=5 a[8]-a[1]= b-a=1 and a+b=a[0]=3 gives b=2 and a =1 Now we have a=1,b=2 So we traverse from a[1] to a[N-2] to calculate values c to h c= a[1]-a=4-1=3 d=a[2]-a=5-1=4 e=a[3]-a=6-1=5 similarly f=a[4]=6,g=a[5]=7 and h=a[6]=8 This will work in O(n) Regards Ankur On Thu, Dec 15, 2011 at 12:42 PM, WgpShashank shashank7andr...@gmail.com wrote: @all , a Naive Approach with Quadratic Time will be for each i=1 to n , check if i and a[i]-i makes given sum , so for each each number we will do the thus can achieve the solution ...i am just thinking about if we can do it linear time ..will post if able to do it :) Thanks Shashank CSe BIT Mesra -- 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/-/lF0kSVRUp5cJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Suggest Algo for this Question
Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. This question was also asked in Amazon -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
Agree with dave..Its still O(n) On Mon, Dec 12, 2011 at 10:57 PM, Dave dave_and_da...@juno.com wrote: @Sagar: Don is correct. n/2+n/4+n/8+... ~= n. But even the first round, involving n/2 comparisons, is O(n). Dave On Dec 12, 11:23 am, sagar pareek sagarpar...@gmail.com wrote: Yes Mr. DoN First round of Tournament sort results in log(n) time for finding largest no. n/2+n/4+n/8 results n/(2^i) where ^ = power On Mon, Dec 12, 2011 at 8:16 AM, Don dondod...@gmail.com wrote: No. To find the largest number in an unsorted array requires looking at each number, which is order n by definition. Don On Dec 12, 10:02 am, sagar pareek sagarpar...@gmail.com wrote: Hi every one. Can we find largest number from an unsorted array in log(n) ? -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
Max Heapify is O(n). On Mon, Dec 12, 2011 at 11:43 PM, ankit gupta ankit.itc...@gmail.comwrote: apply MAXHEAPIFY on root ode and extract the root node -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
By Max Heapify I thought u meant to say u are making a Max Heap .. In case you use Coreman Definition Of max Heapify it just heapifies assuming the heap has been formed, But u need to make a max Heap first dude :) P.S- Clarify your concepts before posting the link :( On Tue, Dec 13, 2011 at 12:11 AM, Dipit Grover dipitgro...@gmail.comwrote: ^it cant get better than O(n) apparently. Just applying max-heapify once would not yield the max element. You need to construct a heap for it, which is no less than O(n). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Detect a loop with just head ptr given
Can we detect if a loop is present in Linked List if only head ptr is given -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Detect a loop with just head ptr given
U cant create any new ptrs .Just use this ptr :) On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri hprem...@gmail.comwrote: Ofcourse we can.. U knw the head address now U start visit the list what is the big deal?? Jst u gotto create two pointer say fast and slow with two diff speed of action.. On Thu, Dec 8, 2011 at 6:27 PM, Ankur Garg ankurga...@gmail.com wrote: Can we detect if a loop is present in Linked List if only head ptr is given -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Thanks To aLgOgEeKs
cWas it offcampus or on campus recruitment dude. On Sat, Dec 3, 2011 at 12:5i7 PM, atul anand atul.87fri...@gmail.comwrote: @payal : last problem is a dutch flag problem. On Sat, Dec 3, 2011 at 3:33 AM, payal gupta gpt.pa...@gmail.com wrote: congrats..:):) plzz...elaborate the last two problemsand it vud be very grateful if u tell their solns tooo... Regards, payal gupta,cse,3rd year, nit-b. On 12/2/11, rahul sharma rahul23111...@gmail.com wrote: plz post how you prepared for MS..like the books or websites you followedwould b of gr8 help. On Fri, Dec 2, 2011 at 9:42 PM, rahul sharma rahul23111...@gmail.com wrote: gr8...congrats dude On Fri, Dec 2, 2011 at 9:05 PM, Karthikeyan V.B kartmu...@gmail.comwrote: Congratulations:) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Google Question--Suggest Algo
You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum. You can assume that n is a power of 2. Example: Array: [0,0,1,1,0,0,1,1,0,1,1,0] n = 12 k = 3 Size of subarrays can be: 2,3,4,5,6 Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0] Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433 Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0] Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333 Source - http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Google Question--Suggest Algo
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0 or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to
split
the array in such way such that the sum of all the expected values
for the
elements selected from each subarray is maximum.
You can assume that n is a power of 2.
Example:
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
Source -
http://stackoverflow.com/questions/8189334/google-combinatorial-optim...
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Google Question--Suggest Algo
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9])+ F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8])+ F(7, 2) ,
ExpVal (A[12 .. 7])+ F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0
or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element
of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly
selected
elements from the k subarrays. Basically means that we will want
to
split
the array in such way such that the sum of all the expected
values
for the
elements selected from each subarray is maximum.
You can assume
Re: [algogeeks] Does Y lies between x and z
As it seems to me this can be solved like this Find LCA(Least common ancestor) of node x and z .. See if it equals y or not . If not recursively search for y in left and right subtree of LCA ..If you find y in the descendents of LCA answer is true else its false . This method will give perfect answer just that complexity would be a bit large (greater than n) but space wll be O(1) neglecting stack space during recursive calls I coded the same and it works to me .. If anyone can suggest a finer approach that wud be great :) Regards Ankur On Thu, Nov 24, 2011 at 11:28 PM, Nitin Garg nitin.garg.i...@gmail.comwrote: Please explain what do you mean by 'path between x and z'. On Wed, Nov 23, 2011 at 11:46 PM, Ankuj Gupta ankuj2...@gmail.com wrote: There is a binary tree (Not a BST) in which you are given three nodes X,Y, and Z .Write a function which finds whether y lies in the path b/ w x and z. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Does Y lies between x and z
This approach would fail in certain cases :P..in fact lot many cases :D..It needs to be modified using space The thing is while calculating LCA we must also store the path in an Array or vector and then Iterate over its elements to check if match occurs. Cant think of O(1) solution though :( On Fri, Nov 25, 2011 at 12:57 AM, Ankur Garg ankurga...@gmail.com wrote: As it seems to me this can be solved like this Find LCA(Least common ancestor) of node x and z .. See if it equals y or not . If not recursively search for y in left and right subtree of LCA ..If you find y in the descendents of LCA answer is true else its false . This method will give perfect answer just that complexity would be a bit large (greater than n) but space wll be O(1) neglecting stack space during recursive calls I coded the same and it works to me .. If anyone can suggest a finer approach that wud be great :) Regards Ankur On Thu, Nov 24, 2011 at 11:28 PM, Nitin Garg nitin.garg.i...@gmail.comwrote: Please explain what do you mean by 'path between x and z'. On Wed, Nov 23, 2011 at 11:46 PM, Ankuj Gupta ankuj2...@gmail.comwrote: There is a binary tree (Not a BST) in which you are given three nodes X,Y, and Z .Write a function which finds whether y lies in the path b/ w x and z. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Finding the repeated element
^^+1..how matrix formed ??
But as Gene said we can use a set to store all the unique elements
Now we xor all the set elements and then xor them with the elements of the
array . This wud give us the repeating element as all the elements coming
once will be 0(xored twice) and repeating element wud be xored twice .
To code it as follows
int FindSingle(int a[],int n){
setints;
s.insert(a,a+n);
setint::iterator it;
it = s.begin();
int XOR= *it;
it++;
while(it!=s.end()){
XOR =XOR^*it;
it++;
}
for(int i=0;in;i++)
XOR=XOR^a[i];
return XOR;
}
On Fri, Nov 25, 2011 at 1:03 AM, kumar raja rajkumar.cs...@gmail.comwrote:
@Anup:
Atleast u tell me how the M has formed???
On 24 November 2011 11:21, Anup Ghatage ghat...@gmail.com wrote:
@kunzmilan
Nice idea, how do you decide the row-size or column-size of the matrix?
On Thu, Nov 24, 2011 at 8:00 PM, kumar raja rajkumar.cs...@gmail.comwrote:
@kunzmilan :
Can u please maintain the clarity ??
How did u find the M
if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it...
On 24 November 2011 06:15, kunzmize an kunzmi...@atlas.cz wrote:
On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote:
@kunzmilan : i did not get u, once explain with example...
On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote:
Matrix M
0 1 0
0 1 0
1 0 0
multiplied with M(T)
0 0 1
1 1 0
0 0 0
gives
1 0 0
0 2 0
0 0 0.
On its diagonal are numbers of repeated elements.
kunzmilan
On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote:
In the given array all the elements occur single time except one
element
which occurs 2 times find it in O(n) time and O(1) space.
e.g. 2 3 4 9 3 7
output :3
If such a solution exist can we extend the logic to find All the
repeated
elements in an array in O(n) time and O(1) space
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
Write the list in the form of a matrix M, e.g.
0 1 0 0...
0 0 1 0...
0 0 0 1...
..etc.,
and its quadratic form M(T)M shows, how many times each element
repeats.
kunzmilan
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Anup Ghatage
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: An Array Problem
Solution given by tech coder is fine and is working .. I coded it and its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an element,
it's too big to maintain the invariant, so it must be popped! We can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder techcoderonw...@gmail.com
wrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the right.
put the first element in stack.
take next element suppose num if this number is less than elements
stored in stack, pop those elements , for these pooped elements num
will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0 (valaue)
@techcoder : If the numbers are not in sorted order, What benefit the
stack would provide ? So, are you storing the numbers in sorted order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted order.
Get
a new element from array and lets call this number as m. Push m into the
stack. Now, find all elements which are = (m-1) using binary search. Pop
out all these elements and assign the value m in the output array.
Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage ghat...@gmail.com
wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta ankuj2...@gmail.com
wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1 correspondence.
output[i] is equal to the input[j] (ji) which is smaller than
input[i] and jth is nearest to ith ( i.e. first element which is
smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Anup Ghatage
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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*
*The Coder*
*Life is a Game. The more u play, the more u win, the more u win , the
more successfully u play*
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Aamir Khan | 3rd Year | Computer Science Engineering | IIT Roorkee
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
Re: [algogeeks] Re: An Array Problem
Here is my code with logic techcoder described ...
void PushSmallerElement(int a[],int n){
stackpairint,int s;
pairint,intp;
int top;
for(int i=0;in;i++){
if(s.empty())
s.push(pairint,int(a[i],i));
else{
p=s.top();
while( !s.empty() a[i]p.first ){
s.pop();
a[p.second]=a[i];
p=s.top();
}
}
s.push(pairint,int(a[i],i));
}
while(!s.empty()){
p=s.top();
s.pop();
a[p.second]=0;
}
}
On Wed, Nov 23, 2011 at 3:43 PM, Ankur Garg ankurga...@gmail.com wrote:
Solution given by tech coder is fine and is working .. I coded it and its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an element,
it's too big to maintain the invariant, so it must be popped! We can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder techcoderonw...@gmail.com
wrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the right.
put the first element in stack.
take next element suppose num if this number is less than elements
stored in stack, pop those elements , for these pooped elements num
will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0 (valaue)
@techcoder : If the numbers are not in sorted order, What benefit the
stack would provide ? So, are you storing the numbers in sorted order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted order.
Get
a new element from array and lets call this number as m. Push m into the
stack. Now, find all elements which are = (m-1) using binary search.
Pop
out all these elements and assign the value m in the output array.
Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage ghat...@gmail.com
wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta ankuj2...@gmail.com
wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1 correspondence.
output[i] is equal to the input[j] (ji) which is smaller than
input[i] and jth is nearest to ith ( i.e. first element which is
smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Anup Ghatage
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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*
*The Coder*
*Life is a Game. The more u play, the more u win, the more u win ,
the
more successfully u play*
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post
Re: [algogeeks] Re: An Array Problem
@Gene
Your algo is also right...Just that I followed techcoders logic and coded
the same...pair I used to map the index of the element ..But urs working
fine too :)
On Wed, Nov 23, 2011 at 7:04 PM, Gene gene.ress...@gmail.com wrote:
Sorry I forgot to initialize p. It's fixed below.
On Nov 23, 6:59 am, Gene gene.ress...@gmail.com wrote:
Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
doesn't mention anything about pairs, which are necessary to obtain
O(n). This is what I meant by almost.
In reverse order, you don't need the pairs. Its simpler.
In a subroutine like yours,
void find_smaller_to_right(int *a, int n)
{
int i, in, p=0, stk[n]; // C99 var length array
for (i = n - 1; i = 0; i--) {
in = a[i];
while (p 0 stk[p - 1] = in) p--; // pop
a[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in; // push
}
}
On Nov 23, 5:13 am, Ankur Garg ankurga...@gmail.com wrote:
Solution given by tech coder is fine and is working .. I coded it and
its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an element,
it's too big to maintain the invariant, so it must be popped! We can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder
techcoderonw...@gmail.com
wrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the
right.
put the first element in stack.
take next element suppose num if this number is less than
elements
stored in stack, pop those elements , for these pooped elements
num
will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0
(valaue)
@techcoder : If the numbers are not in sorted order, What
benefit the
stack would provide ? So, are you storing the numbers in sorted
order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted
order.
Get
a new element from array and lets call this number as m. Push m
into the
stack. Now, find all elements which are = (m-1) using binary
search. Pop
out all these elements and assign the value m in the output array.
Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage
ghat...@gmail.com
wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta
ankuj2...@gmail.com
wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1
correspondence.
output[i] is equal to the input[j] (ji) which is smaller
than
input[i] and jth is nearest to ith ( i.e. first element which
is
smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
You received this message because you are subscribed to the
Google
Groups Algorithm Geeks group.
To post to this group, send email to
algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group
[algogeeks] Linked List Problem-Suggest Algo
a linked list contains 2 19 _ _ 3 47 _ _ _ 2 20 _ _ ..and so on I have to fill those empty nodes with numbers whose sum is equal to the numbers occurring just before the gaps and the number of gaps is determined by the node which is at 2 distance before the gaps with the limitation that their would be no repetition in list only the nodes designating the number of gaps can be repeated for example 2 20 should be broken in two parts like 19 1 3 47 should be broken in three parts like 42 2 3 and not in 44 1 2 because 1 already occurred in the list due previous partition -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Soritng
I think Merge Sort doesnt require any swapping . So , for 3 my answer wud be Merge Sort On Mon, Nov 21, 2011 at 11:55 AM, Dave dave_and_da...@juno.com wrote: @Kumar: For question 1, the answer is radix sort. It doesn't use data comparisons at all. Dave On Nov 21, 12:04 am, kumar raja rajkumar.cs...@gmail.com wrote: if we have set of n elements then 1) which sorting method uses least number of comparisons?? 2) which sorting method uses least number of swaps?? 3) suppose the array is 2 8 4 6 5 9 if we want to swap 8 and 5 the cost is 2(5-2)=6 .here 5 and 2 are indices of 5 and 8. so what sorting method minimizes the cost, i want the answer in general case ,not for this particular array. it is also called least distance sorting -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Google Question--Suggest Algo
Given a string of lowercase characters, reorder them such that the same
characters are at least distance d from each other.
Input: { a, b, b }, distance = 2
Output: { b, a, b }
How to approach this question ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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 Onsite Chennai SDE
We can use a trie here .. Create a trie with all words of dictionary . Now delete the last character of the word and check if such a word is a valid word . If not see if adding a new character can make it a valid word . If not delete the next character and repeat the process again . This is what I can think of here. Any other solutions/guesses ? On Mon, Nov 14, 2011 at 12:43 PM, Aniket aniket...@gmail.com wrote: You are given a word and a dictionary. Now propose an algorithm edit the word (insert / delete characters) minimally to get a word that also exists in the dictionary. Cost of insertion and deletion is same. Write pseudocode for it. Seems like minimum edit distance problem but some modification is needed. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Did they ask you to code this or just asked logic On Sat, Nov 12, 2011 at 4:57 PM, surender sanke surend...@gmail.com wrote: @myself if number of distinct characters are equal then its final string size is 2. else there are more repeated characters other than distinct characters then its 1 correct me !!! surender On Sat, Nov 12, 2011 at 4:46 PM, surender sanke surend...@gmail.comwrote: All distinct combinations will result in string size of 2 + rest repeated characters eg abcabcabc -aabbcc-abc-aa or bb or cc surender On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.com wrote: Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Question
Hey I coded it . The answer is either 2 or 1 ..So I guess you guys are rite
:)
Here is the code
void smallestString(string str){
if(str.empty()) return;
int j=0,i,k=0;
for(i=1;istr.size();i++){
if(str[i]==str[j]){
j++;
}
else if(str[j]!=str[i]){
if((str[i]=='a' str[j]=='b') ||(str[i]=='b' str[j]=='a'
)){
str[j]='c';
}else if((str[i]=='b' str[j]=='c') ||(str[i]=='c'
str[j]=='b' )){
str[j]='a';
}else {
str[j]='b';
}
str.erase(str.begin()+i);
if(j0)j--;
i=j;
}
}
}
On Sat, Nov 12, 2011 at 8:19 PM, Nitin Garg nitin.garg.i...@gmail.comwrote:
If yes, how do you prove it?
On Sat, Nov 12, 2011 at 8:18 PM, Nitin Garg nitin.garg.i...@gmail.comwrote:
I can prove that the size of resulting string will be 1 or 2.
@surender -
what do you mean by no of distinct characters? they are 3 in this case -
a,b and c.
Do you mean to say that the no. of times each character appears are equal
then the final string is of size 2. and 1 otherwise?
On Sat, Nov 12, 2011 at 4:57 PM, surender sanke surend...@gmail.comwrote:
@myself
if number of distinct characters are equal then its final string size is
2.
else there are more repeated characters other than distinct characters
then its 1
correct me !!!
surender
On Sat, Nov 12, 2011 at 4:46 PM, surender sanke surend...@gmail.comwrote:
All distinct combinations will result in string size of 2 + rest
repeated characters
eg
abcabcabc -aabbcc-abc-aa or bb or cc
surender
On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.comwrote:
Given a string consisting of a,b and c's, we can perform the
following
operation:
Take any two adjacent distinct characters and replace it with the
third character. For example, if 'a' and 'c' are adjacent, they can
replaced with 'b'.
What is the smallest string which can result by applying this
operation repeatedly?
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Nitin Garg
Personality can open doors, but only Character can keep them open
--
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.
Re: [algogeeks] Re: Amazon Question
The Complexity of my solution is of Order n . At most I Traverse the whole string twice .. On Sat, Nov 12, 2011 at 8:29 PM, vikas vikas.rastogi2...@gmail.com wrote: seems like quesion of permutation, it will take all the permutation to check which one can lead to answer, there will be always be more than one solution complexity ((n-1)!) anyone for better solution ?? On Nov 12, 4:27 pm, surender sanke surend...@gmail.com wrote: @myself if number of distinct characters are equal then its final string size is 2. else there are more repeated characters other than distinct characters then its 1 correct me !!! surender On Sat, Nov 12, 2011 at 4:46 PM, surender sanke surend...@gmail.com wrote: All distinct combinations will result in string size of 2 + rest repeated characters eg abcabcabc -aabbcc-abc-aa or bb or cc surender On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.com wrote: Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Question
Well it aint O(n) ..:P ...The erase part will be complex and will take shifting string parts . So complexity will be O(n^2) for str.erase operation On Sat, Nov 12, 2011 at 8:34 PM, Ankur Garg ankurga...@gmail.com wrote: The Complexity of my solution is of Order n . At most I Traverse the whole string twice .. On Sat, Nov 12, 2011 at 8:29 PM, vikas vikas.rastogi2...@gmail.comwrote: seems like quesion of permutation, it will take all the permutation to check which one can lead to answer, there will be always be more than one solution complexity ((n-1)!) anyone for better solution ?? On Nov 12, 4:27 pm, surender sanke surend...@gmail.com wrote: @myself if number of distinct characters are equal then its final string size is 2. else there are more repeated characters other than distinct characters then its 1 correct me !!! surender On Sat, Nov 12, 2011 at 4:46 PM, surender sanke surend...@gmail.com wrote: All distinct combinations will result in string size of 2 + rest repeated characters eg abcabcabc -aabbcc-abc-aa or bb or cc surender On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.com wrote: Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Question
@Srinivas Wat if the string is abc then it reduces to cc :) ...So size 2 can also be there.so u cant say it will be 1 always On Sun, Nov 13, 2011 at 12:01 AM, Srinivasa Chaitanya T tschaitanya@gmail.com wrote: On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.com wrote: Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? 1) if the string a..aaa, or bb..bb, etc... string cannot be modified 2) if string starts with ac = this can be reduced to b - aaac - aab - ac - b 3) So if string not of type (1), then it can be reduced to single character always using method 2 e.g: *aab*cacaab // first reduce aab to b *bbc*acaab // reduce bbc to c *ca*caab *bc*aab *aaab* c .. i guess u got the idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- T Srinivasa Chaitanya -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Search an element in an Infinite array
@Bittu...When we choose low as 2^(n-1) and high as 2^n we are reducing the complexity from O(n) (Linear Search ) to logn (base2) . Here the thing is to apply normal binary search between low and high and thats where we decrease the complexity . If the required element is not in this range we change low=high and high = 2*high and again apply Binary Search. In the code before applying binary search u each time check whether k a[high] . If not we change low and high else apply binary search here . Ideally the complexity would be lot less than log(n) but since the no is infinite and k can also be taken very very high then say k lies between 2*(10^9) and 4*(10^9) which is a very high number in Itself . n is that very high number This approach wont work if the infinite array is not sorted Regards Ankur On Mon, Oct 24, 2011 at 7:09 PM, Bittu Sarkar bittu...@gmail.com wrote: @Ankur Don't think there's any major reason for using powers of 2 except the fact that computing the powers of 2 can be done very efficiently than computing the powers of any other number. Complexity in any case remains the same. On 24 October 2011 10:29, rahul sharma rahul23111...@gmail.com wrote: +1 ankur On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.com wrote: Use Binary Search start = 2^n-1 high =2^n where n=0,1 On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal sunny816.i...@gmail.com wrote: hint 1: try to find 2 indexes i, j such that a[i] = K = a[j] On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.comwrote: Given a sorted array of Infinite size, find an element ‘K’ in the array without using extra memory in O (lgn) time -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Bittu Sarkar 5th Year Dual Degree Student Department of Computer Science Engineering Indian Institute of Technology Kharagpur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Onsite
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.comwrote: @Nitin, excellent algo. if S 0 j = i-1 return 0 // I believe this mean there is no solution, you might want to return -1. Thanks, - Ravindra On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg nitin.garg.i...@gmail.comwrote: Lets say the Amount of petrol is Pi and distance to next petrol pump is Di for ith petrol pump. start from i=1, j=1 S =0 while (i=n) S += Pj - Dj; if S = 0 j = i-1 return i if S 0 j = i-1 return 0 else if S = 0 j++ mod n; else if S 0 j ++ mod n, i = j , S = 0; return 0 it will traverse atmost twice, and hence O(n). no extra space required. On Mon, Oct 24, 2011 at 4:06 AM, Aniket aniket...@gmail.com wrote: Suppose there is a circle. You have five points on that circle. Each point corresponds to a petrol pump. You are given two sets of data. 1. The amount of petrol that petrol pump will give. 2. Distance from that petrol pump to the next petrol pump. (Assume for 1 lit Petrol the truck will go 1 km) Now calculate the first point from where a truck will be able to complete the circle. (The truck will stop at each petrol pump and it has infinite capacity). Give o(n) solution. You may use o(n) extra space. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Nitin Garg Personality can open doors, but only Character can keep them open -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Search an element in an Infinite array
Use Binary Search start = 2^n-1 high =2^n where n=0,1 On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal sunny816.i...@gmail.comwrote: hint 1: try to find 2 indexes i, j such that a[i] = K = a[j] On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.com wrote: Given a sorted array of Infinite size, find an element ‘K’ in the array without using extra memory in O (lgn) time -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Inplace Array Convertion
@Sunny Your technique of Inshuffle and Outshuffle are perfect. But how to translate into the code without using extra space or say even constant space On Tue, Oct 18, 2011 at 12:43 AM, Dan dant...@aol.com wrote: I have a hard copy of the book (years back, I implemented a fortran version of the algorithm described in the book). I don't know if you can find an online version or not. I'm sure there is stuff there. Have you done a simple Google search for in place reorder array ?? It's not a difficult algorithm. And Sedgewicks's books are well known. Searches for his name may also yield results. Just FYI: If your rearrangement doesn't have to be in-place... you will achieve more speed by other methods. I did testing with rearrangement of some very large data sets. The in-place method was noticeably slower. It also required you to write your own routine to do the reordering. Using basic fortran, I could do the same thing in just one or two lines of very simple code. The only advantage to the in-place algorithm is that it uses less memory. This should only be important if you are dealing with some very large arrays. Dan :-) On Oct 14, 9:44 pm, Ankur Garg ankurga...@gmail.com wrote: @Dan ..can you post the algo here or link to the book?? @Anika ...yes please post the code here..but please explain a bit about underlying algo ...(algo is more important than actual code ) On Sat, Oct 15, 2011 at 1:54 AM, Dan dant...@aol.com wrote: On Oct 13, 7:52 pm, shiva@Algo shiv.jays...@gmail.com wrote: Convert an array a1 a2 a3...an b1 b2 b3...bn c1 c2 c3...cn to a1b1c1 a2b2c2...anbncn, inplace See the algorithm for memory efficient rearrangement of array elements in one of the books by Robert Sedgewick such as Algorithms in C++ or Algorithms in Pascal, etc. Dan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Amazon Ques Suggest Algo
{You are given an unsorted array of integers. You have to find out the first
sub array whose elements when added sum up to zero.
eg:- int Array[] = {1,2,-4,-3, 6 ,-3.}Here sub array is -3,6,-3 bcos
adding all these sum to zero. A sub array can be of size 2 to whole length
of the array. You can use extra space also for the same
Brute Force will do it in O(n^2). Any better way
I was thinking DP but couldnt find proper sub-problems and even if we do
cudnt figure out lesser than O(n^2) :(
Any suggestions?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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 - Find Pythagorean triplet in an unsorted array
@Shashank ..+1 ..I wud say he must be given a tuning award :D :D for solving such eternal conundrum ;) On Mon, Oct 17, 2011 at 2:37 PM, WgpShashank shashank7andr...@gmail.comwrote: @wladimir , its PPT (Pythagoras triplets ) but its number theory based approach http://en.wikipedia.org/wiki/Pythagorean_triple might not be good idea Here is approach : * * *Euclid's formula*[1]http://en.wikipedia.org/wiki/Pythagorean_triple#cite_note-0 is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers *m* and *n* with *m* *n*. The formula states that the integers p=m^2-n^2 , q=2mn r=m^2+n^2 , we have to sort the array in non-increasing order , then for each mn we have to generate the all such p,q,r in worst case it will also requires O(N^2) such p,q,r for each MN isn't it ? then its not less then O(n^2) ?? Even with this approach,The triple generated by Euclid's formula is primitive if and only if *m* and *n* are coprime and *m*-*n* is odd. If both *m* and *n* are odd, then *a*, *b*, and *c* will be even, and so the triple will not be primitive; however, dividing *a*, *b*, and *c* by 2 will yield a primitive triple if *m* and *n* are coprime. @all other , its similar to 3 sun , can't be done in less then O(N^2) if number are not in range , When the integers are in the range [-*u* ... *u*], 3SUM can be solved in time O(n + *u* lg *u*) by representing *S* as a bit vector and performing a discrete convolution using FFT. i wondered if any other algo/code/link you have which works in less then O(N^2) , Better if One Explain The Approach or Algorithm , You Might able to fill Patent :D Thanks Shashank CSE, BIT Mesra -- 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/-/JQWWHDKMCiAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] print vertical sums of a binary tree
I am assuming we are allowed to use space ..With that i make 2 arrays 1 to
store values from left side and other from right side .
Here is the func
void getLevelSum(node* root,int minL,int maxR,int level){
if(!root) return ;
minL = min(minL,level);
maxR = max(maxR,level);
getLevelSum(root-left,minL,maxR,level-1);
getLevelSum(root-right,minL,maxR,level+1);
}
void getLevelSum(node* root,int level,int minL,int maxR,int left[],int
right[]){
if(!root) return ;
minL = min(minL,level);
maxR = max(maxR,level);
getLevelSum(root-left,level-1,minL,maxR,left,right);
getLevelSum(root-right,level+1,minL,maxR,left,right);
if(level0)
left[abs(level)] +=root-data;
else
right[level] +=root-data;
}
I am traversing whole tree nodes only once but storing them in an array so
Space complexity is also O(n) for me
Anyone having a better solution or approach ?
On Sun, Oct 16, 2011 at 9:27 AM, SUMANTH M sumanth.n...@gmail.com wrote:
Hi,
A binary tree is given we need to print vertical sums of nodes. for
example
12 34 5
| | 5| |
| | / | \ | |
| | / |8 |
| | / | / |\|
| 4 |/| 10
|/ | \9| |
| / | \ | |
7 | 6 |
| | | | |
| | | | |
---
7 4 20 8 10
Here we need to print sum 7,4,20,8,10.
-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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] print vertical sums of a binary tree
Sorry code got reposted twice here is the correct one
void getLevelSum(node* root,int level,int minL,int maxR,int left[],int
right[]){
if(!root) return ;
minL = min(minL,level);
maxR = max(maxR,level);
getLevelSum(root-left,level-1,minL,maxR,left,right);
getLevelSum(root-right,level+1,minL,maxR,left,right);
if(level0)
left[abs(level)] +=root-data;
else
right[level] +=root-data;
}
On Sun, Oct 16, 2011 at 4:23 PM, Ankur Garg ankurga...@gmail.com wrote:
I am assuming we are allowed to use space ..With that i make 2 arrays 1 to
store values from left side and other from right side .
Here is the func
void getLevelSum(node* root,int level,int minL,int maxR,int left[],int
right[]){
if(!root) return ;
minL = min(minL,level);
maxR = max(maxR,level);
getLevelSum(root-left,level-1,minL,maxR,left,right);
getLevelSum(root-right,level+1,minL,maxR,left,right);
if(level0)
left[abs(level)] +=root-data;
else
right[level] +=root-data;
}
I am traversing whole tree nodes only once but storing them in an array so
Space complexity is also O(n) for me
Anyone having a better solution or approach ?
On Sun, Oct 16, 2011 at 9:27 AM, SUMANTH M sumanth.n...@gmail.com wrote:
Hi,
A binary tree is given we need to print vertical sums of nodes. for
example
12 34 5
| | 5| |
| | / | \ | |
| | / |8 |
| | / | / |\|
| 4 |/| 10
|/ | \9| |
| / | \ | |
7 | 6 |
| | | | |
| | | | |
---
7 4 20 8 10
Here we need to print sum 7,4,20,8,10.
-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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Inplace Array Convertion
@Dan ..can you post the algo here or link to the book?? @Anika ...yes please post the code here..but please explain a bit about underlying algo ...(algo is more important than actual code ) On Sat, Oct 15, 2011 at 1:54 AM, Dan dant...@aol.com wrote: On Oct 13, 7:52 pm, shiva@Algo shiv.jays...@gmail.com wrote: Convert an array a1 a2 a3...an b1 b2 b3...bn c1 c2 c3...cn to a1b1c1 a2b2c2...anbncn, inplace See the algorithm for memory efficient rearrangement of array elements in one of the books by Robert Sedgewick such as Algorithms in C++ or Algorithms in Pascal, etc. Dan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Inplace Array Convertion
@Sunny ..Superb Algo ..but can you share some link where we can read abt it :)..especially where the info abt the equation u used is given Thanks in Advance On Sat, Oct 15, 2011 at 12:37 PM, Kunal Patil kp101...@gmail.com wrote: @Sunny: Thanks for the info !! That's gr8.. your logic also seems to be working perfectly fine.. On Sat, Oct 15, 2011 at 12:16 PM, shady sinv...@gmail.com wrote: u can always post the code.,... but before posting code, you must state your algorithm else code becomes useless for other users On Sat, Oct 15, 2011 at 1:10 AM, Anika Jain anika.jai...@gmail.comwrote: i have the code solution to this.. if m allowed to post it here then i can i post it. m i allowed to post code here? On Fri, Oct 14, 2011 at 9:40 PM, gaurav yadav gauravyadav1...@gmail.com wrote: @shiva...keep swapping the underline elements a1*a2*a3a4a5*b1*b2b3b4b5c1c2c3c4c5 a1b1*a3*a4a5a2b2b3b4b5*c1*c2c3c4c5 a1b1c1*a4*a5*a2*b2b3b4b5a3c2c3c4c5 a1b1c1a2*a5*a4*b2*b3b4b5a3c2c3c4c5 a1b1c1a2b2*a4*a5b3b4b5a3*c2*c3c4c5 a1b1c1a2b2c2*a5*b3b4b5*a3*a4c3c4c5 a1b1c1a2b2c2a3b3*b4*b5a5a4*c3*c4c5 a1b1c1a2b2c2a3b3c3*b5*a5*a4*b4c4c5 a1b1c1a2b2c2a3b3c3a4*a5*b5*b4*c4c5 a1b1c1a2b2c2a3b3c3a4b4*b5*a5*c4*c5 a1b1c1a2b2c2a3b3c3a4b4*c4*a5*b5*c5 a1b1c1a2b2c2a3b3c3a4b4c4a5b5c5 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array
@Rahul Pls elaborate with an example ... On Fri, Oct 14, 2011 at 2:35 PM, rahul patil rahul.deshmukhpa...@gmail.comwrote: You can take advantage of a basic property of triagle that sum of largest side of triangle sum of other two sides, After sorting you could easily deside the range in which possible solution could be found for a chosen hypotenuse On Fri, Oct 14, 2011 at 11:10 AM, ravindra patel ravindra.it...@gmail.com wrote: @Wladimir, yeah I have heard about that. Another way of populating primitive pythagoreans is, for any natural number m 1 (m^2 - 1, 2m, m^2 + 1) forms a pythagorean triplet. This is useful in populating pythagorean tiplets but here the problem is to search such triplets from a given int array. @ rahul, Hash of z^2 - x^2 for each pair of z,x itself will of the size n*(n-1). I am not sure how it will work in O(n) time then. Thanks, - Ravindra On Fri, Oct 14, 2011 at 12:25 AM, Ankur Garg ankurga...@gmail.comwrote: @rahul...How do u choose z and x for computing z^2 -x^2 ? On Thu, Oct 13, 2011 at 11:34 PM, rahul rahul...@gmail.com wrote: You can create a hash with sqrt(z2-x2). This will make it o(n). The interviewer just made it lil tricky. That's all -- 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/-/2Ge2pjt4N-4J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 - Find Pythagorean triplet in an unsorted array
BTW can we solve this by hashing..That is the only feasible solution which comes to my mind to reduce the time complexity ? On Thu, Oct 13, 2011 at 11:20 PM, Ankur Garg ankurga...@gmail.com wrote: Dude this is nothing but 3 sum problem http://en.wikipedia.org/wiki/3SUM Ask interviewer to check this link and say he has gone mad!! :P Regards Ankur On Thu, Oct 13, 2011 at 10:29 PM, ravindra patel ravindra.it...@gmail.com wrote: Hi, Another question I faced in Amazon F2F. Given an unsorted array of integers, find all triplets that satisfy x^2 + y^2 = z^2. For example if given array is - 1, 3, 7, 5, 4, 12, 13 The answer should be - 5, 12, 13 and 3, 4, 5 I suggested below algo with complexity O(n^2) - - Sort the array in descending order. - O(nlogn) - square each element. - O(n) Now it reduces to the problem of finding all triplets(a,b,c) in a sorted array such that a = b+c. The interviewer was insisting on a solution better than O(n^2) which I dont think is feasible, but I couldn't prove that. Anyone has any idea. Thanks, - Ravindra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 - Find Pythagorean triplet in an unsorted array
Dude this is nothing but 3 sum problem http://en.wikipedia.org/wiki/3SUM Ask interviewer to check this link and say he has gone mad!! :P Regards Ankur On Thu, Oct 13, 2011 at 10:29 PM, ravindra patel ravindra.it...@gmail.comwrote: Hi, Another question I faced in Amazon F2F. Given an unsorted array of integers, find all triplets that satisfy x^2 + y^2 = z^2. For example if given array is - 1, 3, 7, 5, 4, 12, 13 The answer should be - 5, 12, 13 and 3, 4, 5 I suggested below algo with complexity O(n^2) - - Sort the array in descending order. - O(nlogn) - square each element. - O(n) Now it reduces to the problem of finding all triplets(a,b,c) in a sorted array such that a = b+c. The interviewer was insisting on a solution better than O(n^2) which I dont think is feasible, but I couldn't prove that. Anyone has any idea. Thanks, - Ravindra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Give Algo to do this in O(n)
@Sravan ..Counting Sort takes O(n) time but it needs range of nos to be known @Snehi jain..there is no range given so am not sure if count sort will work ,Can you please elaborate a bit on ur method Ankur On Mon, Oct 10, 2011 at 10:09 PM, sravanreddy001 sravanreddy...@gmail.comwrote: Just went throught what a count sort is at http://en.wikipedia.org/wiki/Counting_sort If all the elements are distinct which is possible, will this count sort have any use? Also, the sorting takes O(nlogn) time right? Did I miss anything? -- 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/-/08bcRsmFYJgJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Memorization
Memoization ? On Mon, Oct 10, 2011 at 6:34 PM, arvind kumar arvindk...@gmail.com wrote: Can anyone tell me how to go about with the memorization technique to retrieve values from already stored values,in case of eveluating sequences(fibonacci series,etc).? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] remove duplicate words from a string
I think this can be done through tries Any better solution ? On Mon, Oct 10, 2011 at 10:59 PM, sachin goyal monugoya...@gmail.comwrote: remove duplicate words from a string with min. complexityy. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] remove duplicate words from a string
@Sunny..How do u intend to store them in a Tree ? Can you explain ? In a trie u first insert the first word ..take the second word..If its not present in the trie u insert it else remove it from original string .Alternatively u store the elements in a trie in the initial string and terminate it with '\0' and return it . In the worst case trie will take O(n) space where n is the no of letters in the string . and Traversal and creation and search too will take O(n). How abt Balanced Binary Tree ? On Tue, Oct 11, 2011 at 12:38 AM, sunny agrawal sunny816.i...@gmail.comwrote: Trie will take too much space.. Balanced Binary tree can be Better ...?? On Tue, Oct 11, 2011 at 12:16 AM, Ankur Garg ankurga...@gmail.com wrote: I think this can be done through tries Any better solution ? On Mon, Oct 10, 2011 at 10:59 PM, sachin goyal monugoya...@gmail.comwrote: remove duplicate words from a string with min. complexityy. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] i cannot solve this written test question
Is it sum of bits or sum of digits ? On Sun, Oct 9, 2011 at 1:39 PM, wujin chen wujinchen...@gmail.com wrote: Given a positive number N, find a minimum number M greater than N, M has the same length with N and the sum of the bits are equal. example: N=134 , M=143, // 1+3+4=1+4+3 N=020, M = 101, //2=1+1 the length of N is less than 1000. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Give Algo to do this in O(n)
Given an unsorted array of Integers Find 2 nos whose diff is minimum Say Array is 4 2 18 19 11 8 5 Nos are 18 and 19 Algo shud be of O(n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Algo for Search in a 2D Matrix
Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Attention All Members
+1 On Sun, Oct 9, 2011 at 2:07 AM, Sunny sunny816.i...@gmail.com wrote: Now All of the messages are being Moderated and will be posted on the group only if they are found relevant, any irrelevant post be simply discarded without any notification till percentage of irrelevant posts reduces by a significant amount. if someone is found posting too many irrelevant post, he/she will be banned. Irrelevant Posts 1. Any Company Interview Question (Except Google, Facebook only) 2. Any Code Debugging Post (of type Plz Debug my code You should be able to do it yourself) 3. any kind of C/C++ output question. 4. Any Company related Queries 5. Any Book Requests 6. Any Post having No subjects. (if Subject are there they must be related and Give idea about the post. and again Don't post the complete Question in the subject. it should be posted in the body of the message) + Any OS compiler or other topics unless it requires some good Quality discussion. All the above types of post (Except 6) are now part of new group Interview Street (search Archives for the link). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Efficient Algo for Merging 2 Binary Search Trees
Hi , Can anyone think of any better for doing this other than converting into List and then converting back again to BST .. Regards -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Deletion in AVL tree
Can anyone suggest a pseudocode handling rotations in an AVL tree for deleting a node I couldnt find one in the internet and was unable to derive a proper logic which cud be transformed into code :( -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Algo for in-place Stack Reversal.
To do inplace stack reversal u need a mechanism by which u can transfer the
first node to last of the stack making sure u have count of other nodes
here
Say u have stack
5- top
4
3
2
1
The answer should generate the stack as
1-top
2
3
4
5
This give hints to recursion . A normal recursive func willlook like
InplaceReverse(stackints){
if(s.empty()) return;
temp=s.top();
s.pop();
InplaceReverse(s);
}
Now if one had to print the stack nodes from bottom to top this would have
helped as we get to bottom of stack.But we need a storing mechanism so may
be one more recursive function can help so that we can pop the nodes first
and then insert the top node
Say the stack at a pt of time is
1-top
2
Then to insert 3 at bottom we shud have some mechanism which can store
values 1 and 2
So u pop 1 and pop 2 ..Insert 2 and then Insert 1
1- top
2
3
Only way to achieve this without using extra space is another recursion .So
I write a helper func which can help me here to achieve this. I call this
helper Func as something like ReverseHelper and push the temp variable to it
.
So
InplaceReverse(stackints){
if(s.empty()) return;
temp=s.top();
s.pop();
InplaceReverse(s);
ReverseHelper(s,temp);
}
ReverseHelper(stackints,int val){
if(s.empty()) {
s. push(val);
return;
}
temp = s.pop();
ReverseHelper(s,val);
s.push(temp);
}
Remember to pass stack as reference
Regards
Ankur
}
On Fri, Oct 7, 2011 at 7:54 PM, sravanreddy001 sravanreddy...@gmail.comwrote:
in place means:
use constant extra space
in simple terms O(1) space
--
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/-/nDVS4k7fF34J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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,microsoft link list probs
Implement recursive merge sort for first question For second just swap the values of node and node b On Wed, Oct 5, 2011 at 9:18 PM, 9ight coder 9ightco...@gmail.com wrote: 1.perform inplace(we cant create new node)merge sort of two sorted linked list.(asked in amazon 1 mon before) 2.a-b-c-d-e convert to b-a-d-c-e without creating new node. (asked in microsoft on 4rth oct at thapar). sugeest solutions. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Ques
Find out the smallest segment in a document containing all the given words. Desired Complexity is O nlogK ..n is the total no of words in the document and k is the number of input words -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] suggestion
Nice Idea but for pulling this you need committed people :) On Mon, Oct 3, 2011 at 7:36 PM, sukran dhawan sukrandha...@gmail.comwrote: Hello guys, Here is a suggestion.With so much talented people in this group,why cant we a website that is similar to geeksforgeeks. It will be really helpful to others if all the topics are well organised in the form of website This is just a suggestion.just ignore the message if im wrong or u guys don like the idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] suggestion
Committed to launch a website,formatting ..clarifying in case you mistook it for somethin else :D On Mon, Oct 3, 2011 at 7:50 PM, Ankur Garg ankurga...@gmail.com wrote: Nice Idea but for pulling this you need committed people :) On Mon, Oct 3, 2011 at 7:36 PM, sukran dhawan sukrandha...@gmail.comwrote: Hello guys, Here is a suggestion.With so much talented people in this group,why cant we a website that is similar to geeksforgeeks. It will be really helpful to others if all the topics are well organised in the form of website This is just a suggestion.just ignore the message if im wrong or u guys don like the idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Can Any1 provide a proper implementation of a Hashtable(Seperation Chaining) in C,C++
-- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Urgent sol needed
Many times this problem has been discussed ..Please check the archives yaar
:(
On Mon, Oct 3, 2011 at 11:39 PM, Shruti Gupta shruti.gupt...@gmail.comwrote:
I had inserted 0 instead of 1 The corrected code will be:
public static void setZeros(int[][] matrix) {
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i matrix.length; i++) {
for (int j = 0; j matrix[0].length;j++) {
if (matrix[i][j] == 1) {
row[i] = 1;
column[j] = 1;
}
}
}
// Set arr[i][j] to 0 if either row i or column j has a 0
for (int i = 0; i matrix.length; i++) {
for (int j = 0; j matrix[0].length; j++) {
if ((row[i] == 1 || column[j] == 1)) {
matrix[i][j] = 1;
}
}
}
On Oct 3, 11:06 pm, Shruti Gupta shruti.gupt...@gmail.com wrote:
Hi!
A effecient way to solve the problem in O(1) space is by making use of
the fact that instead of keeping track of which cell has a 0, we can
just know which row or column has zero, as eventually that row/col
will become 0. The code looks like this:
public static void setZeros(int[][] matrix) {
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i matrix.length; i++) {
for (int j = 0; j matrix[0].length;j++) {
if (matrix[i][j] == 0) {
row[i] = 1;
column[j] = 1;
}
}
}
// Set arr[i][j] to 0 if either row i or column j has a 0
for (int i = 0; i matrix.length; i++) {
for (int j = 0; j matrix[0].length; j++) {
if ((row[i] == 1 || column[j] == 1)) {
matrix[i][j] = 0;
}
}
}
Thus there is no extra space taken.
Shruti
On Oct 3, 12:27 am, rahul sharma rahul23111...@gmail.com wrote:
nput is a matrix of size n x m of 0s and 1s.
eg:
1 0 0 1
0 0 1 0
0 0 0 0
If a location has 1; make all the elements of that row and column = 1.
eg
1 1 1 1
1 1 1 1
1 0 1 1
Solution should be with Time complexity = O(n*m) and O(1) 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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] rise and fall of power
Keep an array to store multiplication of numbers like for input 9 3 U have to compute 9^9 So an array to store the digits and do simple multiplication like 9*9 will give 81 so Array will have 81 then 81*9 729 ..so on Then output the first k digits and last k digits of the array Any1 having a better solution ? On Mon, Oct 3, 2011 at 11:48 PM, g4ur4v gauravyadav1...@gmail.com wrote: can anyone please help me on how to approach this problem= http://www.codechef.com/problems/MARCHA4 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: string compress/expand
Code for Compression
I am doing it inplace
void convert(char* s,int len){
int i=0;
int count=1;
int index=1; //*maintain the index where number is to be added*
for(i=1;i=len;i++){
if(s[i]==s[i-1])
count++;
else{
s[index-1]=s[i-1];*//put the char first like a3abbb . then this
step converts it into a3*
s[index]= (count+'0');/*/convert the count integer into char so
it becomes a3b4bb*
count=1;
index = index+2;
}
}
s[index-1]='\0'*;//terminate the string* *(a3b4bb will become a3b4)*
}
On Mon, Oct 3, 2011 at 12:12 PM, rahul sharma rahul23111...@gmail.comwrote:
check my code for compression..
check if it is ok
abc i/p
o/p abc
means if character has no count.but still present in string it is its only
occurance.plz check that code...
#includeiostream.h
#includeconio.h
int main()
{
cout\nenter the string;
char str[30];
cinstr;
int c=1;
for(int i=0;str[i];i++)
{
if(str[i+1]='0' str[i+1]='9')
{
c=c+(str[i+1]-'0');
for(int j=1;jc;j++)
coutstr[i];
i++;
}
else
coutstr[i];
c=1;
}
getch();
}
On Mon, Oct 3, 2011 at 12:08 PM, Rahul Verma rahulverma@gmail.comwrote:
@rahul sharma
for that you have to check that string is alphanumeric or not. if it is
alphanumeric then you have to call the function exapansion else you have to
call the compression function.
and
if the desired output for *abc *is *a1b1c1* then you have to call the
*exapnsion
function* or if the desired output is *abc* then you have to add a
feature in the *compression function* i.e. in output the string have to
omit the 1's
--
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/-/8olzJ_YJVWMJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Imp-Amazon Question
Define a data structure , using extra memory/space , such that : Insert(int a) Delete(int a) isPresent(int a) get(int a) All above operations on the defined data structure take O(1) , i.e. constant time. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Imp-Amazon Question
Can u provide a proper HashMap Not Implementation..A proper Idea wud do :) On Mon, Oct 3, 2011 at 1:03 AM, Preetam Purbia preetam.pur...@gmail.comwrote: you can implement using hashmap.. On Mon, Oct 3, 2011 at 12:51 AM, Ankur Garg ankurga...@gmail.com wrote: Define a data structure , using extra memory/space , such that : Insert(int a) Delete(int a) isPresent(int a) get(int a) All above operations on the defined data structure take O(1) , i.e. constant time. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Preetam Purbia http://twitter.com/preetam_purbia -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] urgent soln needed
@Rahul
Scan the matrix and whenver u see a[i][j]=0 put a[i]]0]=0 and a[0][j]=0
Meaning to say that put that row or column as 0
Now,
Scan the first row and first column and whereever u see a 0 make that column
and row 0 respectively
Eg
1 1 1 1
0 1 0 1
1 1 1 0
Answer shud be
0 1 0 0
0 0 0 0
0 0 0 0
Scan Array First After Scanning it become
0 1 0 0
0 1 0 1
0 1 1 1
Now Scan first row and for a[0][j] make a[i][j] 0
so
0 1 0 0
0 1 0 0
0 1 0 0
Now scan column ..Remember to start from a[1][0] and a[0][1]
0 1 0 0
0 0 0 0
0 0 0 0
Hope it helps
Ankur
On Fri, Sep 30, 2011 at 3:47 PM, rahul sharma rahul23111...@gmail.comwrote:
provide me with o(1) space ...i need it vey urgent.can it be
done...thnx in advance.
On Fri, Sep 30, 2011 at 3:44 PM, rahul sharma rahul23111...@gmail.comwrote:
sorry n*m complex where n rows and m col
but correct for space pzl and it uses two xtras array row and col
On Fri, Sep 30, 2011 at 3:42 PM, rahul sharma rahul23111...@gmail.comwrote:
i cant find xact soln on previous threadi have sol with n*n
complexity but used space,, i.e
scan whole matrix
if( matrix([i][j]==1)
{
row[i]=1;
col[j]=1;
}
scan agin
if(row[i]==1 ||| col[j]==1)
matrix[i][j]=0;
two n*n loops so takes n*n and uses space too plz give me opt. soln
On Fri, Sep 30, 2011 at 3:08 PM, Yogesh Yadav medu...@gmail.com wrote:
Already discussed
https://groups.google.com/group/algogeeks/browse_thread/thread/8a3e1a6665702f54/66bb2e804b43ae1d?hl=enlnk=gstq=MS+question+ankur#66bb2e804b43ae1d
.
On Fri, Sep 30, 2011 at 2:59 PM, sumit kumar pathak
sumitkp1...@gmail.com wrote:
*find all the zeros in first iteration and store (size = array bool
[2n])*
*and then make zero. *
*time = O(n^2)*
*space = O(n)*
*
*
*case 2:*
* if any zero whole matrix zero, (once we get a zero its row and
column will become zero which in turn lead to whole matrix being zero).
*
*
*regards
- Sumit Kumar Pathak
(Sumit/ Pathak/ SKP ...)
*Smile is only good contagious thing.*
*Spread it*!
On Fri, Sep 30, 2011 at 2:38 PM, rahul sharma rahul23111...@gmail.com
wrote:
it will zero only row not column
On Fri, Sep 30, 2011 at 12:25 PM, Tamanna Afroze afroze...@gmail.com
wrote:
if(matrix[i][j]==0){
for(int j=0;jn;j++)
matrix[i][j]=0;
}
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon - array problem
Is the array Sorted ?
On Thu, Sep 29, 2011 at 4:56 PM, raju nikutel...@gmail.com wrote:
Given an integer array. { 1,2,3,4,5 }
Compute array containing elements
120,60,40,30,24 (2*3*4*5,1*3*4*5, 1*2*4*5, 1*2*3*5, 1*2*3*4)
We shouldn't use division operator( / )
Time complexity O(n) .. Space complexity O(1)
~raju
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] MS Question - Median of a BST without using extra space and in O(n)
I was thinking of making the tree balanced with equal no of nodes in left and right subtree Median will be root in this case Regards Ankur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MS Question - Median of a BST without using extra space and in O(n)
@Anshu Will u be using extra space to store ur nodes in traversal ? On Tue, Sep 27, 2011 at 2:22 PM, anshu mishra anshumishra6...@gmail.comwrote: do the inorder traversal as soon as reached at n/2th element that will be median. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] How to height balance a binary search tree ?
L , R ,LR , RL rotations On Tue, Sep 27, 2011 at 10:35 PM, sukran dhawan sukrandha...@gmail.comwrote: avl tree On Tue, Sep 27, 2011 at 10:15 PM, Ankuj Gupta ankuj2...@gmail.com wrote: Given a bst how to height balance it ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Amazon Ques
Print Reverse of linked list (dont reverse it) with only constant space. Recursion uses stack spaceO(n) ..so post some other solution .. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] MS question
Saw this question in one of the algo communities. Amazon telephonic interview question on Matrix Input is a matrix of size n x m of 0's and 1's. eg: 1 0 0 1 0 0 1 0 0 0 0 0 If a location has 1; make all the elements of that row and column = 1. eg 1 1 1 1 1 1 1 1 1 0 1 1 Solution should be with Time complexity = O(n*m) and space complexity = O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
