Hi Raja,
There is an algorithm in SIAM Journal of Computing, vol. 6, no. 3,
1977 "A New Algorithm for Generating All the Maximal Independent
Sets". Finding maximal cliques is equivalent to finding maximal
independent sets from a graph with all egdes replaced by non-edges and
vice versa.
If you d
is
better than the N*logN as I previously thought.
Thanks.
On Mar 28, 8:49 pm, "Kevin" <[EMAIL PROTECTED]> wrote:
> This is from an interview question, see how do you guys think of it:
>
> Given a Enlgish word, how to find these words that pronounce similar
>
This is from an interview question, see how do you guys think of it:
Given a Enlgish word, how to find these words that pronounce similar
to it?
You can have some reasonable assumptions, such as: you have an
dictionary which tells you how each word pronounce (such as its
phonetic symbols), there
ps.com with HTTP;
Sat, 20 May 2006 02:32:58 + (UTC)
From: "Kevin" <[EMAIL PROTECTED]>
To: "Algorithm Geeks"
Subject: Best way for a tree data structure for fast updating?
Date: Fri, 19 May 2006 19:32:58 -0700
Message-ID: <[EMAIL PROTECTED]>
User-Agent: G2
Fri, 19 May 2006 20:16:09 -0700 (PDT)
X-Google-Token: 7no7WAwAAADis7ct-1g2gXmxLuuZt76W
Received: from 68.78.131.97 by i40g2000cwc.googlegroups.com with HTTP;
Sat, 20 May 2006 03:16:09 + (UTC)
From: "Kevin" <[EMAIL PROTECTED]>
To: "Algorithm Geeks"
Subject: Re: B
Hi Gene,
Can you add some explanation to the code?
Thanks a lot. :-)
--~--~-~--~~~---~--~~
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 unsub
Hi guys,
How can we do this efficiently:
Given a string S. Find all the sub-sequence strings that are of length
K.
For example, given "abcd", and lenght k = 3, we will have:
abc,
abd,
acd,
bcd.
Thanks a lot. :-)
--~--~-~--~~~---~--~~
You received this message
I've searched the google scholar, but find no links.
I'm wondering where can I find this paper.
This is the first paper in heapsort and is published in Communications
of the ACM, 1964
--~--~-~--~~~---~--~~
You received this message because you are subscribed to
I agree this is a different approach. But in terms of speed and space,
I wonder what is its advantages there?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send emai
Talking about radix sorting, my experience is that many job
interviewers (who are coders/developer themselvef) do not like it. Each
time when I mentioned it, they usually did not get happy with it.
What could be the reason? Any bad things in practical for radix
sorting?
--~--~-~--~~
Wrong.
Say, A is "abcd", twice of it is C "abcdabcd"
B is "bdca", B should be the premutation of A, but not a substring of
C.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this
But multiply prime numbers will run out of range of integer quickly (as
I remember multiply the first 10-20 prime will get a too large number
to fit into an integer).
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
But the problem is:
there are much more than 26 possible characters in a string, even ASCII
have 100+ characters I think, not to mention those unicode, those which
use 2 or even more bytes as a character. So the Count[] will be too
large to be practical useful.
--~--~-~--~~--
Given two strings A and B, how to quickly check whether they are
permutation or not?
For example, "abcd" and "bcda" are permutation: same chars, just
different order.
Using hash: hash A and check B will use time O(N), at the cost of extra
N space. How about do not use that much of extra space?
O
Got it. Thank you!
--~--~-~--~~~---~--~~
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 [EMAIL PROTEC
(I got this quetions when trying to apply a position in computer
science / math)
Q: How do you select n random sample data from a sequence of data
points with unknown length?
This should be a very common practical problem, say, you need to make
some prediction using n samples of weather/stock/se
If I understand it correctly, how about just do a BFS search from root
of this tree. We can find the sibling nodes easily in its FIFO and link
them, right?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm
For a binary tree with N nodes, I think it will have n-1 edges. So the
totoal lenght is n-1. Am I right?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to
To make it more clear, suppose we have N process doing their own BFS at
the same time on this graph, so we can not just set one flag in the
node (unless we have N different flag in each node). In the same sense,
we can not "lock" the graph.
So each process itself to use a separate hashtable to ke
Yeah, looks very good!
Thank you. :-)
--~--~-~--~~~---~--~~
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 em
Can we design a data structure that has
O(1) time for push(), pop() and min()?
Using stack, we can not get min() in O(1).
Using heap, we can not get push() in O(1).
So any idea?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Go
Locks can assure one process to do the job properly. It does not allow
multi process to do the same job at the same time. So it is not a
preferred way in my idea.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Alg
But using the counter only allows us to know we are in a loop AFTER we
are already in it for long time. In other words, it does not help
sovling the problem: we can not finish the BFS!
So it is better to have a way to prevent us from getting into the loop
at the first place, right?
--~--~---
oh, another way is have a flag in each node, true or false for visited
or not. But this may have problem is multi threads are using this
graph, I think.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Gee
If we are going to do breadth first search in a graph, and this graph
has cycle, then how can we guarantee the search will end?
Actually, for any kind of graph traversal, how can we make sure we do
not loop forever at somewhere?
What I can think of is to put the node we have examed in a hash, an
The best part of BBS or Web is:
you can ask whatever you want.
if someone knows it, he may reply.
if no one knows it or too lazy to reply, then it doesn't hurt either.
:-)
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Gro
I get what Terry means now. But it still uses 625/800 = 78% of the
naive method in terms of diskspace (or memory, whatever), so I think
the save is not big enough (the job interview is R&D targeted, which I
assume they want to hear one with "large" saving).
Prateek's idea is to reduce the time of
I didn't fully get what you mean, but sounds not memory efficient: if
we need to store the 200 integers per set, and don't forget they say it
could be a lot of sets (even have to write to disk because memory does
not fit).
Please post it back if there are quick method.
Actually, last time one friend got google interview, and was asked this
question.
Some say it is nlogm, if n << m.
Also see here:
http://groups.google.com/group/algogeeks/browse_frm/thread/6314d3437b1a172b?hl=en
Just back from an job interview, one question really sucks! Any idea?
It is given 45 mintues to state your thought (either how to do it, or
why you can not do it).
(Type from what I remember)
1) You choose 5000 different intergers (you can choose any 5000
integers you want to use, just be sure th
Right. So this requires n << m.
I am just picky: any better idea if they have similar size? Maybe n+m
is the fastest in that case, I am thinking.
I am kind of disagree:
we do not need to read through all the (n+m) already sorted numbers,
right?
I remember someone at somewhere saying it only need (nlogm) time, which
will save a lot if one of the array is short.
Any idea of this?
Hi there,
I am wondering how can we do this task:
Given two sorted integer arrays (array size may differ).
Find the number of values that appear in both arrays.
For example, given:
A: 1, 3, 5, 8, 10. 14, 16, 25, 28, 47
B: 2, 4, 7, 8, 11, 12, 14, 17, 47, 56, 64
The result should be 3, since val
33 matches
Mail list logo
