/Cracking-The-Code-Interview

My name is Ozymandias, king of kings; Look on my works, ye Mighty, and despair!

Primary LanguageJavaScript

Welcome to my solutions for Cracking the Code Interview

My Interview Notes:

Walking through a problem:

  1. Listen: Pay very close attention to any information in the problem description. You probably need it all for an optimal algorithm
  2. Example: Most examples are too small or are special cases. Debug your example. Is there any way it's a special case? Is it big enough?
  3. Brute Force: Get a brute-force solution as soon as possible. Don't worry about developing an efficient algorithm and its runtime, then optimize from there. Don't code yet though!
  4. Optimize: Walk through your brute force with BUD optimization or try some of these ideas:
    • Look for any unused info. You usually need all the information in a problem.
    • Solve it manually on an example, then reverse engineer your thought process. How did you solve it?
    • Solve it 'incorrectly" and then think about why the algorithm fails. Can you fix those issues?
    • Make a time vs. space tradeoff. Hash tables are especially useful!
  5. Walk Through: Now that you have an optimal solution, walk through your approach in detail. Make sure you understand each detail before you start coding.
  6. Implement: Your goal is to write beautiful code. Modularize your code from the beginning and refactor to clean up anything that isn't beautiful.
  7. Test: Test in this order:
    1. Conceptual test. Walk through your code like you would for a detailed code review
    2. Unusual or non-standard code.
    3. Hot spots, like arithmetic and null nodes.
    4. Small test cases. It's much faster than a big test case and just as effective.
    5. Special cases and edge cases.

And when you find bugs, fix them carefully

(BUD Optimization: Bottlenecks, Unnecessary Work, Duplicated Work)

Problem Solving Process:

  1. Specification: Identify valid datatypes and ranges for output and inputs, as well as any side effects on inputs, external variable bindings, program environment, or hardware.

  2. Justification: In one or two sentences, describe the purpose of calling this function.

  3. Explanation: Clearly state the relationship between inputs and outputs. Use plain english to completely explain the the system's effects and behavior. Don't use any code in your explanation.

  4. Visualization: Draw a plan for solving the problem that an engineer would understand. Use pictures and avoid letters or words (except when labeling things with a name). You may need to show sample data.

  5. Approximation: Pseudocode your plan. Each line should be:

    • Unambiguous
    • A clear step toward the goal
    • Understandable without reading other steps
    • As high level as possible (You'll use helper functions in smaller steps)

  6. Verification: Using sample data, walk through your pseudocode plan to verify the plan work as expected (When using TDD, you should write a test at this point)

  7. Implementation: Turn your pseudocode into real code.

Whiteboarding Key Pointers:

O-ICE = Output, Input, Constraints, Edge Cases

Output: Ask exactly what your algorithm should return.

Input: Ask exactly what your algorithm will receive to perform work on.

Constraints: Time and space complexity!!! Plus other limitations on side-effects.

Edge Cases: Identify special cases that will need additional consideration in your algorithm.

Examples of Edge Cases:

Numbers:

- negative values - duplicate values - zero values - all the same values - all zeros

Strings:

- duplicate characters - non-alphanumeric (!@#$%^&*) - all the same characters - empty string

Arrays:

- modify the input? - do we have allocated space for increasing array size? - empty array

Sequence of WhiteBoarding:

O-ICE --> Diagramming --> Pseudocode

Always refer logic to a previous section.