aspose file tools*
The moose likes Jobs Discussion and the fly likes Recent interview question - Find a pair in array whose sum is x. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Careers » Jobs Discussion
Bookmark "Recent interview question - Find a pair in array whose sum is x." Watch "Recent interview question - Find a pair in array whose sum is x." New topic
Author

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

Nick Sher
Ranch Hand

Joined: Nov 10, 2008
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.

Please help.


Nick
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18896
    
  40

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Nick Sher
Ranch Hand

Joined: Nov 10, 2008
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

Joined: Feb 12, 2003
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.

I hope this helpful.
Gregg Bolinger
GenRocket Founder
Ranch Hand

Joined: Jul 11, 2001
Posts: 15299
    
    6

I find it humorous that companies ask these kinds of questions and expect to find good engineers.


GenRocket - Experts at Building Test Data
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5389
    
  13

Hi,

I would think of something like this:


Kind regards,
Roel


SCJA, SCJP (1.4 | 5.0 | 6.0), SCJD
http://www.javaroe.be/
arulk pillai
Author
Ranch Hand

Joined: May 31, 2007
Posts: 3223
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.

c) Optimizing the answer.


Java Interview Questions and Answers Blog | Amazon.com profile | Java Interview Books
Jimmy Clark
Ranch Hand

Joined: Apr 16, 2008
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

Joined: Mar 28, 2003
Posts: 11476
    
  94

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.


    The Sun Certified Java Developer Exam with J2SE 5: paper version from Amazon, PDF from Apress, Online reference: Books 24x7 Personal blog
    Gregg Bolinger
    GenRocket Founder
    Ranch Hand

    Joined: Jul 11, 2001
    Posts: 15299
        
        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

    Joined: May 26, 2003
    Posts: 30749
        
    156

    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.


    [Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
    Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
    Rambo Prasad
    Ranch Hand

    Joined: Feb 23, 2006
    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
    }


    Helping hands are much better than the praying lips
    arulk pillai
    Author
    Ranch Hand

    Joined: May 31, 2007
    Posts: 3223
    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
    Bartender

    Joined: Jul 19, 2004
    Posts: 5389
        
      13

    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

    Joined: Apr 16, 2008
    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

    Joined: May 26, 2003
    Posts: 30749
        
    156

    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

    Joined: Apr 16, 2008
    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

    Joined: May 31, 2007
    Posts: 3223
    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

    Joined: May 26, 2003
    Posts: 30749
        
    156

    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 18896
        
      40


    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

    Joined: Nov 03, 2006
    Posts: 1364
        
      17
    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

    Joined: Jul 20, 2009
    Posts: 64
    i would do something like this on Java:


    [SCJP 6.0]
    David Hibbs
    Ranch Hand

    Joined: Dec 19, 2002
    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...!

    "Write beautiful code; then profile that beautiful code and make little bits of it uglier but faster." --The JavaPerformanceTuning.com team, Newsletter 039.
    Sravani Duggirala
    Greenhorn

    Joined: May 06, 2009
    Posts: 4
    s
    arulk pillai
    Author
    Ranch Hand

    Joined: May 31, 2007
    Posts: 3223
    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.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Recent interview question - Find a pair in array whose sum is x.