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
@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
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
@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 --
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
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
@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
:
@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
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
@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
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
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
, 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
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
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
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
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
= 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
@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,
@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
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)
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 -
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
@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
@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
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
@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
+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
@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
@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
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
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)
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
@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
@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
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
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
, 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
@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:
, 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
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
:
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
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
@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
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
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
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
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
@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,
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
@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++;
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
, 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
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:
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
@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
@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
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
@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 --;
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
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
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
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
63 matches
Mail list logo
