Recently, I had an interview with Rikard Gillemyr, VP Engineering of Opera Software. It was great experience that I talked to someone like him.

While interviewing, he gave me a simple data structure question (It has been a while since I worked on algorithm b/c joining the army, so I would say it was not that easy for me), and it was 'finding a loop in a single linked list.'

A single linked list is used as a stack. It is made of nodes where each node has a pointer to the next node or null to end the list. If there is a loop between any nodes inside of single linked list, then it might not get to the end node or contain more then two links to some node.

I found a solution (but not efficient), and it was checking the entire list everytime when a node gets to next node. It ends up with O(n^2) time complexity.

He tried to give me some idea so that I can improve this, but I could not. I got mad to myself little bit, so I tried find better solution without looking or googling anything, and I found one.

If we know the first and last node, and then we reverse the list, we can track back from last node to first node. If it does not get to the first node that we started before we reverse the list, then we can say there is a loop in this single linked list. It ends up with O(n) time complexity.

Eventually, I googled this to check whether there is better answer, and I found a website.

Link to http://ostermiller.org/find_loop_singly_linked_list.html

Like I said, it has been two years not working or reviewing on any algorithm stuff, so before I start refreshing my knowledge, this was very good point to start with. I really enjoyed and had fun.

Thank you, Mr.Gillemyr-

Rikard Gillemyr began his affiliation with Opera Software in 1998, when he and the other co-founders of Hern Labs in Sweden ported Opera 3 to BeOS. After officially joining Opera Software in 2000, Gillemyr has been responsible for many of Opera's major deliveries, including Opera on BREW and the Opera for Devices SDK. Gillemyr previously served as the country manager of Opera's offices in Poland and Korea before his appointment to Vice President of Engineering. He was educated at the Linköping Institute of Technology where he studied Computer Science and Engineering until 1999. Gillemyr holds 360 000 shares and 350 000 options in the company.