from high level and with a very few collisions, it's O(1).
there isn't much to prove because this is based on a common sense.
for example, have the world as a hashtable and all countries as the keys of
it. boxes(storage) marked by different country names(key) and you know
where to locate them.
I am a bit confused. Are you talking about the runtime of hash function
itself or to find the position.
Agree on the efficient hash function design. However, no function could be
designed to fit all cases. A key to make a particular hash function
efficient is to know the potential data size.
@meng You already have the pattern figured out. each time subtract 1
from the lowest digit and add to higher digit(only once), until the
lowest digit equals to closest higher digit. the selection of which
number to start could be figured out with given parameters sum and
combination
@Prem, no
Sorry, but this isn't a mysql group. all discussions need to be
algorithm related.
On Apr 28, 3:04 pm, Aniket aniket...@gmail.com wrote:
I was trying to install mysql 5.5. in Windows XP.After installation
during configuration phase when there was to apply security settings I
m always getting
Why make this overcomplicated?
There isn't a merge sort needed if two arrays were already sorted.
It takes only O(n). Each time, you compare the leading elements and
remove the smaller one and store it in a new array.
On Apr 12, 6:33 pm, Carl Barton odysseus.ulys...@gmail.com wrote:
Very
Folks,
here is an interesting puzzle:
A Rubick's Cube has owl heads on it, which can be misoriented. How
many (times) MORE combinations are there of this cube vs. one that has
blank stickers?
the major difference between the cube with owl's heads and the one
without is you might have the heads
Instead of looking for a common friend of A and B, look for someone
who has friends A and B.
if you are using relational DB, use count()
didn't quite understand your first part that only if A is friend of
B. i assume when A is a friend of B, B is a friend of A as well
On Mar 24, 6:43 am,
let's make this clear.
you have a total of N questions for K students, and each student gets
M questions, where M1+ M2 + M3 ++ Mn = N; Mx union My = {}empty
when you say the repeats should be minimized, i read it as eliminated,
unless you allow a few repeated questions(in a real number,
I have to say: to prove the correctness of this hypotheses is a
wrong question and there isn't an algorithm for proving something
that's infinity.
even number is 2n, where n=1 to infinity.
you can only prove the hypotheses through mathematical methods.
you can verify the correctness. it's like
@Ankit
Simplify what @Dave had said:
1.you build a max heap with first k numbers
2. always compare array[k+n] where n=1.array.size-k
if array[k+n] = k, compare next element in the array
else replace top with array[k+n] and heapify
so the worst case is like @Dave gave: O((N-5) * log
Nice @Don! That's something I was thinking but couldn't come up with
the name.
Finding a large prime itself is already an interesting and difficult
thing in number theory. To prove something on top of that could be
even more difficult
On Mar 24, 12:38 pm, Don dondod...@gmail.com wrote:
This is
is eliminated when it can go to 0.
On Mar 24, 12:20 pm, snehal jain learner@gmail.com wrote:
m*kN . so Mx intersection My is not necessarily empty. so i think your
solution is not optimized.
please correct me if I am wrong.
On Thu, Mar 24, 2011 at 7:10 PM, ligerdave david.c...@gmail.com
the whole point of linked list is to use reference. so just simply
replace values of current node with the next node's and have the
pointer pointing to the node that's next to next.
1-2-3-4-tail
saying you wanna remove 2, you have the pointer pointing to 3 and
became
1-3-4-tail
On Mar 13,
this is a tree traversal(depth first) problem.
as for the extra space, depends on how you see it. fifth can be the
counter and when the counter reaches 0, you have your fifth largest
element
On Jan 21, 9:58 am, nagaraj N nagaraj1...@gmail.com wrote:
How do you find out the fifth maximum element
use linked list. to improve the look up performance, use a binary tree
to map the objects in the linked list
On Jan 13, 1:23 am, Davin dkthar...@googlemail.com wrote:
Smaple Data :
input : abcdacdc
Output : cadb
If the count is same for characters. maintain the original order of
the
@aditya
there is always trade-off. for what it's asking, TRIE is probably the
fastest. the problem already stated, using data structure, which to
me, means, you index a document. indexing is expensive, but it's
overhead process and it has nothing to do w/ finding an existing word
in a doc.
On Dec
man!
On Oct 22, 11:19 pm, Dave dave_and_da...@juno.com wrote:
@Ligerdave: Hey, the King James version of the Bible is only about
600,000 words. I use the Bible as an example only because it is a
fairly large book. Maybe we are talking 10 megabytes to store the
whole thing, seeing
can do !!!
Kishen
On Thu, Oct 21, 2010 at 9:08 AM, ligerdave david.c...@gmail.com wrote:
@Kishen
I don't have much knowledge on parallel computation in OpenCL or CUDA.
Do you mean parallelised=not have to do the computation at all?
did you mean without knowing the boundary
for a large file, you probably would want to use external sort. kinda
like a map-reduce concept. it's actually how sortuniq kinda stuff
work in unix/linux when you try to find some TOP X
again, we are talking about the memory might not hold the entire file
On Oct 21, 9:35 am, Vinay...
level programming languages like Scala which is
also providing these parallel constructs.
If you don't understand GPUs or not familiar with parallel constructs in
Java, then my algorithm will definitely look like O ( n ^ 2 ).
Kishen
On Wed, Oct 20, 2010 at 4:25 PM, ligerdave david.c
,
str2.length
- pointer - 1);
}
return result;
}
On Oct 20, 7:55 am, Asquare anshika.sp...@gmail.com wrote:
@ligerdave -
your algo will fail in the case the two arrays are:
hellostl
eeelexander
ans
@asquare
basically i just added a flag to enable the window slide. good catch
btw!
On Oct 20, 7:55 am, Asquare anshika.sp...@gmail.com wrote:
@ligerdave -
your algo will fail in the case the two arrays are:
hellostl
eeelexander
ans : hellostlexander
but according to ur method
i wanna get a clear picture of this before start.
when you say min length of contiguous sub of an array
let's say array A=[3,1,2,3,4,5], N=6
are below both good solutions?
A[0] to A[m] where m=N
A[i] to A[m] where i=m m=N
On Oct 19, 3:58 am, Abhishek Kumar Singh iiita2007...@gmail.com
wrote:
@Kishen
as long as you have one for loop in another, you wont have O(n). it
will most likely run O(n^2)
On Oct 19, 7:41 pm, Kishen Das kishen@gmail.com wrote:
In the below code the jth and kth inner for loops can be run in parallel
making them O(1) and the entire thing O(n).
for ( i=0 to
what if two elements are not next to each other. would it work?
On Oct 20, 8:19 am, juver++ avpostni...@gmail.com wrote:
Suggested approach by Anirvana doesn't work for this problem.
It's ok if array contain numbers that are repeated twice except one
element and we need to find it.
For this
like i said before, draw a table w/ x=a and y=b
come out w/ the matrix and you would see a patten
30 29 4 3 2 1
30 60 59 34 33 32 31
29 59 58 33 32 31 30
434 338 7 6 5
333 327 6 5 4
232 316 5 4 3
131 30
@Mukesh what's not known? in the problem, it stated an array of
positive numbers
On Oct 6, 11:47 am, Mukesh Gupta mukeshgupta.2...@gmail.com wrote:
@Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the
numbers is not known we cannot predict whether the algo will run in
, Mridul Malpani
malpanimri...@gmail.comwrote:
can this problem be solved in O(n) time and in O(1) space?
On Oct 6, 10:41 pm, ligerdave david.c...@gmail.com wrote:
@mukesh, nope, you do not need to know the range. are you thinking
about array? ankit's solution is the implementation
i think you need to define whether the array is in a sorted order or
not.
some solutions work on both, but if you want the optimized solution,
more information is needed
On Oct 11, 2:59 pm, Asquare anshika.sp...@gmail.com wrote:
Given an array of size n. It contains numbers in the range 1 to
@krunal that's just different representation
On Oct 11, 9:26 am, Krunal Modi krunalam...@gmail.com wrote:
Each edge will have a cost not the nodes(vertices).
Upload an image of the graph.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
are visited, we are done. Output the path A - B - D - F
On Oct 6, 5:47 pm, ligerdave david.c...@gmail.com wrote:
so i was reading a href=http://en.wikipedia.org/wiki/
Dijkstra's_algorithmwiki/a on dijkstra's algorithm for finding
shortest path. i dont think article specifically define
sorting is absolutely required. w/o the sorting, how are you going to
find the min? comparison is also a sorting algorithm.
it also depends on how many suggestions you wanna have. if it's just
the best deal, you can complete this in O(n+m) where n is the number
of different fares of trip to and m
in A plus kth element in B. More so if elements in B are
very small after first few. for example see example
A- 100, 99,
B- 50,9,2,1,1
Here A[i] + B[1} is largest but A[2]+B[1] is much larger than
A[2]+B[2].
Sourav
On Oct 7, 6:22 pm, ligerdave david.c...@gmail.com wrote:
@ Ercan,
yes
:
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
anyone here?
On Oct 6, 10:47 am, ligerdave david.c...@gmail.com wrote:
so i was reading a href=http://en.wikipedia.org/wiki/
Dijkstra's_algorithmwiki/a on dijkstra's algorithm for finding
shortest path. i dont think article specifically define the
requirements of the graph in order to make
use pointer. shift to left if one more leading char has been found.
any unmatched char resets the pointer to first char
once you went through the entire list(first one), the pointer on the
second list tells you where to concatenate
that gives you O(n) where n is the length of first list
On Oct
so i was reading a href=http://en.wikipedia.org/wiki/
Dijkstra's_algorithmwiki/a on dijkstra's algorithm for finding
shortest path. i dont think article specifically define the
requirements of the graph in order to make the algorithm working
properly.(unless i missed something?)
for instance, in
yes, think about the logic working behind bucket sort.
we assume in this problem, memory space is inf
all you need to do is put all numbers in its own bucket
when a number was pushed into one bucket which had already been
occupied, you have the duplicated number there.
when you run to n-1
yes, it can be done in O(n).
think about the logic working behind bucket sort.
we assume in this problem, memory space is inf
all you need to do is put all numbers in its own bucket
when a number was pushed into one bucket which had already been
occupied, you have the duplicated number there.
use mod recursively.
total money(or reminder) mod denomination(big small)
On Oct 5, 7:13 pm, pre lak pre.la...@gmail.com wrote:
Hi all,
Pls help me with the solution to the following problem related to the coin
changing problem.
suppose that the available coins a ein the denominations
@mukesh, nope, you do not need to know the range. are you thinking
about array? ankit's solution is the implementation of bucket
logic.
On Oct 6, 11:47 am, Mukesh Gupta mukeshgupta.2...@gmail.com wrote:
@Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the
numbers is not
use pointers and lengths of two arrays. depends on what K is, if K
m*n/2, you reverse the pointers. therefore, the worst case is either
O(m) when length of m is shorter or O(n) when length of n is
shorter,
make the pointers pointing to the first elements in both arrays.
A)
4,3,2,2,1
^
B)
;
else return numberOfCoins + change(denominations, reminder);
}
On Oct 6, 11:01 am, ligerdave david.c...@gmail.com wrote:
use mod recursively.
total money(or reminder) mod denomination(big small)
On Oct 5, 7:13 pm, pre lak pre.la...@gmail.com wrote:
Hi all,
Pls help me
with a data structure, you can definitely achieve O(N) where N != kN,
N is the length of the number.
On Oct 2, 1:02 pm, Harshal ..Bet oN iT!! hc4...@gmail.com wrote:
you are given n integers in the range 0 to n3-1 ((n to the power 3) - 1) .
how can u sort the numbers in O(n)?
--
You received
First, if you have a set of unique usernames, those could be used to
be keys. How to generate hash is depends on your requirements. You can
add a few prefix chars or postfix
On Sep 30, 2:45 pm, amit amitjaspal...@gmail.com wrote:
Design a hash table to store phone #s. Your job is to write a hash
since this only allows you to go right or down, the easiest(easy to
understand) way is to draw a binary tree, then you will have a pretty
good view on what you have to do. basically recursion from top going
down(return the end node(bottom) and compare left and right
On Sep 30, 5:27 am, Christi
it depends on whether N strings are a subset of a finite set of
strings and the hash function.
collision happens when
# of keys # of H(keys)
by following that, you dont even need an algorithm to find the
collision.
otherwise, there would always be up to N additional storage becoz you
need to
, umesh kewat umesh1...@gmail.com wrote:
still there is some problem related to numbers encoding like..
22333101 here how will u going to
encode it???
On Tue, Sep 28, 2010 at 1:38 AM, ligerdave david.c...@gmail.com wrote:
it's a compression problem. using
any type of replace would need at least one extra memory space.
recursion is the worst, depends how you implement recursion. one
iteration might depends on another, which depends one other, and so
on.. each iteration hold its own stack
On Sep 23, 1:59 pm, Albert alberttheb...@gmail.com
it's a compression problem. using hex instead of oct saves more space
00aaa0ss yyy = 50 2a 0 1s 3f 1\s ay
On Sep 15, 8:21 am, bittu shashank7andr...@gmail.com wrote:
A file is given with many 0s stored in continuous way , store it in
another file such that when you store try
50 matches
Mail list logo