find the k largest or smallest numbers from a set of n numbers

3. How do you find the k largest or smallest numbers from a set of n numbers

Solution:

Build a min/max heap of size K from the available set.

Time complexity: n Log K

Reverse a string

This is one of my favourite and has several correct solutions.

2. Reverse a string.

The best way would be to loop through half of the sting and swap the characters at either end (without using an extra variable!)

A data-structure brain teaser for the day.

Hey guys,

Well I intend to put up a data structure related puzzle, problem, brain-teaser; whatever you wish to call it everyday from today. This is to keep my dedicated at keeping my skills sharp as I recently discovered that I'm faltering big time. So I shall shart off with a few basic old timer problems and then move on to more tricky problems. I shall provide a solution along with the problem and you can better it and enlighten me. So here goes.

1. How do you find loops in a single link list.

Tortise and Hair solution:
Use two pointers and move the first pointer at double the speed of the seconnd, ie, jump the first pointer by two two nodes while the second pointer moves one node at a time. If at any time the two point at the same node, there's a loop in the link list. If you reach the end of the list, there are no loops in the list.

I'm happy that I started this and hope to stick to my plan for a very long time.