Microsoft Interview Question
Software Engineer in TestsLinklist is a serial access data structure , not random access like array. In order to access any node in the linklist we have to traverse from the start of the link list to that node. In array Accessing any element is a O(1) operation where as in linklist it is O(n).
The (log n) efficiency of the binary search is inversely proportional to the access time of the middle element. In binary search we access the middle element log(n) times, as the access time of linklist is O(n) the time complexity of binary search in linklist becomes O(nlogn).
The best inplace solution would be linear search O(n).
We may do this in O(n/2) my having 2 pointers corresponding to even and odd elements ..in this way in the worst case also it loop will run for O(n/2) times...
your solution also same as above...
becoz if you use two pts even and odd,have to do 4 comparisons inside the loop,in worst case you done n/2 * 4 = 2n comparisons,
in the previous ans,have to do 2 comparisons, in worst case we done n * 2 = 2n comparisons,
so both are same time complexity
How about using BinarySearch? Ar running time of the BinarySearch is o(log n).
- master December 29, 2009Finding the number of elements in the list / finding the mid of the linked list will take o(n) worst case. ~ o(n/2). Hence its o(n) again.