@sharad,ya inplace soln is desired...
--
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
algogeeks+unsubscr...@googlegroups.com.
For
if the array contains only numbers 1 to n then it can be done in O(n)
inplace otherwise only way is hashing or sorting.which is trivial
solution...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Its simple...
Reverse the whole string than reverse each word. an dthe work is done
complexity O(n)
This is a standard question of interview
On Sat, Jun 5, 2010 at 9:49 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
Have you posted the same question twice or i am feeling sleepy?
--
@Shobhit
@Rohit
Is it done it linear time?? I dont think so...
On Sat, Jun 5, 2010 at 9:33 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
Tokenize the string and print it reverse!
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of
Rohit, you are very well awake
On Sat, Jun 5, 2010 at 9:49 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
Have you posted the same question twice or i am feeling sleepy?
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer
DP approach for solving this problem.
Anand
On Fri, Jun 4, 2010 at 9:06 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
What precisely did you not understand??
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and
http://codepad.org/NDAeIpxR
Here is code for it
On Sat, May 29, 2010 at 7:45 PM, Anurag Sharma anuragvic...@gmail.comwrote:
@pawan
Will it not take O(n^2) time then.
What he is talking about is solving it in O(nlogn) time
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Sat, May
Tokenization is done in linear time. Just save the words in an list (And
what makes you think of non-linearity in tokenization!)
And then iteration over the tokens is trivially linear.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer
#includestdio.h
int main()
{
short int i=0;
for(i=5i=-1;++i;i0)
printf(%u\n,i);
return 0;
}
o/p coming is 1...4,294,967,295
short int is of 2 bytes
can any one plzz explain the o/p
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
Hi all,
Please correct me if I am wrong. Since quick sort is in-place
sort, there is no difference in stack space whichever order you do it. In
the worst case the stack depth can be O(n) unless you convert the quick sort
of longer sub-array to iteration instead of recursion in which
Hi,
How to find largest palindrome, which is even in length in a string.
Complexity should be lessthan O(n^2).
Ex;- abacbbcababac - Given string.
'abacbbcaba' - is the largest even length palindrome.
Thanks,
Satya
--
You received this message because you are subscribed to the Google Groups
Actually he means the case when you implement quicksort using stacks.
--
--
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
output on my compiler is 165535
as i=0 initialy ++i is true and so for loop condition is true and printf is
executed. when i becomes 65535 then ++i is equal to 0 and so for loop
condition becomes false.
On 5 June 2010 13:44, sharad sharad20073...@gmail.com wrote:
#includestdio.h
int main()
1. first find two consecutive letters which are same.
2 point ptr1 to left character and ptr2 to right one
3. now increment ptr2 and decrement ptr1. compare if they are pointing to
same characters. if yes repeat this step
4. if no then store in length ptr2-ptr1-2
5. go to step 1 untill all
for(int i=0; iword.length-1; i++)
{
if(word[i]==word[i+1]) //for an even palindrome, consecutive letters
at the middle of the string have to be the same
{
palindromeFound=true;
while(n0mword.length) //once you've found the middle of
the palindrome, compare left of
Can be done in O(n log n) without using aux. memory. Can be done in
O(n) if you use something like a hash table.
On Jun 5, 12:40 am, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
Inplace in O(n) seems unlikely to me.
Well you should still try!
how can we make out whether to apply greedy approach or dynamic programming
to a problem??
--
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
@divya,which compiler u r using,i m getting this o/p on gcc compiler
@mohit:loop stops at 4,294,967,295 in gcc
--
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
Greedy can be used to find one solution which has some special
characteristics.
It should be like - You are able to say that if for any instance of size k
the greedy and the optimal solution match, then for any corresponding
instance of size k+1, the greedy solution is atleast as good as optimal.
If you make it unsigned short int.. then it goes to 65535 on g++/gcc
--
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
Ok. so you have a list.
Iterating over it is linear isn't it?
Ahh... you will need a doubly linked list or an arraylist.does it solve ur
prob?
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
turbo c++ and my o/p is logical as well
On 5 June 2010 17:58, sharad kumar sharad20073...@gmail.com wrote:
@divya,which compiler u r using,i m getting this o/p on gcc compiler
@mohit:loop stops at 4,294,967,295 in gcc
--
You received this message because you are subscribed to the Google
Maximum number of elephants alive
Hello guyz,
Every elephant has a birth_time and a death_time. Given N Elephants
with birth times and death times.. How can we find
1) the maximum number of elephants that can be alive at any given
point of time.
2) what is the year in which you can have maximum
Complexity is O(n3) for both above solutions
Ex:
On Sat, Jun 5, 2010 at 3:27 AM, Minotauraus anike...@gmail.com wrote:
for(int i=0; iword.length-1; i++)
{
if(word[i]==word[i+1]) //for an even palindrome, consecutive letters
at the middle of the string have to be the same
{
reason for that o/p is ...
coz range of short int is -32768 to 32767
and value of i start with i=0
and each time it will increment by 1
so corresponding value of i will be
1
2
3
.
.
.
32766
32767
-32768
-32767
.
.
.
.
-2
-1
but
coz in printf u r using %u so it will print...
1
2
3
.
.
.
oh... why did u put %u.
i did not even notice that :P
--
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
This a good example of dynamic programming.
On Fri, Jun 4, 2010 at 10:15 AM, satwik krishna sathi...@gmail.com wrote:
i think the best way to trace is to draw a picture of the stack and put the
values and acc understand the flow
On Fri, Jun 4, 2010 at 7:22 AM, Prashant Kulkarni
use interval trees.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Sat, Jun 5, 2010 at 6:16 PM, amit amitjaspal...@gmail.com wrote:
Maximum number of elephants alive
Hello guyz,
Every elephant has a birth_time and a death_time. Given N Elephants
with birth times and death times..
@Amit :
Query 1 : It can be solved in O(n) by checking which elephants life span
contain the given year
Query 2 : Picking up the fact that a elephant die only after its birth we
can find the second query in O(nlogn)
ALGO:
1. sort in increasing order birth year and death
Find if a number is divisible my 3, without using %,/ or *. You can
use atoi().
--
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
Follow hare and tortoise algorithm.
For even length,
once the traversal through out the string is done, move the fast
pointer to slow pointer +1 location and start iterating for (length/2)
times with 2 indices. One indice increasing for fast pointer and the
other for slow pointer. Keep checking
Given an array with some repeating numbers. Like 12,6,5,12,6
output: 12,12,6,6,5
12 shud come before 6 since it is earlier in list. So cant use a
dictionary.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Apologies.
I thought the question was about just checking for palindrome.
On 6/6/10, Antony Vincent Pandian.S. sant...@gmail.com wrote:
Follow hare and tortoise algorithm.
For even length,
once the traversal through out the string is done, move the fast
pointer to slow pointer +1 location
Given an n X n array with rows sorted and cols sorted, find the number
of negative elements in most efficient way
--
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
Given an array arr[] of n integers, construct a Product Array prod[]
(of same size) such that prod[i] is equal to the product of all the
elements of arr[] except arr[i]. Solve it without division operator
and in O(n).
Can someone explain me the logic.
Thanks!!
--
You received this message
Give a O(nlogk) time algorithm to merge k sorted list into one sorted list,
where n is the total number of elements in all the input list.
My approach:
1. take first element from all the k sorted list and build heap for those
elements.
2. call heapify on all k elements to sort it.
3. repeat the
#includeiostream
using namespace std;
int main()
{
int arr[5]={1,2,3,4,5};
int res[5]={1,1,1,1,1};
int left=1,right=1,i=0;
for(i=0;i5;++i)
{res[i]*=left;
res[4-i]*=right;
left*=arr[i];
right*=arr[4-i];
this problem has been discussed i think..
On Sun, Jun 6, 2010 at 12:15 AM, divya sweetdivya@gmail.com wrote:
Find if a number is divisible my 3, without using %,/ or *. You can
use atoi().
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
What makes you think it is O(n^3).
I did not read the code one but divya's solution seems to be O(n^2)
for worst case.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
Actually complexity is O(n), BUT it won't work for aa. It'll
return aa instead of the whole string.
I think you can use similar approach but add another check under the
first 'if' statement since 'aa'
is a special case. But then again the algo will crap out for a string=
bb. I
Subtract 3 from the number until either you get 0 or a negative
number. If you get 0, its divisible, else not.
You can probably do this by bit shifting too.
On Jun 5, 11:45 am, divya sweetdivya@gmail.com wrote:
Find if a number is divisible my 3, without using %,/ or *. You can
use atoi().
1. check arr[0][0]. If this is non negative, there are 0 negative
numbers. (assuming sorting is ascending)
2. for arr[i][j], increment j until you hit a non-negative number.
this index will be limitRow
3. increment i, until you hit a non-negative number, this index will
be limitColumn,
for
My approach:
let's say we have two sorted arrays.
array1= x1, x2 x3
array2 = y1, y2, y3
array3= z1, z2,z3
all three arrays are sorted.
1. sort x1,y1,z1 using heap sort.
2. do this for rest of the elements of the array to create a final sorted
array in O(nlogk)
On Sat, Jun 5, 2010 at 8:45 PM,
Just read your code. It wont even work.
Do you assume only one even length palindrome!?
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this
Can u elaborate on the 2nd step.
btw, did u understand my soln?
--
--
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
This is almost the most basic dp. Read some of the examples from eva
tardos. That would help.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received
@Rohit I could understand your solution.
second step is sort the element using heap sort.
On Sat, Jun 5, 2010 at 9:04 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
Can u elaborate on the 2nd step.
btw, did u understand my soln?
--
--
assuimg the array is sorted likeeach number below is less than the one
above and more than the one right to it
start from the bottom right ..start moving right until u reach anumber less
than zerocalcuate the num of negative elements in that row(n-current
columng pos)..and then move
48 matches
Mail list logo
