The Complete Coding Interview Guide in Java

Table of contents

1. The Complete Coding Interview Guide in Java
2. Why subscribe?
3. Contributors
4. About the author
5. About the reviewer
6. Packt is searching for authors like you
7. Preface
   1. Who this book is for
   2. What this book covers
   3. To get the most out of this book
   4. Download the example code files
   5. Download the color images
   6. Conventions used
   7. Get in touch
   8. Reviews
8. Section 1: The Non-Technical Part of an Interview
9. Chapter 1: Where to Start and How to Prepare for the Interview
   1. The novice interview roadmap
   2. Know yourself
   3. Know the market
   4. It’s all about getting the right experience
      1. Start something
      2. It’s time to shine online
   5. Time to write your resume
      1. What resume screeners are looking for
      2. How long the resume should be
      3. How to list your employment history
      4. List the most relevant projects (top five)
      5. Nominate your technical skills
      6. LinkedIn resume
   6. The job application process
      1. Finding companies that are hiring
      2. Submitting the resume
   7. I got an interview! Now what?
      1. The phone screening stage
      2. Going to in-person interviews
      3. Avoiding common mistakes
   8. Summary
10. Chapter 2: What Interviews at Big Companies Look Like
    1. Interviews at Google
    2. Interviews at Amazon
    3. Interviews at Microsoft
    4. Interviews at Facebook
    5. Interviews at Crossover
    6. Summary
11. Chapter 3: Common Non-Technical Questions and How To Answer Them
    1. What is the purpose of non-technical questions?
    2. What is your experience?
    3. What is your favorite programming language?
    4. What do you want to do?
    5. What are your career goals?
    6. What's your working style?
    7. Why are you looking to change jobs?
    8. What is your salary history?
    9. Why should we hire you?
    10. How much money do you want to make?
    11. Do you have a question for me?
    12. Summary
12. Chapter 4: How to Handle Failures
    1. Accepting or rejecting an offer
    2. Failure is an option
    3. A company can reject you for a lot of reasons
       1. Getting feedback after the interview
    4. Objectively identifying and eliminating the mismatches
    5. Don’t form an obsession for a company
    6. Don’t lose confidence in yourself – sometimes, they don’t deserve you!
    7. Summary
13. Chapter 5: How to Approach a Coding Challenge
    1. Technical quiz
    2. Coding challenge
       1. The problems specific to coding challenges are meant to be difficult
       2. Tackling a coding challenge problem
    3. Summary
14. Section 2: Concepts
15. Chapter 6: Object-Oriented Programming
    1. Technical requirements
    2. Understanding OOP concepts
       1. What is an object?
       2. What is a class?
       3. What is abstraction?
       4. What is encapsulation?
       5. What is inheritance?
       6. What is polymorphism?
       7. What is association?
       8. What is aggregation?
       9. What is composition?
    3. Getting to know the SOLID principles
       1. What is S?
       2. What is L?
       3. What is I?
       4. What is D?
    4. Popular questions pertaining to OOP, SOLID, and GOF design patterns
       1. What is method overriding in OOP (Java)?
       2. What is method overloading in OOP (Java)?
       3. What is covariant method overriding in Java?
       4. What are the main restrictions in terms of working with exceptions in overriding and overloading methods?
       5. How can the superclass overridden method be called from the subclass overriding method?
       6. Can we override or overload the main() method?
       7. Can we override a non-static method as static in Java?
       8. What are the main differences between interfaces with default methods and abstract classes?
       9. What is the main difference between abstract classes and interfaces?
       10. Can we have an abstract class without an abstract method?
       11. Can we have a class that is both abstract and final at the same time?
       12. What is the difference between polymorphism, overriding, and overloading?
       13. What are the main differences between static and dynamic binding?
       14. What is method hiding in Java?
       15. Can we write virtual methods in Java?
       16. What is the difference between polymorphism and abstraction?
       17. Do you consider overloading an approach for implementing polymorphism?
       18. Which OOP concept serves the Decorator design pattern?
       19. When should the Singleton design pattern be used?
       20. What is the difference between the Strategy and State design patterns?
       21. What is the difference between the Proxy and Decorator patterns?
       22. What is the difference between the Facade and Decorator patterns?
       23. What is the key difference between the Builder and Factory patterns?
       24. What is the key difference between the Adapter and Bridge patterns?
    5. Coding challenges
       1. Example 1: Jukebox
       2. Example 2: Vending machine
       3. Example 3: Deck of cards
       4. Example 4: Parking lot
       5. Example 5: Online reader system
       6. Example 6: Hash table
       7. Example 7: File system
       8. Example 8: Tuple
       9. Example 9: Cinema with a movie ticket booking system
    6. Summary
16. Chapter 7: Big O Analysis of Algorithms
    1. Analogy
    2. Big O complexity time
    3. The best case, worst case, and expected case
    4. Big O examples
       1. Example 1 – O(1)
       2. Example 2 – O(n), linear time algorithms
       3. Example 3 – O(n), dropping the constants
       4. Example 6 – different steps are summed or multiplied
       5. Example 7 – log n runtimes
       6. Example 9 – in-order traversal of a binary tree
       7. Example 10 – n may vary
       8. Example 11 – memoization
       9. Example 13 – identifying O(1) loops
       10. Example 14 – looping half of the array
       11. Example 15 – reducing Big O expressions
       12. Example 16 – looping with O(log n)
       13. Example 17 – string comparison
       14. Example 18 – factorial Big O
       15. Example 19 – using n notation with caution
       16. Example 21 – the number of iteration counts in Big O
       17. Example 22 – digits
       18. Example 23 – sorting
    5. Key hints to look for in an interview
    6. Summary
17. Chapter 8: Recursion and Dynamic Programming
    1. Technical requirements
    2. Recursion in a nutshell
       1. Recognizing a recursive problem
    3. Dynamic Programming in a nutshell
       1. Memoization (or Top-Down Dynamic Programming)
       2. Tabulation (or Bottom-Up Dynamic Programming)
    4. Coding challenges
       1. Coding challenge 1 – Robot grid (I)
       2. Coding challenge 3 – Josephus
       3. Coding challenge 6 – Five towers
       4. Coding challenge 8 – The falling ball
       5. Coding challenge 9 – The highest colored tower
       6. Coding challenge 10 – String permutations
       7. Coding challenge 11 – Knight tour
       8. Coding challenge 12 – Curly braces
       9. Coding challenge 13 – Staircase
       10. Coding challenge 14 – Subset sum
       11. Coding challenge 15 – Word break (this is a famous Google problem)
18. Chapter 9: Bit Manipulation
    1. Technical requirements
    2. Bit manipulation in a nutshell
       1. Obtaining the binary representation of a Java integer
       2. Bitwise operators
       3. Bit shift operators
       4. Tips and tricks
    3. Coding challenges
       1. Coding challenge 1 – Getting the bit value
       2. Coding challenge 2 – Setting the bit value
       3. Coding challenge 3 – Clearing bits
       4. Coding challenge 4 – Summing binaries on paper
       5. Coding challenge 5 – Summing binaries in code
       6. Coding challenge 6 – Multiplying binaries on paper
       7. Coding challenge 7 – Multiplying binaries in code
       8. Coding challenge 8 – Subtracting binaries on paper
       9. Coding challenge 9 – Subtracting binaries in code
       10. Coding challenge 10 – Dividing binaries on paper
       11. Coding challenge 11 – Dividing binaries in code
       12. Coding challenge 12 – Replacing bits
       13. Coding challenge 13 – Longest sequence of 1
       14. Coding challenge 14 – Next and previous numbers
       15. Coding challenge 15 – Conversion
       16. Coding challenge 16 – Maximizing expressions
       17. Coding challenge 17 – Swapping odd and even bits
       18. Coding challenge 18 – Rotating bits
       19. Coding challenge 19 – Calculating numbers
       20. Coding challenge 20 – Unique elements
       21. Coding challenge 21 – Finding duplicates
       22. Coding challenge 22 – Two non-repeating elements
       23. Coding challenge 23 – Power set of a set
       24. Coding challenge 24 – Finding the position of the only set bit
       25. Coding challenge 25 – Converting a float into binary and vice versa
    4. Summary
19. Section 3: Algorithms and Data Structures
20. Chapter 10: Arrays and Strings
    1. Technical requirements
    2. Arrays and strings in a nutshell
    3. Coding challenges
       1. Coding challenge 1 – Unique characters (1)
       2. Coding challenge 2 – Unique characters (2)
       3. Coding challenge 3 – Encoding strings
       4. Coding challenge 4 – One edit away
       5. Coding challenge 5 – Shrinking a string
       6. Coding challenge 6 – Extracting integers
       7. Coding challenge 7 – Extracting the code points of surrogate pairs
       8. Coding challenge 8 – Is rotation
       9. Coding challenge 9 – Rotating a matrix by 90 degrees
       10. Coding challenge 10 – Matrix containing zeros
       11. Coding challenge 11 – Implementing three stacks with one array
       12. Coding challenge 12 – Pairs
       13. Coding challenge 13 – Merging sorted arrays
       14. Coding challenge 14 – Median
       15. Coding challenge 15 – Sub-matrix of one
       16. Coding challenge 16 – Container with the most water
       17. Coding challenge 17 – Searching in a circularly sorted array
       18. Coding challenge 18 – Merging intervals
       19. Coding challenge 19 – Petrol bunks circular tour
       20. Coding challenge 20 – Trapping rainwater
       21. Coding challenge 21 – Buying and selling stock
       22. Coding challenge 22 – Longest sequence
       23. Coding challenge 23 – Counting game score
       24. Coding challenge 24 – Checking for duplicates
       25. Coding challenge 25 – Longest distinct substring
       26. Coding challenge 26 – Replacing elements with ranks
       27. Coding challenge 27 – Distinct elements in every sub-array
       28. Coding challenge 28 – Rotating the array k times
       29. Coding challenge 29 – Distinct absolute values in sorted arrays
    4. Summary
21. Chapter 11: Linked Lists and Maps
    1. Technical requirements
    2. Linked lists in a nutshell
    3. Maps in a nutshell
    4. Coding challenges
       1. Coding challenge 1 – Map put, get, and remove
       2. Coding challenge 2 – Map the key set and values
       3. Coding challenge 3 – Nuts and bolts
       4. Coding challenge 4 – Remove duplicates
       5. Coding challenge 5 – Rearranging linked lists
       6. Coding challenge 6 – The nth to last node
       7. Coding challenge 7 – Loop start detection
       8. Coding challenge 8 – Palindromes
       9. Coding challenge 9 – Sum two linked lists
       10. Coding challenge 10 – Linked lists intersection
       11. Coding challenge 11 – Swap adjacent nodes
       12. Coding challenge 12 – Merge two sorted linked lists
       13. Coding challenge 13 – Remove the redundant path
       14. Coding challenge 14 – Move the last node to the front
       15. Coding challenge 15 – Reverse a singly linked list in groups of k
       16. Coding challenge 16 – Reverse a doubly linked list
       17. Coding challenge 17 – LRU cache
    5. Summary
22. Chapter 12: Stacks and Queues
    1. Technical requirements
    2. Stacks in a nutshell
    3. Queues in a nutshell
    4. Coding challenges
       1. Coding challenge 1 – Reverse string
       2. Coding challenge 2 – Stack of curly braces
       3. Coding challenge 3 – Stack of plates
       4. Coding challenge 4 – Stock span
       5. Coding challenge 5 – Stack min
       6. Coding challenge 6 – Queue via stacks
       7. Coding challenge 7 – Stack via queues
       8. Coding challenge 8 – Max histogram area
       9. Coding challenge 9 – Smallest number
       10. Coding challenge 10 – Islands
       11. Coding challenge 11 – Shortest path
    5. Infix, postfix, and prefix expressions
    6. Summary
23. Chapter 13: Trees and Graphs
    1. Technical requirements
    2. Trees in a nutshell
       1. General tree
       2. Binary Search Tree
       3. Balanced and unbalanced binary trees
       4. Complete binary tree
       5. Full binary tree
       6. Perfect binary tree
       7. Binary Heaps
    3. Graphs in a nutshell
       1. Adjacency matrix
       2. Adjacency list
       3. Graph traversal
    4. Coding challenges
       1. Coding challenge 1 – Paths between two nodes
       2. Coding challenge 2 – Sorted array to minimal BST
       3. Coding challenge 3 – List per level
       4. Coding challenge 4 – sub-tree
       5. Coding challenge 5 – Landing reservation system
       6. Coding challenge 6 – Balanced binary tree
       7. Coding challenge 7 – Binary tree is a BST
       8. Coding challenge 8 – Successor node
       9. Coding challenge 9 – Topological sort
       10. Coding challenge 10 – Common ancestor
       11. Coding challenge 11 – Chess knight
       12. Coding challenge 12 – Printing binary tree corners
       13. Coding challenge 13 – Max path sum
       14. Coding challenge 14 – Diagonal traversal
       15. Coding challenge 15 – Handling duplicates in BSTs
       16. Coding challenge 16 – Isomorphism of binary trees
       17. Coding challenge 17 – Binary tree right view
       18. Coding challenge 18 – kth largest element
       19. Coding challenge 19 – Mirror binary tree
       20. Coding challenge 20 – Spiral-level order traversal of a binary tree
       21. Coding challenge 21 – Nodes at a distance k from leafs
       22. Coding challenge 22 – Pair for a given sum
       23. Coding challenge 23 – Vertical sums in a binary tree
       24. Coding challenge 23 – Converting a max heap into a min heap
       25. Coding challenge 24 – Finding out whether a binary tree is symmetric
       26. Coding challenge 25 – Connecting n ropes at the minimum cost
    5. Advanced topics
    6. Summary
24. Chapter 14: Sorting and Searching
    1. Technical requirements
    2. Sorting algorithms
       1. Heap Sort
       2. Merge Sort
       3. Quick Sort
       4. Bucket Sort
       5. Radix Sort
    3. Searching algorithms
    4. Coding challenges
       1. Coding challenge 1 – Merging two sorted arrays
       2. Coding challenge 2 – Grouping anagrams together
       3. Coding challenge 3 – List of unknown size
       4. Coding challenge 4 – Merge sorting a linked list
       5. Coding challenge 5 – Strings interspersed with empty strings
       6. Coding challenge 6 – Sorting a queue with the help of another queue
       7. Coding challenge 7 – Sorting a queue without extra space
       8. Coding challenge 8 – Sorting a stack with the help of another stack
       9. Coding challenge 9 – Sorting a stack in place
       10. Coding challenge 10 – Searching in a full sorted matrix
       11. Coding challenge 11 – Searching in a sorted matrix
       12. Coding challenge 12 – First position of first one
       13. Coding challenge 13 – Maximum difference between two elements
       14. Coding challenge 14 – Stream ranking
       15. Coding challenge 15 – Peaks and valleys
       16. Coding challenge 16 – Nearest left smaller number
       17. Coding challenge 17 – Word search
       18. Coding challenge 18 – Sorting an array based on another array
    5. Summary
25. Chapter 15: Mathematics and Puzzles
    1. Technical requirements
    2. Tips and suggestions
    3. Coding challenges
       1. Coding challenge 1 – FizzBuzz
       2. Coding challenge 2 – Roman numerals
       3. Coding challenge 3 – Visiting and toggling 100 doors
       4. Coding challenge 4 – 8 teams
       5. Coding challenge 5 – Finding the kth number with the prime factors 3, 5, and 7
       6. Coding challenge 6 – Count decoding a digit's sequence
       7. Coding challenge 7 – ABCD
       8. Coding challenge 8 – Rectangles overlapping
       9. Coding challenge 9 – Multiplying large numbers
       10. Coding challenge 10 – Next greatest number with the same digits
       11. Coding challenge 11 – A number divisible by its digits
       12. Coding challenge 12 – Breaking chocolate
       13. Coding challenge 13 – Clock angle
       14. Coding challenge 14 – Pythagorean triplets
       15. Coding challenge 15 – Scheduling one elevator
    4. Summary
26. Section 4: Bonus – Concurrency and Functional Programming
27. Chapter 16: Concurrency
    1. Technical Requirements
    2. Java concurrency (multithreading) in a nutshell
    3. Questions and coding challenges
       1. Coding challenge 1 – Thread life cycle states
       2. Coding challenge 2 – Deadlocks
       3. Coding challenge 3 – Race conditions
       4. Coding challenge 5 – Executor and ExecutorService
       5. Coding challenge 7 – Starvation
       6. Coding challenge 10 – Thread versus Runnable
       7. Coding challenge 12 – wait() versus sleep()
       8. Coding challenge 14 – ThreadLocal
       9. Coding challenge 15 – submit() versus execute()
       10. Coding challenge 16 – interrupted() and isInterrupted()
       11. Coding challenge 18 – sharing data between threads
       12. Coding challenge 20 – Producer-Consumer
       13. Producer-Consumer via wait() and notify()
28. Chapter 17: Functional-Style Programming
    1. Java functional-style programming in a nutshell
       1. Key concepts of functional-style programming
    2. Questions and coding challenges
       1. Coding challenge 1 – Lambda parts
       2. Coding challenge 2 – Functional interface
       3. Coding challenge 3 – Collections versus streams
       4. Coding challenge 4 – The map() function
       5. Coding challenge 5 – The flatMap() function
       6. Coding challenge 6 – map() versus flatMap()
       7. Coding challenge 7 – The filter() function
       8. Coding challenge 8 – Intermediate versus terminal operations
       9. Coding challenge 9 – The peek() function
       10. Coding challenge 10 – Lazy streams
       11. Coding challenge 11 – Functional interfaces versus regular interfaces
       12. Coding challenge 12 – Supplier versus Consumer
       13. Coding challenge 13 – Predicates
       14. Coding challenge 14 – findFirst() versus findAny()
       15. Coding challenge 15 – Converting arrays to streams
       16. Coding challenge 16 – Parallel streams
       17. Coding challenge 17 – The method reference
       18. Coding challenge 18 – The default method
       19. Coding challenge 19 – Iterator versus Spliterator
       20. Coding challenge 20 – Optional
       21. Coding challenge 21 – String::valueOf
    3. Summary
29. Chapter 18: Unit Testing
    1. Technical Requirements
    2. Unit testing in a nutshell
    3. Questions and coding challenges
       1. Coding challenge 1 – AAA
       2. Coding challenge 2 – FIRST
       3. Coding challenge 3 – Test fixtures
       4. Coding challenge 4 – Exception testing
       5. Coding challenge 5 – Developer or tester
       6. Coding challenge 6 – JUnit extensions
       7. Coding challenge 7 – @Before* and @After* annotations
       8. Coding challenge 8 – Mocking and stubbing
       9. Coding challenge 9 – Test suite
       10. Coding challenge 10 – Ignoring test methods
       11. Coding challenge 11 – Assumptions
       12. Coding challenge 12 – @Rule
       13. Coding challenge 13 – Method test return type
       14. Coding challenge 14 – Dynamic tests
       15. Coding challenge 15 – Nested tests
    4. Summary
30. Chapter 19: System Scalability
    1. Scalability in a nutshell
    2. Questions and coding challenges
       1. Coding challenge 1 – Scaling types
       2. Coding challenge 2 – High availability
       3. Coding challenge 3 – Low latency
       4. Coding challenge 4 – Clustering
       5. Coding challenge 5 – Latency, bandwidth, and throughput
       6. Coding challenge 6 – Load balancing
       7. Coding challenge 7 – Sticky session
       8. Coding challenge 8 – Sharding
       9. Coding challenge 9 – Shared-nothing architecture
       10. Coding challenge 10 – Failover
       11. Coding challenge 11 – Session replication
       12. Coding challenge 12 – The CAP theorem
       13. Coding challenge 13 – Social networks
    3. Practicing is the key to success
       1. Designing bitly, TinyURL, and goo.gl (a service for shorting URLs)
       2. Designing Netflix, Twitch, and YouTube (a global video streaming service)
       3. Designing WhatsApp and Facebook Messenger (a global chat service)
       4. Designing Reddit, HackerNews, Quora, and Voat (a message board service and social network)
       5. Designing Google Drive, Google Photos, and Dropbox (a global file storage and sharing service)
       6. Designing Twitter, Facebook, and Instagram (an extremely large social media service)
       7. Designing Lyft, Uber, and RideAustin (a ride-sharing service)
       8. Designing a type-ahead and web crawler (a search engine related service)
       9. Designing an API rate limiter (for example, GitHub or Firebase)
       10. Designing nearby places/friends and Yelp (a proximity server)
    4. Summary
31. Other Books You May Enjoy
    1. Leave a review - let other readers know what you think