This week's book giveaway is in the OCMJEA forum. We're giving away four copies of OCM Java EE 6 Enterprise Architect Exam Guide and have Paul Allen & Joseph Bambara on-line! See this thread for details.
I have an interview in a few days and they're asking me to find a get middle algorithm to mylinkedlist class, I'm completely confused on how to do and this job will be the start of my career since I graduated last year, your help will be appreciated, thanks!
First, a couple of hints for your interview: always capitalize class names, never capitalize method names, and a LinkedList class is going to be more useful if you make it public. Little things like that convince interviewers that you know what you're doing.
I think keeping the current size of the linked list in your class would make finding the middle element easier. You could always find this size by walking through the list, but it would just be nicer to have it all ready. You'd also have to decide if you want retrieval of the element to take linear, aka O(n), time, or if you need it to be constant, aka O(1), time and are willing to pay a price as nodes are added or removed. That's as much of a hint as I'm willing to give for something that's meant as a test of your skill!
Greg Charles wrote:First, a couple of hints for your interview: always capitalize class names, never capitalize method names, and a LinkedList class is going to be more useful if you make it public. Little things like that convince interviewers that you know what you're doing.
Also pay attention to the fact that Java is case sensitive. So Class MyLinkedList is different from class MyLinkedList; in fact, the first one (that you wrote) is wrong.
harshvardhan ojha wrote:Thanks greg for the explanation, here if Adeola will keep count then he needs to retrive only n/2 elements from head or else all next in an array, where he can get in O(1)?
Good question! If adding nodes can only be done at the tail, then enhancing the add to move the middle element to "middle.nextElement" every other time would allow you to retrieve the middle element in constant time, while keeping the add also constant. If you allow for adds at random positions, then the add would probably become O(n), but the retrieve of the middle could remain constant. Then it becomes a question of which operation you want to optimize for.