• Post Reply Bookmark Topic Watch Topic
  • New Topic

Java question  RSS feed

 
Ben Synes
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was recently asked this question,wehich I got wrong, and I cant understand some of the concepts stated in the question.

Your class, LocatorSolution, must find the index of an item efficiently from within a sorted array of candidates. The implementation must be written from first principles, and must not make use of classes not explicitly mentioned in the interface definition. The solution should adhere to the specification below when supplied with reasonable inputs and must provide a no-throw guarantee.



1. I didnt understand  first principles", but I took it as being not using any libraries, or classes outside of core java. So what do first principles actually mean, stand for?
2. I interpreted the no throw guarantee, as surrounding my implementing logic with a try catch, catching every Exception, and hence not throwing anything up to a caller, like IndexOutOfBounds, or any other uncherked exception.


Would be good to hear your thoughts on this question. Thanks
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
 
Ben Synes
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The question was sent from a recruitment agency screening potential candidates before forwarding them through to potential employers.
 
Dave Tolls
Ranch Foreman
Posts: 3056
37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For 1, it means you can only use the classes actually given in the interface.
So in this case String and String[].

For 2, I would expect the solution to not throw an exception at all, yes.
 
Ben Synes
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My solution is as follows, which sadly was not good enough.


I made some assumptions, as follows:
1. Using the enhanced for loop over the index based for, your test as far as I could gather, didnt suggest otherwise
2. We always return the first index of a matched itemSought, there could be multiple in the candidates array
3. I would obviously have added/began with a unit test, but it was not explicitly asked for, please dont judge me as unprofessional
4. The enhanced for loop performs faster than index based for
*/
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16057
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Did you get any feedback on what was wrong with your solution?
Ben Synes wrote:
4. The enhanced for loop performs faster than index based for

Why do you think this? This is not necessarily true.
 
Ben Synes
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I remember reading on JavaCodeGeeks an in depth analysis of the for vs the enhanced for, and the results indicated that the enhanced for was generally quicker overall. But maybe this was with only certain data types.

I got no feedback whatsoever as to what was wrong with my solution.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think that you forgot about the "sorted" part of the question. There is a very good reason that the inputs are guaranteed to be sorted.

Henry
 
Ben Synes
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong wrote:I think that you forgot about the "sorted" part of the question. There is a very good reason that the inputs are guaranteed to be sorted.

Henry


I dont understand? Guaranteed to be sorted would be perhaps meaning a Comparator was used? But if so, we still need only return the index if found in the array, regardless of position??

Please explain to me if you could.

 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ben Synes wrote:
I dont understand? Guaranteed to be sorted would be perhaps meaning a Comparator was used? But if so, we still need only return the index if found in the array, regardless of position??

Please explain to me if you could.


Basically, this may be a standard algorithms test. They are testing to see if you will implement it as a binary search... which has a big advantage over a linear search (which you implemented).

Henry
 
Ben Synes
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the answer. Coincidentally when I was reading about the performance of the enhanced for  vs plain for, there were a third set of results for the binary search, which were faster than both of some of the datasets. When I saw this problem, I just saw String, which I thought was simple enough to detect in a standard for way, as you rightly pointed out, the "hidden" clue is the sorted. Thanks for pointing this out. I feel such a novice now.
 
Junilu Lacar
Sheriff
Posts: 11476
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Interesting way to phrase it, use only first principles. A background in Computer Science or at least a familiarity with various sort and search algorithms would have helped you. Don't feel bad if you have neither but if you have the former, you should go back and ask for a refund. The key word in that question was "sorted" which should instantly pull up "Binary search" in your mind. At least now you know.
 
Junilu Lacar
Sheriff
Posts: 11476
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know if I would have equated the "no throw guarantee" to the use of a try-catch either. There are only a few things that can cause an exception so I would have just put up some guard clauses. Try-catch blocks are expensive and if performance is a primary concern, you should try to avoid using them.
 
Ben Synes
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:I don't know if I would have equated the "no throw guarantee" to the use of a try-catch either. There are only a few things that can cause an exception so I would have just put up some guard clauses. Try-catch blocks are expensive and if performance is a primary concern, you should try to avoid using them.


So what kind of guard clauses could I use here? What kind of cases could be guarded against?

I saw initially only a concern of IndexOutOfBounds, but this was mitigated with the enhanced for. As there are many Runtime exceptions which could potentially be thrown, a guard against all of them would be kind of lengthy no?


 
Ben Synes
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I googled about "first principles" before attempting the task. Surprisingly there are terms around math such as:

starts with formal logic, the axiomatization of arithmetic, lambda calculus (the theory of partial recursive functions), and automata theory up through Turing machines.


All looks a bit heavy, of course I learned Big O notation at university, and yes Im even further noviced now, because it was Computer Science. To late for a refund I guess, but perhaps their failings should be something I correct by myself.

 
Dave Tolls
Ranch Foreman
Posts: 3056
37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A null String[].
You shouldn't need to worry about a null String, though.
 
Junilu Lacar
Sheriff
Posts: 11476
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Null and empty array argument, just off the top of my head. Guard clauses would just return -1 in those cases. I'd have to see some code to say for sure if null elements would be a concern but I would keep that in mind as well. Since the array is already presorted, I would think that if null elements could be present, they be in the front. Like I said, I'd have to see code but I'm still lazing around in bed right now.
 
Ben Synes
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for help. I really appreciate it.

 
Campbell Ritchie
Marshal
Posts: 56525
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ben Synes wrote:I googled about "first principles" before attempting the task. . . .
I am not convinced that “first principles” is the correct phrase to use in a programming exercise. I think they mean that you have to write the algorithm yourself.
As well as Jesper's strictures about try‑catch, I would not like simple catch (Exception ex).... You should catch a specific Exception and you should know which sort of Exception to expect. You should know that the loops cannot throw an index out of bounds exception.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!