Interview

NOTE

• Insure all solutions handle edge cases and large inputs.
• It is better to submit something sub-optimal than something that doesn’t work.

Table: Compensations List

TODO

• Project Euler (up to problem 60)
• Review ‘Traversal’ algorithms
• Review ‘Divide & Conquer’ algorithms
• Come up with five different answers to the types of questions in the leadership principles questions.
• Study algorithms and data structures
  • hash maps, stacks/queues/heap/priority que
  • link lists/reverse link lists (space vs time)
  • recursion/recursive strings
  • binary search
  • Arrays - 2d/3d
  • graphs/graph traversal
  • [Big O notation](Big O notation)
  • Some tools you might find useful to study up for the coding portion include:
    • Leet Code or Codefights
    • Elements of Programming Interviews
    • Cracking the coding interview
    • AWS Application Architecture Center– these are the tools that we use to develop amazon services/products.
• What is the best way to build a string in
  • C
  • C++
  • Java
  • Javascript
  • Python
  • Go
  • Rust
• Write implementation for run length encoding
• Google and read about
  • “Amazon parking lot example design” and be familiar with those concepts
  • “Solve boggle board algorithm”
  • Binary search questions
• Implement a cache in
• Implement path-finding algorithems (shortest distance between two points in a grid accounting for obsticals)in

Q: When would you use breadth-first search verses depth-first search? What are the trade-offs?

Breadth-first search is best used when the node that is being searched for would be close to the root of the Binary-Search tree but a BFS may be impractical in the case that the tree is very wide or if solutions are frequent but located deep in the tree.

Depth-first search should be used when the node that is being searched for would most often be located deep in the binary-search tree, and even still the depth may need to be restricted for DFS to be preformat.

As for trade-offs, these algorithms being used on graphs, parallelism of BFS would need a shared data structure between threads. This is generally not good for multithreading. And DFS might be easier to distribute evenly between machines though exact ordering of visited nodes isn’t easily maintained.

Questions to ask the interviewers

1. What are the plans for Amazon oen the next 5 to 10 years and how could I help achieve these goals?

2. What innovative products or services is Amazon currently developing?

3. What are the first things that I would be focused on in this position?

TECHNICAL TOPICS

Check list

• Programming Languages
• Data Structures
• Algorithms
• Coding
• Databases
• Operating Systems
• Competencies

Problem Solving

Extracted to the Science Problem Solving wiki.

References:

• seven steps for problem solving
• optimizing with BUD
• optimizing with time and space
• optimizing with DIY

Programming Languages

Familiarity with a prominent language is generally a prerequisite for success. Be familiar with the syntax and nuances of common languages.

• Java
• Python
• C#
• C/C++
• Ruby
• JavaScript
• Go
• Rust

Data Structures

Storing and providing access to data in efficient ways. Understand the inner workings of common data structures and be able to compare and contrast their usage in various applications. Know the runtimes for common operations as well as how they use memory. Wikipedia is a great resource for brushing up on data structures.

Algorithms

Basic implementation strategies of different classes of algorithms is more important than memorizing the specific details of any given algorithm. Consider reviewing traversals and divide and conquer algorithms. Consider knowing how and when to use a breadth-first search vs. a depth-first search, and what the tradeoffs are. Knowing the runtimes, theoretical limitations, and basic implementation strategies of different classes of algorithms > memorizing specific details of any given algorithm.

Coding

The most important thing a Software Engineer does is write scalable, robust, and well-tested code. Be comfortable coding by hand.

Expect to be asked to write syntactically correct code—no pseudo code.

Check for edge cases and validate that no bad input can slip through.

The goal is to write code that’s as close to production-ready as possible. This is your chance to show off your coding ability.

Tips and Tricks:

• Don’t just dive in, make sure you know all the details and everyone is ready What algorithms, data structures, bounds, types, indices?
• Use language features
  • If you aren’t sure about a feature should be used, ask.
  • Assume imagining reasonable functions are permissible and implement later if necessary.
• Use reasonable style for the chosen language and be consistent.
• Use error cases, boundary checking, guards, or write a comment about doing these if they are time consuming.

Expectations

Code should be ‘WARMED’:

• Writable
• Arguable
• Readable
• Maintainable
• Executable
• Debug-able

Before you start coding, you should know things like:

• Input and output datatypes and bounds.
• What index calculations may be needed.
• What helper functions may be needed.
• What data structures you might use and when and how they may change.

Wait until everyone is ready to code before you start coding. Don’t rush into coding a solution if you don’t fully understand what the requirements are or others don’t fully understand what you will be doing. This leads to misunderstanding, wasted time, and incomplete solutions.

Understanding the ‘gist’ isn’t good enough. Talk about the blind spots or concerns you think you might have with others.

If you get confused while writing the code for your solution, don’t ‘power through it’. Go back to your example case or walk what you have done so far and figure out or clarify what needs to be done.

Structure

Writing structured code insures that your code is readable and maintainable and makes life easier for you and anyone else that has to read or edit your code.

Here are some tips for writing structured code:

• Modularize code from top down, driven by the next most interesting piece of code.
• Ignore things that don’t show good signals (but check with others first). These could be imagined, like a ‘max’ function in a language that doesn’t have it in the standard libraries. Be sure to ask others if this is acceptable, they may ask for you to implement these functions.
• Focus on what shows signal
• Talk to others, don’t guess their expectations.

Object-Oriented Design

Good design is paramount to extensible, bug free, long-lived code. Using object-oriented design best practices is one way to build lasting software. Have a working knowledge of a few common and useful design patterns. Know the appropriate use of inheritance and aggregation. Expect to defend and describe your design choices.

Verification

You will be expected to be able to verify that your code works by walking an execution of a test case manually.

Note that your original example shouldn’t be reused here as the test case. Good examples are large and large test cases take a very long time to run through manually.

Generally, this isn’t a good idea for two reasons:

1. The example is usually too large to manually test efficiently
2. You might have not planned for a scenario in your algorithm because it was over fit to this case.

An Efficient Verification Process:

1. Conceptual walk through (no test case) Walk through your code conceptually. Think through each line.

   What does it do? Is that the right thing to do?

2. Look at hot sports (areas where issues are likely to occur)

   Where are the high risk areas in the code?

   • Math
   • Moving indices
   • Parameters when calling recursively
   • Base cases
3. Run manual tests
   • Start with small tests (2 or 3 elements)
   • Edge cases
     • Boring edge cases: Nulls, empty strings, single element, invalid input, etc.
     • Interesting edge cases: big numbers, negatives, all special characters, sorted input, all duplicates
   • General (large) cases

Design Patterns

TODO(tlc): Fill this in

Communication

Here are some tips for communicating during your interview

1. Drive through the problem

   Don’t make the interviewer ask you to improve your solutions. Instead, be the one to look for these improvements yourself.

2. Show your thought process

   If your interviewer understands how you’re approaching your solutions, the can better:

   • Offer suggestions
   • Evaluate your approach
   • Understand tha your doing well

3. Ask questions

   Is the data sorted? Is the tree balanced? Can I modify the array? Do I need to print the strings, return the strings, or just return the count?

4. Propose an initial solution, but also think about its issues.

   Start with the brute force solution, state it’s time and space complexity, and build from there.

5. Talk while you code if possible and explain what you’re doing.

6. Use examples to explain your approach

   Don’t use code as the way to explain your process. It takes too long. Rather, use examples and talk through them with your interviewer.

7. Accept and be open about your mistakes.

   It’s normal to make some mistakes but it is important that you’re open about them and accept them.

8. Keep trying

   Interviewers want candidates who keep trying to make progress, even when they get stuck or the question is hard for them. The don’t want people that give up when the going gets tough.

9. Listen to your interviewer

   If your interviewers is making suggestions, it’s because they think it’s useful to you. Make sure you understand what they’re getting at. Listening well helps you make progress and shahs collaboration skills.

10. Make sure you capture the value of their hints.

    If your interviewer ever offers the same hint more than once, that’s a BIG hint that you missed something and that it’s really important to the interviewer that you understand that hint.

11. Follow along if the interviewer leads you somewhere.

    If the interviewer leads you down a process, then follow them. They could be leading you to some sort of pattern of processing or just curious to see what you would do. In any case, follow along.

Databases

Most of the software that we write is backed by a data store, somewhere. Many of the challenges we face arise when figuring out how to most efficiently retrieve or store data for future use. The more you know about how relational and non-relational databases work and what tradeoffs exist between them, the better prepared you will be.

Operating Systems

Be familiar with some OS topics that can affect code performance. You won’t need to know how to build your own operating system from scratch, but you should have an understanding of: memory management, processes, threads, synchronization, paging, and multithreading.

Competencies

There are three competencies that will be evaluated: systems design, logic and maintainability,

• Working knowledge of a few common and useful design patterns
• Understanding of Object-Oriented design
• Be prepared to discuses latency and concurrency.
• Study
  • Distributed systems
  • Struct-of-Array? (SOA)
  • n-tiered software architecture
  • Best practices accessability, maintainability, and scalability in the tech stack or infrastructure you would like to use
  • scalability concepts and technology
    • caching
    • load balancing
    • non-relational databases
    • micro services
    • sharding

Systems Design

Systems design competency is the measurement of your ability to “black box” design a software system. The goal is for you to deliver a design in production with considerations of deployment, scaling, failures, availability, and performance. (practice drawing high-level diagrams)

Systems typically require components, something to store data, something to make decisions, and APIs or processes.

Tips for System Design Questions

Ask clarifying questions to define the scope and requirements.

• Who are you designing the system for and why?
• What expectations do the have in terms of functionality?
• What things would a customer just assume will be in the system but they may not think about in the forefront of their minds? (e.g.: “It’ll be fast and secure”)
• Understand first what problem your system is supposed to solve. If you don’t fully understand the problem, ask more questions and collect scope and requirement information.
• Write out the requirements and assumptions you are making and base your design on them.
• Draw diagrams if it helps clarify your thoughts.
• Consider scaling and fault tolerance when design solutions to the problem.

Fulfill captured requirements (e.g., constraints, scalability, maintenance)

Things that influence the design typically include:

• non-functional requirements
  • amount of load
  • load distribution
  • security
• ways of interaction with the system
  • user access
  • scheduled processes
  • synchronous / asynchronous communication
• data flow

Explicitly mention all assumptions that are being made

Spend the majority of time on the Critical Requirements identified and on the core functionality.

Justify design choices that are made.

Design the solution for scale, i.e., would more transactions seamlessly work?

Design for operational performance and develop plans for failure and measure results.

When you have a design that you think solves the customer’s problem, ensure that it also incorporates operations and think about operations and resilience you design

• What are the key business and technical metrics for the system? How will someone use that to identify problems?

• What are the potential bottlenecks or pain points?

• What failure points exist?

• what redundancy can we build in to reduce single points of failure?

• How does someone get logs and debug the system?

  Lastly, identify potential shortcomings and tradeoffs with different designs (e.g., performance, fault tolerance, dependencies)

  If there are multiple ways to design a system that satisfy the requirements, describe the tradeoffs of both approaches, choose one and explain why. Having conversations with the interviewer and explaining your thought process , might help you to make a choice.

  The interviewers are looking for a high level of understanding of how to design a system and deep knowledge into at least one area. If the interviewer asks you to dive deep into something you are unfamiliar with, tell them and suggest other areas that you are more familiar with and dive into that. Offer to respond to their question afterwards when you have had a chance to read more about it.

Logic and Maintainability

Be technical in your solutions and be ready to write WARMED code. (Writable, Arguable, Readable, Maintainable, Executable, and Debug-able)

Always be considerate of edge cases, write syntactically correct code (respective of the language, no pseudo-code); be clean and clear about what you are doing.

Tips for Logic and Maintainability

Create simple code (e.g., leverage reuse, properly format, don’t use improper coding constructs or features that you’re less familiar with).

Feel free to write out examples of how your code will be used. If it seems overly complex, go bock and rethink if that’s how you’d want your coworkers to use your code and if there are ways to simplify it.

Time is precious. Rather than spending time trying to think of an optimal solution start with a working solution, no matter how simple, and enhance it as you go.

Think about extendibility, make sure you are able to extend the code if and when requirements change, avoid a single function that does everything.

Create maintainable code (e.g., be able to quickly trace impact of changes and have clear variable naming conventions).

Make sure that your method, parameter, and variable names are clear & descriptive (e.g., don’t just use “a” or “foo”) and try to separate out functionality into discrete methods/functions with clear responsibilities. Remember that the code will likely remain in use for a long time, far longer than it took to write it, so the clearer things are the more the future maintainers wil thank you (maybe you’ll even thank yourself).

Your code should be reasonably easy to maintain as the requirements change (i.e., traffic or load increases).

Organize code in a way that is easy to read and understand. Use functions, classes, and light inheritance to break up your solution into logical components. This improves readability and makes it easier to extend the solution for new requirements.

Create mostly syntactically correct code (minor issues like a few syntax errors should be forgiven)

Pick the coding language you are most comfortable with. Ensure that you’re comfortable with the idioms and convention of you chosen language (e.g., error/exception handling, managing resources like file I/O, network connections, etc.) and use descriptive names.

If you need a method call but forget its exact name or arguments, call that out and ask the interviewer if you can make up a name and arguments.

Create code that works as intended. Start small, solving one thing at a time, and iterate over your solution as you ask questions or the interviewer does more follow-ups. If you see clear design patterns or abstractions that can be applied from the very beginning, apply those! It is better to realize code can be refactored to support more requirements in a maintainable way, rather than building a complex solution or investing time applying a design pattern that doesn’t solve the requirements.

Think through test cases (both working and breaking), edge cases, boundary conditions, null/nil/none/nan etc. Try and enumerate these cases before you begin coding so that when you have a solution you feel works, you can use these as validation. Be sure to also confirm test cases with your interviewer.

// This is example code in c++
class BookFilter {
    virtual bool apply(Book) = 0;
};

class TitleFilter: public BookFilter {
    std::string m_title;

    public:
    TitleFilter(std::string title): m_title(title) {}
    overide bool apply(const Book &book) {
        if(Book.title.find(m_title) != std::string npos) {
            return true;
        } else {
            return false;
        }
    }
};

typedef enum {
    BIG,
    MEDIUM,
    SMALL
} BookSize;

class BookSizeFilter: BookFilter {
    BookSize m_desiredSize {};
    BookSizeFilter(BookSize desiredSize): m_desiredSize(desiredSize) {}
    overide bool apply(const Book &book) {
        unsigned int minPages = 0;
        unsigned int maxPages = 0;

        switch(m_desiredSize) {
            case SMALL: {
                minPages = 0;
                makPages = 100;
            } break;
            case MEDIUM: {
                minPages = 101;
                maxPages = 500;
            } break;
            case BIG: {
                minPages = 501;
                maxPages = std::UINT_MAX;
            } break;
            default: {}
        }
        return ((Book.pageCount >= minPages) && (Book.pageCount < maxPages));
    }
};

bool BookPassesFilters(const Book &book, std::List<BookFilter> &filters) {
    for (auto filter : filters) {
        if (!filter.apply(book)) { return false; }
    }
    return true;
}

std::set<Book> FilterBooks(std::List<Book> bookList, std::List<BookFilter> &filters) {
    std::set<Book> result;

    for(auto book : booklist) {
        if(bookPassesFilters(book, filters)) {
            result.push_back(book);
        }
    }

    return result;
}

This code response shows strength in:

1. Breaking functionality into separate functions and classes rather than a monolithic implementation.
2. The use of an enumeration helps consistency and provides an idiomatic way for users of the code to specify parameters.
3. A class structure makes the addition of new filters, even by those who don’t have access to the source code, easy.
4. Code is easy to read. Classes and member variables are descriptive enough to know what they represent without being verbose.

Data structures and algorithms

TODO(tlc): you are here

Leadership Principles

Customer Obsession

Leaders start with the customer and work backwards. They work vigorously to earn and keep customer trust. Although leaders pay attention to competitors, they obsess over customers.

TODO(tlc) Example: “Describe a time when you went above and beyond what was expected to help a customer?”

A:

Ownership

Leaders are owners. They think long term and don’t sacrifice long-tern value for short-term results. They act on behalf of the entire company, beyond just their own team. They never say “that’,s not my job.”

TODO(tlc) Example: “Tell me about a time when you failed at work?”

A:

Invent and Simplify

Leaders expect and require innovation and invention from their team and always find ways to simplify. They are externally aware, look for new ideas from everywhere, and are not limited by “not invented here.” Because we do new things, we accept that we may be misunderstood for long periods of time.

Are Right, A Lot

Leaders are right a lot. They have strong judgement and good instincts. They seek diverse perspectives and work to disconfirm their beliefs.

Learn and Be Curious

Leaders are never don leaning and always seek to improve themselves. They are curious about new possibilities and act to explore them.

Hire and Develop the Best

Leaders raise the performance bar with every hire and promotion. They recognize people with exceptional talent and willingly move them throughout the organization. Leaders develop leaders and are serious about their role in coaching others. Leaders work on behalf of their people to invent mechanisms for individual development.

Insist on the Highest Standards

Leaders have relentlessly high standards – many people may think theses standards are unreasonably high. Leaders are continually raising the bar and driving their teams to deliver high quality products, services, and processes. Leaders ensure that defects do not get sent down the line and that problems are fixed so the stay fixed.

Think Big

Thinking small is a self-fulfilling prophecy. Leaders create and communicate a bold direction that inspires results. They think differently and look around corners for ways to serve customers.

Bias for Action

Speed matters in business. Many decisions and actions are reversible and do not need extensive study. We value calculated risk taking.

Frugality

Accomplish more with less. Constraints breed resourcefulness, self-sufficiency and invention. There are no extra points for growing headcount, budget size, or fixed expenses.

Earn Trust

Leaders listen attentively, speak candidly, and treat others respectfully. They are vocally self-critical, even when doing so is awkward or embarrassing. Leaders do not believe their or their team’s shit doesn’t stink. They benchmark themselves and their teams against the best.

Dive Deep

Leaders operate at all levels, stay connected to the details, audit frequently, and are skeptical when metrics and anecdote differ. No task is beneath them.

Have Backbone, Bet on It; Disagree and Commit

Leaders are obligated to respectfully challenge decisions when they disagree, even when doing so is uncomfortable or exhausting. Leaders have conviction and are tenacious. They don not compromise for the sake of social cohesion. Once a decision is determined, they commit wholly. They bet on it.

TODO(tlc) Example: “Tell me about a time when you had a disagreement with somebody at work”

A:

Deliver Results

Leaders focus on the key inputs for their business and deliver them with the right quality and in a timely fashion. Despite setbacks, they rise to the occasion and never compromise.

TODO(tlc) Example: “Describe a time when you overcame a difficult challenge at work”

A:

Strive to be Earth’s Best Employer

Leaders work every day to create a safer, more productive, higher performing, more diverse, and more just work environment. They lead with empathy, have fun at work, and make it easy for others to have fun. Leaders ask themselves: “Are my fellow employees growing? Are they empowered? Are they read for what’s next?”; Leaders have a vision for and commitment to their employees’ personal success, no matter where they work.

Success and Scale Bring Broad Responsibility

We started in a garage, but we’re not there anymore. We are big, we impact the world, and we are far from perfect. We must be humble and thoughtful about even the secondary effects of our actions. Our local communities, planet and future generations need us to be better everyday. We must begin each day with a determination to make better, do better, and be better for selves, our customers, our employees, our partners, and the world at large. And we must end every day knowing we can do even more tomorrow. Leaders create more than thy consume and always leave things better than how they found them.

Software Interview Preparation (SIP)

Leadership Questions

You will know you are being asked a “Leadership” (a.k.a, behavior) question when you hear something along the lines of, “Tell me about a time when –”, such as “Tell me about a time when you had to make a decision between two different technologies”.

When answering behavior questions, follow the “situation, behavior, impact” (SBI) idiom.

For situation, describe what the situation was and what the team was trying ta achieve. For behavior, describe what was done and what plan of action was made. And for impact, describe the outcome and try to be quantitative about the results.

System Design Questions

1. Don’t jump into trying to solve the problem. Try to understand the question. Ask more questions (about scale, performance, requirements, etc.).
2. Try to make the the design and implementation a conversation as though the interview and you were apart of a team.

Programming

1. Analyze the domain of the problem
2. Disambiguate the unknowns. Ask questions about the inputs, processing, outputs, and edge cases.
3. Talk aloud about what you are thinking and doing and include the interviewer.

Example: Run-Length Encoding

Input: aaaabbccc expected Output: 4a2b3c

clarifying questions: Are there only lower case characters? Can there be numbers? How should we deal with special characters such as whitespace, punctuation?