book

The Complete Coding Interview Guide in Java

by Anghel Leonard

August 2020

Intermediate to advanced

788 pages

15h

English

Packt Publishing

Read now

Unlock full access

Why subscribe?ContributorsAbout the authorAbout the reviewerPackt is searching for authors like you
Who this book is forWhat this book coversTo get the most out of this bookDownload the example code filesDownload the color imagesConventions usedGet in touchReviews
The novice interview roadmapKnow yourselfKnow the marketIt’s all about getting the right experienceStart somethingIt’s time to shine onlineTime to write your resumeWhat resume screeners are looking forHow long the resume should beHow to list your employment historyList the most relevant projects (top five)Nominate your technical skillsLinkedIn resumeThe job application processFinding companies that are hiringSubmitting the resumeI got an interview! Now what?The phone screening stageGoing to in-person interviewsAvoiding common mistakesSummary
Interviews at GoogleInterviews at AmazonInterviews at MicrosoftInterviews at FacebookInterviews at CrossoverSummary
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
Accepting or rejecting an offerFailure is an optionA company can reject you for a lot of reasonsGetting feedback after the interviewObjectively identifying and eliminating the mismatchesDon’t form an obsession for a companyDon’t lose confidence in yourself – sometimes, they don’t deserve you!Summary
Technical quizCoding challengeThe problems specific to coding challenges are meant to be difficultTackling a coding challenge problemSummary
Technical requirementsUnderstanding OOP conceptsWhat is an object?What is a class?What is abstraction?What is encapsulation?What is inheritance?What is polymorphism?What is association?What is aggregation?What is composition?Getting to know the SOLID principlesWhat is S?What is L?What is I?What is D?Popular questions pertaining to OOP, SOLID, and GOF design patternsWhat 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 challengesExample 1: JukeboxExample 2: Vending machineExample 3: Deck of cardsExample 4: Parking lotExample 5: Online reader systemExample 6: Hash table Example 7: File systemExample 8: TupleExample 9: Cinema with a movie ticket booking systemSummary

AnalogyBig O complexity timeThe best case, worst case, and expected caseBig O examples Example 1 – O(1)Example 2 – O(n), linear time algorithmsExample 3 – O(n), dropping the constantsExample 6 – different steps are summed or multipliedExample 7 – log n runtimesExample 9 – in-order traversal of a binary treeExample 10 – n may varyExample 11 – memoizationExample 13 – identifying O(1) loopsExample 14 – looping half of the arrayExample 15 – reducing Big O expressionsExample 16 – looping with O(log n)Example 17 – string comparisonExample 18 – factorial Big OExample 19 – using n notation with cautionExample 21 – the number of iteration counts in Big OExample 22 – digitsExample 23 – sortingKey hints to look for in an interviewSummary
Technical requirementsRecursion in a nutshellRecognizing a recursive problemDynamic Programming in a nutshellMemoization (or Top-Down Dynamic Programming)Tabulation (or Bottom-Up Dynamic Programming)Coding challengesCoding challenge 1 – Robot grid (I)Coding challenge 3 – JosephusCoding challenge 6 – Five towersCoding challenge 8 – The falling ballCoding challenge 9 – The highest colored towerCoding challenge 10 – String permutationsCoding challenge 11 – Knight tourCoding challenge 12 – Curly bracesCoding challenge 13 – StaircaseCoding challenge 14 – Subset sumCoding challenge 15 – Word break (this is a famous Google problem)
Technical requirementsBit manipulation in a nutshellObtaining the binary representation of a Java integerBitwise operatorsBit shift operatorsTips and tricksCoding challengesCoding challenge 1 – Getting the bit valueCoding challenge 2 – Setting the bit valueCoding challenge 3 – Clearing bitsCoding challenge 4 – Summing binaries on paperCoding challenge 5 – Summing binaries in codeCoding challenge 6 – Multiplying binaries on paperCoding challenge 7 – Multiplying binaries in codeCoding challenge 8 – Subtracting binaries on paperCoding challenge 9 – Subtracting binaries in codeCoding challenge 10 – Dividing binaries on paperCoding challenge 11 – Dividing binaries in codeCoding challenge 12 – Replacing bitsCoding challenge 13 – Longest sequence of 1Coding challenge 14 – Next and previous numbersCoding challenge 15 – ConversionCoding challenge 16 – Maximizing expressionsCoding challenge 17 – Swapping odd and even bitsCoding challenge 18 – Rotating bitsCoding challenge 19 – Calculating numbersCoding challenge 20 – Unique elementsCoding challenge 21 – Finding duplicatesCoding challenge 22 – Two non-repeating elementsCoding challenge 23 – Power set of a setCoding challenge 24 – Finding the position of the only set bitCoding challenge 25 – Converting a float into binary and vice versaSummary
Technical requirementsArrays and strings in a nutshellCoding challengesCoding challenge 1 – Unique characters (1)Coding challenge 2 – Unique characters (2)Coding challenge 3 – Encoding stringsCoding challenge 4 – One edit awayCoding challenge 5 – Shrinking a stringCoding challenge 6 – Extracting integersCoding challenge 7 – Extracting the code points of surrogate pairsCoding challenge 8 – Is rotationCoding challenge 9 – Rotating a matrix by 90 degreesCoding challenge 10 – Matrix containing zerosCoding challenge 11 – Implementing three stacks with one arrayCoding challenge 12 – PairsCoding challenge 13 – Merging sorted arraysCoding challenge 14 – MedianCoding challenge 15 – Sub-matrix of oneCoding challenge 16 – Container with the most waterCoding challenge 17 – Searching in a circularly sorted arrayCoding challenge 18 – Merging intervalsCoding challenge 19 – Petrol bunks circular tourCoding challenge 20 – Trapping rainwaterCoding challenge 21 – Buying and selling stockCoding challenge 22 – Longest sequenceCoding challenge 23 – Counting game scoreCoding challenge 24 – Checking for duplicatesCoding challenge 25 – Longest distinct substringCoding challenge 26 – Replacing elements with ranksCoding challenge 27 – Distinct elements in every sub-arrayCoding challenge 28 – Rotating the array k timesCoding challenge 29 – Distinct absolute values in sorted arraysSummary
Technical requirementsLinked lists in a nutshellMaps in a nutshellCoding challengesCoding challenge 1 – Map put, get, and removeCoding challenge 2 – Map the key set and valuesCoding challenge 3 – Nuts and boltsCoding challenge 4 – Remove duplicatesCoding challenge 5 – Rearranging linked listsCoding challenge 6 – The nth to last nodeCoding challenge 7 – Loop start detectionCoding challenge 8 – PalindromesCoding challenge 9 – Sum two linked listsCoding challenge 10 – Linked lists intersectionCoding challenge 11 – Swap adjacent nodesCoding challenge 12 – Merge two sorted linked listsCoding challenge 13 – Remove the redundant pathCoding challenge 14 – Move the last node to the frontCoding challenge 15 – Reverse a singly linked list in groups of kCoding challenge 16 – Reverse a doubly linked listCoding challenge 17 – LRU cacheSummary
Technical requirementsStacks in a nutshellQueues in a nutshellCoding challengesCoding challenge 1 – Reverse stringCoding challenge 2 – Stack of curly bracesCoding challenge 3 – Stack of platesCoding challenge 4 – Stock spanCoding challenge 5 – Stack minCoding challenge 6 – Queue via stacksCoding challenge 7 – Stack via queuesCoding challenge 8 – Max histogram areaCoding challenge 9 – Smallest numberCoding challenge 10 – IslandsCoding challenge 11 – Shortest pathInfix, postfix, and prefix expressionsSummary
Technical requirementsTrees in a nutshellGeneral treeBinary Search TreeBalanced and unbalanced binary treesComplete binary treeFull binary treePerfect binary treeBinary HeapsGraphs in a nutshellAdjacency matrixAdjacency listGraph traversalCoding challengesCoding challenge 1 – Paths between two nodesCoding challenge 2 – Sorted array to minimal BSTCoding challenge 3 – List per levelCoding challenge 4 – sub-treeCoding challenge 5 – Landing reservation systemCoding challenge 6 – Balanced binary treeCoding challenge 7 – Binary tree is a BSTCoding challenge 8 – Successor nodeCoding challenge 9 – Topological sortCoding challenge 10 – Common ancestorCoding challenge 11 – Chess knightCoding challenge 12 – Printing binary tree cornersCoding challenge 13 – Max path sumCoding challenge 14 – Diagonal traversalCoding challenge 15 – Handling duplicates in BSTsCoding challenge 16 – Isomorphism of binary treesCoding challenge 17 – Binary tree right viewCoding challenge 18 – kth largest elementCoding challenge 19 – Mirror binary treeCoding challenge 20 – Spiral-level order traversal of a binary treeCoding challenge 21 – Nodes at a distance k from leafsCoding challenge 22 – Pair for a given sumCoding challenge 23 – Vertical sums in a binary treeCoding challenge 23 – Converting a max heap into a min heapCoding challenge 24 – Finding out whether a binary tree is symmetricCoding challenge 25 – Connecting n ropes at the minimum costAdvanced topicsSummary
Technical requirementsSorting algorithms Heap SortMerge SortQuick SortBucket SortRadix SortSearching algorithms Coding challengesCoding challenge 1 – Merging two sorted arraysCoding challenge 2 – Grouping anagrams togetherCoding challenge 3 – List of unknown sizeCoding challenge 4 – Merge sorting a linked listCoding challenge 5 – Strings interspersed with empty stringsCoding challenge 6 – Sorting a queue with the help of another queueCoding challenge 7 – Sorting a queue without extra spaceCoding challenge 8 – Sorting a stack with the help of another stackCoding challenge 9 – Sorting a stack in placeCoding challenge 10 – Searching in a full sorted matrixCoding challenge 11 – Searching in a sorted matrixCoding challenge 12 – First position of first oneCoding challenge 13 – Maximum difference between two elementsCoding challenge 14 – Stream rankingCoding challenge 15 – Peaks and valleysCoding challenge 16 – Nearest left smaller numberCoding challenge 17 – Word searchCoding challenge 18 – Sorting an array based on another arraySummary
Technical requirementsTips and suggestionsCoding challengesCoding challenge 1 – FizzBuzzCoding challenge 2 – Roman numeralsCoding challenge 3 – Visiting and toggling 100 doorsCoding challenge 4 – 8 teamsCoding challenge 5 – Finding the kth number with the prime factors 3, 5, and 7Coding challenge 6 – Count decoding a digit's sequenceCoding challenge 7 – ABCDCoding challenge 8 – Rectangles overlappingCoding challenge 9 – Multiplying large numbersCoding challenge 10 – Next greatest number with the same digitsCoding challenge 11 – A number divisible by its digitsCoding challenge 12 – Breaking chocolateCoding challenge 13 – Clock angleCoding challenge 14 – Pythagorean tripletsCoding challenge 15 – Scheduling one elevatorSummary
Technical RequirementsJava concurrency (multithreading) in a nutshellQuestions and coding challengesCoding challenge 1 – Thread life cycle statesCoding challenge 2 – DeadlocksCoding challenge 3 – Race conditionsCoding challenge 5 – Executor and ExecutorServiceCoding challenge 7 – StarvationCoding challenge 10 – Thread versus RunnableCoding challenge 12 – wait() versus sleep()Coding challenge 14 – ThreadLocalCoding challenge 15 – submit() versus execute()Coding challenge 16 – interrupted() and isInterrupted()Coding challenge 18 – sharing data between threadsCoding challenge 20 – Producer-ConsumerProducer-Consumer via wait() and notify()
Java functional-style programming in a nutshellKey concepts of functional-style programmingQuestions and coding challengesCoding challenge 1 – Lambda partsCoding challenge 2 – Functional interfaceCoding challenge 3 – Collections versus streamsCoding challenge 4 – The map() functionCoding challenge 5 – The flatMap() functionCoding challenge 6 – map() versus flatMap()Coding challenge 7 – The filter() functionCoding challenge 8 – Intermediate versus terminal operationsCoding challenge 9 – The peek() functionCoding challenge 10 – Lazy streamsCoding challenge 11 – Functional interfaces versus regular interfacesCoding challenge 12 – Supplier versus ConsumerCoding challenge 13 – PredicatesCoding challenge 14 – findFirst() versus findAny()Coding challenge 15 – Converting arrays to streamsCoding challenge 16 – Parallel streamsCoding challenge 17 – The method referenceCoding challenge 18 – The default methodCoding challenge 19 – Iterator versus SpliteratorCoding challenge 20 – OptionalCoding challenge 21 – String::valueOfSummary
Technical Requirements Unit testing in a nutshellQuestions and coding challengesCoding challenge 1 – AAACoding challenge 2 – FIRSTCoding challenge 3 – Test fixturesCoding challenge 4 – Exception testingCoding challenge 5 – Developer or testerCoding challenge 6 – JUnit extensionsCoding challenge 7 – @Before* and @After* annotationsCoding challenge 8 – Mocking and stubbingCoding challenge 9 – Test suiteCoding challenge 10 – Ignoring test methodsCoding challenge 11 – AssumptionsCoding challenge 12 – @RuleCoding challenge 13 – Method test return typeCoding challenge 14 – Dynamic testsCoding challenge 15 – Nested testsSummary
Scalability in a nutshellQuestions and coding challengesCoding challenge 1 – Scaling typesCoding challenge 2 – High availabilityCoding challenge 3 – Low latencyCoding challenge 4 – ClusteringCoding challenge 5 – Latency, bandwidth, and throughputCoding challenge 6 – Load balancingCoding challenge 7 – Sticky sessionCoding challenge 8 – ShardingCoding challenge 9 – Shared-nothing architectureCoding challenge 10 – FailoverCoding challenge 11 – Session replicationCoding challenge 12 – The CAP theoremCoding challenge 13 – Social networksPracticing is the key to successDesigning 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
Leave a review - let other readers know what you think

Content preview from The Complete Coding Interview Guide in Java

Chapter 8: Recursion and Dynamic Programming

This chapter covers one of the favorite topics of interviewers: Recursion and Dynamic Programming. Both work hand in hand, so you must be able to cover both. Commonly, the interviewer expects to see a plain recursive solution. However, they may ask you to provide some optimization hints or even to code an optimized version of your code. In other words, your interviewer will want to see Dynamic Programming at work.

In this chapter, we will cover the following topics:

Recursion in a nutshell
Dynamic Programming in a nutshell
Coding challenges

By the end of this chapter, you will be able to implement a wide range of recursive algorithms. You'll have a significant number of recursive patterns and approaches ...