but actually we need something better as per prob,
cannot be done in O(n).
so we need to think of something like O(n lg n) or O( n ^ 3/2) :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
Google has many visitors to its site. And it tracks what pages the
customers visited, etc and other stuff. Lets say you store the data of
customer id and the page id as a record in a log-file. Now assuming
that you have created one log file for each day with that above data-
format. Give me the
@sharad
while storing each element in hash by your approach u ll check if its
already there in hash. so the complexity here will be O(n2). correct me if i
m wrong. isnt there ny better algo..?
On 6 June 2010 06:28, sharad kumar aryansmit3...@gmail.com wrote:
@dhivya:keep storing the first
No it will be O(n).
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
Algorithm
#includeiostream
#includemap
#includeiterator
using namespace std;
int main()
{
int arr[5]={12,3,4,3,3};
mapint,intmp;
int i=0;
for(i=0;i5;++i)
{
if(!(mp[arr[i]]))
mp[arr[i]]=i;
else
continue;
@sharad: Your code seems will seem to give output 12,3,4 and not
12,3,3,3,4. It semes from the original description of the problem that
you also need to keep count of frequency of occurance of items in the
map.
Secondly, you have iterated through the map and got the elemenst in
same order as you
Hi All
Here is a problem for us to solve:
Write a function which takes as parameters one regular
expression(only ? and * are the special characters to consider) and a
string and returns whether the string matched the regular expression.
--
You received this message because you are subscribed
Suffix tree is obviously there but
1. It requires more lots of space. Just draw a suffix tree and you will know.
2. Pre-processing takes time. We cant ignore this time because its
proportional to N.
There is one linear solution described here:
Use hash table with customer ID as key.
There can be three components in value: 1. num_days 2. pages 3. flag
For each line, calculate hash, find value for given key.
Increment appropriate values (i.e. pages or num_days).
If num_days 1 pages 1, add this customer to result array, mark
this
lets say u entered a*.nw aab is i/p string then recursivley substitute a and
check for it.or use a table for storing the augmented grammer
On Sun, Jun 6, 2010 at 6:02 PM, Veer Sharma thisisv...@rediffmail.comwrote:
Hi All
Here is a problem for us to solve:
Write a function which takes
A square Island surrounded by bigger square, and in between there is
infinite depth water. The distance between them is L. The wooden
blocks of L are given.
The L length block can't be placed in between to cross it, as it will
fall in water (just fitting).
How would you cross using these L length
There are N nuts and N bolts, all unique pairs od Nut and Bolt
You cant compare Nut with Nut.
You cant compare Bolt with Bolt
You CAN compare Nut with Bolt
Now how would you figure out matching pairs of nut and bolt from the
given N nut and Bolt.
The basic soln is O(N^2). Give O(NlogN soln)
--
Convert in O(n) time:
a1a2a3a4.aNb1b2b3b4.bN
to
a1b2a2b2a3b3a4b4..aNbN
--
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 this group, send email
in o(n) take a separate array of size 2n and for iteration a[i] and a[i+1]
should have ai and bi elelemnt
On Sun, Jun 6, 2010 at 7:39 PM, sharad sharad20073...@gmail.com wrote:
Convert in O(n) time:
a1a2a3a4.aNb1b2b3b4.bN
to
a1b2a2b2a3b3a4b4..aNbN
--
You received this
I am sorry for the link if it caused any confusion. It was just a part of
the signature. Kindly disregard the link in this context.
Anurag Sharma
On Sun, Jun 6, 2010 at 7:55 AM, Minotauraus anike...@gmail.com wrote:
I think you can do this in O(n) time. Feel free to correct me where
I'm
this is ques by adobe and they want inplace soln..
--
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 this group, send email to
output willl be 12 12 5 6 6
On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote:
@divya: Does your problem require the output to be sorted also? What
will be the output required if inout is 12,5,6,12,6? Will it be
12,12,6,6,5 or 12,12,5,6,6,?
Sain
On Jun 6, 12:01 am, divya
1. have an array of N years. starting with first year and ending at last year.
O(N) space here. initialise all elements to zero.
2. Take array of E and birthyear first. Whenever you encounter new
birthyear, do array[year]++.
3. Take array of E and deathyear now. Whenever you encounter new
place the L block diagonally...
--Sundeep.
On Sun, Jun 6, 2010 at 7:29 PM, sharad sharad20073...@gmail.com wrote:
A square Island surrounded by bigger square, and in between there is
infinite depth water. The distance between them is L. The wooden
blocks of L are given.
The L length block
Given an array of size n wherein elements keep on increasing
monotically upto a certain location
after which they keep on decreasing monotically, then again keep on
increasing, then decreasing
again and so on. Sort the array in place (ie. using only O(1) extra
memory).
--
You received this
In order to make it inplace, time complexity has gone to n^2.
Rearrange(array,int N) //So array size is 2N
{
int i = 1;//points to index array[1] which has a2 since a1 is already
at the correct place;
int j = N;//array[0] to array[N-1] is a1 to aN. so j is index of b1
//it
@divya:go through the elements and keep inserting them in a BST. While
inserting if elements already exists in BST, increase its frequency
(Node of BST has element a nd frequency). Also if elemengs is newly
inserted then also place it in a seperate array. So this array (say
Array M) will become
Here is a modified version tower of hanoi. Along with usual tower of
hanoi conditions there ia also a condition that a disk cannot rest
over another disk that is more than one size larger. For eg disk 2 may
rest on disk 3 but not on disk 4. How to make changes to the existing
algo to incorporate
Take a Nut, try putting it to all bolts (this is Comparing Nut with
Bolt). If Nut goes not go and fit into bolt, keep the bolt on left, if
Nut fits loose, keep the bolt on right and keep the bolt and nut which
match, at centre. This is pivot of quicksort. All bolts to left of
this central Nut+bolt
How do you count the number of ways a number can be expressed as a sum
of 2 or more numbers?
For eg. if the number is 5 , count=3 i.e 1+1+1+1+1, 4+1, 3+2
note 2+3 is same as 3+2
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
I meant O(n) considering there are n elements and not n rows/
columns. :-)
so my n = nrows x ncolumns. Since we talk of input size in terms of
number of elements
I thought it'd be n instead of nrowsXncolumns.
On Jun 6, 4:26 am, Senthilnathan Maadasamy
senthilnathan.maadas...@gmail.com wrote:
@Anand: Thanks for the code. I knew you could do it by bit
shifting. :-)
On Jun 5, 10:21 pm, Anand anandut2...@gmail.com wrote:
Here is a code for it.http://codepad.org/umkh3pjf
On Sat, Jun 5, 2010 at 7:14 PM, Minotauraus anike...@gmail.com wrote:
Subtract 3 from the number until either
Here is my approach is o(n).
http://codepad.org/YAFfZpxO
http://codepad.org/YAFfZpxO
On Sun, Jun 6, 2010 at 7:28 AM, sharad kumar sharad20073...@gmail.comwrote:
this is ques by adobe and they want inplace soln..
--
You received this message because you are subscribed to the Google
Here is my approch which runs in O(n).
http://codepad.org/d3pzYQtW
http://codepad.org/d3pzYQtW
On Sun, Jun 6, 2010 at 7:47 AM, divya jain sweetdivya@gmail.com wrote:
output willl be 12 12 5 6 6
On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote:
@divya: Does your problem
In number theory, a partition of a positive integer n is a way of
writing n as a sum of positive integers. Two sums that differ only in
the order of their summands are considered to be the same partition;
if order matters then the sum becomes a composition. The number of
partitions of n is given
30 matches
Mail list logo
