Interview Question

Senior Software Engineer Interview New York, NY

write a function to find the K biggest elements in the

  array, and return the sum in linear time.
Tags:
algorithm
Answer

Interview Answer

1 Answer

0

pseudocode (assumes k ≤ n and n > 0)

sumOfKLargest(k, A[0..n-1])

num ← 1
count ← A[0]
lowest ← count

for i ← 1 to n-1 do
  if num ≠ k
    count ← count + A[i]
    if A[i] < lowest
      lowest ← A[i]
    num ← num + 1
  else if lowest < A[i]
    count ← count - lowest + A[i]
    lowest ← A[i]

return count

Anonymous on Mar 31, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.