I think in this case actually the date does matter. Can you think this
problem as a regression problem. Given two coordinates date and
prices, we are actually trying to find minimum number of line segments
that fit the data best. What I mean by best fit to data is actually
the exact criteria you
does not seem possible, there is a proof that shows that comparison
based algorithm can have at best O(nlogn) worst case running time. You
can check this proof from algorithms CLRS book.
Using this proof, by master's theorem if the merge operation can be
implemented in O(lgn) using merge sort
Ok I see your point, I thought that it asked to provide an algorithm
with overall complexity O(logn), which is not possible.
why not use a binary search like procedure to fix the worst case.
Choose the array lets say list L with the bigger number, then instead
of checking each element of smaller
Dijkstra's algorithm is a dynamic programming algorithm. no matter
which path is first discovered, the relax operation (if the new path
is shorter update the path to the node, step 3) will find the correct
answer in the end. The smallest distance criteria, which selects the
next current node (step
over again.
or,
if you have more vertices between nodes in my example above, you are
able to find the shortest path by following wiki steps.
On Oct 12, 2:05 am, Gönenç Ercan gon...@gmail.com wrote:
Dijkstra's algorithm is a dynamic programming algorithm. no matter
which path is first
after that? Will be great if you can give some more detail.
Thanks
Sourav
On Oct 7, 5:30 am, Gönenç Ercan gon...@gmail.com wrote:
merge the A and B in a queue in sorted order. find the following
number (next in original array a_i+1) of the largest number (next in
queue a_i) execute
A - 5, 4, 2, 1
B - 6, 5, 4, 2, 1
k = 3,
ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the
algorithm below give 8 (a=2, b=6)?
On Oct 6, 9:06 pm, ligerdave david.c...@gmail.com wrote:
use pointers and lengths of two arrays. depends on what K is, if K
m*n/2, you reverse the
Doesn't this use O(n^3) space and the time complexity will also be
O(n^3) (passing through n^3 different possible values).
Use Radix Sort with radix/base equal to n, meaning that instead of
using the digits of numbers in base 10, find the digits in base n.
On Oct 3, 1:30 pm, bittu
for question 2. it seems awful but;
Since there are no paranthesis and /,* preceeds +,- if there
is an * or / , the leftmost one should be performed before the others.
First check the case if no *,/ occurs by checking all the sums
n1,n2,n3,n4; -n1,n2,n3,n4 (there are 2^4, either negative
As far as I know; Count sort is O(n+M) where M is the maximum value.
Radix sort is O((n+c)k) where k is the number of digits and c is the
cost of sorting a digit. So in this case if the number were
represented as binary it would be 2, so k = log_2(n^3) = 3logn and
c=2. So the complexity would be
It is the maximum number of overlapping flights. Sort the all the
times in a single array, increment a counter when a plane lands,
decrement when it flies.
The other algorithm I think can be by assigning the maximum number of
flights to different ladders until all flights are assigned. To assign
Use a trie, the memory needed will be less than having a list of
strings and it will be faster than hashTable (array implementation of
trie). Check Trie in Wikipedia. If the datastructure is going to be
static, then using a Directed acyclic finite automata (dafsa) may be
even better.
On Sep 30,
One thing to note is that, this graph is a directed acyclic graph,
since by definition there can be no edge from a smaller or equal sized
envelope to a large one. In this setting it is possible to find the
longest path, by a topological sort and dynamic programming in linear
time O(V+E). Funny
missing a point?
On Sep 30, 11:43 am, Gönenç Ercan gon...@gmail.com wrote:
One thing to note is that, this graph is a directed acyclic graph,
since by definition there can be no edge from a smaller or equal sized
envelope to a large one. In this setting it is possible to find the
longest path
14 matches
Mail list logo
