[algogeeks] Re: stacks
Well. the idea of an array is - given an integer 'i', you should support RANDOM ACCESS to the ith element in the 1d array. Since, we have two stacks, if you want to access an ith element ( say, i = 5 ),pop all the top 4 elements from the 1st stack and push it to the second stack. Now, access the 5th element on top of the 1st stack, then, pop the elements from the 2nd stack back and push them to the 1st stack. However, access is O(n) due to the inherent property of a stack which forbids random access! On Jul 23, 2:00 pm, Kamakshii Aggarwal kamakshi...@gmail.com wrote: consider a language that does no have arrays...but u can define stack data type like stack s; using pop ,push and other operations on 2 stacks,how can one dimensions array can be implemented?? -- Regards, Kamakshi kamakshi...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MS
@akshata sharma:
Kindly post a new question as a separate thread and not as a reply to
an existing one so tat it would be noticed by many ppl!
As akash suggestd, use a bit vector called 'visited' of 26 size for
ASCII or of a larger size in case of Unicode ( still constant space
and i dont think declaring 26 variables counts as an additional DS!!),
if visited then , ignore the character while processing.
a simple algorithm,
int last_ptr=0;
for ( i = 0 - N )
{
if(visited(a[i])) continue;
else a[last_ptr++]=a[i];
visited(a[i]) = true;
}
a[last_ptr]=NULL;
print (%s,a) ;
On Jul 23, 12:56 pm, Akshata Sharma akshatasharm...@gmail.com wrote:
better than O(n^2)..
On Sat, Jul 23, 2011 at 1:08 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:
Given a string *Str of ASCII characters, write the pseudo code to remove
the duplicate elements present in them. For example, if the given string is
Potato, then, the output has to be Pota. Additional constraint is, the
algorithm has to be in-place( no extra data structures allowed) . Extend
your algorithm to remove duplicates in the string which consisted of UNICODE
characters.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sum to K problem
@navneet: good one.. In my above explanation, u could keep track of
back pointers
so that u may want to print the subset containing the sum..
On Jul 2, 11:54 am, Navneet Gupta navneetn...@gmail.com wrote:
Wrote the code for same.
#includeiostream
using namespace std;
int max(int a,int b)
{
if(ab)
return a;
else
return b;
}
int main()
{
int n,k;
cout\nEnter the count of numbers :;
cinn;
//Set of Elements
cout\nEnter the elements :;
int *A;
A = new int[n];
for(int i = 0; in; i++)
cinA[i];
//Input Sum Value
cout\nEnter the value of k :;
cink;
//Matrix for holding boolean values for subproblems (max subproblems
upto nk)
int **M;
M = (int **)new int[n];
for(int i=0; in; i++)
M[i] = new int[k+1];
//Populate all the values to false
for(int i=0; in; i++)
for(int j=0; j=k; j++)
M[i][j] = 0;
for(int i=0; in; i++)
M[i][0] = true;
for(int i=1; in; i++)
for(int j=0; j=k; j++)
if(j-A[i]=0)
{
M[i][j] = max(M[i-1][j], M[i-1][j-A[i]]);
}
if(M[n-1][k] == 1)
cout\nPossible Subset present;
else
cout\nPossible Subset not present;
cin.get();
return 0;
}
On Fri, Jun 24, 2011 at 11:42 PM, ross jagadish1...@gmail.com wrote:
This is the subset sum problem which is NP,.
The DP is as follows,
M[i,j] = 1 , if a subset of first i elements has a sum = j.
else 0,
The recurrence is,
M[i,j] = max(M[i-1,j] , M[i-1,j-Ai]) where Ai is the ith element.
You can maintain back pointers to keep track of previous elements so
that
the solution can be reconstructed from the DP.
Once this matrix is populated till sum=k, Then, the column
corresponding to sum=k, gives
the answer. complexity o(nk).
On Jun 20, 6:38 pm, Harshal hc4...@gmail.com wrote:
The problem is NP. Complexity using DP will be O(nk), where n is number of
elements and k is required sum.
S[0]=true; //choose no element
S[1...k] = false;
for each number i in your input
for s = k downto i
if ( S[s - i] == true )
S[s] = true;
S[s] = true indicates a sum of i can be obtained from a subset of the set.
To get the elements, we can make S[s] contain the list of numbers that
contain the sum.
On Mon, Jun 20, 2011 at 6:53 PM, Navneet Gupta
navneetn...@gmail.comwrote:
Ideally, yes it can. Though i would be happy even if someone gives a
good answer for non-negative values.
On Mon, Jun 20, 2011 at 6:28 PM, Akshata Sharma
akshatasharm...@gmail.com wrote:
@Navneet: does the set contains negative elements also?
On Mon, Jun 20, 2011 at 12:26 PM, pacific :-) pacific4...@gmail.com
wrote:
@vaibhav : Please note that more than two numbers can sum upto k.
On Mon, Jun 20, 2011 at 12:21 PM, vaibhav shukla
vaibhav200...@gmail.com
wrote:
sort the array using merge sort : order nlogn
take the first element,subtract it with 'k' , then search the result
using binary search in rest of the array : order nlogn
hence u get two elements which sum up to K in order nlogn
On Mon, Jun 20, 2011 at 12:14 PM, Navneet Gupta
navneetn...@gmail.com
wrote:
Right, in the worst case, complexity with be O(2^N).
So what are the possible optimizations here? Would building
pre-computed
data structures with intermediate sum values help in finding such
pairs in
less complexity? I think then we can apply dynamic programming to
find
such
pairs.
On Mon, Jun 20, 2011 at 12:09 PM, oppilas .
jatka.oppimi...@gmail.com
wrote:
I think its a NP problem. The solution complexity can go up O(2^N)
in
worst case.
On Mon, Jun 20, 2011 at 11:55 AM, Navneet Gupta
navneetn...@gmail.com
wrote:
Given a set of integers , find a set of numbers such that they sum
to
a given number k .
Notice the set of numbers can have 2 or more than 2 numbers.
--Navneet
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr
[algogeeks] Re: Queue to support insert , delete, find max in o(1)
@Divye: Awesome solution dude with amortized complexity of O(1)! The examples made things even clearer :) On Jun 26, 8:13 am, DK divyekap...@gmail.com wrote: I've solved it for find_min() - the find_max implementations are analogous. Example: i = insert d = delete i 1 - q - 1 dq - 1 -- min value i 2 - q - 1 2 dq - 1 2 (min value = 1) d - q - 2 dq - 2 -- Note: min value changed i 0 - q - 2 0 dq - 0 -- Note: min value changed Hope this makes things even clearer. :) As for the bonus part. Let me know if you need an example. :) -- DK http://twitter.com/divyekapoorhttp://www.divye.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.
[algogeeks] Sorting Array
Given a sequence of numbers in the range of 1-N^2, what is the most efficient way to sort the numbers (better than NlgN).. Can counting sort be used here? Is an O(N) solution possible.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting Array
@radhakrishnan: Counting sort in this case, will be O(n2).. as it involves traversing the entire array! On Jun 26, 5:03 pm, L prnk.bhatna...@gmail.com wrote: Count sort is O(n+k), since k~n^2 here, it will be O(N^2). Radix sort has complexity O(r.n) which is nearly O(n logn). Are you sure that the person asking this question wanted O(n) ? On Jun 26, 1:31 pm, radha krishnan radhakrishnance...@gmail.com wrote: Yes ! Count Sort !! On Sun, Jun 26, 2011 at 1:44 PM, ross jagadish1...@gmail.com wrote: Given a sequence of numbers in the range of 1-N^2, what is the most efficient way to sort the numbers (better than NlgN).. Can counting sort be used here? Is an O(N) solution possible.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting Array
@L: It was asked if we could take advantage of the ranges of the integers between 1-N^2.. I doubt if its possible. On Jun 26, 5:33 pm, ross jagadish1...@gmail.com wrote: @radhakrishnan: Counting sort in this case, will be O(n2).. as it involves traversing the entire array! On Jun 26, 5:03 pm, L prnk.bhatna...@gmail.com wrote: Count sort is O(n+k), since k~n^2 here, it will be O(N^2). Radix sort has complexity O(r.n) which is nearly O(n logn). Are you sure that the person asking this question wanted O(n) ? On Jun 26, 1:31 pm, radha krishnan radhakrishnance...@gmail.com wrote: Yes ! Count Sort !! On Sun, Jun 26, 2011 at 1:44 PM, ross jagadish1...@gmail.com wrote: Given a sequence of numbers in the range of 1-N^2, what is the most efficient way to sort the numbers (better than NlgN).. Can counting sort be used here? Is an O(N) solution possible.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting Array
@Rujin Cao: Yea, your formulation of the problem is correct.. my bad,. missed that there are N numbers. can u elaborate more on the discretization procedure and how ll u do counting sort (which might warrant traversing of N^2 elements) On Jun 26, 5:45 pm, Rujin Cao drizzle...@gmail.com wrote: @ross: I guess the orignal problem is that there are N numbers which are all in the range [1, N * N], can you do the sorting in O(N) time complexity? If this is true, we can firstly do the discretization and then do the counting sort. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Product of N numbers - with Constraints
Given an array A , of N integers ( In no particular order), fill up an auxilary array B such that B[i] contains the product of all elements in A other than A[i]. Constraints: O(n) Time, Can this be done with O(1) space? Division is *not* allowed . eg: A 1 2 3 4 5 B 120 60 40 30 24 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting Array
@Divye: Good theoretical proof and analysis as well.. As you
mentioned, this one works like charm for uniformly distributed
inputs :)
On Jun 26, 8:36 pm, DK divyekap...@gmail.com wrote:
Use a radix sort.
Complexity of the radix sort is O(N k) where k is the number of digits used
to represent the number in some base b.
If we use the convenient fiction that both N and N^2 fit into the same 32
bit integer then
k is a constant and we get an O(N) sort. (It's kindof cheating :) ).
Okay, since we don't want to cheat on this one, keep reading below: :)
Another method is to divide the Numbers into N bins of size N numbers.
Eg. Bin 1 = 1 to N, Bin 2 = N+1 to 2N ...
Assuming uniform distribution, the bins will have N/N ~ 1 element each.
If the distribution is non-uniform then no bin will have more than N
elements.
For small bins, apply a variant of insertion sort (which performs faster
than O(n log n) sorts for 12 elements) and if N is large, will perform
much faster than counting sort.
For large bins, apply an O(n log n) sort or radix sort or counting sort.
(make a choice depending on number of elements in the bin. eg. Num_elements
~ N then choose counting sort, else choose radix or O(n log n) sorts)
Complexity analysis:
1. No bin will have more than N elements.
2. No bin while being sorted will have a range N.
If the data distribution is uniform, the solution will be very very quick
(order of N) as the sorting time for bins with just 2 to 3 elements is
approximately O(num_elements) ~ O(1) and number of such bins is O(N).
If the data distribution is non-uniform, then complexity will depend on the
number of bad bins and the size of bad bins.
Let K bins be bad. Here, K is a value dependent on data distribution of the
input.
If K is small, number of elements per bin is large - apply counting sort on
the bins - complexity O(K N) which is approximately O(N)
If K - log N, apply an O(N log N) sort to the bins - complexity O( K * N/K
log (N/K)) - O(N log (N/log N))
If K log N but K N, worst case - complexity Sum over K bins{min{O(Ni
log (Ni)), O(N)}} (you can cheat this to O(N) by using something like radix
sort)
If K - N - Not possible as you won't have that many bad bins as the number
of elements per bin will approach 1.
So, in short, you can get a complexity of the kind O(N log (N/log N)) which
is slightly better than O(N log N).
Hope this helps!
--
DK
http://twitter.com/divyekapoorhttp://www.divye.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.
[algogeeks] Re: Product of N numbers - with Constraints
@Dave: Very good solution.. I had thought an idea of using separate
arrays to store next and previous products. And multiplying the
elements of the 2 arrays to give B. The solution given by you
satisfies ALL constraints inplace :)
@sameer: Your solution is not O(1) in space dude..Dave's solution is
good.
On Jun 26, 9:47 pm, Ashish Goel ashg...@gmail.com wrote:
this is goog question
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, Jun 26, 2011 at 10:04 PM, Dave dave_and_da...@juno.com wrote:
@Ross: This satisfies your constraints...
B[0] = 1;
for( i = 1 ; i N ; ++i )
B[i] = B[i-1] * A[i-1];
int x = 1;
for( i = N-1 ; i 0 ; --i )
{
x *= A[i];
B[i-1] *= x;
}
Dave
On Jun 26, 11:08 am, ross jagadish1...@gmail.com wrote:
Given an array A , of N integers ( In no particular order), fill up an
auxilary array B such that B[i] contains the product of
all elements in A other than A[i].
Constraints:
O(n) Time,
Can this be done with O(1) space?
Division is *not* allowed .
eg: A 1 2 3 4 5
B 120 60 40 30 24
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Queue to support insert , delete, find max in o(1)
Hi, I know that a stack can be modified with another stack to support push pop min in const time. Design a FIFO data structure to support ins, del, and find min in O(1). Extra space allowed. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Queue to support insert , delete, find max in o(1)
@piyush, Dude, how will that make findmin() to be O(1) because, once the minimum element is deleted, u would require changes in the others .. Correct me if i am wrong.. Eg: consider inserting, 1 5 6 7 9 in order into the circular LL. When u make each node keep track of the minm before it, all will retain 1 as minm.. Now consider deleting 1. how will that affect the rest of the list? On Jun 24, 3:07 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: Can we use circular linked list with each new inserted node keeping track of the minimum before it?? On Fri, Jun 24, 2011 at 3:20 PM, ross jagadish1...@gmail.com wrote: Hi, I know that a stack can be modified with another stack to support push pop min in const time. Design a FIFO data structure to support ins, del, and find min in O(1). Extra space allowed. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Queue to support insert , delete, find max in o(1)
@Piyush: Dude, that method u suggested wont work ... It works for stacks because, while deletion of an element, We may verify if it is in the top of second stack and delete it.. (Since both the data structures are LIFO) Here in this case, if u delete, you cannot remove the top of stack and delete an element in the queue... eg: 1 22 3 44 stack contains(minnm) : 1 if u delete 1, then u pop it from the stack and minm must be 2 I doubt if this problem has a solution. Correct me if i am wrong. On Jun 24, 3:33 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: ohh sorry, my bad..I missed that issue...then we can use the same logic of using one more stack that we use for implementing modified stack keeping track of the min()..I hope this will solve the issue On Fri, Jun 24, 2011 at 3:57 PM, ross jagadish1...@gmail.com wrote: @piyush, Dude, how will that make findmin() to be O(1) because, once the minimum element is deleted, u would require changes in the others .. Correct me if i am wrong.. Eg: consider inserting, 1 5 6 7 9 in order into the circular LL. When u make each node keep track of the minm before it, all will retain 1 as minm.. Now consider deleting 1. how will that affect the rest of the list? On Jun 24, 3:07 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: Can we use circular linked list with each new inserted node keeping track of the minimum before it?? On Fri, Jun 24, 2011 at 3:20 PM, ross jagadish1...@gmail.com wrote: Hi, I know that a stack can be modified with another stack to support push pop min in const time. Design a FIFO data structure to support ins, del, and find min in O(1). Extra space allowed. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sum to K problem
This is the subset sum problem which is NP,. The DP is as follows, M[i,j] = 1 , if a subset of first i elements has a sum = j. else 0, The recurrence is, M[i,j] = max(M[i-1,j] , M[i-1,j-Ai]) where Ai is the ith element. You can maintain back pointers to keep track of previous elements so that the solution can be reconstructed from the DP. Once this matrix is populated till sum=k, Then, the column corresponding to sum=k, gives the answer. complexity o(nk). On Jun 20, 6:38 pm, Harshal hc4...@gmail.com wrote: The problem is NP. Complexity using DP will be O(nk), where n is number of elements and k is required sum. S[0]=true; //choose no element S[1...k] = false; for each number i in your input for s = k downto i if ( S[s - i] == true ) S[s] = true; S[s] = true indicates a sum of i can be obtained from a subset of the set. To get the elements, we can make S[s] contain the list of numbers that contain the sum. On Mon, Jun 20, 2011 at 6:53 PM, Navneet Gupta navneetn...@gmail.comwrote: Ideally, yes it can. Though i would be happy even if someone gives a good answer for non-negative values. On Mon, Jun 20, 2011 at 6:28 PM, Akshata Sharma akshatasharm...@gmail.com wrote: @Navneet: does the set contains negative elements also? On Mon, Jun 20, 2011 at 12:26 PM, pacific :-) pacific4...@gmail.com wrote: @vaibhav : Please note that more than two numbers can sum upto k. On Mon, Jun 20, 2011 at 12:21 PM, vaibhav shukla vaibhav200...@gmail.com wrote: sort the array using merge sort : order nlogn take the first element,subtract it with 'k' , then search the result using binary search in rest of the array : order nlogn hence u get two elements which sum up to K in order nlogn On Mon, Jun 20, 2011 at 12:14 PM, Navneet Gupta navneetn...@gmail.com wrote: Right, in the worst case, complexity with be O(2^N). So what are the possible optimizations here? Would building pre-computed data structures with intermediate sum values help in finding such pairs in less complexity? I think then we can apply dynamic programming to find such pairs. On Mon, Jun 20, 2011 at 12:09 PM, oppilas . jatka.oppimi...@gmail.com wrote: I think its a NP problem. The solution complexity can go up O(2^N) in worst case. On Mon, Jun 20, 2011 at 11:55 AM, Navneet Gupta navneetn...@gmail.com wrote: Given a set of integers , find a set of numbers such that they sum to a given number k . Notice the set of numbers can have 2 or more than 2 numbers. --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- best wishes!! Vaibhav Shukla DU-MCA -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, chinna. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- --Navneet -- You received this message because you are subscribed to the Google Groups
[algogeeks] Sort - Consecutive Array in O(n)
Given an array, A, find if all elements in the sorted version of A are consecutive in less than O(nlogn). eg: A: 5 4 1 2 3 on sorting 1 2 3 4 5 all elements are consecutive -- true A: 1 9 2 22 on sorting 1 2 9 22 all elements are NOT consecutive - false -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sort - Consecutive Array in O(n)
One solution would be to : check if max-min = N and that all elements are unique in the array. However, this may require space complexity.. Looking for a better solution. On Jun 25, 12:44 am, ross jagadish1...@gmail.com wrote: Given an array, A, find if all elements in the sorted version of A are consecutive in less than O(nlogn). eg: A: 5 4 1 2 3 on sorting 1 2 3 4 5 all elements are consecutive -- true A: 1 9 2 22 on sorting 1 2 9 22 all elements are NOT consecutive - false -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Question on Combination
@Piyush: Awesome solution dude!
To avoid repetitions you had started the recursion from the current
index instead of zero.
On Jun 23, 11:01 am, Piyush Sinha ecstasy.piy...@gmail.com wrote:
sorry a lil bit modification in the above answer..
*int ref[] = {1,2,3};*
*void printcombination(int n,int index,int i)*
*{*
* static int a[100];*
* int j;*
* if (n == 0)*
* {*
* for(j=0;jindex;j++)*
* printf(%d ,a[j]);*
* printf(\n);*
* }*
* else if(n0)*
* {*
* for(j=i;j3;j++)*
* {*
* a[index]=ref[j];*
* printcombination(n-ref[j],index+1,j);*
* }*
* }*
*} *
*main()*
*{*
* int n;*
* printf(enter value of n :);*
* scanf(%d,n);*
* printcombination(n,0,0);*
*}*
On Thu, Jun 23, 2011 at 11:17 AM, Piyush Sinha
ecstasy.piy...@gmail.comwrote:
pass one more argument to the function *int index* and instead of
starting the loop from *i = 0 to N, *make it start from *i = index to N *and
then call
*printcombinations(a,sum-a[i],level+1,index+1);
*I think it will work then...
On Thu, Jun 23, 2011 at 10:48 AM, ross jagadish1...@gmail.com wrote:
Given an array and a sum S output all combinations of elements that
sum to S.
eg: 1 2 3
sum = 3
1+1+1,
2+1
3
I came up with the foll algorithm, but it outputs 2+1 and 1+2 again.
(does not handle repetitions)
printcombinations(int a[],int sum,int level) {
if(sum==0) { print array}
else if (sum0) {
for ( i = 0 to N ) {
array[level]=a[i];
printcombinations(a,sum-a[i],level+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.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926*
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: strings
@Harshal,
Even if you use a buffer of size 256 it is still O(1), because 256 is
a constant invariant of n...
Ur solution is correct!
On Jun 22, 10:24 am, Harshal hc4...@gmail.com wrote:
ignore above solution. My bad, did'nt see O(1) space constraint!!
On Wed, Jun 22, 2011 at 10:53 AM, Harshal hc4...@gmail.com wrote:
You can make use of an auxiliary array(initialized to 0) to store the count
of each char and then print it that many times.
char inp[]=abcdaabcdefe;
int buff[256]={0};
for(int i=0;istrlen(inp);i++)
buff[inp[i]]++;
for(int j=0;j256;j++)
while(buff[j]--) cout(char)j;
On Wed, Jun 22, 2011 at 10:27 AM, Sriganesh Krishnan
2448...@gmail.comwrote:
Input will be a string. We need to o/p a string with the order of
characters same as the input but with same characters grouped together.
I/P: abcdacde
O/P: aabccdde
I/P: kapilrajadurga
O/P: kpilrrjdug
I/P: 1232
O/P: 1223 …….. O(n) time……….. O(1) space….
how can you approach these type of string related problems, is there any
specific technique involved?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Harshal Choudhary,
Final Year B.Tech CSE,
NIT Surathkal, Karnataka, India.
--
Harshal Choudhary,
Final Year B.Tech CSE,
NIT Surathkal, Karnataka, India.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sort the array
@himanshu: I dont think, the approach works, in present form. in place merge sort or insertion sort is fine. Test with, 12 13 19 16 and 0 20 10 14 as 2 parts of the array. On Jun 22, 8:42 am, Sriganesh Krishnan 2448...@gmail.com wrote: ya...we can do it in O(n) n time!!! nice question! On Tue, Jun 21, 2011 at 11:01 PM, himanshu kansal himanshukansal...@gmail.com wrote: @anika: yar merge sort vl tk nlogn timeinstead u cn do dt maintain two ptrs one at the beginning and one intitially pointing to middle of the array... thn compare the elemnts pointed by them and swap the values if necesary nd incremnt d ptr as u go on... ths vl tk (n/2)+(n/2)-1 =O(n) time corrct me if m wrong On Tue, Jun 21, 2011 at 10:56 PM, Anika Jain anika.jai...@gmail.comwrote: its like inplace mergesort On Tue, Jun 21, 2011 at 10:13 PM, aanchal goyal goyal.aanch...@gmail.com wrote: you have an array of size n where first n/2 is sorted and the sencond half is sorted . You need to sort the entire array inplace Its second modification version is where first part is sorted and other is NOT sorted . You need to make entire sorted . -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Himanshu Kansal Msc Comp. sc. (University of Delhi) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Question on Combination
Given an array and a sum S output all combinations of elements that
sum to S.
eg: 1 2 3
sum = 3
1+1+1,
2+1
3
I came up with the foll algorithm, but it outputs 2+1 and 1+2 again.
(does not handle repetitions)
printcombinations(int a[],int sum,int level) {
if(sum==0) { print array}
else if (sum0) {
for ( i = 0 to N ) {
array[level]=a[i];
printcombinations(a,sum-a[i],level+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.
[algogeeks] Re: finding vlaue of nCr
Hi,
Ya DP with memoization is best..
nCr= n-1Cr-1 + n-1 C r
DP]i,j] = DP[i-1,j-1] + DP[i-1,j];
(LINEAR SPACE COMPLEXITY is possible because at each time we require
only 2 rows of the matrix)
Base Cases,
nCn = 1. DP[i,i]=1.
1Cn = 1 DP[1,j] =1.
nC1 = n .
nC0 = 1
for ( i = 0 - N )
for ( j= i - N )
{
if(i == j) dp[i.j] =1.
else if (j==1) dp[i j ] = i;
else if (j == 0) dp [ i j] = 1;
else
DP]i,j] = DP[i-1,j-1] + DP[i-1,j];
}
On Jun 21, 1:34 pm, kartik sachan kartik.sac...@gmail.com wrote:
but for big numbers this method is very expensiveand hope
give TLE in 1 sec question where n=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.
[algogeeks] Re: finding vlaue of nCr
A small correction, j = 0 to i.
On Jun 21, 2:01 pm, ross jagadish1...@gmail.com wrote:
Hi,
Ya DP with memoization is best..
nCr= n-1Cr-1 + n-1 C r
DP]i,j] = DP[i-1,j-1] + DP[i-1,j];
(LINEAR SPACE COMPLEXITY is possible because at each time we require
only 2 rows of the matrix)
Base Cases,
nCn = 1. DP[i,i]=1.
1Cn = 1 DP[1,j] =1.
nC1 = n .
nC0 = 1
for ( i = 0 - N )
for ( j= i - N )
{
if(i == j) dp[i.j] =1.
else if (j==1) dp[i j ] = i;
else if (j == 0) dp [ i j] = 1;
else
DP]i,j] = DP[i-1,j-1] + DP[i-1,j];
}
On Jun 21, 1:34 pm, kartik sachan kartik.sac...@gmail.com wrote:
but for big numbers this method is very expensiveand hope
give TLE in 1 sec question where n=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.
[algogeeks] Re: How to remove duplicate element from array in one pass.
@sunny agarwal: Yes, it would be considered constant space.. even if it required 1MB of space . By big oh notation of space, we mean cases where input size, 'n' tends to infinity and the space requirement of the algorithm proposed does not approach infinity. here, even if n-infinity, input size would still be 8kb.. hence O(1) space. hope tat helps. On Jun 13, 12:38 pm, sunny agrawal sunny816.i...@gmail.com wrote: hello all, what if character are not ASCII but are Unicode characters. then we will need 8 KB of memory instead of 32 bytes as in for ASCII's would that also be considered as Constant space( O(1) ) as it is independent of input size ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Mathematical Induction
@howtechstuffworks:
Your question seems to be - why 'k+1' and not 'k+2' or 'k+3' or
something else.
The simple reason is that,
Given that P('k') and P('k+1') is true, we can extend it for ANY value
of k.
(ie) k+2 , can be derived from 'k+1' by substituting k=k+1.
similarly k+3 can be derived from 'K+1' by substituting k=k+1
twice..
The reason thus is that, there ANY INTEGER can be expressed in terms
of its consecutive integer (consecutive - differ by ONE). that is why
k+ 'ONE' is chosen for proving so that the induction works for all
numbers.
(Assuming u prove for P(k+2) as true as in your claim, you cannot
derive P(k+1) as true from these statements by substituting k=k+2..
And if your prove truth for P(2k) as claimed by you, then numbers
which are NOT even, cannot be expressed in the form 2k by substituting
int value for k.)
If you prove P(3k), then numbers which are NOT multiples of 3 cannot
be expressed in the form 3k by substituting integer value for k)
so, k+1 becomes the natural choice so that all possible values greater
than the base case are considered. Hope that helps.
On Jun 13, 9:29 am, HowTechStuffWorks howtechstuffwo...@gmail.com
wrote:
Thanks, Gene. That was an very thoughtful example. I have one more
doubt like, what we are trying to prove here. That the example will
work for all numbers(all natural numbers, not only for an multiple of
two or three or some number) or this example will work for all
possible(infinite) numbers.
Regarding the Trees problem, since the initial value is one and all
the tree down will have an even number of child say 2^i till the leaf.
Isn't it possible to prove based on the theorm, that an odd number +
even number is always an odd number. Also we can reduce it to the form
that number of elements is given by the formula, (2^k-1). 2^anything =
even; even-1 = odd;
If I do by mathematical Induction,
base case : k = 1; value = 1;
kth step : kth step (2^k-1)
k+1th step : (2^k+1)-1 = (2^k.2)-1; what are we
proving here? and how are we verifying it
When I tried to apply some numbers for the value, I came across this
thought.
k = 0; value = 1
k = 3; Value = 8
k+1 = 4 Value = 16 = this can be derived from (2^k+1)-1 = (2^k .
2^1)-1 = (8.2) -1 = 15
But I am not sure how to proceed with the abstract inductive step and
I am not sure what we are trying to prove.
Also why we always want to prove the k+1 th step??? why not k+2th or K
+i th step
Also can you give me some example where the induction fails.
Thank you very much.
On Jun 12, 11:15 pm, Gene gene.ress...@gmail.com wrote:
Suppose you want to prove that you can climb all the way to the top of a
ladder. One way to do this is in two parts: First prove you can stand on
the bottom step. Call this step 1 and number the rest of the steps 2,3,..N
upward to the top of the ladder.
The second part is to prove that if you are on any step K, you know how to
take one step upward to step K+1. (I'm not telling you how to do that here.
But suppose you know how.) This is called the inductive step. (Pun
intended.)
The principle of indication is that these two proof parts taken together
provide the desired proof.
In this case, the proof is constructive. (This isn't always true.) You
effectively get an algorithm for climbing the ladder as a byproduct of
proof: Stand on the first step 1. Now use the inductive step with K=1 to
get to step K+1 = 2. Use it again with K=2 to get to K+1=3. Continue using
N-1 times. This puts you at the top of the ladder.
Note that in computer science you often need more complex kinds of induction
- for example over data structures - rather than integers. For a simple
example, take induction over trees. Prove that complete binary trees (where
all nodes are either leaves or have 2 children) always have an odd total
number of nodes.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Sorting an array - using the foll functions
There is an array in an external system (i.e. u cannot access the array elements directly). The system exposes 3 functions of O(1) - (assume) : length() - returns the length of the array. get(i) - returns the element at index i. reverse(i,j) - reverses the elements in the array from index i to index j (both indexes inclusive). sort the array in the best possible way using only these 3 operations? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting an array - using the foll functions
@aashish,
Yeah, i went through the link, nice one dude! But, i believe even that
would be O(n2).
On Jun 12, 2:42 pm, ross jagadish1...@gmail.com wrote:
@piyush:
Hi piyush,
It is reverse the elements from i to j..
For example, 12 22 33 44 55 66 63
when given reverse (0,2) produces 33 22 12 44 55 66 63.. so on
One very naive approach for this problem would be to use a variant of
bubble sort with a swap flag,
swap=1;
while(swap) {
swap = 0;
for(i=0 to len)
if(get[i]get[i+1]) {reverse (i,i+1); swap=1}
}
But, here the function reverse has just been used to swap and does not
serve its intended purpose..
complexity is O(n2). Any better approach?
On Jun 12, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote:
@rossI have a doubt regarding reverse function...
does it rotate the array or reverse it??
for say it is 12345
reverse(0,4) make it 51234 or 54321???
On 6/12/11, ross jagadish1...@gmail.com wrote:
There is an array in an external system (i.e. u cannot access the
array elements directly).
The system exposes 3 functions of O(1) - (assume) :
length() - returns the length of the array.
get(i) - returns the element at index i.
reverse(i,j) - reverses the elements in the array from index i to
index j (both indexes inclusive).
sort the array in the best possible way using only these 3 operations?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: FOR ALL INDIANS PLZ READ IT
+1 On Jun 12, 3:38 pm, Arpit Sood soodfi...@gmail.com wrote: @present moderators + admin atleast make those people as group moderators along with you who are active. On Sun, Jun 12, 2011 at 3:21 PM, Akshata Sharma akshatasharm...@gmail.comwrote: finally!!! finally!! we have found the group admin! I agree with gaurav, please care to ban people like panzer and other spammers in future. On Sun, Jun 12, 2011 at 10:31 AM, Gaurav Aggarwal 0007gau...@gmail.comwrote: so mr group manager, is this not your responsibility to filter the group messages and remove people like sohail panezar who continuously spam the group?? On Sun, Jun 12, 2011 at 10:15 AM, sharad kumar aryansmit3...@gmail.comwrote: please guys maintain the dignity of the forum...btw I'm the group manager. On Sun, Jun 12, 2011 at 9:17 AM, Priyanshu priyanshuro...@gmail.comwrote: hey harshal, i think u r pretty good in assuming things up.Never did i told all muslims are terrorist nor did i told all pakistanis are terrorist. So STFU. On Sat, Jun 11, 2011 at 8:21 PM, Harshal hc4...@gmail.com wrote: hey Priyanshu, no offence but that's too much dude!! Not all of them are terrorists and many muslims live in our country also! Those who want to give a call, do it, those who don't want, its their choice! But don't spoil the group by commenting irrelevant. And regarding the admin of the group, its Sridhar Ratna, sridharinfin...@gmail.com. He's no longer active I think. On Sun, Jun 12, 2011 at 2:17 AM, Priyanshu priyanshuro...@gmail.comwrote: By this time one would have known that u are from pakistan asshole. At least our country has a chance and hope to recover from this, but ur country will rot in hell u son of a terrorist. PG On Fri, Jun 10, 2011 at 8:59 AM, Umer Farooq the.um...@gmail.comwrote: Where is the admin of this group? These guys are discussing something completely irrelevant to Algorithms. Could anyone please take a notice of this in order to maintain the dignity of this group and filter the spam? On Fri, Jun 10, 2011 at 8:30 PM, coder dumca coder.du...@gmail.comwrote: so what ? supporting anna hazare is not a bad idea. On Thu, Jun 9, 2011 at 12:54 PM, Naveen Kumar naveenkumarve...@gmail.com wrote: There is no such condition put up by the govt. If you give a missed call you are showing your support to Anna Hazare Please read http://theindiapost.com/delhi/support-hazare-give-call-02261550789/ On Thu, Jun 9, 2011 at 12:15 PM, Abdul Rahman Shariff ears7...@gmail.com wrote: did u try it ?? nd did u get the msg?? On Thu, Jun 9, 2011 at 1:06 AM, kartik sachan kartik.sac...@gmail.com wrote: Frnz govt of india has put a condition dat lokpal bill will b implemented if 25 crore ppl spport it. plz give a miss kol(free) to 02261550789 .kol ends itself n u ll get a msg rply. Plz support against corruption... -- *WITH REGARDS,* * * *KARTIK SACHAN* *B.TECH 2ND YEAR* *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. -- Ehab Abdul Rahman Shariff -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers Naveen Kumar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this
Re: [algogeeks]
@sunny agarwal : i dont think, it is O(lgn) its not a BST and further u need to check for existence of y in the path from lca to x or lca to z., so it l be O(n).. On Jun 10, 1:57 pm, sunny agrawal sunny816.i...@gmail.com wrote: find common Ancestor of both. see if y lies on path from x or z to this ancestor O(lgn) On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal goyal.aanch...@gmail.comwrote: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 IV 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.
[algogeeks] Re: Puzzle
@lalit:
The idea here would be for Train T,
make it cross its own parachute first. Then move both the train fwd
until
the trailing train reaches a parachute. When the trailing train
reaches the parachute
of the leading train, make it move faster than the leading train .
Naturally the leading
train would execute MF MF MB (effectively moves 1 step), and the
trailing train would
have moved 3 steps (MF MF MF) and would ultimately catch up and
collide with the
leading train.
To make things clear go thro' the code,
label: MF MF MB
if(parachute)
{MF MF MF}
GOTO label
Hope it helps,
On Jun 10, 12:06 am, LALIT SHARMA lks.ru...@gmail.com wrote:
A helicopter drops two trains, each on a parachute, onto a straight
infinite railway line. There is an undefined distance between the two
trains. Each faces the same direction, and upon landing, the parachute
attached to each train falls to the ground next to the train and detaches.
Each train has a microchip that controls its motion. The chips are
identical. There is no way for the trains to know where they are. You need
to write the code in the chip to make the trains bump into each other. Each
line of code takes a single clock cycle to execute.*
You can use the following commands (and only these);*
MF - moves the train forward
MB - moves the train backward
IF (P) - conditional that's satisfied if the train is next to a parachute.
There is no then to this IF statement.
GOTO
--
Lalit Kishore Sharma,
IIIT Allahabad (Amethi Capmus),
6th Sem.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MS Q
An algorithm is:
Have a bit array B of 256/65k size.
If an color 'i' is encountered in the solution, set its B[i]=1;
Traverse the solution array S,
if(S[i]==B[i]) hits++;
else if ( B[S[i]] ) pseudohits++;
On Jun 10, 9:40 am, Harshal hc4...@gmail.com wrote:
#includeiostream
#includestring
using namespace std;
void mastermind(char* guess, char* sol, int *hits, int *pseudohits)
{
int temp[256] = {0};
int len1=strlen(sol);
int len2=strlen(guess);
while(--len1+1)
(guess[len1]==sol[len1]) ? ((*hits)+=1,temp[len1] = 1) : (temp[sol[len1]]
+= 1);
while(--len2+1)
if(temp[len2]!=1 temp[guess[len2]] 0)
(*pseudohits)++, temp[guess[len2]] -= 1;
}
int main()
{
int hits=0,pseudo=0;
mastermind(RGGB,YRGB,hits,pseudo);
couthits pseudo;
}
On Fri, Jun 10, 2011 at 2:31 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
Game of master mind: you have four balls, and four different colors, as a
solution. The user tries to guess the solution. If they guess the right
color for the right spot, it counts as a 'hit'. If it's the right color, but
the wrong spot, it counts as a psuedo-hit. For example: if the solution is
'RGGB' and the user guesses 'YRGB' they have 2 hits and one pseudo hit.
Write a program to, given a solution and a guess, calculate the number of
hits and pseudo hits.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Harshal Choudhary,
III Year B.Tech CSE,
NIT Surathkal, Karnataka, India.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Difference btwn elements in a sorted array a-b=k
Given an integer 'k' and an sorted array A (can consist of both +ve/- ve nos), output 2 integers from A such that a-b=k. PS: nlogn solution would be to check for the occurence of k-a[i] (using bin search) when you encounter a[i]. methods like hash consume space. Is an O(n) solution with O(1) extraspace possible? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Difference btwn elements in a sorted array a-b=k
Can u use the same logic u use for a+b=k for difference.. because, here if you increase a or decrease b in both case difference will increase.. ? correct me if i am wrong. On Jun 7, 2:39 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: Whats the problem in using two pointers one pointing the lower index while the other pointing the upper index?? On Tue, Jun 7, 2011 at 2:57 PM, ross jagadish1...@gmail.com wrote: Given an integer 'k' and an sorted array A (can consist of both +ve/- ve nos), output 2 integers from A such that a-b=k. PS: nlogn solution would be to check for the occurence of k-a[i] (using bin search) when you encounter a[i]. methods like hash consume space. Is an O(n) solution with O(1) extraspace possible? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Difference btwn elements in a sorted array a-b=k
@piyush: in the case of a+b=k, assuming a and b are 2 ptrs to start and end, when u increase a, sum increases and when u decrease b sum decreases. i doubt if that s the same case for a-b.. On Jun 7, 2:47 pm, ross jagadish1...@gmail.com wrote: Can u use the same logic u use for a+b=k for difference.. because, here if you increase a or decrease b in both case difference will increase.. ? correct me if i am wrong. On Jun 7, 2:39 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: Whats the problem in using two pointers one pointing the lower index while the other pointing the upper index?? On Tue, Jun 7, 2011 at 2:57 PM, ross jagadish1...@gmail.com wrote: Given an integer 'k' and an sorted array A (can consist of both +ve/- ve nos), output 2 integers from A such that a-b=k. PS: nlogn solution would be to check for the occurence of k-a[i] (using bin search) when you encounter a[i]. methods like hash consume space. Is an O(n) solution with O(1) extraspace possible? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Scheduling
@Aakash Johari: Sorting works fine if all jobs can be completed in a day.. I have a modification to this question - suppose the time to do a job is not one day and is given as Ti for job i, then how should one solve it? On Jun 7, 11:58 am, Aakash Johari aakashj@gmail.com wrote: yes, it's correct. simply sort according to their costs (in decreasing order) On Mon, Jun 6, 2011 at 11:52 PM, sunny agrawal sunny816.i...@gmail.comwrote: Sort in decreasing order of Ci ? On Tue, Jun 7, 2011 at 8:22 AM, aanchal goyal goyal.aanch...@gmail.comwrote: Given n jobs, each ith job has a cost Ci associated with it. The waiting time for a job i is defined as Ci*Delay, where Delay is the number of days it takes from the first day to complete a job. Assume each job can be completed in 1 day. So, a job started at day 1 will have delay=1, the one started at day 2 will have delay=2, etc. Order the jobs in such a way that waiting time is minimum. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 IV 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. -- -Aakash Johari (IIIT 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.
[algogeeks] Min Enqueue Dequeue in O(1)
Design a Queue (strictly fifo) to support findmin, enqueue, dequeue in o(1). extra space allowed. (for a stack, its trivial with 2 stacks) Can the same approach be applied for a queue? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: get rid of sohail panzer spam
i think each of us in the group should start to spam sohail panzer's gmail id in separate mails :P On Jun 7, 8:32 pm, nicks crazy.logic.k...@gmail.com wrote: haha...like it !! On Tue, Jun 7, 2011 at 8:04 AM, anshu anshumishra6...@gmail.com wrote: For those people who want to get rid of sohail panzer spam create a filter From : sohail.panz...@gmail.com mark on Delete 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.
[algogeeks] Re: Min Enqueue Dequeue in O(1)
Can u pls elaborate on your approach further? On Jun 7, 10:17 pm, NIKHIL JAIN nikhil.jain.shali...@gmail.com wrote: it with the change that now it is min On Tue, Jun 7, 2011 at 10:47 PM, NIKHIL JAIN nikhil.jain.shali...@gmail.com wrote: i think sliding window is based on On Tue, Jun 7, 2011 at 9:26 PM, ross jagadish1...@gmail.com wrote: Design a Queue (strictly fifo) to support findmin, enqueue, dequeue in o(1). extra space allowed. (for a stack, its trivial with 2 stacks) Can the same approach be applied for a queue? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Samsung Bangalore is hiring a lot!!!!
@sayan: thanks for the info :) Any idea on the compensation dude? On Jun 7, 10:53 pm, sayan nayak sayanna...@gmail.com wrote: :D.Sure.Afterall Destiny is not a matter of chances,it all abt ur choices :) On Tue, Jun 7, 2011 at 11:20 PM, sunny agrawal sunny816.i...@gmail.comwrote: uninterested can filter messeges from sayanna...@gmail.com. :P On Tue, Jun 7, 2011 at 11:14 PM, sayan nayak sayanna...@gmail.com wrote: Multiple openings in Samsung Bangalore in following domains: 1. Wireless protocols 2. Android 3. Multimedia 4. Browser 5. mobile application. 6.Embedded System. interested people can send their resume to sayanna...@gmail.com. Regards, Sayan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 IV 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.
[algogeeks] Re: Array Merge Problem
@aakash Johari:
Let a and b be the 2 arrays.
At each stage of the process, if an element of A is greater than B,
then swap the largest element of A with the smallest element of B
and adjust pointers.
A : 2 4 15 12
B : 0.2 1 33 44
Now, 20, therefore swap 0 with 12..
Every step of the process, gets in the smallest elemnt of A and swaps
it
with the largest element of B.
Hope its clear.
On Jun 6, 11:15 am, Aakash Johari aakashj@gmail.com wrote:
@ross: I couldn't get reddy's solution. Please explain.
On Sun, Jun 5, 2011 at 10:50 PM, Deepak Jha deepak.127.0@gmail.comwrote:
the below solution should work given the input array is sorted ( I am
assuming ascending order)
void rearrangeArray(int[] a, int[] b){
int m = a.length;
int n = b.length;
int i = m - 1;
int j = 0;
while((i =0) (j = n-1)){
if(a[i] b[j]){
int temp = a[i];
a[i] = b[j];
b[j] = temp;
}
i--;
j++;
}
}
On Sat, Jun 4, 2011 at 2:29 PM, ross jagadish1...@gmail.com wrote:
Hi Rohit all,
Sorry that there was a small typo in the 'n' 'm' texts.
The example given by me is anyway the correct one.
Sravan Reddy's solution worked fine.
On Jun 4, 10:08 am, rohit rajuljain...@gmail.com wrote:
i think solution would be like this
eg:
A : 1 2 3 B: 0 1.5 4 5 9
Output:
A can contain any combination of nos 0,1,1.5
and B should contain 2 3 4 5 9 (in any order.)
this example is given by ROSS itself.
so sravanreddy solution is right , correct me if i'm wrong.
On Jun 3, 8:07 pm, bittu shashank7andr...@gmail.com wrote:
@sravanreddy...logical bugs if A is size of n B is size m from your
example assuming nm so if you want smallest m elements in A then u
only capacity of n elements didn't allocate memory so these elements
initialized by INT_MIN for m-n nodes so thatarrayA can hold m
smallest elements then what r u swapping u dude..isn't garbage
value ?? you will get at 1st step only just run it ?? in you algo
A_End=m-1(which 4th position inArraythat DNE)..?? also you have to
free memory for m-n inarrayB as it contains n largest elements .
take
A= 1,2,3 n=3
B= 0,1,4,5,9 m=5
after allocating memory toArrayA for m-n elements A will looks
likes 1 2 3 INT_Max INT_Max
now what you wants A should contains m smallest elements B have n
largest elements
so O/P should be A=1,2,3,1,0 B=INT_Max,INT_Max,4,5,9 now free
memory used by 1st elements inarrayB so that A will represent M
smallest elements B will have n Largest elements
so that above will work.
Hope I am Correct let me know if any issue with explanation
Thanks
ShashankThe Best Way To Escape From Theproblemis To Solve It
CSE,BIT Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT 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.
[algogeeks] Re: Peoplesoft Developer // Chicago, IL // 4 month contract+
people like you pollute algogeeks!! Go get a life and get lost! We would love to work in the US but we are not here to get spammed by you. On Jun 7, 12:08 am, sohail panzer sohail.panz...@gmail.com wrote: Dear Consultant, Hope you are doing good, Please let me know if you are comfortable with the requirement. *Please reply at soh...@panzersolutions.com* *Position :Peoplesoft Developer Location:Chicago, IL Duration:4 month contract+* *Responsibility Summary: * Responsible to customize and test application engine components as well as online functionality enhancements of varying complexity in a PeopleSoft environment. Perform development and testing throughout the standard development life cycle assisting with the functional analysis as needed. Work closely with the Business Analysts to ensure that the business requirement needs are met. Document all changes, following a standard methodology. *Skill set needed:* Working knowledge of the PeopleSoft EPM application - EPM 9.0 (Preferably) architecture and processes. Experience with ABM (Activity Based Management) or FTP (Funds Transfer Pricing) is highly preferred. Extensive working Experience with PeopleTools (8.49 Preferred): Application Designer Page/Component/Menu Development Component Interface Application Engine PeopleCode Integration Tools P/S Query Online and Batch troubleshooting Application Server and Web Server (Web Logic) Experience with working in DB2 AIX environments Expertise in Relational Database/SQL Knowledge (DB2 preferred) Experience with writing and modifying UNIX scripts Experience in full life cycle implementation / upgrade of PeopleSoft systems Knowledge, Skills and Abilities: Thorough knowledge of applications/development methodologies Considerable knowledge of performance tuning Skill in project management experience Skill in operating independently Skill in exhibiting solid analysis, decision-making, and problem solving Ability to assess requirements, alternatives, and risks/benefits for low- to high-impact projects Ability to communicate effectively verbally and in writing. === -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Merge Problem
Hi Rohit all, Sorry that there was a small typo in the 'n' 'm' texts. The example given by me is anyway the correct one. Sravan Reddy's solution worked fine. On Jun 4, 10:08 am, rohit rajuljain...@gmail.com wrote: i think solution would be like this eg: A : 1 2 3 B: 0 1.5 4 5 9 Output: A can contain any combination of nos 0,1,1.5 and B should contain 2 3 4 5 9 (in any order.) this example is given by ROSS itself. so sravanreddy solution is right , correct me if i'm wrong. On Jun 3, 8:07 pm, bittu shashank7andr...@gmail.com wrote: @sravanreddy...logical bugs if A is size of n B is size m from your example assuming nm so if you want smallest m elements in A then u only capacity of n elements didn't allocate memory so these elements initialized by INT_MIN for m-n nodes so thatarrayA can hold m smallest elements then what r u swapping u dude..isn't garbage value ?? you will get at 1st step only just run it ?? in you algo A_End=m-1(which 4th position inArraythat DNE)..?? also you have to free memory for m-n inarrayB as it contains n largest elements . take A= 1,2,3 n=3 B= 0,1,4,5,9 m=5 after allocating memory toArrayA for m-n elements A will looks likes 1 2 3 INT_Max INT_Max now what you wants A should contains m smallest elements B have n largest elements so O/P should be A=1,2,3,1,0 B=INT_Max,INT_Max,4,5,9 now free memory used by 1st elements inarrayB so that A will represent M smallest elements B will have n Largest elements so that above will work. Hope I am Correct let me know if any issue with explanation Thanks ShashankThe Best Way To Escape From Theproblemis To Solve It CSE,BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Intersection of 2 linked lists -
Given 2 linked lists, determine whether they intersect or not? (question is not find the point of intersection, which i am sure can be done by computing the lengths of both lists (len1 and len2) and traversing the larger list by |len1 - len2| and traversing subsequently until 2 ptrs meet. I am looking for a bettre approach that does not find the intersection pt but whether that the lists intersect or not -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: HOT HOT HOT!!! AIX Engineer position in Miami Florida
@sohail panzer: PEOPLE LIKE YOU POLLUTE ALGOGEEKS. JUST SHUT UP AND STOP SPAMMING THIS GROUP!! On Jun 3, 1:36 am, sohail panzer sohail.panz...@gmail.com wrote: Dear Professional, Hope you are doing well. I am a technical recruiter with Panzer Solutions LLC Software Implementing and IT consulting company located in CT. Please go through the Job Description and send me your updated resume with contact information. * Please reply at soh...@panzersolutions.com* * **HOT HOT HOT!!!* Title : AIX Engineer Location : Miami Florida Duration : 4 week contract possible extensions Pay rate : $42 corp to corp Start Date : 6.6.2011 We need someone that can come down to Miami Florida and stay in a hotel for a month and do this project. Create LPARs profiles Create redundant VIOs LPARs Create NIM servers Install AIX 5.3 and AIX 6.1 operating systems Configure HACMP on Oracle Servers Secure o/s based on corporate security guidelines Implement departmental backup processes on servers Performing testing of environment. Thank you, Sohail Khan | Technical Recruiter Panzer Solutions LLc 45 Stuart Ave, K Norwalk, CT 06850 USA Voice: 203-813-2052 soh...@panzersolutions.com URL:www.panzersolutions.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Intersection of 2 linked lists -
Hi Ankit, Thats was Nice solution ! :) In case we maintain a pointer to the last node in the linked list, then it is O(1) in time right? On Jun 3, 12:00 am, ankit sambyal ankitsamb...@gmail.com wrote: Traverse the 2 linked lists. Check if the node just before NULL is the same in both the linked lists. If it is then there is an intersection(return 1), otherwise not (return 0). The logic is that whenever 2 linked lists intersect, all the nodes starting from the point of intersection to the end of the linked lists are the same. Time Complexity:O(m+n),where m n are the size of the 2 linked lists Space Complexity : O(1) Ankit Sambyal BITS Pilani On Thu, Jun 2, 2011 at 11:54 AM, ross jagadish1...@gmail.com wrote: Given 2 linked lists, determine whether they intersect or not? (question is not find the point of intersection, which i am sure can be done by computing the lengths of both lists (len1 and len2) and traversing the larger list by |len1 - len2| and traversing subsequently until 2 ptrs meet. I am looking for a bettre approach that does not find the intersection pt but whether that the lists intersect or not -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: HOT HOT HOT!!! AIX Engineer position in Miami Florida
@Harshal: Dude, this panzel should be banned! Every time his spam posts top the list! On Jun 3, 7:35 am, Harshal hc4...@gmail.com wrote: yes panzer dude we would love to work in miami. But for some of us this is high time now and we are here to discuss about algos/DS. So kindly get lost from this group. Where is admin!!! On Fri, Jun 3, 2011 at 8:49 AM, ross jagadish1...@gmail.com wrote: @sohail panzer: PEOPLE LIKE YOU POLLUTE ALGOGEEKS. JUST SHUT UP AND STOP SPAMMING THIS GROUP!! On Jun 3, 1:36 am, sohail panzer sohail.panz...@gmail.com wrote: Dear Professional, Hope you are doing well. I am a technical recruiter with Panzer Solutions LLC Software Implementing and IT consulting company located in CT. Please go through the Job Description and send me your updated resume with contact information. * Please reply at soh...@panzersolutions.com* * **HOT HOT HOT!!!* Title : AIX Engineer Location : Miami Florida Duration : 4 week contract possible extensions Pay rate : $42 corp to corp Start Date : 6.6.2011 We need someone that can come down to Miami Florida and stay in a hotel for a month and do this project. Create LPARs profiles Create redundant VIOs LPARs Create NIM servers Install AIX 5.3 and AIX 6.1 operating systems Configure HACMP on Oracle Servers Secure o/s based on corporate security guidelines Implement departmental backup processes on servers Performing testing of environment. Thank you, Sohail Khan | Technical Recruiter Panzer Solutions LLc 45 Stuart Ave, K Norwalk, CT 06850 USA Voice: 203-813-2052 soh...@panzersolutions.com URL:www.panzersolutions.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Intersection of 2 linked lists -
Hi Arpit, I dont think this sort of intersection is possible.. A linked list has only one next pointer and it can point to single node only. In the counter example you gave, the next ptr of node 3 points to two nodes. So, such a case does not arise. On Jun 3, 9:26 am, Arpit Mittal mrmittalro...@gmail.com wrote: L1 L2 1 5 2 7 3 9 4 Is this situation not possible? On Thu, Jun 2, 2011 at 10:23 PM, anand karthik anandkarthik@gmail.comwrote: How can that be unless 3 has two next nodes? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Finding circle areas under dust bins
Hi all, Given a huge circular area containing lot of people (whose positions are given as coordinates) how will you place dustbins in the area, such that no person has to move more than 100 metres to reach a dustbin. Minimize the number of dustbins. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding Blocks in a matrix
@Anshu
If you do
add top bottom, left right element to the popped element in qeuue
should you need to do it for each element in the matrix.
So, will that not be O(n3)??
Clarify if i am wrong.
On May 30, 9:52 am, Aakash Johari aakashj@gmail.com wrote:
At the each level, traversed by BFS, you will have to check whether the
vertex in this level has the element same as it found in the previous level.
If it is different, then count it.
On Sun, May 29, 2011 at 10:43 PM, anshu mishra
anshumishra6...@gmail.comwrote:
@piyush
void bfs(int mat[][n], bool flag[][n], int i, int j)
{
queue.push(mat[i][j]);
while (!q.empty())
{
x = q.top();
q.pop();
add top bottom, left right element in qeuue if their flag is true and their
value is equal to x and mark their flag false;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT 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.
[algogeeks] Re: Finding Blocks in a matrix
@anshu mishra:
Hi, kindly clarify on this small doubt of mine.
Your algo is
while (!q.empty())
{
x = q.top();
q.pop();
if(node notvisited already adjacent to x value = x)
add to queue
}
For the graph,
1 1 2
1 3 1
2 3 4
first,
queue = 1 (at 0,0)
then you would add the 2 1s at (0,1) and (1,0) to the queue.
So far, i can understand.
now, if you start to pop elements, you ll see that there s no element
with
*equal value as 1* adjacent to the popped elements and the queue
would be
empty.
. How does the algo proceed from here and keep track of count?
.
On May 30, 10:22 am, anshu mishra anshumishra6...@gmail.com wrote:
@ross no, a particular element has to read only 5 times maximum.
1 reading (i,j) (if its flag is already false skip)
2 read by top element
3. read by bottom element
4 read by left element
5 read by right element
coz atleast one of the this operation its flag will be unset(false), then we
have to just skip 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] Re: Finding Blocks in a matrix
@anshu mithra:
Hi,
Thanks for clarifying! :)
On May 30, 11:06 am, anshu mishra anshumishra6...@gmail.com wrote:
main()
{
for (i = 0; i n; i++)
{
for (j = 0; j n; j++)
{
if (flag[i][[j])
{
bfs(mat, flag, i, j);
count++;
}
}}
}
bfs(mat[][], flag[][], i, j)
while (!q.empty())
{
x = q.top();
q.pop();
if(node notvisited already adjacent to x value = x)
add to queue
}
}
this is thw whole 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.
[algogeeks] Binary Tree Problem
Given a binary tree(not a BST) find the 2 nodes of the binary tree which are separated by maximum distance. By distance, we mean no. of edges in the path from node1 to node2. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Binary Tree Problem
@piyush, Hi, thanks alot for the solution, Thats to find the diameter of a tree. :) But, how would you obtain the 2 nodes which have the max. distance betwn them? On May 30, 1:17 pm, Vipul Kumar vipul.k.r...@gmail.com wrote: That is same as finding the diameter of the tree. On Mon, May 30, 2011 at 1:44 PM, Piyush Sinha ecstasy.piy...@gmail.com wrote: There can be two cases to it Case 1 - The maximum distance passes through the root node. 1 / \ 2 3 / \ 4 5 Maximum distance is between 4 and 5 i.e. 4 Case 2 - The maximum distance lies in either of the two subtrees 1 / \ 2 3 / \ 4 5 / \ \ 6 7 8 / \ 9 10 / \ 11 12 Here the greatest maximum distance is between 11 and 12. i.e 8 Hence, the greatest distance between any two nodes of a tree T is the largest of the following quantities: * the greatest distance of T’s left subtree * the greatest distance of T’s right subtree * the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T) On Mon, May 30, 2011 at 1:26 PM, ross jagadish1...@gmail.com wrote: Given a binary tree(not a BST) find the 2 nodes of the binary tree which are separated by maximum distance. By distance, we mean no. of edges in the path from node1 to node2. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Piyush Sinha IIIT, Allahabad +91-8792136657 +91-7483122727 https://www.facebook.com/profile.php?id=10655377926 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Scheduling dp problem - MSFT interview
You are given a sequence of jobs. The no. of days which each job takes to complete is also provided. You are also given the penalty amount to be paid per day each day a job left done. Give an optimal ordering among jobs to minimize penalty. There are no concurrent jobs. eg: Jobs: J1 J2 J3 no. of days to complete: 1 10 4 Penalty incurred each day1000 30 40 the job is pending output: Schedule is J1 J3 J2 hence, J1 goes for 1st day. J3 for subsequent 4 days. J2 for the next 10 days. Penalty incurred = (delay for job i ) * (penalty per day of job i) = = (0)(1000) + (1)(40) + 5(30) = 190 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] A Graph Problem
There are n persons. You are provided with a list of ppl which each person does not like. Determine the minm no. of houses required such that, in no house 2 people should dislike each other. Is there a polynomial time solution exist for this? Or is this not solvable at all? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: A Graph Problem
@anshu mishra: Yeah. Thanks! :) On May 30, 8:26 am, anshu mishra anshumishra6...@gmail.com wrote: it is exactly a graph coloring problem. so it has no polynomial order solution. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding Blocks in a matrix
@vishal Hi, I do not get you. Can you please elaborate a little more how you ll use hash? On May 30, 8:50 am, Vishal Thanki vishaltha...@gmail.com wrote: what about using a hash function? On Mon, May 30, 2011 at 10:18 AM, ross jagadish1...@gmail.com wrote: Given a matrix, you need to find the number of blocks in it. A block has the same numbers. EG: 1 1 3 1 2 3 2 2 4 has 4 blocks namely, 1 1 1 2 2 2 3 3 4 1 2 3 4 5 6 7 8 9 has 9 blocks 1 1 1 1 1 3 4 4 5 has 4 blocks, 1 1 1 1 1 3 5 4 4 I used an algorithm as follows, for each element[i,j] in the matrix, enqueue adjacent indices into a queue if they contain the same element. else incremt blockcount; return blockcount; But, this complexity is O(n^3) any better solution exists? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Array Merge Problem
Hi all, Given 2 sorted arrays: A and B each holding n and m elements respectively,. Hence, total no. of elements = m+n Give an algorithm to place the smallest 'm' elements(out of the m+n total available) in A and the largest 'n' elements in B. ( A and B need not be sorted in the end) eg: A : 1 2 3 B: 0 1.5 4 5 9 Output: A can contain any combination of nos 0,1,1.5 and B should contain 2 3 4 5 9 (in any order.) Constraints: No extra space. Linear Time preferred -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Merge Problem
@sravanreddy:
Hey, Nice Solution :) cool!
On May 29, 7:44 am, sravanreddy001 sravanreddy...@gmail.com wrote:
Maintain a pointer A_end = m-1;
doing a comparision something similar to merge sort
int i=0;j=0;
while (i m){
if (a[i] b[j])
i++;
else{
swap(a[A_end],b[j])
A_end --;
j++;
}
}
This runs in O(m) time and no extra space, also the sort order is not
guarenteed.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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 Interview Question
Hi all, Given an array of elements find the largest possible number that can be formed by using the elements of the array. eg: 10 9 ans: 910 2 3 5 78 ans: 78532 100 9 ans: 9100 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Odd Even Sort array
Hi all, Sort all elements in odd indices of an array in ascending order and even indices in descending order. Finally, rearrange so that all even indexed elements come first. eg: input – 7 2 6 4 8 3 1 even indexed : 7 6 8 1 = sort 8 7 6 1 odd indexed: 2 4 3 = sort 2 3 4 output – 8 7 6 1 2 3 4 What could be the best algo to solve it? Is it possible to arrive at the output using only 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.
[algogeeks] league problem
I have a problem where I'm putting a tennis league together under certain constraints: Each week, each player must play against a unique opponent. In addition, in a doubles league, each player must have a unique partner each week. There are limited numbers of courts. For example, if 11 people sign up for a singles league where there are only 3 courts available, 5 people will have a bye each week. I need everybody in my leagues to have the same number of byes and I would ideally like their byes to be spaced out over the course of the league. I have written a round robin generator in python that rotates players opponents each week according to according to the following diagram: 1 2 - 3 - 4 / | 5 - 6 -7 - 8 From here, I am able to zip the pairs up into a list of tuples for each week. For example, the first week from the above diagram would produce a list like this [(1,5), (2,6), (3,7), (4,8)] and the second week would be [(1,6), (5,7), (2,8), (3,4)]. Unfortunately, since the first position remains fixed in this algorithm, I am unable to remove items from the list to account for court constraints/ bye weeks without having the first player always play or always have a bye week. Would you guys approach this problem differently? The problem gets even tougher for a doubles league. Thoughts and theories appreciated... --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] League Scheduling Problem
I have a problem which is a variation of the Sports League Scheduling Problem. This problem pertains specifically to a tennis league at my own sports club. Each winter, the pro puts out a blank sheet of paper for people to sign up for tennis leagues. From year to year, the number of people who sign up fluctuates; however, the number of tennis courts available stays the same at 4 courts. For my particular problem, lets say that 12 people sign up for the league (this is a singles league) so each week, 4 people will have byes and 8 will play. Can anyone come up with an algorithm which allows each player to play each other player 1 time only and also deals out a fair number of bye weeks to each player? Assume the league runs until every player has played every other player once. If anybody can come up with such an algorithm, would it scale well to years when a different number of players signed up? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
