Interview questions
- what’s difference C++ and java
- explain about java static
- is java use call by reference or call by value
- get the algorithm to fine nth value from the last element in single linked list, and write code
all questions look pretty easy though,
anyway, the last algorithm question. because it’s just one direction single linked list, we should travel from the start node to the last node. then we figure it out how many elements in that linked list when we reached the last element. then we can simply travel again from the start node to (m-n)th element. complexity is O(n).
I was trying to bring up some other data structure like stack or hash table but, all those are not good in terms of space efficiency. we do not have to wast precious resource which doesn’t increase the performance that much.
There’s two ways to do this, the first uses less resources, but requires two passes as you mention. Only way to do it efficiently in one pass would be to keep references to the last n values you’ve looked at, storing them in a queue of length n. Add the latest one, and if the queue is full pop out the oldest one, since it is surely > n from the end. Since you’re only saving references, it’s not a huge memory hog unless n gets to be too big, then it would be a trade off between the two, and it would probably be worth bonus points to explain the measurements of that trade off.
take two pointers,initially both are holding Head node of Linked List .
Step1 : move the first pointer , N node ahead . Means now first pointer pointing to the Nth node of linked list .
Step2 : Now move both pointer together until first pointer reached at tail.
Step3: At this condition the Second pointer is pointing to Nth node from last.