Interview Problem

Revision en3, by sagnihotri, 2017-12-03 21:11:31

Given an array of integers . find the sub-array with sum closest to a number T.
I was asked to answer M queries and in each query we are give number T.
I came up with a solution of nlogn + m*n*logn but interviewer was not satisfied and wanted me to come up with nlogn + m*n solution.
(He rejected me solely on this )
.
Can anyone suggest me what can be optimised solution for this.
My solution involves storing prefix sum in set and finding prefix[i]-T value in set.

Tags #interview

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English sagnihotri 2017-12-04 07:10:22 23 Tiny change: ' integers . find the' -> ' integers (positive and negative). find the'
en4 English sagnihotri 2017-12-03 21:12:29 40
en3 English sagnihotri 2017-12-03 21:11:31 155
en2 English sagnihotri 2017-12-03 21:09:21 13 Tiny change: ' array of non negative integers ' -> ' array of integers '
en1 English sagnihotri 2017-12-03 21:03:41 370 Initial revision (published)