# Recent interview question - Find a pair in array whose sum is x.

Nick Sher
Ranch Hand
Posts: 78
Hi,

I hope this is the right place to ask this question. In a recent interview for SE position. I was asked the following question:

Write a function which has input (array x, integer y) and checks x to find the pair of integers which have sum equal to y. Returns true or false?
I gave the answer that I will compare every integer in x with another in x. Just a guess. Of course, this is a wrong answer. I did not have idea of where i was getting to. Then time complexity was asked about the solution.

How do I solve this problem? What is its complexity?
And where do I find these questions for interview?
What is the recommended books to prepare for such questions?

This was my first interview.

Henry Wong
author
Marshal
Posts: 21191
81
I gave the answer that I will compare every integer in x with another in x. Just a guess.

Well, now that the interview is over... and you have time to think about it a bit.... take a shot a coming up with an answer. What do you think the answer should look like?

Henry

Nick Sher
Ranch Hand
Posts: 78
Henry Wong wrote:
What do you think the answer should look like?

Hi Henry, I have tried and couldn't get the steps for it. I also thought of sorting the array. but then I don't know where I am heading to. How do I start?

Or, I just thought of this one:
Pick the element from x and subtract it from y.
Check if the result exists in the x. True if found.
Else continue with next element in x until no more elements remaining

Dave Trower
Ranch Hand
Posts: 86
Your answer is not wrong but it is not the most efficient solution.
Your answer has a complexity of N squared where N is the number of elements in X.
I have a solution as long as we can assume the numbers in X are positive.

First create a boolean array of size Y and initialize each element to FALSE.
boolean[] numberList = new boolean[y];
Now look at each number in array X one by one with a for loop (lets use i as the looping variable)
1) First determine if X[i] >Y, if it is go to the next number.
2) int neededNumber = Y - x[i]
if(numberList[neededNumber])
return true;
3) numberList[x[i] ]= true;
4) If you search the entire list without every returning true, return false.

This method only looks at each member in X once.

Gregg Bolinger
GenRocket Founder
Ranch Hand
Posts: 15302
6
I find it humorous that companies ask these kinds of questions and expect to find good engineers.

Roel De Nijs
Sheriff
Posts: 10213
129
Hi,

I would think of something like this:

Kind regards,
Roel

arulk pillai
Author
Ranch Hand
Posts: 3387
Gregg Bolinger wrote:I find it humorous that companies ask these kinds of questions and expect to find good engineers.

Like to hear your point of you on this. I think the logical questions like the one above in addition to technical and open-ended questions in are useful in assessing a prospective candidate. These types of questions always have three parts to it

a) Knowing the approach to take. Because some questions can take longer to solve efficiently. Some pseudocode and thinking aloud in the interview can show that you know how to go about tackling the problem. You can also narrate some of the alternative approaches to solving it like possibility of recursive method calls, use of collection class like a Set (no duplicates) or Stack (FILO), loops, etc.

b) Coming up with the correct answer.

Jimmy Clark
Ranch Hand
Posts: 2187
This question is a joke...company or recruiter will never find what they think they are looking for. Imagine that they gave him a big yellow pencil with a bright eraser and lined paper to write the codez...

Andrew Monkhouse
author and jackaroo
Marshal Commander
Posts: 11887
203
I am not sure that I am arguing again Gregg, but my opinion is that this question, and many like it, can be used as part of the interview process, and as such it can help. If a company uses this type of question on it's own with an absolute "good solution" vs "interview failed" then they will loose good candidates and hire some who can only answer this type of question.

When used properly, this question should take well under an hour to cover - for a good candidate it will take less than half an hour. Which leaves plenty of time for other questions to investigate other strengths / weaknesses.

I have a different question that I use, but the same principles apply. When I ask the question, I hope to see:
• workable code
• unit testing
• performance considerations
• being able/willing to modify code

• I do not expect candidates to jump and and cover all 4 points instantly, but I hope that with a little prompting we can go over all 4 points.

It is depressing how many people fail the very first point. I don't often see someone unwilling to modify their code, but it does happen, and an attitude of "I wrote it therefore it is good" does not sit well with me.

One of the nice things about this type of question is that it doesn't really matter what language you use to solve the problem - so if a candidate says they are better at C than Java then I let them solve it using C. This also requires no esoteric APIs - anyone with a basic knowledge of whatever language they are comfortable with should be able to handle it.

I would repeat that this is not a pass/fail type of question (at least when I use it) - I usually look for employees who are going to be around for a few years. So if they can code a working solution but don't do any of the other tasks then we could still consider them for a more junior position, and teach them unit testing. Or if they start of TDD and get to a solution that performs well all by themselves then we might consider them for a more senior position. But as I mentioned earlier, this is only part of the interview process - they might ace this test and still not be hired, or they might not even get past the first step in this test and still get hired. It depends on how they do in the other areas I interview in.

Gregg Bolinger
GenRocket Founder
Ranch Hand
Posts: 15302
6
I see your point Andrew. And to this point:

I usually look for employees who are going to be around for a few years

I am usually looking for 3-6 months, so I suppose that plays a factor in how you interview someone as well. I did have a question in my last interview on how to implement a HashMap class assuming it didn't already exist. But that still seems like a more relevant question than the one the OP is talking about.

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34669
367
I thing Andrew makes excellent points. I also have candidates code (especially contractors who will mainly be writing code on the job.) I find the process they go about it is a better indicator of job performance than verbal questions. Not to say I don't ask verbal questions too. I've just been amazed by the correlation. Especially as an early filter of:

1) Do they really know Java
2) Can they look stuff up on the internet they don't know and assimilate it quickly
3) Can we work well as a team (through question prompting)

Plus the good developers fly through the questions leaving more time for discussion. The ones who "program by assembling code snippets they don't understand" or "program by lying" don't get anywhere.

Ranch Hand
Posts: 628
My crude Algorithm for complexity O(nlgn)

Let the sum be SUM

let the array be array[n].
sort the array -->Time complexity O(nlgn)
int x
for Y = 1 to n repeat{
x=binarysearch(array, (SUM-Y)) -->O(lgn)-->This happens n times..so it is O(nlgn)
binary search routine will performs binary search in the array for elements (SUM-Y) and returns true if found
Print Y and (SUM-Y) as a pair for the answer
}

arulk pillai
Author
Ranch Hand
Posts: 3387
Try it yourself with something like..............

Generally, it is not a good practice to have nested loops as it makes your code harder to read. Try to incorporate Roel's solution ( ).

Roel De Nijs
Sheriff
Posts: 10213
129
Hi Nick (and all other ranchers),

I created a small test program which have 4 different solutions:
• the nested loops
• the bit vector (see post Dave Trower)
• the 2 pointers coming together (see my previous post)
• the binary search (see post Rambo Prasad)

• The first 2 solutions can be applied on a random array, the last 2 solutions require a sorted array.

An example of the output could be:

And with a small adjustment I was able to calculate averige times of each algorithm:

Kind regards,
Roel

Jimmy Clark
Ranch Hand
Posts: 2187
Asking rudimentary low-level programming questions when searching for an experienced software engineer is not a good path for finding the best candiate in a reasonable time-frame.

Asking rudimentary low-level programming questions when searching for an entry-level programmer's position is more appropriate, in my opinion.

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34669
367
James Clark wrote:Asking rudimentary low-level programming questions when searching for an experienced software engineer is not a good path for finding the best candiate in a reasonable time-frame.

I am so close to agreeing with this. I make two changes though - and I bet they change the spirit of it.

"Asking rudimentary low-level programming questions" --> "Asking just rudimentary low-level programming questions" - Of course you should ask about design/architecture/etc. The programming questions are to show they can code.

"finding the best candiate" --> "finding one of the best candidate" - I don't need the absolute best candidate. I need a candidate that meets my needs. If three of them do, I don't necessarily need the best.

Jimmy Clark
Ranch Hand
Posts: 2187
lol....looks like you're reading English sentences like they are Java statements (syntax).

They are some situations where experienced software engineer does not have to code, or his/her code is never used in real situations. Personally, my programmers write code. I tell them what to code. If I write code, it would be only for proof-of-concept and/or prototype, and it gets thrown in trash eventually.

The interview question in this post is kinda simple. My responses are based on knowing that in reality they could be more complex, especially with an inexperienced interviewer. So, generally it is the principle that I disagree with.

If you can demonstrate significant knowledge of how to use various API, it doesn't really matter if you can recite the steps of a low-level Java array-based parsing algorithm. This type of fresh programming knowledge is more appropriate for mainframe, COBOL systems, or real-time control software...not Java.

arulk pillai
Author
Ranch Hand
Posts: 3387
James, I can understand where you are coming from, but I have come across shocking code written by even exeperienced professionals.
In my current job, I saw a piece of code that has 8 levels of nested for loops. The code does its job, but when someone has to debug or maintain it, it is very frustrating and time consuming.

Even though the above logical question is rudimentary, you will be surprised to see how many can get it right. Aslo, it is better to ask elementary question as there is only limited time and candidates could be nervous too

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34669
367
arulk pillai wrote: Aslo, it is better to ask elementary question as there is only limited time and candidates could be nervous too

I think this is an important point. When I started giving coding questions to consultants, people thought I was being too tough. (This was when the market was hot and anyone could call themselves a Java developer.) Whereas I think my coding questions are ridiculously easy for an experienced person.

I'd rather give someone something easier that they know like the back of their hand. And see they know it well. I explained this to a non-techie friend by saying "you don't forget how to spell basic words just because you are nervous. If someone is forgetting the basics, we have a problem.

Henry Wong
author
Marshal
Posts: 21191
81

It is also amazing how many supposedly very experience developers forget basic stuff from their 101 data structures and algorithms classes. It may seem somewhat insulting to ask simple questions, but it does a good job at doing a cut.

Henry

Katrina Owen
Sheriff
Posts: 1367
18
My team and I have interviewed a good number of people this past year, and it has been an incredibly frustrating experience. We have interviewed a lot of candidates who appear to have relevant experience, relevant expertise, interviewed well over the phone, etc... and who approached every single thing we discussed with brute force.

We weren't looking for intricate algorithms knowledge, just enough to be able to suggest alternate approaches. Shoot - I have friends who aren't even in tech fields who would have suggested a binary search if I asked them about this type of problem, even though they wouldn't know what to call it.

I'm sure we could have chosen a better way to assess technical skill, but even basic questions certainly helped uncover some glaring gaps.

So, yeah...

Anastasia Sirotenko
Ranch Hand
Posts: 64
i would do something like this on Java:

David Hibbs
Ranch Hand
Posts: 374
Gregg Bolinger wrote:I find it humorous that companies ask these kinds of questions and expect to find good engineers.

I find myself straddling the line on this one. Like Gregg, I groan a bit when I hear of these questions and lament a bit when someone is passed over simply because they don't know the optimal answer. On the other hand, I can also see it as useful--but not in the way others seem to have used it.

What I find important is to see how the person thinks. I want to know that the resulting solution will actually match the problem, not the assumed problem. Do they go straight to the (textbook) solution, or can they reason through it? Do they seek clarification?

Active questions help me to see that they know there are always hidden requirements or considerations and that they think about their solution. For example, if I asked this question and my candidate paused and then asked...

"Is the array sorted?"
"Can the array contain negative numbers?"
"How big can the array be?"
"Is memory use a consideration?"

I would find it much more compelling than if they just slapped out the code for a brute force search or a binary search. If they at least know the advantages/disadvantages of their solution, that's a good sign! On the other hand, if they still can't come up with a solution at all--good or bad--that's compelling in a different direction...!

Sravani Duggirala
Greenhorn
Posts: 4
s

arulk pillai
Author
Ranch Hand
Posts: 3387
Good point David. You can also get some hints as to how a particular candidate will handle pressure, if he or she is proactive, positive, motivated, flexible, willing to learn, etc.