Home Coding Interview
Post
Cancel

Coding Interview

Posted Dec 14, 2022 Updated Sep 28, 2023
By Jiacen (Jason) Xu
6 min read

Interview Preparation

1. Top 10 mistakes

  1. Practicing on a computer: Use pen and paper
  2. Not rehearsing Behavioral Questions
  3. Not doing a mock interview
  4. Trying to Memorize Solutions
  5. Not soluving problems out loud
  6. Rushing
  7. Sloppy Coding: imagine you are writing for real-world maintainability
  8. Not Testing
  9. Fixing Mistakes Carelessly
  10. Giving up

2. Behavioral Preparation

Think about the question: Tell me about a time when you ....

Common Questions Project Project
Most Challenging    
What you learned    
Most Interesting    
Hardest Bug    
Enjoyed Most    
Conflicts with Teammates    

2.1 Questions for the interviewer

General:

  1. How much of your day do you spend coding?
  2. How many meetings do you have every week?
  3. What is the ratio of testers to developers to program managers? What is the interaction like? How does project planning happen on the team?

Insightful:

  1. I noticed that you use technology X. How do you handle problem Y?
  2. Why did the product choose to use the X protocol over the Y protocol? I know it has benefits like A, B, C, but many companies choose not to use it because of issue D.

Passion:

  1. I am very interested in scalability. Did you come in with a background in this, or what opportunities are there to learn about it?
  2. I am not familiar with technology X, but it sounds like a very interesting solution. Can you tell me a bit more about how it works?

3. Technical Question

How to practice a Question?

  1. Try to solve the problem on your own.
  2. Write the code for the algorithm on paper.
  3. Test your code on paper: general cases, base cases, error cases, and so on.
  4. Type your paper code as-is into a computer: start a list of all the errors you make to keep these in mind in the real interview.

3.1 Must-have Knowledge

Data structure Algorithms Concepts
Linked Lists breadth First Search Bit Manipulation
Binary Trees Depth First Search Singleton Design Pattern
Tries Binary Search Factory Design Pattern
Stacks Merge Sort Memory (Stack vs Heap)
Queues Quick Sort Recursion
Vectors/ArrayLists Tree Insert/Find/e.t.c. Big-O Time
Hash Table    

Make sure you understand how to use and implement them and, where applicable, what the space and time complexity is. For the data structure and algorithms, be sure to practice implementing them from scratch. Hash tables are important.

3.2 Five Steps to a Technical Question

  1. Ask your interviewer questions to resolve ambiguity: data types, data range, assumptions, who is the user?
  2. Design an Algorithm
    1. what is the space and time complexity?
    2. What if there is a lot of data?
    3. Does it cause other issues?
    4. If there are other issues or limitations, did you make the right trade-offs?
    5. If they gave specific data, have you leveraged that information? Usually there is a rason to give specific information.
  3. Pseudocode
  4. Code
    1. Use data structures generously
    2. Don’t crowd your coding: start fromt he upper left hand corner of a whiteboard.
  5. Test:
    1. Extreme cases: 0, negative, null, maximums, minimums
    2. User error: if user passes in null or a negative value?
    3. General cases

3.3 Five Main Algorithm Approaches

  1. Examplify
  2. Pattern Matching: try to modify the solution to a related problem to develop an algorithm.
  3. Simplify and Genearlize
  4. Base case and Build
  5. Data Structure Brainstorm: Linked list, Array, Binary tree, Heap, Dictionary…

3.4 Good Code Properties

  • Correct
  • Efficient
  • Simple
  • Readable
  • Maintainable

4. Interview Questions

4.1 Data Structures

  • Arrays and Strings
    • Hash Tables: map keys to values for highly efficient lookup.
      • ❗️practice both implementing and using hash table.
    • ArrayList (Dynamically Resizing Array)
    • StringBuffer
  • Linked Lists
    • Creating a Linked List
    • Deleting a Node from a Singly Linked List
    • The Runner Technique
    • Recursive Problems
  • Stacks and Queues
    • Implementing a Stack
    • Implementing a Queue
  • Trees and Graphs
    • ❗️Potential Issues to Watch Out For
      • Binary Tree vs Binary Search Tree
      • Balanced vs Unbalanced
      • Full and Complete
    • Binary Tree Traversal
      • in-order/post-order/pre-order traversal
    • Tree Balancing: Red-Black Trees and AVL Trees
    • Tries
    • Graph Traversal
      • Depth First Search
      • Breadth First Search

4.2 Concepts and Algorithms

4.2.1 Bit Manipulation - Bit Manipulation by Hand - Bit facts and Tricks - Common Bit Tasks: Get, Set, Clear, and Update Bit

4.2.2 Brain Teasers - Start Talking - Develop Rules and Patterns - Worst Case Shifting - Algorithm Approaches: Consider 5 methods from 3.3

4.2.3 Mathematics and Probability - Prime Numbers - Divisibility - Checking for Primality - Generating a List of Primes: The Sieve of Eratosthenes - Probability - A and B - A or B - Independence - Mutual Exclusivity

4.2.4 Object-Oriented Design

  • How to approach Object-Oriented Design Questions
    • Step 1: Handle Ambiguity (Some descriptiones are vague which need to make clear)
    • Step 2: Define the Core Objects
    • Step 3: Analyze Relationships
    • Step 4: Investigate Actions
  • Design Patterns
    • Singleton Class: a class can have only one instance.
    • Factory Method: an interface to create an instance of a class.

4.2.5 Recursion and Dynamic Programming

  • How to Approach
    • Bottom-Up Recursion
    • Top-Down Recursion
  • Dynamic Programming
    • A simple example: Fibonacci Number
  • Recursive vs. Iterative Solutions

4.2.6 Scalability and Memory Limits

  • The Step-By-Step Approach
    • Step 1: Make believe
      • Assuem the data can fit on one machine without limitations.
    • Step 2: Get Real
    • Step 3: Solve Problems
  • What do you need to know: Information, Strategies and Issues
    • Dividing up lost of data
      • by order of appearance
      • by hash value
      • by actual value
      • arbitrarily

4.2.7 Sorting and Searching

  • Common Sorting Algorithms
    • Bubble Sort
      • Runtime: average O ($n^2$) and worst case.
      • Memory: O (1).
    • Selection Sort
      • Runtime: average O ($n^2$) and worst case.
      • Memory: O (1).
    • Merge Sort
      • Runtime: average O ($n\cdot Log(n)$) and worst case.
      • Memory: depends.
    • Quick Sort
      • Runtime: average O ($n\cdot Log(n)$) and worst case O ($n^2$)
      • Memory: O ($Log(n)$)
    • Radix Sort
      • Runtime: average O($k\cdot n$)

4.2.8 Testing

  • What the interviewer is looking for?
    • Big picture understanding
    • Knowing how the pieces fit together
    • Organization
    • Practicality
  • Testing a Real World Object
    • Step 1: Who will use it? And why?
    • Step 2: What are the use cases?
    • Step 3: What are the bounds of use?
    • Step 4: What are the stress/ failure conditions?
    • Step 5: How would you perform the testing?
  • Testing a piece of Software
    • Manual vs. Automated Testing
    • Balck Box Testing vs. White Box Testing
    • Step 1: Are we doing Balck Box Testing or White Box Testing?
    • Step 2: Who will use it? And why?
    • Step 3: What are the use cases?
    • Step 4: What are the bounds of use?
    • Step 5: What are the stress conditions/failure conditions?
    • Step 6: What are the test cases? How would you perform the testing?
  • Testing a Function
    • Step 1: Define the test cases
      • the normal case
      • the extremes
      • Nulls and “illegal” input
      • Strange input
    • Step 2: Define the expected result
    • Step 3: Write test code
  • Troubleshooting Questions
    • Step 1: Understand the Scenario
    • Step 2: Break Down the Problem
    • Step 3: Create Specific, Manageable Tests

Reference

  • Cracking the Coding Interview: 150 Programming Questions and Solutions
Summary
PhD
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents

CCS 20222 Summary

Tricks Summary 2023