wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Maximum sum of 2 array elements
        
(Message started by: mad on Feb 6^th, 2008, 10:14pm)

Title: Maximum sum of 2 array elements
Post by mad on Feb 6^th, 2008, 10:14pm

Q.1)S contains the set of positive integer.Find the largest number c such that c=a+b where a,b,c are distict numbers in the set.

Q.2)write the program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.

Sorry if this has been posted before. Please provide the link in that case.

Title: Re: Maximum sum of 2 array elements
Post by 4ortySe7en on Feb 11^th, 2008, 10:30am

1.
Brute force approach will take O(n³) time.
But it can also be solved in O(n²) time and O(n) space:
[hide]First, sort the list and make a copy of it. Then, starting with the first element( call it 'a'), subtract the element value from each of the remaining elements of the second list. Now, there are two sorted list. And greatest common element( call it b) between them can be found in O(n) time. This element when added with 'a' gives the greatest common element (call it c) for that 'a'. Repeat this process for all elements in the list and the greatest among all c's is the answer. [/hide]
If preserving the order of the elements is not required, then it can solved in O(n²) time and in space.
[hide]Sort the elements. Now, start with the last element( call it a_k), find the first two consecutive number a_i and a_j in the list, such that a_i + a_j >= a_k, and j= i +1.
a₁....a_i-1 a_i...a_j a_j+1...a_k..a_n

if a_i+ a_j = a_k, then return a_k .
else
if a_i-1+ a_j < a_k
j++;
if a_j+1+ a_i > a_k
i--;
It can be easily proved that atleast one of the above two condition is always true. Thus, at each step atleast one element is discarded. Total time it would take is O(k) time.
In order to get the final answer this has to be done for all k's from k=n to 1. So, overall complexity becomes O(n²).

[/hide]

2.

This can be solved in O(n) time and O(n) space.
[hideb]Make a suffix tree out of the file and find the 10 deepest forks in it.[/hideb]

Title: Re: Maximum sum of 2 array elements
Post by johny_cage on Feb 11^th, 2008, 11:33pm

@47

Why it is in O(n²)?
It can be done in O(n log n), as sorting takes that much time. And after it, do O(n) searching with two pointer technique.

Any doubt, welcome....

Title: Re: Maximum sum of 2 array elements
Post by 4ortySe7en on Feb 12^th, 2008, 12:21am

on 02/11/08 at 23:33:13, johny_cage wrote:

@47

Why it is in O(n²)?
It can be done in O(n log n), as sorting takes that much time. And after it, do O(n) searching with two pointer technique.

Any doubt, welcome....

The second step needs to be performed for each element present in the list. That makes it O(n²) time algo..

Title: Re: Maximum sum of 2 array elements
Post by johny_cage on Feb 12^th, 2008, 1:04am

Ohhhhh!!!!! :o

i just take the question otherwise.....

yups u r right.... ::)

Title: Re: Maximum sum of 2 array elements
Post by kvs007 on Mar 7^th, 2008, 11:41pm

To get the top ten words in the file you can implement a hashmap with the keys as hashcode of words and value their count. then get the top ten counts from the hashmap. It will take O(n)

Title: Re: Maximum sum of 2 array elements
Post by mad on Mar 8^th, 2008, 4:39pm

q)Given an array of non negative integers and an integer k, you are required to device an O(n) time algorithm to find out if there exists at least one pair of integers, say i and j, in the given array such that i+j equals k. That is, you are required to return a boolean value.The array is not sorted.

Title: Re: Maximum sum of 2 array elements
Post by m_aakash on Mar 8^th, 2008, 4:45pm

on 03/08/08 at 16:39:57, mad wrote:

Using hashtable we can get O(n) expected time. Is it possible to get O(n) worst case time if elements are arbitrary?