pkpawan's blog

Can we have better solution than O(n^2 log n) for the following problem 1.
By pkpawan, history, 2 years ago, In English

Problem 1 from Past Online assesment of Citadel

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
2 years ago, # |
  Vote: I like it -10 Vote: I do not like it

I am just able to come up with O(n^2 log n). First we will sort the array . We are finding all the pair possible for (i,j) ---> (i<j) such that (A[i] + A[j])<= thresold ,now let the remaining rem = thresold — (A[i] + A[j] ) now if (rem > A[j]), then we will find the larges (value<= rem) in array of remaining elements using binary search and no of valid triplets is (k — j), where 'k' is index of that value.

We will find this for all the valid pairs.

So O(n^2) for valid pairs and for each pair finding the A[k] is (logn). So O(n^2 log n)

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You can achieve $$$O(n^2)$$$ if you replace binary search with two pointers.

    There are no known significantly better upper bounds and the lower bound is widely known open problem. More details here.

    → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Just curious, does Citadel hire from India?

→ Reply