On Wednesday, July 23, 2014 8:41:33 AM UTC-4, bujji wrote:
Suppose that we are given a sequence of n values x1, x2, ..., xn and seek
to
quickly answer repeated queries of the form: given i and j, find the
smallest value
in xi, . . . , xj .
Design a data structure that uses O(n) space
No.
In C++ you can't either. You can declare a new class that _extends_ a
previous one, but you can't change a declaration once it's complete.
On Jun 8, 11:38 am, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote:
is it possible to override struct definition in c
in header.h header file i
Does this sufficae?
Suppose you were using a dictionary from the frapplewonk language,
which has only 5 words:
tab
oma
to
am
ba
Then the biggest rectangle is clearly
tab
oma
On Jun 4, 10:39 pm, Ashish Goel ashg...@gmail.com wrote:
preparing a sample itself is a great problem here, that is
Finding a given element in an unsorted list in less than O(n) time
(with a normal RAM model of computation) is easy to prove impossible.
On Jun 3, 11:01 am, abhinav gupta abhinav@gmail.com wrote:
We have given a list 14 6 7 15 8 9 we have to find 15 in (log
n ) times.
--
This is exactly right. If it happens to work it's probaby because a
pointer to the current top of heap was returned by malloc(), and just
by luck writing to it did not mess anything up. For fun, try this:
main()
{
int *p=malloc(0);
int *q = malloc(sizeof(int));
*p=2566;
are often trading
constant factors of memory usage for speed.
On May 31, 2:06 pm, Mad Coder imamadco...@gmail.com wrote:
@Gene: Can you tell some other ways of graph representation in case of
sparse matrix as till now I consider adjacency list as the best method for
the same.
--
You received
You didn't say C or C++. It makes a difference. A void pointer is
just a pointer that can point to any kind of data. You convert it to
a specific type by using casts. So just implement an exogenous list
the same way you would if data had some type Foo. The replace all
the Foo pointers with
Since the number of moves must be optimal, this seems to be a search
problem. A-Star is the right search algorithm. This is an algorithm
that's somewhere between depth first and breadth first. It expands the
tree according to a heuristic that you choose, which can shrink the
run time enormously.
I'm interested to see problems where tree implementation causes a
performance problem. Example?
Choice of graph data structures is very problem-dependent. An
adjacency matrix will probably be fastest and simplest for dense
graphs. For sparse ones there are many, many answers.
An efficient way
original post I had a typo.
On May 27, 9:54 am, atul anand atul.87fri...@gmail.com wrote:
@Gene :
NODE *convert(NODE *root, NODE *list)
{
if (root == NULL) return list;
NODE *left_subtree = root-left;
root-left = convert(root-right, list);
return convert(left_subtree, root);
}
what
This is a pretty nice question because it requires you to show
knowledge in many different areas. In business settings, logs can
make the difference between success and failure, not to mention
complying with law.
Here are some dimensions of the design space:
* Convenience of the programmer's
A callback is a function, say B, that you provide to some other
function F in order to control F's behavior.
The intuition is that F is defined with a hole in its specification
that it fills up by calling back to the B you furnished.
A simple example of a callback is the comparison function
Another approach is to form a singly linked, NULL-terminated list
(connected e.g. by 'left' pointers). This is a harder problem, and
it
might be required if you have a purpose for the other (right)
pointer. If you need a doubly linked list it's easy to walk down the
singly linked one, creating
This will work in fine, but multiplying primes requires arbitrary
precision arithmetic for keys of any significant length.
You don't need to compute a hash at all. Just maintain two buffers
long enough to hold the longest word and an O(n) sort like counting
sort. If you are using Latin (8-bit)
The problem is not so clear, so you must make some assumptions to gat
an answer. Since we have water, we have to envision the histogram in
3d. Then assume that the distance between histogram bars is 1 and bar
i has height H[i], 0=iN, zero width and unit depth, and the base
plane is at zero. Water
This question has no answer. Every good student of computer science
will know that you choose a data structure based on the _operations_
that must be performed on it: insert, lookup and what flavors of
lookup, delete, etc.. So if an interviewer uses this question, he or
she is probably trying to
Ah but this isn't a key because ac would have the same ascii sum as
bb.
On May 14, 1:11 pm, payal gupta gpt.pa...@gmail.com wrote:
@atul
instead of sorting the string individually which would require tc- O(nlogn)
shouldnot it be a better idea to use the sum of the ascii values of the
Yes exactly. And now I hope to convince you that it's good to learn a
few languages so you can use the best one for the problem at hand. In
Perl for example, your proposed algorithm looks like this:
while () {
chomp;
push @{ $map{join('', sort split('', $_))} }, $_;
}
while ( (undef, $val) =
The scanner part of any program that processes a language is probably
a DFA.
There are three main methods to code DFAs. Two use an explicit
variable to represent state in this fashion:
int state = INITIAL_STATE;
while (!is_accepting_state(state)) {
char ch = get_next_char();
state =
You just need to make sure that the same character is never swapped to
the same position twice. Here is one way to do it.
#include stdio.h
#include string.h
void swap(char *s, int i, int j)
{
char t = s[i];
s[i] = s[j];
s[j] = t;
}
void permute(char *s, int n)
{
if (s[n]) {
int i;
constant time,
but that's normal for RAM computation models used for most algorithms.
Gene
On May 5, 4:32 am, saurabh singh saurab...@gmail.com wrote:
After giving some thought,I think even radix sort may not be sufficient.
Complexity of radix sort is O(k*n) where k is the number of buckets
required
You can't solve a problem like this with only examples of . A
complete definition is necessary. For example, what do you do with
a1 ? 2b
Report mismatch?
What do you do with
1 abc ? 2 2
Do you report or mismatch?
Here is one of infinitely many complete definitions consistent with
your
You can't solve a problem like this with only examples of . A
complete definition is necessary. For example, what do you do with
a1 ? 2b
Report mismatch?
What do you do with
1 abc ? 2 2
Do you report or mismatch?
Here is one of infinitely many complete definitions consistent with
your examples:
Good question. The problem is not well-defined. It's possible that
75 should be omitted because there are deeper subtrees to the left and
right. But we'll never know for sure because examples don't make a
good definition.
On Apr 8, 2:29 pm, atul anand atul.87fri...@gmail.com wrote:
i guess
This problem isn't carefully defined. If you have 3,4,2 then 2 is the
first value smaller and of higher index than both 3 and 4. So which
to swap with?
On Mar 24, 10:01 am, Navin Kumar navin.nit...@gmail.com wrote:
Given an array of integers, for each index i, you have to swap the value at
i
My friend, all you have to do is read the manual.
http://dev.mysql.com/doc/refman/5.6/en/c.html
On Mar 22, 1:14 pm, Gobind Kumar Hembram gobind@gmail.com wrote:
Hi
Do any one know how to configure MySQL Connector ; so as to connect to
MySql using C.If any one have any idea ; please
I'll point out that if you are building a system where this problem
actually occurs (as in generating DAGs in a compiler expression
optimizer), you can nearly always engineer the problem down to O(log(|
T|)) if T is balanced and O(|T|) in the worst case.
Trees need parent pointers, and also a map
in the buffer before processing it. It needs to be
placed carefully, and it needs to be processed from both ends to a
certain point in the middle.
On Mar 20, 7:32 am, atul anand atul.87fri...@gmail.com wrote:
using Gene logic , but we need to take care of number with more than 1
digits , so updated
is not showing on your server
yet.
On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote:
@Gene : your code will work fine by changing the argument passed from
main(), you just need to call rite f(n, 1, 1); from main instead of f(n,
1, 0);
On Mon, Mar 19, 2012 at 10:10 AM, atul anand
It's not hard if all the run lengths are at least 2.
void decode(char *buf, int in_size, int buf_size)
{
int i, j, rl, p;
char t;
// Reverse the input.
for (i = 0, j = in_size - 1; i j; i++, j--) {
t = buf[i]; buf[i] = buf[j]; buf[j] = t;
}
// Copy to end of buffer (carefully)
:27 pm, Gene gene.ress...@gmail.com wrote:
Dave, this is very beautiful. Here is a less elegant proof, though it leads
to an efficient algorithm.
In a different problem some time ago, there was a statement that every
number with a 3 in the units position has a multiple that consists of
all
It looks from the example like you pick the largest (as if the digits
were a binary number). Here's what I get:
#include stdio.h
unsigned f(unsigned n, unsigned fi, unsigned fim1)
{
if (fi n) return n;
unsigned r = f(n, fi + fim1, fi);
if (r = fi) {
putchar('1');
return r - fi;
It looks from the example like you pick the largest (as if the digits
were a binary number). Here's what I get:
#include stdio.h
unsigned f(unsigned n, unsigned fi, unsigned fim1)
{
if (fi n) return n;
unsigned r = f(n, fi + fim1, fi);
if (r = fi) {
putchar('1');
return r - fi;
When the n'th number (nk) is received, apply the following algorithm:
1. Generate random real r uniformly distributed in [0..1].
2. If r k/n, throw away the new number,
3. else generate random integer i in [1..k] and replace the number in
the i'th storage location with the new one.
This is
This is very beautiful. Here is a less elegant proof, though it leads
to an efficient algorithm.
In a different problem some time ago, there was a statement that every
number with a 3 in the units position has a multiple that consists of
all 1s. The proof needs a little number theory. Any
, 4:27 pm, Gene gene.ress...@gmail.com wrote:
This is very beautiful. Here is a less elegant proof, though it leads
to an efficient algorithm.
In a different problem some time ago, there was a statement that every
number with a 3 in the units position has a multiple that consists of
all 1s
;
System.out.println(m= + m + chars= +
suffixTreeChars(s));
}
}
public static void main(String [] argv) {
new SuffixTreeProblem().test();
}
}
On Mar 14, 1:06 am, Gene gene.ress...@gmail.com wrote:
Let's try
{ reverse( $ a b a a b a a a b ... a^n b ) | n = 0,1,2
they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
Given a linked l
On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote:
Since
that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
Given a linked l
On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote:
Since there is no mention of weights, you are looking for any spanning
tree. Primm and Kruskal
(error: p= + p.val + q= +
q.val);
count++;
}
System.err.println(# nodes: + count);
}
public static void main (String [] args) {
new ListCopy().run();
}
}
On Mar 13, 3:15 pm, Gene gene.ress...@gmail.com wrote:
Copying a full graph requires a BFS
{ reverse( $ a b a a b b a a a b b b ... a^n b^n ) | n = 0,1,2,... }
On Mar 13, 12:47 am, reynald reni reni.reyn...@gmail.com wrote:
Construct an infinite family of strings over a fixed alphabet, where
the total length of the edge-labels on their suffix tree grows faster
than O(m), where 'm'
Let's try
{ reverse( $ a b a a b a a a b ... a^n b ) | n = 0,1,2,... } .
Note that m = n(n+1)/2 + n = O(n^2)
Think about adding suffixes to the tree from shortest to longest.
So suppose you are now adding something of the form
reverse( $ X a^L Y )
where L is the length of the longest run
This is nearly what malloc() and similar memory allocators do. If you
look at an operating system book or web search you'll get lots of
approaches. The overall problem of finding the best allocation is NP
hard, so you must use some kind of heuristic. The most common ones
are called First fit
at 7:01 AM, Gene gene.ress...@gmail.com wrote:
It's a fact from number theory that
x * (x^(M-2)) = 1 (mod M)
if M is prime. So x^(M-2) is the multiplicative inverse of x (mod
M). It follows by identities of modulo arithmetic that
n!/(r!(n-r)!) = n! * inv(r!) * inv( (n-r)! ) (mod M
This is a nice paper. I think that for matrix multiplication it ends
up saying pretty much the same as we've been discussing.
The OP said serial code. Vector code isn't serial. However it's
easy to try vectorization these days. The latest versions of gcc will
do a very reasonable job with the
--)
53 hash = partial_name_hash(*name++, hash);
54 return end_name_hash(hash);
55 }
56
On Mar 3, 8:32 am, aanchal goyal goyal.aanch...@gmail.com wrote:
Gene:
I am talking about file names.
On Sat, Mar 3, 2012 at 1:07 AM, Gene gene.ress...@gmail.com wrote:
It's possible
What Don so succinctly said is this: Comparison sort _requires_ O(n
log n) comparisons. If you had the data structure you're asking for,
you could easily implement a comparison sort: Just insert n items,
then then repeat n times: find min and delete that min. With your
proposed time bounds, the
in
unpredictable ways. You might find it interesting to turn off your
network and see if you can get further improvement by making blocks a
little bigger than you could with the network turned on.
On Mar 5, 2:08 pm, Arun Vishwanathan aaron.nar...@gmail.com wrote:
@Gene: if all matrices are of N x N
It's a fact from number theory that
x * (x^(M-2)) = 1 (mod M)
if M is prime. So x^(M-2) is the multiplicative inverse of x (mod
M). It follows by identities of modulo arithmetic that
n!/(r!(n-r)!) = n! * inv(r!) * inv( (n-r)! ) (mod M)
This is what the code is computing. A basic number
The Wikipedia entry is pretty good:
http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm
Read the Algorithm section a few times and draw some examples and
you'll probably start seeing it.
On Mar 3, 7:56 am, saurabh singh saurab...@gmail.com wrote:
Its quite trivial.
At least until you have
It's possible you're not getting any clear answers because the
question is unclear. Linux does many different kinds of name lookup
all over the system. What names are you talking about?
On Mar 1, 3:50 pm, aanchal goyal goyal.aanch...@gmail.com wrote:
anyone knows what hash function is used
My crazy guess is that you need to add 1900 and then these are
important years. Maybe years when a team won some sports
championship? I'm getting this from the no math or outside
knowledge. You need inside knowledge.
On Feb 27, 8:24 am, karthikeya s karthikeya.a...@gmail.com wrote:
3, 39,
A related interesting problem is counting binary set hierarchies: the
number of perfect binary trees you can build over the same set of
n=2^k leaves, where there is no distinction between left and right
children.
In other words, starting with n=2^k elements, put them into disjoint
sets of 2
This depends on the compiler and even on the options you give the
compiler. The C nor C++ standards don't say.
So the asker of the question hasn't give you enough information.
If you assume 32-bit x86 gcc with no packing options or pragmas, I
think shorts (which are 2 bytes long) are aligned on
For big matrices, using all the caches well is very important. The
usual approach is block tiling as you say. You want two blocks to fit
nicely in the L1 cache. The most highly optimized schemes will have a
hierarchy of tiles where two tiles at the second level will fit in the
L2 cache, etc.
-byte boundary after 5
8 + 4 = 12, so the struct takes 12 bytes
On Feb 29, 12:03 pm, Karunakar Reddy karunakar.r...@gmail.com wrote:
how in the second case it is 12?can u tell the clear expl..
On Wed, Feb 29, 2012 at 8:39 AM, Gene gene.ress...@gmail.com wrote:
This depends
This not a bad thought experiment, but sorry this isn't true. First,
there is a problem of cycles. If a graph is undirected, you can pick
any edge and go back and forth an arbitrary number of times along that
edge to make any path as long as you want.
So if there exists _any_ path there is no
be 0.5 ( G(h - 1, i - 1) + G(h
- 1, i+1) )
i am not clear why the parents of a cup in upper row are consecutive?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 10:43 AM, Gene gene.ress...@gmail.com wrote:
G is just
Dave's code is good. Here is a more abstract way of thinking about
it. Maybe helpful?
Number the rows starting at the top with h=0, and the left i=0. Then
the parents of cup(h,i) are always cup(h-1,i-1) and cup(h-1,i). When
h0, i0 or i h, the parent does not exist.
Let F(h, i) be the amount
practical purposes. It's
untested but ought to work.
On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote:
Gene, your DP is what i was thinking of but in code i could not coreleate
G(h - 1, i - 1) + G(h - 1, i) part (:
Best Regards
Ashish Goel
Think positive and find fuel in failure
One way to think about it: Given an input list with n items, consume
the first ceiling((n-1)/2)=floor(n/2) items building the left
subtree. Then consume the next item to use for the new tree root.
Then consume the rest of the elements, which number n - floor(n/2) - 1
to build the right subtree.
Nice. The code is very clean.
It's worth noting in case anyone is intending to implement this that
it's easy find graphs where exhaustive DFS runs in exponential time.
One that's easy to envision is a chain of diamonds
S8o8o8o ... o8D where S is the source and D the destination
with all edges
Ah, this reminds me of a beautiful thing that a fine gentleman CB
Falconer posted once in comp.programmer. It was so elegant that my
normally bad memory still remembers it after some years.
You can simplify the merge by using a dummy node for the head of the
merged list rather than just a
Exactly. The other trick is when maintaining a list in ascending
sorted order, to give the sentinel a key of infinite. This way you
need not check for the end of list at all. The key comparison will
always stop before the last element. I vaguely recall Wirth uses this
example in his book
Not to mention the subject line seems to be asking about B-Trees,
which is no kind of binary tree, so the OP gets it wrong, too.
On Feb 20, 7:28 pm, Dave dave_and_da...@juno.com wrote:
@Don: By that measure, it also is trivial if the tree is a BST. You
just find the largest node x and the
...@gmail.com wrote:
@gene probably you are saying this on the basis of the subject of the
mail?Please read the problem statement stated in the mail.Even its a B
tree doesn't effects the algorithm proposed by don which says *traverse
each node and keep track of minimum.*
So irrespective
Just the topic line:
Finding closest double in a Btree
On Feb 20, 9:37 pm, Dave dave_and_da...@juno.com wrote:
@Gene: I don't know what is confusing about the OP's problem
statement:
Question is given a binary tree and a key K, code to find the node
with the
closest value.
What do you
The topic of the discussion is:
Finding closest double in a Btree
A binary tree that is also a B-Tree is (roughly) a Binary Search
Tree.
On Feb 20, 9:37 pm, Dave dave_and_da...@juno.com wrote:
@Gene: I don't know what is confusing about the OP's problem
statement:
Question is given
What language are you using? In most languages a bool is either 1 byte
or 4 bytes long. So you'd be wasting a tremendous amount of time and
space if you're doing the additions one bit at a time.
Here's roughly how it work work in C, but you'll get a faster result
with GNU mp on most machines
If you want to do something of practical importance that has not
already been done many times, you can look at parallel collision
detection. Collision detection is very important in physical
simulations (as in mechanical design tools, CGI, and computer games).
On Feb 12, 10:58 am, Arun
I think all the answers are wrong. Also pre-order is probably the
wrong term here. The conventional term is prefix or Polish notation.
You'd break up this expression at the level of lowest precedence as:
(A - B) - C
where A = ~16, B = ~14 / ~12, and C = 2 * 8 .
Note I'm using ~ for unary
You can extend this thinking to finding the value mod M of any string
of base B digits. (In this case M=5, B=2, and you are looking for a
mod 5 value of zero.) Construct a finite automaton with M states 0 to
M-1. The current state of the automaton tells you the value mod M of
the digits seen so
To find sqrt(a), this is equivalent to Newton's Method with f(x)=x^2 -
a. Newton is: x_{i+1} = x_i + f'(x_i) / f'(x_i). So you have x_{i+1}
= x_i + (x_i^2 - a) / (2 x_i) = (x + a/x) / 2, which is just what the
Babylonian method says to do.
Newton's method roughly doubles the number of
If the interviewer actually said 10^80 data items, he/she was
expecting you to say it's a silly question.
Do you realize how much 10^80 is? A terabyte is 10^12 bytes. So we
are talking about 10^68 1 Tb disk drives just to hold 1 byte records.
The number of grains of sand that would make up the
Which language?
On Jan 15, 8:23 pm, Ashish Goel ashg...@gmail.com wrote:
Hi,
given a string in hex, convert it into int.
Write test cases for the same.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you
And it ought to. Did you try it?
On Jan 15, 9:55 pm, Ashish Goel ashg...@gmail.com wrote:
a 0x should come as a negative number
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Jan 16, 2012 at 8:19 AM, Gene
*s = '9')
i = (i 4) + (*s - '0');
else if ('a' = *s *s = 'f')
i = (i 4) + *s + (10 - 'a');
else if ('A' = *s *s = 'F')
i = (i 4) + *s + (10 - 'A');
else break;
if (i 0xf00) break;
s++;
}
return i;
}
On Jan 15, 10:01 pm, Gene gene.ress
To find sqrt(a), this is equivalent to Newton's Method with
f(x)=x^2 - a.
Newton is:
x_{i+1} = x_i + f'(x_i) / f'(x_i).
So you have
x_{i+1} = x_i + (x_i^2 - a) / (2 x_i) = (x + a/x) / 2,
which is just what the Babylonian method says to do.
Newton's method roughly doubles the number
I'm sorry for not being specific. I meant it doesn't converge for all
roots, e.g. cube root.
On Jan 15, 10:18 pm, Dave dave_and_da...@juno.com wrote:
@Gene: Actually, Newton's Method for sqrt(a), where a 0, also
sometimes called Heron's Method, converges for every initial guess x_0 0
)
{
if (arr[i-1][j]==0 arr[i][j-1]==0 arr[i-1][j-1]==0)
count++;
else if (arr[i-1][j]==1 arr[i][j-1]==1 arr[i-1][j-1]==0)
count--;
}
On Wed, Jan 11, 2012 at 8:10 AM, surender sanke surend...@gmail.comwrote:
@gene
in that case ur erase() should even consider diagonal elements
surend...@gmail.com wrote:
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really
This is pretty funny because modern ECG machines generate digital
output. You might first look into whether you can get the digits
directly from the machine rather than scans of paper.
But suppose you can't. I assume you asking how to find numerical
coordinates for the curve by scanning and then
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient
The 1's and 0's are in matrix R. We want to compute an integer matrix
M of the same dimensions as R such that Mij is the size of the largest
square of 1's of which Rij is the bottom right corner. As we go we
can keep track of max(Mij), and this will be the answer.
So how to compute Mij? The
Exactly. And note that if pointers and unsigned integers have the
same number of bits, overflow can't be a problem as long as the array
elements are 2 bytes or more long. I.e. if you have an n-bit machine,
the last 2-byte array element can't have index more than 2^n/2 - 1 =
2^(n-1) - 1.
If the graph is planar and you have it's embedding, then you can do
better than O(N), at least on a random graph. Otherwise this has to be
impossible because the graph gives you no information, and you must
look at each vertex.
On Jan 5, 1:17 pm, dabbcomputers dabbcomput...@gmail.com wrote:
you
sravanreddy...@gmail.com wrote:
@Gene: I didn't understand on what you termed as embedding Can you
provide more insights on this?
@dabbcomputers: also, listing set of points (not just one) isn't going to
be a better than O(n) solution.
for eg: a value of R that eliminates only half the points outside
Don't forget repeats. The string aaa has only one permutation.
A related interesting question is how to write a permutation
iterator. Here is the interface:
typedef struct {
// your code here
} PERMUTATION_ITERATOR;
/* Initialize the given permutation iterator with the string of n
Any reasonable algorithm is goingto compute a histogram of the data
then sort into frequency order to produce the output.
The histogram (map from data values to frequency counts) can be stored
in a simple array if the data are small integers as in the example.
If the data are not nice, then a
The description is fine. It is tricky to get implementation exactly
right for the cases where the ray pierces a vertex or coincides
exactly with an edge, especially with floating point rather than
rational arithmetic. Franklin's code (link is given on the page)
works well. I'd never code it
The simplest algorithm is probably to check each point against all
others while maintaining a list of the top 3. Since 3 is a small
number, you can just maintain the top 3 in sorted order by insertion.
For a bigger K top-K you'd use a max heap.
This can also be done in O(n log n) time by building
Longest path won't work so well because it will return infinity if a
path contains a positive cycle, which doesn't apply here because once
you pick up an apple, it's gone.
On Dec 13, 7:17 am, vikas vikas.rastogi2...@gmail.com wrote:
Graph
take up, right and bottom as nodes connected to current
of research. So this is a
useful thing to discuss.
Gene
On Dec 11, 8:11 pm, bharath sriram bharath.sri...@gmail.com wrote:
Hey group
This is kind of a cliched question but given a file with billion numbers
and the task is to compute 'k' largest numbers from this file, what
approach
Guys, if you can find a solution that is not exponential time in the
worst case you are going to be famous because this problem is NP-Hard
in the strong sense. I.e. there is not even a pseudo-polynomial time
algorithm. To get a perfect solution every time, you can't do better
than heuristic
Exactly. Really you should see this with almost no thought. It's
called an adversary argument and goes like this.
Since you don't know the order of elements in A, envision them as
being put in order by an adversary that always knows in advance what
element you're going to examine next. Now no
You can do a zig-zag traversal of a tree by using 2 stacks in place of
the 2 queues you'd use for level order traversal. As you do the zig-
zag traversal, just keep track of the current and previous node
visited and set previous-zznext = current at each visit.
On Dec 11, 1:52 am, AMAN AGARWAL
This is nice. There is also an article on how to do this iteratively
with a stack:
http://groups.google.com/group/comp.programming/msg/41f46b2801c4f84e
This solution actually traverses a BST of any shape, tears it apart,
and reassembles it as a perfectly balanced tree. However, it will
also
We talked about the problem of removing as many parentheses as
possible:
http://groups.google.com/group/algogeeks/browse_thread/thread/26ce36ad34dce9dc/e8fb40ab2ba0ecc0
You didn't define duplicate. For (a*b)+c, the parens don't add any
information. Should they be removed? The algorithm given
possible but messier. You have to track the last
node added at each level or something equally messy and error prone.
By the same logic, you can do the zig-zag order with a single deque,
but it's also messier this way.
On Dec 11, 12:23 pm, atul anand atul.87fri...@gmail.com wrote:
@Gene : if i am
You can make them immutable and hide the constructor (make it
private), then provide a factory function
public createPerson(String firstName, String lastName, Date dob)
that internally maintains a hash of all Person's created so far and
never creates the same one twice. If you request the same
1 - 100 of 415 matches
Mail list logo
