This is a special case of shuffling problem. In shuffling problem we have
to merge k (here k = 3) parts of array such that each kth element is from
the same sub-array and in same order. For eg -
a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should become = a1 b1 c1 a2 b2 c2 a3
b3 c3 a4 b4 c4.
Usually
Sorry, small mistake in designated index calculation.
It should be k*p2 % (n-1) instead of (k*p2 -1) % (n - 1).
Thanks,
- Ravindra
On Thu, Nov 3, 2011 at 11:37 PM, ravindra patel ravindra.it...@gmail.comwrote:
This is a special case of shuffling problem. In shuffling problem we have
to merge
algorithm finds a number in the range 300,000,000 to
999,999,999. Does it?
Dave
On Oct 29, 12:30 pm, ravindra patel ravindra.it...@gmail.com wrote:
Assuming that we know the lower bound and upper bound of the range of
numbers (If not then we can determine it in one pass).
// Solution 1
Assuming that we know the lower bound and upper bound of the range of
numbers (If not then we can determine it in one pass).
// Solution 1
let lb = lower bound, ub = upper bound, sum = 0;
for each number read from file - sum = sum - number + ub--;
at the end of for loop sum += lb; // This is
I dont think the greedy approach gives the optimal solution here. Take the
below case -
Items are - 5, 4X2, 3, 2X2 and bins are of size 10. Greedy approach will
make choice in order -
bin1 - 5 + 4
bin2 - 4 + 3 + 2
bin3 - 2
Total bins required - 3
While in optimal solution -
bin1 - 5 + 3 +2
bi2 -
using power of 2 approach doubles the scope of search each time.
How about using approximation. Say I have lower bound lb and upper bound ub.
Now -
initially lb = 0, ub = 1;
while (a[ub] k)
{
lb = ub;
ub = (ub*k) / a[ub];
}
after end of this loop we'll have a lower bound and upper
@Nitin, excellent algo.
if S 0 j = i-1 return 0 // I believe this mean there is no
solution, you might want to return -1.
Thanks,
- Ravindra
On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg nitin.garg.i...@gmail.comwrote:
Lets say the Amount of petrol is Pi and distance to next petrol pump
Excerpt from The C Programming Language by Kerninghan Ritchie -
*int fflush(FILE *stream) - *On an output stream, fflush causes any
buffered but unwritten data to be written; *on an input stream, the effect
is undefined*.
So fflush was never meant for stdin.
- Ravindra
On Sun, Oct 9, 2011 at
@Anshu
first check that particular number can be written as the sum of two
squares or not
What would be the way to figure it out.
O(n * (number of side which is largest one for any triplet))
Didn't get it.
Thanks,
- Ravindra
On Wed, Oct 19, 2011 at 11:09 AM, anshu mishra
@Wladimir, yeah I have heard about that. Another way of populating primitive
pythagoreans is, for any natural number m 1 (m^2 - 1, 2m, m^2 + 1) forms
a pythagorean triplet. This is useful in populating pythagorean tiplets but
here the problem is to search such triplets from a given int array.
@
Is there a pattern in the indices of the numbers we are swapping. some
formula which may tell the next two indices to swap.
Thanks,
- Ravindra
On Fri, Oct 14, 2011 at 9:40 PM, gaurav yadav gauravyadav1...@gmail.comwrote:
@shiva...keep swapping the underline elements
Hi,
Another question I faced in Amazon F2F.
Given an unsorted array of integers, find all triplets that satisfy x^2 +
y^2 = z^2.
For example if given array is - 1, 3, 7, 5, 4, 12, 13
The answer should be -
5, 12, 13 and
3, 4, 5
I suggested below algo with complexity O(n^2) -
- Sort
Here is a solution based on the fact that the matrix is quiet similar to a
min heap. each cell is smaller than its down and right neighbor.
Note :- This solution modifies the original matrix.
Algo -
repeat k-1 times
set a[0][0] = INFINITY
minHeapify the Matrix (see
it usually works like this -
public class Test1
{
private static Test1 obj; // Static member hence singleton
private Test1() // To prevent the Compiler from creating default
constructor
{
// Do whatever initialization required
}
public static Test1
OR
10
/ \
5 15
/ \/ \
@Bittu, Vaibhav
Can you please illustrate your algo for below arrays.
Array1 - {1, 3, 5, 7}
Array2 - {0,0,0,2,0,4,6,8}
Thanks,
- Ravindra
On Wed, Jul 13, 2011 at 9:47 PM, vaibhav shukla vaibhav200...@gmail.comwrote:
start from the end of both the arrays... and try simple merge process
.
PS: Still, if you are suggesting that we should not consider 0 as a value.
Then you can perform an compaction operation on 2nd array.
Regards,
Sandeep Jain
On Wed, Jul 13, 2011 at 10:18 PM, ravindra patel ravindra.it...@gmail.com
wrote:
@Bittu, Vaibhav
Can you please illustrate your
proposed is the original problem. I am just
asking you to assume is as a slightly more complicated variant of the
orginal problem :-).
Regards,
Sandeep Jain
On Wed, Jul 13, 2011 at 10:53 PM, ravindra patel ravindra.it...@gmail.com
wrote:
@Sandeep,
If we do compaction then it becomes
There are infinite solutions to this problem. Say x flowers are plucked and
y flowers are offered in each temple. then -
2(2(2(2x-y) -y) -y) -y =0
i.e.
16x-15y=0;
any pair the x and y satisfying this equation is a solution.Smallest numbers
are 15, 16 as Abhishek told.
Thanks,
- Ravindra
On
/Subset_sum_problem )
I really appreciate a O(n) solution to this problem on a single-processor
system.
Kishen
On Sun, Oct 24, 2010 at 1:50 PM, ravindra patel
ravindra.it...@gmail.comwrote:
It has nothing to do with time complexity.
My bad. Wrong choice of words. So in the PRAM model you can say
=i+1 to n
for k=j+1 to n
compare A[i,j] and A[j,k]
if A[i,j]==A[j,k]
find i,j,k are collinear.
so we should need O(n^3), is it right?
On Sun, Oct 24, 2010 at 1:05 AM, ravindra patel
ravindra.it...@gmail.comwrote:
Can be done in O(n^2) time using the slope as people suggested
@ Kishen
So lets say you have 100 parallel processors and you are given an array of
100 elements, then the loop will execute in 1 clock. Now lets say on the
same machine you are given a problem array of 1 million elements. So how
many clocks are you gonna consume, assuming all your 100 processors
for time complexity on scalar machine or on a parallel machine.
Unless specified otherwise, my assumption by default would be a scalar one
though.
- Ravindra
On Sun, Oct 24, 2010 at 11:50 PM, ravindra patel
ravindra.it...@gmail.comwrote:
@ Kishen
So lets say you have 100 parallel processors
Can be done in O(n^2) time using the slope as people suggested above.
1- Sort the points in increasing order of x cord. O(nlogn)
2- prepare a n*n matrix A where A[i,j] = slope( point(i), point(j) ) -
O(n^2) [Note that point i and j are sorted in increasing order of x]
3- find a pair of A[i,j]
@Asquare
If you have additional array, why'd you take so much pain. Just put each
number in corresponding bucket (read same index in the new array). The empty
buckets are the missing numbers.
Thanks,
- Ravindra
On Wed, Oct 13, 2010 at 12:03 AM, Asquare anshika.sp...@gmail.com wrote:
Thanks
) in case b).
We have:
f(n) = 2^(n+1) - 2 and
g(n) = 4f(n-1)+3.
So g(n) = 4*2^n-5
On 2010-10-9 1:56, ravindra patel wrote:
@Terence
Solution for first one is trivial. Just double the number of moves of
typical ToH as each pair requires now 2 moves.
In second one the approach
@Terence
Solution for first one is trivial. Just double the number of moves of
typical ToH as each pair requires now 2 moves.
In second one the approach is correct but the calculation is wrong.
F(n) = 4f(n-1) + 3 = 3(4^n -1)/(4-1) = 4^n-1 = 2^2n -1.
This can however be optimized as you can
@Mridul
Thats correct. You can however optimize on space complexity. At any point of
time you need only current max row and previous max row, so you can manage
with only 2 rows (in fact just 1 if you optimize furthure).
On Sun, Oct 3, 2010 at 1:02 PM, Mridul Malpani
Your test case is wrong. With this pattern you can have at max n/3
occurrences of 1. The questions says that repeated element has n/2
occurrences
On Thu, Aug 5, 2010 at 8:37 PM, Manjunath Manohar
manjunath.n...@gmail.comwrote:
consider the test case of...
1 2 3 1...
1 repeated n/2 times and
Nice solution. Reduces number of comparisons to half of Ashish's algo. The
complexity remains O[n] though. Can it be made more efficient, like O[log n]
On Thu, Aug 5, 2010 at 10:59 PM, Pramod Negi negi.1...@gmail.com wrote:
compare pair wise i.e a[0] and a[1]a[2] and a[3]..
leave out last
30 matches
Mail list logo
