Блог пользователя pkpawan

Can we have better solution than O(n^2 log n) for the following problem 1.
Автор pkpawan, история, 2 года назад, По-английски

Problem 1 from Past Online assesment of Citadel

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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)

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    → Ответить
»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Just curious, does Citadel hire from India?

→ Ответить