Sample problems to improve knowledge of data structures

Question

I have seen majority of web programmers (writing some script with sql to make CRUD applicationg) do not know how to build a business logic in relatively complex situations like, using Stack, or Queue or write recursive algorithm. These programmers have habit of simply searching code on google and paste it, but dont understand which data structure do what and when to use what.

I am trying to conduct a session to train web programmers to improve their knowledge with data structures, e.g. I gave a sample program to count repeatations of the word in given text, one should use Dictionary/Hashtable, but even after guiding them to use Dictionary, they were still not able to do it.

I need sample problem definitions (Sure I can certainly figure out answers, but I dont want anyone to give code here, only problem definitions) that should train them to use Stack, Queue, List, Dictionary etc.

If I give them things like parse and expression, they will have heart attack, so I need simple algorithms to start with, just simple as counting repeatations in the given text.

Please assume only .NET 2.0, so generics is fine, but no Linq etc.

Answer 1

Here are a few.

1)

Given a string consisting only of '(' and ')' give an algorithm to check if it is a well bracketed expression (i.e. the brackets are matched properly).

Example: "(())()()" is well bracketed, but "())(" is not.

2)

Represent a number as a linked list of digits. Give algorithms to find the sum and product of such lists. (This representation can in fact be used to represent large integers).

3)

User first enters a bunch of distinct numbers. Output the total number of numbers received, followed by the numbers themselves, in the order they were received. For extra credit, flag an error if user inputs the same number more than once.

4)

User enters a bunch of numbers, possibly duplicated. Output the number of distinct numbers received and in the reverse order in which they were received.

So, if user enters 11 22 22 11 10, you output 3 followed by 10 22 11.