According to me Nishaanth's solution is incorrect, as let for n =10, your
output : m=16
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
Try this on a notepad. you will only 15A's
On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath saikat@gmail.comwrote:
According to me Nishaanth's
Hi,
I think this method will work:
Possible Number of A's = N/2(1+R)
where R=N-(N/2+3)
assuming 11/2 = 5
Thanks
Preetam
On Fri, Jan 21, 2011 at 2:29 AM, Anand anandut2...@gmail.com wrote:
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then
Q4 its One Binary Semaphore problem try different combination while
preserving original values of S T
Q2 A Please Read Out SJF (CPU Scheduling Algorithm)
Q3 C.. Please Read What is Paging Page Fault --performance is
Answer Chosen By Navies not Experts.. Actual Answer is Less Page
Faults
Keys 23 may be combined, cause there is no sense to use them separately.
It's cost of pressing is 2, however.
For all other keys the cost is 1 though.
DP[i][n] - maximum number of A's we can produce with cost of pressings = i
and we have string of A's with size n in a clipboard.
DP[N][any] -
http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote:
Given
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above four
keys), please write a program to produce maximum numbers of
How about the following dynamic programming solution.
Let dp[i] be the max no of As with i keystrokes.
dp[i]=max(dp[i-1]+1,2*dp[i-3])
dp[N] is the required solution.
Correct me if i am wrong.
On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote:
RAM Question ;- Ans D... Larger RAM - Larger number of frames per process
- lesser number of pagefaults - increased performance.
Scheduling :- Ans D..All are correct. @all those guys who say only I and
III, why not II ? Preemption doesnt guarantee bounded waiting.Starvation may
still happen.
Pipeline : Choice B : 165 ( this pipeline wastes 20 ns between last 2 stages
for each item )
Scheduling : Choice B
Few page faults : Choice D
Synchronization : Choice B
On Wed, Jan 19, 2011 at 10:26 AM, nishaanth nishaant...@gmail.com wrote:
RAM Question ;- Ans D... Larger RAM - Larger number
there will be 1 or 2 rounds of telephonic interviews. How and what to
prepare for that?
--
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
wch college u are in ?
--
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,
nitk
On Tue, Jan 18, 2011 at 6:36 PM, shubham singh shubhamsisodia0...@gmail.com
wrote:
wch college u are in ?
--
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
agr.bhav...@gmail.com
*Sender: * algogeeks@googlegroups.com
*Date: *Mon, 17 Jan 2011 09:36:20 +0530
*To: *algogeeks@googlegroups.com
*ReplyTo: * algogeeks@googlegroups.com
*Subject: *Re: [algogeeks] Re: google mcqs
answer is b
Increasing the RAM of a computer typically improves performance
thats cool i am from uptu google didnt visit here so no idea :D :D
--
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
+0530
*To: *algogeeks@googlegroups.com
*ReplyTo: * algogeeks@googlegroups.com
*Subject: *Re: [algogeeks] Re: google mcqs
answer is b
Increasing the RAM of a computer typically improves performance
because:
a. Virtual memory increases
b. Larger RAMs are faster
c. Fewer segmentation
thanks very much.
On Sun, Jan 16, 2011 at 5:04 PM, Lakhan Arya lakhan.a...@gmail.com wrote:
@pacific
Sets of size 2 can have 2 elements common with set of size greater
than 2. for example if set is (1,2) than it is adjacent to sets like
(1,2,3) (1,2,4), (1,2,3,4...n) etc.
So (1,2) is
@Lakhan
Why are you not considering sets of size 2 ? Because two sets of size two
cannot have both of the elements as same.
On Sat, Jan 15, 2011 at 9:39 PM, Lakhan Arya lakhan.a...@gmail.com wrote:
@bittu
I don't think answer of 6th question to be a)
No. of vertices of degree 0 will be
@pacific
Sets of size 2 can have 2 elements common with set of size greater
than 2. for example if set is (1,2) than it is adjacent to sets like
(1,2,3) (1,2,4), (1,2,3,4...n) etc.
So (1,2) is adjacent to (1,2,3), (1,2,4) etc.
On Jan 16, 1:04 pm, pacific pacific pacific4...@gmail.com wrote:
.02(5000)+.1(1500)+0.3(0)+$50=$300
On Jan 12, 4:47 am, snehal jain learner@gmail.com wrote:
An insurance company issues a policy on a small boat under the following
conditions:
The replacement cost of $5000 will be paid for a total loss. If it is not a
total loss,
but the damage is more
@ashish, you are wrong.
The solution is
for the first output the time taken = 150 + 5 + 120 + 5 + 160 + 5 +
140 = 585ns
for the remaining 999 output it will take 999*165 = 164835 ns
so, in total = 164835+585 = 165420 ns.
So, option b is the correct one
On Jan 16, 8:18 pm, Ashish Goel
answer is b
Increasing the RAM of a computer typically improves performance
because:
a. Virtual memory increases
b. Larger RAMs are faster
c. Fewer segmentation faults occur
d. Fewer page faults occur
--
You received this message because you are subscribed to the Google Groups
ans is a of
Increasing the RAM of a computer typically improves performance
because:
a. Virtual memory increases
b. Larger RAMs are faster
c. Fewer segmentation faults occur
d. Fewer page faults occur
--
You received this message because you are subscribed to the Google Groups
: [algogeeks] Re: google mcqs
answer is b
Increasing the RAM of a computer typically improves performance
because:
a. Virtual memory increases
b. Larger RAMs are faster
c. Fewer segmentation faults occur
d. Fewer page faults occur
--
You received this message because you are subscribed
: * algogeeks@googlegroups.com
*Date: *Mon, 17 Jan 2011 09:36:20 +0530
*To: *algogeeks@googlegroups.com
*ReplyTo: * algogeeks@googlegroups.com
*Subject: *Re: [algogeeks] Re: google mcqs
answer is b
Increasing the RAM of a computer typically improves performance
because:
a. Virtual memory
1.c U Can verify by putting n =I where I is positive integer value say
n=5 try it out its so easy
2 a...what i have understood.
as we know that formal grammar is defined as (N, Σ, P, S)
so For instance, the grammar G with N = {S, A}, Σ = {a, b}, P
with start symbol S and rules
S →
@bittu
I don't think answer of 6th question to be a)
No. of vertices of degree 0 will be those who didnot intersect with
any set i exactly 2 points. All sets of size greater than equal 2 must
intersect with any other set having exactly 2 common elements between
them in exactly 2 points. e.g if a
@Wei Please test you code on cdbbcbbca. I believe it outputs 2
instead of 8.
On Jan 14, 4:09 am, Wei.QI qiw...@gmail.com wrote:
FindStartIndex(char[] a)
{
int start = 0;
int current = 1;
while(current a.Length)
{
if(a[current] a[start])
{
A cool way of solving this is by using the suffix tree.
1. Concatenate the string with itself.
2. Create a suffix tree.
3. Descend along the least lexicographic path from the root.
Solution works in O(n).
On Jan 15, 4:55 pm, Jammy xujiayiy...@gmail.com wrote:
@Wei Please test you code on
@Jammy
There is a bug at line
if(startnext == current || a[startnext] a[currentnext])
{
if(current currentnext)
{
break;
}else
{
current = currentnext; // +1;
@shehal
Concatenate string to itself and then find smallest suffix of length = n
--
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
Here is general dicsussion on this topic:
http://forums.topcoder.com/;jsessionid=A92760DB520220B76858A0675626EBAC?module=ThreadthreadID=641215start=0mc=4#1100409
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
Here is compact linear solution (it is based on some non-trivial
observations):
int min = 0, p = 1, l = 0;
while (p n min + l + 1 n) {
int cmp = buffer[min + l] - buffer[(p + l) % n];
if (cmp == 0)
++l;
else if (cmp 0) {
p += l + 1;
l = 0;
}
else {
Answer for question 6 maybe b)
also for question 7 maybe b)
On Jan 12, 2:14 pm, snehal jain learner@gmail.com wrote:
1. Quick-sort is run on two inputs shown below to sort in ascending
order
(i) 1,2,3, ….,n
(ii) n, n - 1, n - 2, …., 2, 1
Let C1 and C2 be the number of comparisons made
this will not work out
a[0]b[0] doesn't mean that a[0]+b[i] is ith largest sum
try
int a[]={10,8,6,4,1};
int b[]={9,6,3,2,1};
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Oct 6, 2010 at 11:36 PM, ligerdave david.c...@gmail.com wrote:
@lalit
hi its because whenever we talk about multi-threading we
need to take care of synchronization as the problem clearly says
application made only single threaded means not synchronized
otherwise as a programmer its his job to make a app..for multithreaded
environment so that such problem
@bittu
I would like to discuss one thing regarding your approach ,
How you managed to put forward your 1st statement that is of Synchronization
.
On Fri, Jan 7, 2011 at 1:18 PM, Pedro Rezende web...@gmail.com wrote:
Hi all!
And what could be the best way to test / debug issues like these?
http://coders-stop.blogspot.com/2010/12/most-used-data.html
On Jan 7, 5:24 pm, bittu shashank7andr...@gmail.com wrote:
You have a stream of infinite queries (ie: real time Google search
queries that people are entering). Describe how you would go about
finding a good estimate of 1000 samples
Corrupted heap may be the case.
On Jan 6, 8:38 pm, soundar soundha...@gmail.com wrote:
Maybe the code has lot of dynamic updations..So for each kind of i/
p there can be different places where the updated value is used.
--
You received this message because you are subscribed to the Google
After Spending Some Time To Analyze This Problem..I Got Its Non-
Synchronization,Multi Threading Problem..Let Me Describe..-
As The Source Program Build To Single Threaded Environment so When
Multiple User Trying To Access The Same Part of Program at the same
time ,its surely crashes..as Its Not
@Douglas, nicely put!!!
On Fri, Jan 7, 2011 at 8:37 PM, Douglas Diniz dgdi...@gmail.com wrote:
Some examples, supposing you do always the same thing:
1-) You have a program that use some random number, and based on the
number the program do different things, and this different things
crash
Hi all!
And what could be the best way to test / debug issues like these?
2011/1/7 vaibhav agrawal agrvaib...@gmail.com
@Douglas, nicely put!!!
On Fri, Jan 7, 2011 at 8:37 PM, Douglas Diniz dgdi...@gmail.com wrote:
Some examples, supposing you do always the same thing:
1-) You have a
Maybe the code has lot of dynamic updations..So for each kind of i/
p there can be different places where the updated value is used.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Btw...another observation in case 1.2:
I wrote:
Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the
minimum element(x[h] is minimum)
Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]
Here, just setting dp[i][j]=v will do (athough the complexity is same
in both the cases)
because for
The description on internal nodes indicates this:
The value of an AND gate node is given by the logical AND of its TWO
children's values.
The value of an OR gate likewise is given by the logical OR of its TWO
children's values.
On 2010-12-28 13:35, suhash wrote:
Your approach is for a
Let cst[i][j] store the cost to flip node i to given gate j (0-'AND',
1-'OR').
Then: cst[i][j] = 0,if j==gate[i];
cst[i][j] = 1,if j!=gate[i] and ok[i];
cst[i][j] = INFINITY, if j!=gate[i] and !ok[i];
1. To get value 1:
1.1 flip current gate to AND, and change all
@Terence: I like your explanation. Very short and crisp! :)
On Dec 28, 12:10 pm, Terence technic@gmail.com wrote:
Let cst[i][j] store the cost to flip node i to given gate j (0-'AND',
1-'OR').
Then: cst[i][j] = 0, if j==gate[i];
cst[i][j] = 1, if j!=gate[i] and ok[i];
Sorry my mistake! But the general problem with more than 2 children
possible is more interesting! :)
On Dec 28, 10:58 am, Terence technic@gmail.com wrote:
The description on internal nodes indicates this:
The value of an AND gate node is given by the logical AND of its TWO
children's
This problem can be solved using dp in O(n), where 'n' is the number
of nodes in the tree.
Definitions:
Let gate[i] be a boolean denoting whether the gate at node 'i' is
'AND' or 'OR'. (0-'AND' 1-'OR')
Let dp[i][j] store the minimum no. of swaps required to get a value of
'j' (0 or 1), for the
Your approach is for a binary tree, but the problem statement does not
say anything about it.
On Dec 28, 10:27 am, pacific pacific pacific4...@gmail.com wrote:
here is my approach :
Starting from the root node ,
if root node need to have a 1 ...
if root is an and gate :
flips =
According to me, the problem is regarding fastest search of
substrings..
Hashing is one of the solutions.
Use Rabin-Karp Search..
Use wiki at:
http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm#Rabin.E2.80.93Karp_and_multiple_pattern_search
On Dec 14, 4:01 pm, sourabh jakhar
Read each file word by word and insert into a Suffix Tree...
Terminal node of each word contains the FileNo/FileName...
Quite simple
On Dec 14, 5:42 pm, Tuaa vention.goth...@gmail.com wrote:
According to me, the problem is regarding fastest search of
substrings..
Hashing is one of the
Sorry Dave. This doesn't do it either.
Try
100 90 2 1
13 5 2 1
The sums are
113, 103, 15, 14,
105, 95, 7, 6,
102, 92, 4, 3,
101, 91, 3, 2
So the top N=4 are
113, 105, 103, 102.
Your algorithm produces
113, 105, 102, 101.
On Oct 16, 12:26 am, Dave dave_and_da...@juno.com wrote:
Hmm...
First, drawing the table is O(n^2). So we have to assume you never
really draw the table.
Second, your description is too imprecise to say if it will work in
general. Give a pseudocode, please. I don't believe that any
algorithm based on local inspection of this table will work. In
Since the priority queue operation delete min must be O(log n) the
running time here can't be better than O(n log n).
On Oct 16, 11:06 am, juver++ avpostni...@gmail.com wrote:
Keep priority queue of pairs - sum and respective indices in the
arrays.
Start from pair (a[0] + b[0], (0, 0)).
@Dave
yes im also trying to say the same point as Gene
these problem is similar to
*Least fare for a return trip Algorithm* where u have suggest
the exactly same algorithm..
@Gene do see these similar problem
[algogeeks] Least fare for a return trip Algorithm
here we have to
@Coolfrog$ and Gene: I understand now, and agree that my algorithm is
incorrect. Just because I've used a flight in one trip doesn't mean
that it can't also be used in another more expensive trip. Sorry.
Dave
On Oct 17, 10:24 pm, coolfrog$ dixit.coolfrog.div...@gmail.com
wrote:
@Dave
yes im
Keep priority queue of pairs - sum and respective indices in the
arrays.
Start from pair (a[0] + b[0], (0, 0)).
while (queue is not empty n 0) {
retrieve largest sum from the queue, (sum, (i, j))
add sum to the result array
--n;
add pairs (a[i + 1] + b[j], (i + 1, j)) and (a[i] + b[j +
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
Hi Arun. Last time we discussed this problem I came up with the same
idea. Unfortunately it doesn't work. The problem is that in order
for the merge to be correct, each pair of pointers must be
guarenteed to produce sums that are in non-increasing order. They
don't. For example, if you run
Doesn't something like this work:
ia = 1
ib = 1
output ia, ib, A(ia) + B(ib)
for i = 2 to n
if A(ia+1) + B(ib) A(ia) + B(ib+1) then
ia = ia + 1
else
ib = ib + 1
end if
output ia, ib, A(ia) + B(ib)
end for
Dave
On Oct 14, 2:55 am, Harshal hc4...@gmail.com wrote:
After reading Gene's example, change my pseudocode to this:
ia = 1
ib = 1
output ia, ib, A(ia) + B(ib)
for i = 2 to n
if A(ia+1) + B(ib) A(ia) + B(ib+1) then
ia = ia + 1
output ia, ib, A(ia) + B(ib)
else if A(ia+1) + B(ib) A(ia) + B(ib+1) then
ib = ib + 1
@sourav
I think the best way to explain my logic is to draw a 2D matrix
5 4 2 1
6
5
4
2
then you would find the patten. i have something draw on the paper. if
you need, i guess i can scan and send it out
On Oct 7, 10:05 am, sourav souravs...@gmail.com wrote:
@lingerdave
If you get
@ Ercan,
yes, you were right. i forgot about that.
anyway, that's the idea. you would need to move pointers on both,
depends on which is bigger. for loop w/ i=k, when the loop stops, you
have the pointers pointing at the numbers you wanted
On Oct 6, 7:16 pm, Gönenç Ercan gon...@gmail.com wrote:
A - 5, 4, 2, 1
B - 6, 5, 4, 2,
M - 6,b,5,a,5,b,4,a,4,a,2,a,2,a,1,a
x=6b, find the index of B[1]=5 in A, which is 0. so 1 big number. k=1
x=5a, find the index of A[1]=4 in B, which is 3. so there are 2 more,
k=3
.
.
.
In the case if k=2 is asked, we know that k=2 can be found when a=5,
then
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)
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
On Fri, Sep 17, 2010 at 3:36 PM, Krunal Modi krunalam...@gmail.com wrote:
Your solutions are pretty impressive.
Which place(country) are you from ?
where are you studying (or done :) ) ?
Keep it up...
Good Wishes..
--Krunal
On Sep 14, 9:29 pm, Gene gene.ress...@gmail.com wrote:
You can
nice recurrence
On Sep 14, 9:29 pm, Gene gene.ress...@gmail.com wrote:
You can approach this the same way you'd do it by hand. Build up the
string of brackets left to right. For each position, you have a
decision of either ( or ) bracket except for two constraints:
(1) if you've
take this approach
fill array of snakes starting position in snake[num_snake]
for each snake[i] , take the end of snake and fill in some other array
take random number gen and fill these arrays--
e.g. end_snake[i] = ran(start_snake[i]-10) // so that snake does not
end up in same row
same logic
Your solutions are pretty impressive.
Which place(country) are you from ?
where are you studying (or done :) ) ?
Keep it up...
Good Wishes..
--Krunal
On Sep 14, 9:29 pm, Gene gene.ress...@gmail.com wrote:
You can approach this the same way you'd do it by hand. Build up the
string of brackets
@bittu, we are here to discuss the way to solve it. Posting a code here will
not do anything good.
Anil Kumar S. R.
http://sranil.googlepages.com/
The best way to succeed in this world is to act on the advice you give to
others.
On 14 September 2010 13:33, bittu shashank7andr...@gmail.com
Some people have sent email asking what the stack looks like as the
program runs. It's pretty silly to worry about this. If you really
want to know, it's easy to modify the program to print a stack
trace.
Here you go:
#include stdio.h
// Buffer for strings of ().
char buf[1000];
typedef
#includestdlib.h
#includestdio.h
#includemath.h
#includeconio.h
///O(N^2) solution Does solution exits
in O(n) or (nlogn)..? reply me sum1 git dis..
//i will post analysis of dsi program later
int turn, square;
long game, totalgames;
int seed;
int chutehit[10],
You can approach this the same way you'd do it by hand. Build up the
string of brackets left to right. For each position, you have a
decision of either ( or ) bracket except for two constraints:
(1) if you've already decided to use n left brackets, then you can't
use a another left bracket and
Hi
On 14 September 2010 13:33, bittu shashank7andr...@gmail.com wrote:
#includestdlib.h
#includestdio.h
#includemath.h
#includeconio.h
///O(N^2) solution Does solution exits
in O(n) or (nlogn)..? reply me sum1 git dis..
//i will post analysis of dsi
And please stop posting the same thing twice. It's been happening for
the past couple of days at least.
@Question:
I think you can use graphs and flood fill algo for this. Every
possible move can be represented with an edge. Flood fill will help
you figure out possible moves from you current
Just find out the max and 2nd max in n + log(n) -2 steps and add them.
there is no need for sorting as such
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from
but addition also should be in array
On Sun, Aug 22, 2010 at 3:05 AM, arpit agarwal erarpitagar...@gmail.comwrote:
Just find out the max and 2nd max in n + log(n) -2 steps and add them.
there is no need for sorting as such
--
You received this message because you are subscribed to the
Some additions below:
On Jul 4, 1:30 am, Amit Jaspal amitjaspal...@gmail.com wrote:
Thanks Ashish for this wonderful postI must say many of my doubts
regarding networking were cleared
And I will highly appreciate if any one can add on to this wonderful post by
ashish..
On Sat, Jul
Is it necessary that the sectors allocated to the file are strictly in
increasing number?
Can file2 have sectors like *sec12-sec10-null* ???
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Sat, May 29, 2010 at 12:37 AM, Atul Kumar atul...@gmail.com wrote:
Sorry the example should be
Here is the code snippet for it.
http://codepad.org/COlqFBbR
let me know if you have any questions.
Anand
On Fri, May 28, 2010 at 12:37 PM, Atul Kumar atul...@gmail.com wrote:
Sorry the example should be
file1 = sec2 - sec7-sec9 - sec11 - null
file2 = sec10 - sec12- null
as first sector
Sorry the example should be
file1 = sec2 - sec7-sec9 - sec11 - null
file2 = sec10 - sec12- null
as first sector contains the file information.
google don't hear DFS or linear parsing, give me the code ;)
On May 27, 11:28 am, Atul Kumar atul...@gmail.com wrote:
There is a file system on the
You'd better wite a program.
On 11 окт, 10:42, Vaibhav Jain [EMAIL PROTECTED] wrote:
Algo:
1. initialize final_result array with whole sequence and count number of
keywords in no_of_keys and initialize counter array for keywords with value
zero.
2. if sequence_ptr is not null then start
You'd better write a program.
On Oct 11, 10:42 am, Vaibhav Jain [EMAIL PROTECTED] wrote:
Algo:
1. initialize final_result array with whole sequence and count number of
keywords in no_of_keys and initialize counter array for keywords with value
zero.
2. if sequence_ptr is not null then
Algo:
1. initialize final_result array with whole sequence and count number of
keywords in no_of_keys and initialize counter array for keywords with value
zero.
2. if sequence_ptr is not null then start scanning the sequence if
keyword_matches() in sequence put into temp_array and update pointer
No, I am not trying to do that at all. The trie is built to contain
only keywords. It can then be used to answer the question for the
current character 'Is this character part of a candidate keyword?' and
do this O(1). Candidate keywords are identified initially by the trei
root returning a
No, I am not trying to do that at all. The trie is built to contain
only keywords. It can then be used to answer the question for the
current character 'Is this character part of a candidate keyword?' and
do this O(1). Candidate keywords are identified initially by the trei
root returning a
I just wanted to see the trei.
Try Suffix Tries ( FYI : reTRIEval )
-vEnKAt
--
Blog @ http://blizzardzblogs.blogspot.com
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
Hi Andrey,
On Oct 8, 7:56 pm you wrote:
... Enumerating of the words makes no sense.
Agreed.
... As Vishal suggested a trie looks more realistic. Building the
trie can be done O(m), with m - total characters in keywords.
Identifying whether a document character is part of a keyword
I have to admit that I was wrong in my previous post. I stated that if
we have all words in the enumerated we can operate with them better
(faster) but it is true. Enumeraing of the words makes no sence..
Similar objections to using a hash table to assign integers to words.
If collisions are
reposting since it didn't appear yesterday, apologies
A small variation of Vishal's algorithm to eliminate the need of the
bitmap. I use a hash table of integers index by the keyword,
initialized to all 0. I also make use of the property that in the
shortest summary the first and the last
On 1 окт, 06:20, Sticker [EMAIL PROTECTED] wrote:
En, it is the idea. You assume each keyword is a single character and
you use a map to hash key words and their counts. Each time you extend
the range to right hand side, you may increase the counts of some
found key words and each time you
Check this program:
#include map
#include string
#include iostream
#include algorithm
#include iterator
using namespace std;
class Range : public pairconst char*, const char* {
public:
size_t size() const { return second - first; }
Range(const char* f=0, const char * s=0)
En, it is the idea. You assume each keyword is a single character and
you use a map to hash key words and their counts. Each time you extend
the range to right hand side, you may increase the counts of some
found key words and each time you shrink the range from the left hand
side, you decrease
We might even use String Trie. The search time would be O(m) where m is the
length of maximum length keyword. Since mN (normally), it would be as good
as O(1).
This would of course require preprocessing. Again, I am assuming no
constraint on space.
On 9/25/07, Sticker [EMAIL PROTECTED] wrote:
To Vishal: My idea is similar to yours. I like to use hash table as
well. But I wonder which hash function can you use to insert and find
keywords with O(1) time? Keywords are not single characters. They are
normal words. That's basically what I am aftering.
On Sep 25, 2:11 pm, Mayur [EMAIL
the problem is you need a hash table to maintain all the keywords,:)
because they do not have to be a single characters, or you can store them in
array, but then you need binary search,:)
Vishal 写道:
How about keeping two pointers - startp and endp.
Keep a count of frequencies of keywords
Hash table should give you O(1) insertion and search complexity; which is
what we need, right?
There is no constraint on space complexity, I believe.
On 9/24/07, daizisheng [EMAIL PROTECTED] wrote:
the problem is you need a hash table to maintain all the keywords,:)
because they do not have
Vishal 写道:
Hash table should give you O(1) insertion and search complexity; which
is what we need, right?
There is no constraint on space complexity, I believe.
On 9/24/07, * daizisheng* [EMAIL PROTECTED]
mailto:[EMAIL PROTECTED] wrote:
the problem is you need a hash table to
Another possibility is to first pre-process the keywords into
automaton-like structure (Google for Aho Corasick string matcher), and
then use it over the document. This would probably be helpful only if
the number of keywords is much smaller than the document itself..
On 9/25/07, daizisheng
201 - 300 of 300 matches
Mail list logo
