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