An objective response:
While my initial response to this question was based on my empirical experience as a soon-to-graduate CS student and my projected opinion of the type of people I wanted to work with in the CS field. There is actually an objective (with respect to the subjective opinions of the ACM SIGCSE and IEEE computing societies) answer. Every 10 years the ACM and the IEEE bodies cooperate on a joint publication that details suggestions for undergraduate computer science curriculum based on professional knowledge of the state of the computing industry. More information can be found at cs2013.org. The committee publishes a final report listing their curriculum recommendation.
That said, I still think my list is pretty good.
Original answer below.
What Should I Know?
Minimum
I think an adept programmer should have at least undergraduate level knowledge in Computer Science. Sure, you can be effective at many jobs with only a small subset of Computer Science because of the rock solid community CS sits upon, and the narrowed focus of most professional positions. Also, many people will further specialize after undergraduate study. However, I do not think either are an excuse to not be privy of foundational CS knowledge.
To answer the title question, here is what an undergraduate CS student (the foundation for an adept programmer) should know upon graduation:
Data Structures
- Machine Data Representation
- Ones, Two's Complement, and Related Arithmetic
- Words, Pointers, Floating Point
- Bit Access, Shifting, and Manipulation
- Linked Lists
- Hash Tables (maps or dictionaries)
- Arrays
- Trees
- Stacks
- Queues
- Graphs
- Databases
Algorithms
- Sorting:
- Bubble Sort (to know why it's bad)
- Insertion Sort
- Merge Sort
- Quick Sort
- Radix style sorts, Counting Sort and Bucket Sort
- Heap Sort
- Bogo and Quantum Sort (=
- Searching:
- Linear Search
- Binary Search
- Depth First Search
- Breadth First Search
- String Manipulation
- Iteration
- Tree Traversal
- List Traversal
- Hashing Functions
- Concrete implementation of a Hash Table, Tree, List, Stack, Queue, Array, and Set or Collection
- Scheduling Algorithms
- File System Traversal and Manipulation (on the inode or equivalent level).
Design Patterns
- Modularization
- Factory
- Builder
- Singleton
- Adapter
- Decorator
- Flyweight
- Observer
- Iterator
- State [Machine]
- Model View Controller
- Threading and Parallel Programming Patterns
Paradigms
- Imperative
- Object Oriented
- Functional
- Declarative
- Static and Dynamic Programming
- Data Markup
Complexity Theory
- Complexity Spaces
- Computability
- Regular, Context Free, and Universal Turing Machine complete Languages
- Regular Expressions
- Counting and Basic Combinatorics
Beyond
To get into what you're asking about later in your question, if you are familiar with the above, you should be easily able to identify the appropriate pattern, algorithm, and data structure for a given scenario. However, you should recognize that there is often no best solution. Sometimes you may be required to pick the lesser of two evils or even simply choose between two equally viable solutions. Because of this, you need the general knowledge to be able to defend your choice against your peers.
Here are some tips for algorithms and data structures:
- Binary Search can only (and should) be used on sorted data.
- Radix style sorts are awesome, but only when you have finite classes of things being sorted.
- Trees are good for almost anything as are Hash Tables. The functionality of a Hash Table can be extrapolated and used to solve many problems at the cost of efficiency.
- Arrays can be used to back most higher level data structures. Sometimes a "data structure" is no more than some clever math for accessing locations in an array.
- The choice of language can be the difference between pulling your hair out over, or sailing through, a problem.
- The ASCII table and a 128 element array form an implicit hash table (=
- Regular expressions can solve a lot of problems, but they can't be used to parse HTML.
- Sometimes the data structure is just as important as the algorithm.
Some of the above might seem like no brainers, and some may seem vague. If you want me to go into more detail, I can. But, my hope is when encountered with a more concrete question such as, "Design a function that counts the number of occurrences of every character in a String", you look to the tip about the ASCII table and 128 element arrays forming neat implicit hash tables for the answer.
Based off these ideas, I will propose an answer the locker problem outlined in your question.
Answer to the problem posed in your question.
This may not be the best answer to your question, but I think it's an interesting one that doesn't require anything too complex. And it will certainly beat the time complexity of using a queue, or stack which require linear time to determine whether a locker is free or not.
You have 0-999 lockers. Now, because you have a fixed number of lockers, you can easily conceive a hashing function with no collisions on the range 0-999. This function is simply h(x) = x mod 1000. Now, [conceptually] construct a hash table with integer keys and the contents of a 1000 element char array as your values. If a customer wants to reserve locker 78 for use, simply put 78 into the hash function (returning 78), and then add that number to the base pointer of the array -- storing a true value at the location pointed to by the offset value. Similarly, if you need to check whether 78 is in use, simply read the value stored at that location and check against true.
This solution operates in constant time for lookups and storage as opposed to a log(n) time storage and lookup in the case of a priority queue backed by a binary tree. The description is intentionally verbose so you can see the higher concepts being boiled down into an efficient algorithm.
Now, you might ask, what if I need to know all of the available lockers, wouldn't a priority queue be better? If there are k available lockers in the priority queue, iterating over all of them will take k steps. Further, depending on your priority queue implementation, you might have to rebuild your priority queue as you look at it all.. which would take k*log(k) : (k < 1000) steps. In the array solution, you only have to iterate of a 1000 element array and check which ones are open. You can also add an available or used list to the implementation to check in k time only.
