Re: [algogeeks] Re: Amazon interview Question
Hi Ritesh
Yeah, you are right. we do not need to sort. my bad
Thank you for explaining clearly
On Thu, Dec 27, 2012 at 4:29 AM, Ritesh Mishra rforr...@gmail.com wrote:
@anurag : there is no need to SORT. as it will increase complexity O(n) to
O(n log n).
here is the correct code.. please look over it and notify me if i'm wrong .
T.C. = O( n )
// ex: 1 4 3 2 0 i'm explaining on behalf of it.
bool permute (int *arr , int N )
{
if ( N=1 ) return false;
for ( int i = N-2 ; i = 0 ; i-- )
{
if ( arr[i+1] arr[i]) // now i points to 1
{
for ( int j = N-1 ; j i ; j--)
{
if ( arr[i] arr[j]) // now j points to 2(just greater
than 1 )
{
swap(arr[i],arr[j]) ;//this will generate 2 4 3 1 0
since 4310 are already sorted in reverse
//thus no need to sort again in
inc order rather than reversing
i++ ; j = N-1;
while(ij) swap(arr[i++],arr[j--]) ; // reversing the
seq 4..0 to 0..4
return true ;
}
}
}
}
return false ;
}
Regards,
Ritesh Kumar Mishra
Information Technology
Third Year Undergraduate
MNNIT Allahabad
On Mon, Dec 24, 2012 at 7:56 PM, marti amritsa...@gmail.com wrote:
I REPEAT, THERE is no need to SORT;
http://en.wikipedia.org/wiki/Permutation#Lexicographical%5Forder%5Fgeneration
On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
For a given number, find the next greatest number which is just greater
than previous one and made up of same digits.
--
--
--
Regards
Anurag Gupta
IV Year Computer Engineering
Delhi Technological University
(Formerly Delhi College of Engineering)
--
Re: [algogeeks] Re: Amazon interview Question
@marti your answer is completely wrong (check for 234987156221 ans is 2349871*61225 * whereas your answer would be 2349871*65225*) and we do need to sort On Mon, Dec 17, 2012 at 9:10 AM, marti amritsa...@gmail.com wrote: Yeah thanks Sandeep, theres an error in example...it should be 5436827.However there is no need to sort. On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote: For a given number, find the next greatest number which is just greater than previous one and made up of same digits. -- -- Regards Anurag Gupta IV Year Computer Engineering Delhi Technological University (Formerly Delhi College of Engineering) --
Re: [algogeeks] Amazon interview Question
loop from the end of given number till you get a digit less than the previously scanned digit.Let the index of that number be 'i' . if index = -1,then the given number is the largest one else do the following 1) swap the digit at the index i with the digit just greater than it in the scanned portion 2) sort the remaining scanned digits after index i. Ex:- let the given number be 51432 the digit '1' is the first digit less that its previously scanned digit '4' thus, we swap 2 which is the smallest greater digit the '1' in scanned portion to get 52431 and the we sort the remaining digits after the index to get 52134. --
Re: [algogeeks] direct i online test
The complexity of above code is exponential. Here is the simple recurrence for the given problem F(n) = 2*F(n-1) + F(n-2) + F(n-3) for n = 4 where F(1) = 2 F(2) = 5 F(3) = 13 precompute the values and each query will then be O(1) On Thu, Aug 23, 2012 at 8:22 PM, bala bharath bagop...@gmail.com wrote: Can u please explain ur code..!!! -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Question asked in Amazon online test
if we just need to determine number of swaps, it can be Done in O(n) Ex : 11100010 start counting number of zeros from the end so we have zeroCount = 1 whenever we encounter a 1 we add current zeroCount to numberOfSwaps so numberOfSwaps = 1 and so on the final value of numberOsSwaps is the answer correct me if i am wrong -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] how to solve
you dont need that much to do this problem modify merge method in mergesort to calculate the sum in nlgn think about it it's quite easy you must have heard of Count Inversion problem , this is similar to that problem On Tue, Apr 10, 2012 at 6:49 AM, bharath kannan bharathgo...@gmail.comwrote: I dont know if it can be solved in O(n). But O(nlogn) can be done using BIT. Refer topcoder tutorial for Binary indexed trees. On Mon, Apr 9, 2012 at 10:56 AM, tarun chabarwal admin20...@gmail.comwrote: how should i approach this problem https://www.spoj.pl/problems/DCEPC206/ can it be solved in O(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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Anurag Gupta III Year Computer Engineering Delhi Technological University (Formerly Delhi College of Engineering) -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon question
I think this works and the complexity is O(sqrt(n))
#includecmath
#includecstdio
#includeiostream
#includecstring
#includecstdlib
using namespace std;
# define INFY 17
int main()
{
int n, i, j;
int val, minDiv, minDis;
while(1)
{
cin n;
minDis = INFY;
for (i = n; i = n+2; i++)
{
for (j = 1; j*j = i; j++)
{
if (i % j == 0minDis (i/j - j) )
{
minDis = i/j - j;
minDiv = j;
val = i;
}
}
}
coutval minDiv val/minDivendl;
}
//system(pause);
return 0;
}
On Mar 22, 10:34 am, atul anand atul.87fri...@gmail.com wrote:
@Rujin : mathematically point 2.2 seems straight forward but can we achieve
value of x and y with an algo whose complexity wud be O(sqrt(E)) ??
On Wed, Mar 21, 2012 at 2:37 PM, Rujin Cao drizzle...@gmail.com wrote:
One possible way is:
1) Put the three candidate number together into an array [n, n + 1, n + 2]
2) Iterate each element *E* in that array and test whether *E* is a prime
number
2.1) If it is, there will be only one way to find the two numbers
product to be *E*, i.e. {x = 1, y = E} OR {x = E, y = 1}, so the result
is E - 1
2.2) Otherwise, we should choose x and y that are closest to the
sqrt of *E*, which is quite straight forward.
E.g. 72 = 8 * 9 and 72 = 2 * 36 (2 8 and 36 9, so |9
- 8| |36 - 2|)
So total time complexity is O(sqrt(E)).
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] MODULUS
how can we take mod by a very large number for example 100283 int mod = 100283; ans % mod is not working Please Help -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: check Similar array
What about this approach: First we will scan the first array and find the smallest number. if it is -ve then we increment all numbers in both the arrays by that number . This ensures that every integer in first array is = 0 some integers in 2nd one maybe -ve if it is,then two arrays are not similar else we follow frequency based tests to find out if two array are similar or not. Time and space Complexity = O(n) This approach assumes that even after adding that most negative number each number in both arrays will be inside the limits of their data types (long long etc) Any counter test case(s)? On Jan 5, 5:35 pm, saurabh singh saurab...@gmail.com wrote: Some very nice approaches have been presented but I still feels for practical situations its better to sort and compare..All other algorithms presented above restricts the max value for an element in the array.In case the maximum value is small,we can simply count sort,and the algorithm will still be O(N) (Much simpler and immune to problems such as finite word size) Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Thu, Jan 5, 2012 at 5:17 PM, atul anand atul.87fri...@gmail.com wrote: @Shashank : as i have mentioned in the question , no sorting allowed. if question would have allowed sorting then why not sort both array and compare it would be much simpler and no need of doing costlier operation like finding power. complexity = O(nogn) + O(mlogm) + O(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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] SuperSum
SuperSum is a function defined as: * SuperSum(0 , n) = n, for all positive n. * SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... + SuperSum(k-1 , n), for all positive k, n. Given k and n, return the value for SuperSum(k , n) modulo 17. 1=k=50 1=n=1,000,000,000 For Example: SuperSum(1,3) = 6 SuperSum(2,3) = 10 SuperSum(4,10) = 2002 SuperSum(10,35) = 150595840 I thought of constructing a table dp [50][20] and pre-computing these values but the solution will definitely time out as n can be upto 10^9. Please suggest how to approach this problem (and more importantly such problems)? 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Algm
that means the range of input is 1 to n^3 i.e there are n numbers and the numbers can vary from 1 to n^3 On Nov 14, 3:48 pm, Carl Barton odysseus.ulys...@gmail.com wrote: Bit confused by your n^3. Could you clarify? In the mean time Radix is an O(n) sorting algorithm. Where n is the length of the array. On 14/11/2011, Vijay Khandar vijaykhand...@gmail.com wrote: Which is the sorting algm sorts the integers [1...n^3] in O(n). a)Heapsort b)Quicksort c)Mergesort d)Radix sort please tell anyone. Vijay. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: median from continuous stream
read this http://www.geeksforgeeks.org/archives/14873 On Nov 8, 10:29 am, Arun Vishwanathan aaron.nar...@gmail.com wrote: Hi to find running median from a stream of random generated numbers I have heard of the 2 heap ( min and max heap ) solution but I fail to understand it...could someone please explain with a small example or so ?? thanks! -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: EOF
@ kunal I was attempting this problem: http://www.spoj.pl/problems/NHAY/ here,input size of haystick is not limited so,can you tell me how to read the haystick. On Sep 7, 12:06 am, Kunal Patil kp101...@gmail.com wrote: If I understand question correctly, then just read as many characters as you can using standard string functions. (like fgets n all related) Output these all characters in a file. Iterate until you have read all the characters and go on appending what you have read to file. You intended to ask something else? -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] EOF
how to read a string whose length is not known and string is so long that we can't read it all at once? input (i.e string) is terminated by EOF -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: C code scanf problem
@ Mehnaaz :the variable no_p will be equal to 0,since it is an
external one
so the declaration char p[no_p][max] is equivalent to p[0][max];
and size of p is zero.
then how you can insert anything into it
as you are doing in for loop?
no_p may receive some non zero value afterwards but array p is not re-
declared so
it doesnt has any space alloted to it ,then how for loop is working
without any glitch?
On Aug 24, 5:58 pm, Mehnaaz mehnaazmohiud...@gmail.com wrote:
#include stdio.h
#define max 30
int no_p;
int main() {
char p[no_p][max];
char x;
int i=0;
printf(enter the no of productions..\n);
scanf(%d, no_p);
printf(you have entered :%d\n, no_p);
printf(Variable who's FOLLOW you want\n);
scanf(%c, x);
printf(you have entered :%c,X);
printf(\n);
for( i =0 ; i no_p ; i++){
printf(enter the production # %d,i+1);
scanf(%s,p[i]);
}
//follow(p,x);
return 0;
}
the output i am getting goes like this
..
enter the no of productions..
3
you have entered :3
Variable who's FOLLOW you want
you have entered :
enter the production # 1
...
at the line 4 of the output its supposed to wait for my scanf() entry
value right??..but it executes the printf after that giving you have
entered
i'm using gcc to compile this
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: wht is d logic behind this
you refer cormen too On Jul 29, 11:19 am, jagrati verma jagrativermamn...@gmail.com wrote: an array containing +ve and -ve integers.find sub array with the largest sum -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Java Book
Please suggest any good book for Java (for beginners) Thanks in advance :) -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: RIDDLE OF THE DAY 29 april
Maid was the criminal because she lied. The day was sunday and you don't get mails on sunday On Apr 29, 12:57 pm, Lavesh Rawat lavesh.ra...@gmail.com wrote: * RIDDLE OF THE DAY A man was killed on Sunday morning. His wife found the body and called the police. The police arrived and questioned the chef, maid, butler, and gardener. Their alibis were: Chef - making breakfast Maid - getting mail Butler - setting table Gardener - watering plants The police immediately arrested the criminal. Who was it and how did they know? * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/04/riddle-of-day-29-april.h... Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
