Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Interview question int array

 
Jehan Jaleel
Ranch Hand
Posts: 196
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all,

I recently took an interview and got a challenging question on integer arrays. Basically if you have an int array of both positive and negative and you want get a sub array where the total is the largest sum possible, how would you do this? The interviewer said he needed the beginning and ending indecies from the original array.

Any suggestions on how this could be coded?
 
Carey Brown
Ranch Hand
Pie
Posts: 1074
11
Eclipse IDE Firefox Browser Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is the input array in sorted order. That would be the simplest problem to solve. Else you would probably need to try all combinations of sums of some starting point to some ending point and make note of the one with the greatest sum.
 
Jelle Klap
Bartender
Posts: 1951
7
Eclipse IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Backtracking maybe?
 
fred rosenberger
lowercase baba
Bartender
Pie
Posts: 12022
25
Chrome Java Linux
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Questions like this are usually less about giving a solution than seeing how you approach the problem. Are you making assumptions? do you dive in with writing actual code?

I would immediately start asking questions about the array given.

is it sorted?
what are the possible ranges of values?
Is speed more important that memory consumption?
Will I need to do this once, for one specific array, or will this be used over and over for many different inputs?
What is the expected size of the input array?

I wouldn't even try to write a single line of code until i had those questions answered.
 
Alexander Sales
Ranch Hand
Posts: 89
Eclipse IDE Java Tomcat Server
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
please illustrate your problem.
 
Mike Simmons
Ranch Hand
Posts: 3028
10
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I expect the answer to "is it sorted?" would be "no". That would have made the problem too simple.

There is a way to solve this with a single loop that reads each value in the array exactly once.
 
fred rosenberger
lowercase baba
Bartender
Pie
Posts: 12022
25
Chrome Java Linux
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Simmons wrote:I expect the answer to "is it sorted?" would be "no". That would have made the problem too simple.

agree, but it is still a valid question to ask.

Mike Simmons wrote:There is a way to solve this with a single loop that reads each value in the array exactly once.

now you've given me something to think about during my lunch break.
 
Mike Simmons
Ranch Hand
Posts: 3028
10
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:
Mike Simmons wrote:I expect the answer to "is it sorted?" would be "no". That would have made the problem too simple.

agree, but it is still a valid question to ask.

Oh, absolutely - particularly in an interview. Same with the other questions suggested by you and others.
 
Jehan Jaleel
Ranch Hand
Posts: 196
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks all for your valuable advice. I think you are right in that the question was more about the approach then the actual solution. Actually they asked me this during a phone screen which is more of a reason to think that.

My face to face interview is next week. Any further tips you can offer on how to prepare and for the actual interview itself would be great appreciated.

Thanks again.
 
Stephan van Hulst
Bartender
Pie
Posts: 4840
34
Chrome Netbeans IDE Windows
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If anyone is interested, this is how I would do it for any old array:
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic