Archive for the ‘Data Structures’ Category

Dijkstra’s algorithm used to solve shortest path problem.. Its used in routing…

For given source vertex(node) in the graph ,the alg will find the shortest path between the vertex and with every other vertex.

Ex: Finding shortest route between one city and all other cities..

Read Full Post »

Consider a singly linked list. What is the optimal way to traverse to an Nth element from the last element of that singly linked list. Any algorithms or logic to achieve in optimal way?

Naive soln :

  • First find the total number of nodes, by iterating the entire list ..
  • Now subtract the nth last node from the total number
  • Now again iterate from the head node to the nth nodeā€¦

But it require two complete iteration..

Optimized soln :

  • Create two pointers and point those pointers to head node..
  • Iterate first pointer to nth node..
  • Now, iterate both first node pointer and second node pointer, until first node pointer reaches the end of the list .. Now second pointer will be pointing to the nth node from the last node.. (more…)

Read Full Post »