@ankit: pls explain the time complexity..
i dont think its O(log n)
On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.comwrote:
@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
@ankit :please explain by taking an example.
On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji vetribal...@gmail.comwrote:
@ankit: pls explain the time complexity..
i dont think its O(log n)
On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.comwrote:
@Dumanshu: In each
@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 vetribal...@gmail.com 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 ankitsamb...@gmail.com
wrote:
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 varunpahwa2...@gmail.comwrote:
@ankit :please explain by taking an example.
On Fri,
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
@ankit: think u missed heapify..
time complexity is O(n logn)
On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal ankitsamb...@gmail.comwrote:
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
@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
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
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 radhakrishnance...@gmail.com
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 Thu, Jun 9, 2011 at 10:54 AM, Dumanshu duman...@gmail.com wrote:
hey... we have 300 million (9- digit) numbers. So we have to print a
Create a range tree, pruning out as needed to stay in the memory
constraint.
Don
On Jun 9, 6:24 am, Dumanshu duman...@gmail.com 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
11 matches
Mail list logo
