Monish, please take a look at a similar problem about poor elephants in
the neighboring topic started today. I believe the problem has a similar
solution. Each start point increases the no. of active intervals by one;
each end point decreases it. So, we do the following:
1. Convert the
Can you tell the 'size' of your array 'f' if the intervals are [0, 10],
[10, 9223372036854775808] ?
Programmers should realize their critical importance and responsibility in
a world gone digital. They are in many ways similar to the priests and
monks of Europe's Dark Ages; they are the only ones
Adding to the question. See inline.
On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
There are n Intervals. *1 = n = 1,000,000.* *Limits of interval are
within 64 bit signed int.* Given a set of m numbers, tell in how many
intervals does each number exists.
Example: 4
yeah interval tree and binary indexed tree is a one solution which will
give you answer in log(n) time for each query ,but if i got all the
interval at the beigning of time i can get solution in O(1) time by O(n
) preprocessing take array f initialize with zero,now for each
interval(l,r) do
typo mistake take prefix sum of f and see each index value...continue
On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
There are n Intervals. Given a set of m numbers, tell in how many
intervals does each number exists.
Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers
How was your interview? Can you please share the questions for benefit
of others?
On Oct 1, 3:37 pm, Siddhartha Banerjee thefourrup...@gmail.com
wrote:
lol!!!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
Here is O(n) alg...
Does Waste Memory Though :) just don't have an array over 4G, and you
should be good.
proc Merge_Partition(A)
B = {};
index = 0;
count0 = 0;
count1 = (n/2);
while index to A.length
B[index++] = A[count0++];
B[index++] = A[count1++];
end while
return B
end proc
On
This is a simple merge, so what is the trick? Did you forget something?
On Mon, Aug 1, 2011 at 3:19 PM, Gary Drocella gdroc...@gmail.com wrote:
Here is O(n) alg...
Does Waste Memory Though :) just don't have an array over 4G, and you
should be good.
proc Merge_Partition(A)
B = {};
index =
@Diniz I guess they asked to do in inplace ( with no extra array )
On Mon, Aug 1, 2011 at 2:41 PM, Douglas Diniz dgdi...@gmail.com wrote:
This is a simple merge, so what is the trick? Did you forget something?
On Mon, Aug 1, 2011 at 3:19 PM, Gary Drocella gdroc...@gmail.com wrote:
Here is
@Dave awesome..!
On Sat, Jul 16, 2011 at 7:15 PM, Dave dave_and_da...@juno.com wrote:
@Anand: Assuming that the file contains unsigned 32-bit integers. Set
an integer array a[65536] to zero, read through the file and tally the
numbers based on their low-order 16 bits: a[j0x]++. Since 4.3
how about using voters algorithm? TC O(n) and SC O(1)
On Jul 16, 6:28 am, Anand Shastri anand.shastr...@gmail.com wrote:
Given a file containing 4,300,000,000 integers, how
can you *find **one* that *appears* at *least **twice*
--
You received this message because you are subscribed to the
If the there are problems with hashing method,
What about simply sorting the numbers then comparing the adjacent numbers
!
Time complexity O(nlogn)+O(n)=O(nlogn)
Cheers!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this
@Anand: Assuming that the file contains unsigned 32-bit integers. Set
an integer array a[65536] to zero, read through the file and tally the
numbers based on their low-order 16 bits: a[j0x]++. Since 4.3
billion exceeds 2^32, by the pigeonhole principle, there will be at
least one tally, say
A B are the concatenation of A and B. Set the following order relation
between the numeric strings
A = B iff A B = B A
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Sat, May 28, 2011 at 1:54 PM, sunny agrawal sunny816.i...@gmail.comwrote:
@Logic King
No, My algo will take
here's efficient oneliner without any string manipulation
divide every number by 10^(log10(x).ceil)
sort
convert back to original numbers
join array into string
there are edge-cases where this doesn't work but they can be dealt with
easily - have to go back to work :)
--
You received this
so here's oneliner code in ruby:
a.map{|x| x=x*10+1; -x/10.0**Math.log10(x).ceil}.sort.map{|x|
(-x).to_s[2..-2]}.join
--
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
for eg 10, 9
most signifacnt digit of 10 is 1 and 9 is 9
so after sorting based on most significant digit is
10,9
output 910
2nd ex 2,3,5,78
most significant digit is 2,3,5,7
so out put is 78532
On May 29, 12:59 am, Vishal Jain jainv...@gmail.com wrote:
Can this work...
Lets say I have
@vishal,Sanjeev..
for the inputs 18,187.. apply ur method..
18 -- 188
187-- 187
18187 - ur method
18718 - actual
@Sunny...
i agree that your algorithm takes the *O(N logN)* time.. but again..
the problem is it* doesn't get* the exact solution.
Do we really have a polynomial solution for this
@sravanreddy001
i don't find any cases for which my algo fails and its O(nlgn)
i may be missing something
can you tell any case where it fails
On Sun, May 29, 2011 at 10:15 PM, sravanreddy001
sravanreddy...@gmail.comwrote:
@vishal,Sanjeev..
for the inputs 18,187.. apply ur method..
18 --
I think he means to edit the comparison function to get the order. so
at a time only 2 elements are compared.
On May 28, 7:51 am, Logic King crazy.logic.k...@gmail.com wrote:
@sunny it will work fine if you have 2 numbers only...but what about the
list...3..4 or 5..or morethen the possible
Here is a Java impl...
public class LargestPossibleNumber {
static class LPNComparator implements ComparatorString {
@Override
public int compare(String s1, String s2) {
int l1 = s1.length(); // new element
int l2 = s2.length(); // existing element
if (l1 == l2) {
for (int i1 = 0, i2 = 0; i1
@Logic King
No, My algo will take only O(nlgn) where n is no of elements.
what i mean by editing the comparision function cmp function of sort of
algorithm.h
sort(a,a+n, cmp);
where cmp is the comparision function defined in my prev. post
it will take equal no. of comparision as in sorting.
No, Kadane's algorithm considers subarray sum, we are considering
concatenation ( for whole array ).
The solution with custom string comparator : http://ideone.com/doASH.
On May 27, 9:15 pm, Supraja Jayakumar suprajasank...@gmail.com
wrote:
Hi
Isnt this the Kadane's (largest subarray) problem
@Shubham: Try 8, 89, 7. Your algorithm gives 8897, but the right
answer is 8987.
Dave
On May 27, 1:11 pm, shubham shubh2...@gmail.com wrote:
check whether these steps work:
step 1:
sort the given numbers in the decreasing order based on their first
digit.
step 2:
if two
@sunny it will work fine if you have 2 numbers only...but what about the
list...3..4 or 5..or morethen the possible number of combinations will
be 'N!'...where n is the number of digits...the code will work quite
slowly for larger 'n'.
On Fri, May 27, 2011 at 3:33 PM, Dave
@all geeks ..check out the algo solution with detailed explanation
here
http://shashank7s.blogspot.com/2011/03/wap-to-find-all-possible-palindromes-in.html
let me know if it will fail for any test cases
Thanks Regards
Shashank Mani The Best Way To Escape From The problem is Solve
It
check this one out:
#includeiostream
#includecstdio
#includevector
#includecstring
using namespace std;
int check_palin(string str,int *start)
{
int pos=-1,ret,size=str.size()-1;
char last_char=str[size];
while(possize)
{
ret=0;int i;
pos=str.find(last_char,pos+1);
take “aabab” for example, the result is aba, b,a; however, the
right result is aa,bab
On Wed, May 11, 2011 at 10:57 AM, shubham shubh2...@gmail.com wrote:
check this one out:
#includeiostream
#includecstdio
#includevector
#includecstring
using namespace std;
int check_palin(string
@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?
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
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
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
74 matches
Mail list logo
