Hey the file has random 300 million numbers (9 digit)...there might be
duplicates... not a particular sequence out of the many missing
numbers we have to print just one... someone please try to understand
the solution given alongwith the question.
On Jun 10, 12:49 pm, ankit sambyal wrote:
>
@Balaji : No, I didn't miss it. Since we had broken the file
containing 300 million integers into smaller files containing much
less numbers. So, the time complexity of min heapify is not O(logn),
but it is O(log(no. of numbers in smaller file)), which is constant.
Correct if I am wrong.
On Fri,
@ankit: think u missed heapify..
time complexity is O(n logn)
On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal wrote:
> Lets say we have 9 numbers from 1 to 10 and one number is missing. We
> hv a RAM which can accomodate only 3 nos.
> 9,6,7,4,3,2,1,5,10
> So, we split the file into 3 smaller file
Lets say we have 9 numbers from 1 to 10 and one number is missing. We
hv a RAM which can accomodate only 3 nos.
9,6,7,4,3,2,1,5,10
So, we split the file into 3 smaller files each containing 3 nos.
File1: 9,6,7
File2: 4,3,2
File3: 1,5,10
Now take each file into memory one by one and min heapify
the
can anyone explain "Since there
are less than 2^32 numbers in the file there is bound to be one number
in the array that is less than 2^16." in dumanshu's solution.
On Fri, Jun 10, 2011 at 12:39 PM, varun pahwa wrote:
> @ankit :please explain by taking an example.
>
>
> On Fri, Jun 10, 2011 at 12
@Balaji: Sorry, the time complexity was not O(log n). It is O(n).
On Thu, Jun 9, 2011 at 11:43 PM, Vetri Balaji wrote:
> @ankit: pls explain the time complexity..
> i dont think its O(log n)
>
> On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal
> wrote:
>>
>> @Dumanshu: In each iteration, we r r
@ankit :please explain by taking an example.
On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji wrote:
> @ankit: pls explain the time complexity..
> i dont think its O(log n)
>
>
> On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal wrote:
>
>> @Dumanshu: In each iteration, we r removing the smallest num
@ankit: pls explain the time complexity..
i dont think its O(log n)
On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal wrote:
> @Dumanshu: In each iteration, we r removing the smallest number. If
> at any iteration we can't find the next smallest no., it means that
> no. is missing.
>
>
>
> On T
Create a range tree, pruning out as needed to stay in the memory
constraint.
Don
On Jun 9, 6:24 am, Dumanshu wrote:
> Given a file containing roughly 300 million social security numbers(9-
> digit numbers) find a 9-digit number that isnt there in the file. You
> have unlimited drive space but on
@Dumanshu: In each iteration, we r removing the smallest number. If
at any iteration we can't find the next smallest no., it means that
no. is missing.
On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu wrote:
> hey... we have 300 million (9- digit) numbers. So we have to print a
> number which isn
hey... we have 300 million (9- digit) numbers. So we have to print a
number which isn't already there in the file.
We are not given that number beforehand. You are saying to check "u
are going to check whether a number N exist ".
On Jun 9, 4:46 pm, radha krishnan
wrote:
> Ma approach is to xor th
11 matches
Mail list logo
