You have N guards in a line each with a demand of coins.You can skip paying
a guard only if his demand is lesser than what you have totally paid before
reaching him.Find the least number of coins you spend to cross all guards.
I think its a DP problem but cant come up with a formula.Another
I guess it doesn't require a DP, I might have understood your question
wrongly but from what I have understood solution is as follows :
S = sum at a particular point
A[N] = array which contains guard's respective demands
i = 0, S=0;
while (i N)
{
if (A[i] = S)
{
S += A[i];
}
i++;
@above
[20, 20, 3, 42]
regards
- Sumit Kumar Pathak
(Sumit/ Pathak/ SKP ...)
*Smile is only good contagious thing.*
*Spread it*!
On Mon, Feb 4, 2013 at 7:40 AM, navneet singh gaur
navneet.singhg...@gmail.com wrote:
I guess it doesn't require a DP, I might have understood your question
0
On 1/16/12, Ravi Ranjan ravi.cool2...@gmail.com wrote:
An ant moves on a regular grid of squares that are coloured either black or
white.
The ant is always oriented in one of the cardinal directions (left, right,
up or down) and moves from square to adjacent square according to the
An ant moves on a regular grid of squares that are coloured either black or
white.
The ant is always oriented in one of the cardinal directions (left, right,
up or down) and moves from square to adjacent square according to the
following rules:
- if it is on a black square, it flips the color of
Given a 2D matrix which is both row wise and column wise sorted. Propose an
algorithm for finding the kth smallest element in it in least time
complexity
A General Max Heap can be used with k space and n+klogk complexity
Any other solution or even a way by which we dont scan the whole matrix to
im assuming it be a square matrix
then kth smallest element will be in a first k*k sub matrix.
jst look for smallest element in the diagonal of this matrix.
it will give the kth smallest element .
On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg ankurga...@gmail.com wrote:
Given a 2D matrix which
Please tell the algo of this problem
hasPathSum()
We'll define a root-to-leaf path to be a sequence of nodes in a tree
starting with the root node and proceeding
downward to a leaf (a node with no children). We'll say that an empty
tree contains no root-to-leaf paths. So for
example, the
We are not supposed to use any loop.
So that leaves us with recursion. I get the idea and it was working too. But
i couldn't UNDERSTAND how the recursion was working. Can someone explain how
recursion would work in that case please?
--
You received this message because you are subscribed to
wat is ur question finding maximum path sum or anything other than this?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
i am bit confused...
how come using recursion makes this in-place recursion occurs with a
stack.. so you will be piling up more and more variables each time... ?
On Fri, Oct 7, 2011 at 5:19 PM, .itoa nitm...@gmail.com wrote:
We are not supposed to use any loop.
So that leaves us with
Hmm i guess you are correct! Recursion would require stacking up. Then how
are we going to do it ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
But , let's say if we do by recursion , then could you explain the way it
would work ?
And this in-place keyword is not clear to me. Does it mean we can't use
buffer / temporary variables or something else?
--
You received this message because you are subscribed to the Google Groups
Algorithm
An in place algorithm is one which only uses a constant amount of extra
memory.
So recursion is a problem as it will use an implicit stack of size O(n)
which is linear extra memory, not constant.
On 7 October 2011 15:16, .itoa nitm...@gmail.com wrote:
But , let's say if we do by recursion ,
in place means:
use constant extra space
in simple terms O(1) space
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/nDVS4k7fF34J.
To post to this group,
To do inplace stack reversal u need a mechanism by which u can transfer the
first node to last of the stack making sure u have count of other nodes
here
Say u have stack
5- top
4
3
2
1
The answer should generate the stack as
1-top
2
3
4
5
This give hints to recursion . A normal recursive func
@Ankur: +1
On Fri, Oct 7, 2011 at 8:44 PM, Ankur Garg ankurga...@gmail.com wrote:
To do inplace stack reversal u need a mechanism by which u can transfer the
first node to last of the stack making sure u have count of other nodes
here
Say u have stack
5- top
4
3
2
1
The answer
hey guys , do tell me a book for algo( other than cormen) with good no. of
illustrations or any resource or link on net(especially for dp,
backtracking, np problems etc )
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
Data Structures and Algorithms
Alfred V. Aho (Author), Jeffrey D. Ullman (Author), John E.
Hopcroft (Author)
Thank you,
Sid.
On Tue, Sep 6, 2011 at 3:45 PM, Neha Gupta nehagup...@gmail.com wrote:
hey guys , do tell me a book for algo( other than cormen) with good no.
of illustrations or any
Fundamentals of Computer Algorithms by Sartaj Sahni
On Tue, Sep 6, 2011 at 3:45 PM, Neha Gupta nehagup...@gmail.com wrote:
hey guys , do tell me a book for algo( other than cormen) with good no. of
illustrations or any resource or link on net(especially for dp,
backtracking, np problems etc
@siddharam ...iski ebook milegi to refer
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
The Algorithm Design Manual By Steve S. Skiena
-- Prashant Kulkarni
On Tue, Sep 6, 2011 at 3:48 PM, Udit Gupta uditgupta...@gmail.com wrote:
Fundamentals of Computer Algorithms by Sartaj Sahni
On Tue, Sep 6, 2011 at 3:45 PM, Neha Gupta nehagup...@gmail.com wrote:
hey guys , do tell me a
@neha: there is site calledhttp://library.nu
register there, u'll get majority of the books.
Thank you,
Sid.
On Tue, Sep 6, 2011 at 3:54 PM, Prashant Kulkarni prashant.r.k...@gmail.com
wrote:
The Algorithm Design Manual By Steve S. Skiena
-- Prashant Kulkarni
On Tue, Sep 6, 2011 at
thanku sid :)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this
The Algorithm Design Manual is the best book you can refer. But its not for
beginners.
Cheers,
Mani
On Tue, Sep 6, 2011 at 4:09 PM, siddharam suresh siddharam@gmail.comwrote:
@neha: there is site calledhttp://library.nu
register there, u'll get majority of the books.
Thank you,
Sid.
thnx to 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
Hi, Naman,
I have a O(32n) algorithm. You can solve this problem by creating a
empty Trie http://en.wikipedia.org/wiki/Trie, then you add each number's
binary form(from high to low) into the Trie.
For each number X, start from the root of the Trie, if mth bit of X is
P(0 or 1), then
you have a path of N steps
at every step, you can take onl;y 1 step or 2 steps.
how to print all the possible paths that you can take..
PS: please dont give the exact code.your approaches will be
appreciated:)
--
You received this message because you are subscribed to the
Hi, you can do this by recursion ,
printPath (int length)
{
if(lenght == N) return;
else
{
if(lenght+1 = N) { Printf ( --one step --) call printPath (length+1)
}
else if(lenght+2 = N) { Printf ( --two steps --) call printPath
(length+2) }
else
return;
}
}
On Sun, Aug 28, 2011 at 5:42 PM,
what is the initial value of length that u r passing??
On Sun, Aug 28, 2011 at 6:47 PM, prashant thorat
prashantnit...@gmail.comwrote:
Hi, you can do this by recursion ,
printPath (int length)
{
if(lenght == N) return;
else
{
if(lenght+1 = N) { Printf ( --one step --) call printPath
sorry, pls ignore above code ..a bit modifie code
I'm passing length = 0
printPath (int length)
{
if(lenght == N) return;
else
{
if(lenght+1 = N)
{ Printf ( --one step --) call printPath (length+1) }
else if(lenght+2 = N)
{ Printf ( --two steps --) call printPath (length+2) }
@prashant:
if u remove else from this line
else if(lenght+2 = N)
{ Printf ( --two steps --) call printPath (length+2) }
i think then the code will work properly.
correct me if i am wrong
On Sun, Aug 28, 2011 at 7:01 PM, prashant thorat
prashantnit...@gmail.comwrote:
sorry, pls ignore above
we can make a BST(Binary search tree) for this problem, suppose the path is
of length 10, and currently i am on 1st platform ,then this one should be in
our root node and children of this root would be 2 and 3...Similarly we
iterate until we find 10 in every leaves of BST.Then we can easily print
Hi,
Just posted another problem, which comes in category of hard problems.
http://industryinterviewquestions.blogspot.com/2011/04/least-number-of-trips-to-number-wires.html
--
Munish
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
reducing more complexity of the tree is not binary, it will be like below
instead of node containning the name
it will have a (character,count , is_last_char_of_string)
the complexity for searching the word is present or not is length_of_word
now we can create tree like this words (
Hey guys,
you guys have came across many time with mirror a tree. if anyone has
effective ways interms of memory efficiency way to implement mirror of a tree.
Sent from my iPhone
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
The most crude method would be to do a comparison in the entire array list
and increment as and when we find a match.
But this method gives a complexity of O(n2).
The same method above can be used , and comparisons can be done from either
ends of array, which reduces the
complexity to O(n2 / 2)
sort list.txt|uniq -c
On Fri, Oct 15, 2010 at 7:00 AM, Kumar S kush...@gmail.com wrote:
Q : A file has list of names. We need an algorithm to find the number each
names repeats in that list. NOT case sensitive
Example...
namefile.txt has the content..
bob
abi
jack
ram
jim
tim
u can do it by making binary search tree and each node should has 2 data
parts i.e, name and count. Whnevr u encounter the same name, update the
count of that corresponding node else keep on extending the tree.
On Fri, Oct 15, 2010 at 7:00 AM, Kumar S kush...@gmail.com wrote:
Q : A file has
I think one way we can do it is to sort all the names. And then do the
linear scan to find the distinct names and their corresponding count.
Another way is to maintain a hash map. Check for each name if it already
exists in the map. If it exists, simply increase the counter by 1 otherwise
insert
Storing in hash DS is good..
Another option may be to use Trie DS to store names..at each node of trie
the initial count would be 0..whenever a name is encountered then Trie would
be updated with that entry and at the last character of the word in node the
count will be incremented..
On Sat, Oct
http://userweb.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html
_Asit
On Wed, Sep 22, 2010 at 9:12 AM, pre pre.la...@gmail.com wrote:
Hi all,
pls help me solve this problem..
Design an algorithm to find the majority element of an array..
majority element must be an element tht has the
Use majority vote algorithm:
http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
On Wed, Sep 22, 2010 at 9:12 AM, pre pre.la...@gmail.com wrote:
Hi all,
pls help me solve this problem..
Design an algorithm to find the majority element of an array..
majority element must be an
You are provided with a stream of integers, design a data structure to
store the number of occurrences of each integer.
If the set of integers is known, then the problem becomes simple.
If the set of integers is known:
Have a hash of the known set of integers. Parse the input stream, hash
it to
Hello fellas,
i am lookin for an algorithm to find all the possible subsets in a
given set
So, if the Set is say, A={a,b,c} omit the null set
o/p: --- {a} {b} {c} {a,b} {b,c} {a,c} {a,b,c} omit the
null set
regards,
Abhijeet
--~--~-~--~~~---~--~~
You
we have many machines connected to each other. However, administering these
machines is a great hassle. That is because a machine can be administered
only by a machine connected directly to it (a machine that is an
administrator can administrator itself). So, the system administrators have
do we have an algo for finding the union of two sets ???
data structure suitable for set operations
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Hi
Can anyone tell me about constraint satisfaying algorithm(simulated
annealing)??
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
If you have to implement a phone book of 10 millin people in NYC, what
data structure would you use and why ?
Show the implementation if HashTable or Binary Trees?
Thanks,
Raj
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the
Write algorithm for finding the GCD of given numbers.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this
My problem is to find out longest subsequence of integers in increasing
order in an array of integers.
If any one have solution tell it to me.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
51 matches
Mail list logo
