4

I encountered a question where a given array of integers I needed to find the pair which could satisfy the given sum.

The first solution that came to me was to check all possible pairs which was about O(n^2) time, but the interviewer requested me to come up with the improved run time at which I suggested to sort the array and then do binary search but that was also O(nlogn).

Overall I failed to come up with the O(n) solution. Googling that I came to know that it can be achieved via extra memory using set.

I know that there cannot be any fix rules to thinking about algorithms but I am optimistic and think that there must be some heuristic or mental model while thinking algorithms on array. I want to know if there is any generic strategy or array specific thinking which would help me explore more about solution rather than acting dead.

CodeYogi
  • 1,352
  • 1
  • 18
  • 41
  • 3
    You can only read algorithms and try to understand the concepts. In other words: Gain more experience and you will improve. Read what others do and learn from them. REMARK: Especially hashing is often a way to reduce (average) complexity because it allows access in O(1). – MrSmith42 Oct 10 '16 at 09:16
  • @MrSmith42 that counts as one advice :) – CodeYogi Oct 10 '16 at 09:17
  • Check with same similar question [hear](http://stackoverflow.com/questions/11928091/linear-time-algorithm-for-2-sum) – Vinod Oct 10 '16 at 09:18
  • 1
    Algorithm problem is not differed much from any other types of problem. First, there are two parts for solving a problem, domain knowledge and problem solving strategy. For domain knowledge, you need to have good understanding about existing data structure and classic algorithms, they will be the tools for u to solve any algorithm problem, learn to use them smartly and effectively. For problem solving strategy, take a look at the classic book : How to solve it by Polya for a systematic approach. Last advice: Practice makes perfect. – Pham Trung Oct 10 '16 at 09:36
  • After you solve this one, start thinking about finding a combination of possibly more than two numbers to get to given sum. It suddenly becomes a lot more complicated ;) – Artur Biesiadowski Oct 10 '16 at 11:28

1 Answers1

2

Generally, think about how to do it naively first. If in an interview, make clear what you are doing, say "well the naive algorithm would be ...".

Then see if you can see any repeated work or redundant steps. Interview questions tend to be a bit unrealistic, mathematical special case type questions. Real problems more often come down to using hash tables or sorted arrays. A sort is N log N, but it make all subsequent searches O log N, so it's usually worth sorting data. If data is dynamic, keep it sorted via a binary search tree (C++ "set").

Secondly, can you "divide and conquer" or "build up". Is the N = 2 case trivial? In than case, can we divide N = 4 into two N = 2 cases, and another integration step? You might need to divide the input into two groups, low and high, in which case it is "divide and conquer", or you might need to start with random pairs, then merge into fours, eights and so on, in which case it is "build up".

If the problem is geometrical, can you exploit local coherence? If the problem is realistic instead of mathematical, and there typical inputs you can exploit (real travelling salesmen don't travel between cities on a random grid, but over a hub and spoke transport system with fast roads connecting major cities and slow roads then branching out to customer destinations)?

Malcolm McLean
  • 6,258
  • 1
  • 17
  • 18