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
On Friday, 8 July 2011 04:13:38 UTC+10, Piyush Sinha wrote:
Given an array of integers A, give an algorithm to find the longest
Arithmetic progression in it, i.e find a sequence i1 i2 … ik,
such that
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
largest
In the first pass create a difference array of size n-1 where n is the size
of the input array.
D[i] = A[i+1] - A[i]
Look for for the longest consecutive no. of times an element is repeated in
the difference array.
public void longestAP(int[] a, int n) {
int[] diff = new int[n-1];
http://theory.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf
On Fri, Nov 16, 2012 at 8:55 PM, rajesh pandey rajesh.pandey.i...@gmail.com
wrote:
I think its the stricter version of LIS , where when you see for the
increasing number , just see the number which is greater with the number k
than the
@deepak : all the numbers in the array should be continuous or those k
elemenst can be any where ?
On Thu, Nov 15, 2012 at 2:18 PM, deepak mishra deepakmnni...@gmail.comwrote:
On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:
Given an array of integers A, give an algorithm to
I think its the stricter version of LIS , where when you see for the
increasing number , just see the number which is greater with the number k
than the previous one.
Thanks ,
Rajesh Pandey
On Fri, Nov 16, 2012 at 7:55 PM, bharat b bagana.bharatku...@gmail.comwrote:
@deepak : all the
On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:
Given an array of integers A, give an algorithm to find the longest
Arithmetic progression in it, i.e find a sequence i1 i2 … ik,
such that
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
largest
sdfsdfsdfsdfsdf
On Monday, 11 July 2011 17:01:36 UTC+5:30, Sunny wrote:
@Divye sir
yeah that will work fine if D is in reasonable limits ..
On Mon, Jul 11, 2011 at 4:26 PM, DK divye...@gmail.com javascript:wrote:
@Ritu: Your solution is incorrect.
Consider
1 3 41 43 47 49 90 100
On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:
Given an array of integers A, give an algorithm to find the longest
Arithmetic progression in it, i.e find a sequence i1 i2 … ik,
such that
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
largest
On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote:
Given an array of integers A, give an algorithm to find the longest
Arithmetic progression in it, i.e find a sequence i1 i2 … ik,
such that
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
largest
A solution given below taken from cracking the Coding interview book...
Solution is create a Comparator and a small change in compare method is
that u sort the characters of that string and then compare.
and just sort the arrays, using this compareTo method instead of the usual
one.
@vikas
I believe that if we generalize the question saying that there are N
students and K schools, such that each school can accommodate at max
(N/K) students (which means each school needs to accommodate exactly
(N/K) students. Given this we need to find the minimum distance.
By O(n^3), in this
@ above
small correction..
/*
By O(n^3), in this case it means O((N/K ^ K)) .
*/
Therefore, N = 9, K=3.. hence (9/3)^3 = 27
On Aug 4, 4:24 am, Lucifer sourabhd2...@gmail.com wrote:
@vikas
I believe that if we generalize the question saying that there are N
students and K schools, such that
What is N? This is a fixed-size problem so by definition, every
solution will be constant time.
Don
On Aug 1, 2:48 am, vikas rai vikasloves...@gmail.com wrote:
There is a set of 9 students and 3 schools Every school can be alloted
atmax 3 students .Every school and student has its coordinates
I think it can be done by using some randomized algorithm.
Divide the array into subarrays of equal size and then pick a random
element from each group.Do it 3-4 times,if random number comes out equal
for most of the times,return that element.
I haven't tried it.
On Fri, Jul 13, 2012 at 10:53 AM,
I guess the
linkhttp://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.htmltalks
about modified quick sort approach. Remember, if your choise of pivot
is bad everytime, this will have a worst case performance of O(n). You
should refer to Selection
To Mr. B
how will you find median in O(n) time? please elaborate.
On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:
I found a similar solution looking somewhere else.
The solution for this problem is:
a. There can be atmost 3 elements (only 3 distinct elements with each
@sachin: you can find median in linear sort.
http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote:
To Mr. B
how will you find median in O(n) time? please elaborate.
On Wednesday, July 11,
@sachin:
http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote:
To Mr. B
how will you find median in O(n) time? please elaborate.
On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B
can some body please explain voting algo to me .
On Wed, Jul 11, 2012 at 12:42 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@sachin:
http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal
I found a similar solution looking somewhere else.
The solution for this problem is:
a. There can be atmost 3 elements (only 3 distinct elements with each
repeating n/3 times) -- check for this and done. -- O(n) time.
b. There can be atmost 2 elements if not above case.
1. Find the median of
My previous email got sent accidentally..
Assume if we have 90 elements and need to find 30 elements that are
repeating..as per Sanjay's algo,divide it to 45 elements.. To find majority in
45 elements, the number should repeat = 23 times.. This might not be valid
since the number could
we can use voting algorithm this..
maintain a variable count and a variable index.now make a scan for 1 to
n-3.during a scan initialize count with 1 and index with 0.now if
a[i]==a[index] then increment count else decrement count.when count reached
0.start again incrementing it when u get a new
@above
On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote:
Design an algorithm that, given a list of n elements in an array, finds
all the elements that appear more than n/3 times in the list. The algorithm
should run in linear time
( n =0 ).
You are expected to use
@jalaj :- we will be sorting a copy of the word and then matching the
sorted_sequence with the sorted_sequence of the copy of other words.
It will still be in-place, because we are using a space of Word size where
the input is a dictionary.
This is an amortized in-place.
--
Navin Kumar Gupta
This will work in fine, but multiplying primes requires arbitrary
precision arithmetic for keys of any significant length.
You don't need to compute a hash at all. Just maintain two buffers
long enough to hold the longest word and an O(n) sort like counting
sort. If you are using Latin (8-bit)
I have a doubt. If u r doing inplace sorting of a word during checks for a
word, wouldnt that change that word there itself? then how will the
original anagram get restored to arrange in the output in sorted manner?
On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar jitender...@gmail.comwrote:
The
It can be done inplace, then Time Complexity will be O( N^2 x W ) where N
is no. of words and W is word size.
Start from the left and sort the current word.
Keep a pointer PTR to the first index of the element left to process.
Initially it will be 0.As we add words this pointer moves
@prem: can you please explain the approach clearly, I did't get the
approach.
regards
Abhishek
On May 23, 7:43 pm, Doom duman...@gmail.com wrote:
I am trying to understand the question.. please let me know the answer for
the following cases..
case1:
test
testlong
testlongtest
Atul,
I think that your approach will work, although it may take a huge
amount of time.
One way to potentially make it faster is to select the invoices with
the smallest number of combinations first.
If you first select all of the invoices with exactly one possible
combination, this will prevent
@Hemesh : dats would be an over kill , you are converting O(n) solution to
a subset sum problem which NP
On Tue, Mar 20, 2012 at 7:35 PM, Hemesh Singh hemesh.mn...@gmail.comwrote:
Isn't it a standard subset sum problem? You can generate the Fibonacci
numbers and put them in an array. Now just
Isn't it a standard subset sum problem? You can generate the Fibonacci
numbers and put them in an array. Now just apply the standard algorithm to
find that which Fibonacci numbers add up to make the given sum. Please
correct me if I am wrong.
On Mon, Mar 19, 2012 at 8:58 PM, atul anand
Thanks.
I noticed this too. If the n'th 1/0 digit is supposed to correspond
with the n'th fibonacci number, then my original code would have been
right. But the example isn't done this way.
I fixed the code to match the example the evening of the 18th
(Eastern time), but I guess the change is
@gene it does show your updated code.
@atul from the given input it seems different from Fibonacci encoding.
On Mon, Mar 19, 2012 at 5:32 PM, Gene gene.ress...@gmail.com wrote:
Thanks.
I noticed this too. If the n'th 1/0 digit is supposed to correspond
with the n'th fibonacci number, then
@Gene : yeah i skipped ur updated code...its dere
@shady : it is similar to fib encoding...you just need to reverse the
output from gene code and append '1' at the end...
while decoding it ...this extra '1' is not considered..
i am nt sure but maybe the reason for adding '1' at the end is to
It looks from the example like you pick the largest (as if the digits
were a binary number). Here's what I get:
#include stdio.h
unsigned f(unsigned n, unsigned fi, unsigned fim1)
{
if (fi n) return n;
unsigned r = f(n, fi + fim1, fi);
if (r = fi) {
putchar('1');
return r - fi;
It looks from the example like you pick the largest (as if the digits
were a binary number). Here's what I get:
#include stdio.h
unsigned f(unsigned n, unsigned fi, unsigned fim1)
{
if (fi n) return n;
unsigned r = f(n, fi + fim1, fi);
if (r = fi) {
putchar('1');
return r - fi;
VCE hyderabad
On Mon, Mar 5, 2012 at 3:28 PM, adarsh kumar algog...@gmail.com wrote:
Which college?
On Sun, Mar 4, 2012 at 10:16 AM, teja bala pawanjalsa.t...@gmail.comwrote:
Google is visiting our campus 4 different roles As of now IT field
technician is confirmed so how to approach
Which college?
On Sun, Mar 4, 2012 at 10:16 AM, teja bala pawanjalsa.t...@gmail.comwrote:
Google is visiting our campus 4 different roles As of now IT field
technician is confirmed so how to approach 4 written test. ??
--
You received this message because you are subscribed to the
Google is visiting our campus 4 different roles As of now IT field
technician is confirmed so how to approach 4 written test. ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@Dave : is it a working code??
i have executed your code but getting wrong output...and value of s is
becoming -ve inside loops.
--
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.
0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h
- 1, i+1) )
i am not clear why the parents of a cup in upper row are consecutive?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 10:43 AM, Gene
Well the OP is not clear. You could be right. I solved this problem
once before, and there the glasses were arranged in a pyramid like
they do at weddings in my country (this will only look right if you
set the fixed-width font in Groups:
U
U U
U U U
U U U U
U U U U U
---
The previous proposed solutions all seem far too complicated. It is
not necessary to use a graph data structure. We can simply use an
array to store the quantities of the cups in a row, and update the
array to move to the next row. It would look something like this:
double cupQuan(double L,
Dave, why the assumption that nothing is coming from left side.
Every cup gets something from cup left above and right above itself when
they have something extra?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Feb 27, 2012 at 8:17 PM, Dave
@Ashish: I didn't make any assumption that nothing comes from the
left. Does my code give the wrong answer?
Dave
On Feb 27, 10:36 am, Ashish Goel ashg...@gmail.com wrote:
Dave, why the assumption that nothing is coming from left side.
Every cup gets something from cup left above and right
Dave's code is good. Here is a more abstract way of thinking about
it. Maybe helpful?
Number the rows starting at the top with h=0, and the left i=0. Then
the parents of cup(h,i) are always cup(h-1,i-1) and cup(h-1,i). When
h0, i0 or i h, the parent does not exist.
Let F(h, i) be the amount
Gene, your DP is what i was thinking of but in code i could not coreleate
G(h - 1, i - 1) + G(h - 1, i) part (:
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:
G(h - 1, i - 1) +
@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right child.
here is the explanation :-
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
@Atul: I don't have an n in my algorithm, so I'm not sure what your
assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
where h is the height of the triangle of cups, but the number of cups
is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
yours.
You'll have to
G is just a helper function. You can in line this function and
eliminate it.
When you do this, you'll end up with
F(h, i) = 0.5 * (l + r)
where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else
0
and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0
Here l is the left
@Dave : yeah sorry its O(n) where n is number of nodes.
yeah as i said before its a nice approach...
On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote:
@Atul: I don't have an n in my algorithm, so I'm not sure what your
assessment that my algorithm is O(n^2) means. My
@Gene , @dave : +1 +1
On Tue, Feb 28, 2012 at 10:49 AM, atul anand atul.87fri...@gmail.comwrote:
@Dave : yeah sorry its O(n) where n is number of nodes.
yeah as i said before its a nice approach...
On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote:
@Atul: I don't have
You are assuming is to be a binary tree, its not. Some nodes will
share a common pour.
On Feb 25, 9:24 pm, atul anand atul.87fri...@gmail.com wrote:
i guess this would work...
n=number of nodes
h=height;
pour=quantity poured;
capacity = capacity of each cup
n=pow(2,h+1) -1;
@all
same doubt qstn appears to be of binary tree DS
but the diagram given in between qstn is not like Binary tree so
sharing is there
so how sharing is done plz explain??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
@Ravi: checkout this code...i have created tree where there is sharing of
nodes..
here is my code :-
please let me know is case you find any bug.
#includestdio.h
typedef struct tree{
int idx;
float data;
struct tree *left;
struct tree *right;
}node;
node *createNode(int index)
{
node *temp;
buddy i said that kadane's algo(max subsum) wouldn't work..
On Feb 25, 1:31 pm, Ashish Goel ashg...@gmail.com wrote:
max subsum problem
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, Feb 25, 2012 at 1:03 PM, karthikeya s
it will
the diff is of fuel and dist forms the content of array which moves from 1
to 2n-1 elements(break the circle and instead of elem like 1,2,n have
1,2,n,1,2,...n-1
i.e. total 2n-1 so that mod stuff is not required.
now find maxsubSum such that sum=0 and count of nodes is n
not clear ehy
@all: how is the problem solved using a heap...can someone explain. did not
understand what was on the net...
On Thu, Feb 3, 2011 at 2:23 AM, Avik Mitra tutai...@gmail.com wrote:
I am proposing a solution for problem 2..
2.
Given a text file, implement a solution to find out if a pattern
@Sourabh - whats the running time?
On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote:
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
O(N*K)
On Nov 28, 1:04 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
@Sourabh - whats the running time?
On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote:
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks
Hi
I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?
On Nov 28, 2:17 am, sourabh
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking N/K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm,
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time will be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM,
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to
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,
585 + (160 + 5)for slowest transactions *999 for the rest of the
instructions!
On Tue, Sep 27, 2011 at 12:49 AM, Gene gene.ress...@gmail.com wrote:
You guys have the right idea except that since it's multiple choice
you can do this with no math. With 1000 data items and only 4 stages,
the
clock period=(slowest stage delay)+(Buffer delay).
slowest stage delay is 160 ns and Buffer delay is 5ns. Buffer delay will
always be there between two stages .
clock period=165ns.
In the pipelining the time it takes =(k+n-1) * (clock period)
k=number of stages and n=number of
Thats right. Clock speed is governed by slowest processing stage + register
delay. With clock cycle of (160+5) ns even the faster stages will be forced
to run slowly. As a result 1st instruction will take 165*4 ns and rest of
following 999 instructions will take 165*999 ns.
On Tue, Sep 27, 2011
@bharat:
for the second part where u multiplied (160+5) with 999, it should be
160*999 because it is max of (150,120,160,140,5). Correct me if i am
wrong.
On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com
wrote:
for the first instruction : 150+5+120+5+160+5+140=585 ns
for the
You guys have the right idea except that since it's multiple choice
you can do this with no math. With 1000 data items and only 4 stages,
the bottleneck has to be the slowest pipeline stage with its register
delay. So you can answer b in 10 seconds and move on to the next
question!
On Sep 26,
@Sukran: Well, I would hire about 1000 smart people and let them do
it. :-)
Dave
On Sep 20, 2:12 am, sukran dhawan sukrandha...@gmail.com wrote:
How do you implement google maps ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
they are using a highly optimized A* algo for rout finding
On Tue, Sep 20, 2011 at 10:01 PM, Dave dave_and_da...@juno.com wrote:
@Sukran: Well, I would hire about 1000 smart people and let them do
it. :-)
Dave
On Sep 20, 2:12 am, sukran dhawan sukrandha...@gmail.com wrote:
How do you
Well, I think its not that the algorithm be written with all Google maps
features in place. Rather it is a open ended question, where interviewer is
trying to find
the candidates view of algorithm design.
@Deepak: It should be fine even if some reasonably good algo is given.
my 2 cents:
For the
hi,
I am not able to add a person to the algogeeks group. Is there a limit on
the number of people who could join a particular google groups ?
At present there are 7960 people :)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
*no, there is no such limit
*regards
- Sumit Kumar Pathak
(Sumit/ Pathak/ SKP ...)
*Smile is only good contagious thing.*
*Spread it*!
On Fri, Sep 9, 2011 at 1:59 PM, shady sinv...@gmail.com wrote:
hi,
I am not able to add a person to the algogeeks group. Is there a limit on
the number
It seems Dipankar Algo is appropriate at this point of time.
each time successor and predecessor check needs to be done at each
node and the value need to be updated, This is O(log n) approach
because once we check, we move into particular direction.
On Aug 21, 4:59 pm, rahul aravind
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
Hi, here i maintained two pair of indexes with respect to a and b, reply if
u found any test case which fails..
int npairs()
{
int a[] = {0,1,4,5,9,11,20};
int b[] = {0,2,3,6,8,11,15};
int c[20];
int len = sizeof(a)/sizeof(a[0]);
int i1,j1,i2,j2;
i1=len-1;
j1=len-2;
i2=len-2;
j2=len-1;
Find the largest ceil(sqrt(n)) elements of A and B using a sliding window in
time O(n) and then take their cross in time sqrt(n)^2 ie O(n).
--Shambo
On Mon, Jul 11, 2011 at 12:37 PM, surender sanke surend...@gmail.comwrote:
Hi, here i maintained two pair of indexes with respect to a and b,
@Shambo: That doesn't work.
Consider:
A = 1 10 100 1000
B = 1 2 3 4
The top 4 pairs are: (1000,4), (1000,3), (1000,2) and (1000,1)
--
DK
http://twitter.com/divyekapoor
http://www.divye.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
it has O(n2) solution
take nxn matrix and for every a[j](j=1 to n) store the d (a[j]-a[i])
value for all i j
the trick is that d of the longest AP will occur maximum number of
times in matrix
count the maximum occuring d value and reconstruct the sequence by
going through matrix
-Ritu
--
@Sunny: Thanks for this counterexample. The O(N) algorithm currently seems
unfeasible to me.
@Piyush: Are you sure an O(N) algo exists?
Here's an O(N log N) algo (without the N^2 memory requirements of Sunny's
algo as it doesn't generate duplicates)
For arrays
A = a1 a2 ... an
B = b1 b2
@Dk..i dint frame the question buddy...:P
I found it over here
http://geeksforgeeks.org/forum/topic/google-interview-question-for-software-engineerdeveloper-about-algorithms-75
On Mon, Jul 11, 2011 at 3:14 PM, DK divyekap...@gmail.com wrote:
@Sunny: Thanks for this counterexample. The O(N)
small mistake change a to b
if( (a[i1-1]+b[j2-1] a[i1]+b[j1]) (a[i1-1]+a[j2-1] a[i1]+b[j1]) )
surender
On Mon, Jul 11, 2011 at 3:54 PM, DK divyekap...@gmail.com wrote:
@surender: Your algo fails. See the counterexample posted by Sunny.
--
DK
http://twitter.com/divyekapoor
1 - 100 of 300 matches
Mail list logo
