Java Interview Challenger (Rafael Chinelato del Nero) (Z Library)

Java Interview Challenger Ace Java Interviews by Mastering Fundamentals of Data Structures and Algorithms Rafael Chinelato del Nero This book is for sale at http://leanpub.com/java_interview_challenger This version was published on 2023-09-21 This is a Leanpub book. Leanpub empowers authors and publishers with the Lean Publishing process. Lean Publishing is the act of publishing an in-progress ebook using lightweight tools and many iterations to get reader feedback, pivot until you have the right book and build traction once you do. © 2023 Rafael Chinelato del Nero

Contents Java Interview Process . . . . . . . . . . . . . . . . . . . . . 1 Interview Mindset . . . . . . . . . . . . . . . . . . . . . . . 1 CV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Market Yourself . . . . . . . . . . . . . . . . . . . . . . . . 2 Interview Modalities . . . . . . . . . . . . . . . . . . . . . 6 Take Home Project . . . . . . . . . . . . . . . . . . . . . . 7 Code Quality . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Code Design . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Algorithms Interview . . . . . . . . . . . . . . . . . . . . . 9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Memory Allocation . . . . . . . . . . . . . . . . . . . . . . . 13 Data in Binary Number . . . . . . . . . . . . . . . . . . . . 13 Contiguous Memory Slots Allocation . . . . . . . . . . . . 14 Array Allocation . . . . . . . . . . . . . . . . . . . . . . . 15 Static Memory Allocation . . . . . . . . . . . . . . . . . . 17 Dynamic Memory Allocation . . . . . . . . . . . . . . . . 17 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Big O Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Asymptotic Notations . . . . . . . . . . . . . . . . . . . . . 19 Big O Notation in Practice . . . . . . . . . . . . . . . . . . 20 Constant – O(1) . . . . . . . . . . . . . . . . . . . . . . . . 20 Accessing an Array by Index . . . . . . . . . . . . . . . . 22 Logarithmic – O(log n) . . . . . . . . . . . . . . . . . . . . 22 Linear – O(n) . . . . . . . . . . . . . . . . . . . . . . . . . 25

CONTENTS Two Inputs – O(m + n) . . . . . . . . . . . . . . . . . . . . 26 Log-linear – O(n log n) . . . . . . . . . . . . . . . . . . . . 27 Quadratic – O(n²) . . . . . . . . . . . . . . . . . . . . . . . 28 Cubic – O(n ^ 3) . . . . . . . . . . . . . . . . . . . . . . . . 29 Exponential – O(c ^ n) . . . . . . . . . . . . . . . . . . . . 30 Brute-force Password Break . . . . . . . . . . . . . . . . . 31 Factorial O(n!) . . . . . . . . . . . . . . . . . . . . . . . . . 31 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Array Memory Allocation . . . . . . . . . . . . . . . . . . 35 Static Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Insert an Element in the Middle of the Array . . . . . . . 37 Dynamic Arrays . . . . . . . . . . . . . . . . . . . . . . . . 38 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Get a character from a String . . . . . . . . . . . . . . . . 43 Copy a String . . . . . . . . . . . . . . . . . . . . . . . . . 44 String Encodings What to Use? . . . . . . . . . . . . . . . 47 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Hashtable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 What is a Hash Function? . . . . . . . . . . . . . . . . . . 51 Hash function Collision . . . . . . . . . . . . . . . . . . . 52 Hash collision in practice with Java . . . . . . . . . . . . . 54 Optimizing Hash Collision in Java . . . . . . . . . . . . . 57 Optimizing Hash Collision in Java . . . . . . . . . . . . . 60 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Singly Linked List Structure . . . . . . . . . . . . . . . . . 64 Add Elements to Linked List . . . . . . . . . . . . . . . . . 66 Search Element from Linked List . . . . . . . . . . . . . . 68 Inserting Element in the middle of a Linked List . . . . . 70 Doubly Linked List . . . . . . . . . . . . . . . . . . . . . . 71

CONTENTS Circular Linked List . . . . . . . . . . . . . . . . . . . . . . 74 Pros from Linked List . . . . . . . . . . . . . . . . . . . . . 75 Cons from Linked List . . . . . . . . . . . . . . . . . . . . 75 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Inserting and Removing Elements from a Stack with Java 77 Stack inherits Vector . . . . . . . . . . . . . . . . . . . . . 79 Using Stack with Deque and ArrayDeque . . . . . . . . . 80 Time Complexity from Stack . . . . . . . . . . . . . . . . 82 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 What is Queue? . . . . . . . . . . . . . . . . . . . . . . . . 85 Inserting Elements at the Start and the End of the Queue 88 Deleting Elements at the Start and End of the Queue . . . 89 Big(O) Notation – Time Complexity of a Queue . . . . . 90 Delete the first element of the queue . . . . . . . . . . . . 92 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Undirected Graph . . . . . . . . . . . . . . . . . . . . . . . 98 Directed Graph . . . . . . . . . . . . . . . . . . . . . . . . 99 Acyclic and Cyclic Graph . . . . . . . . . . . . . . . . . . 101 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Ternary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . 109 K-ary tree . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Perfect Binary Tree . . . . . . . . . . . . . . . . . . . . . . 111 Complete Binary Tree . . . . . . . . . . . . . . . . . . . . . 111 Full Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . 112 Balanced Binary Tree . . . . . . . . . . . . . . . . . . . . . 113 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

CONTENTS Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Seeing LIFO/FILO in practice . . . . . . . . . . . . . . . . 120 Recursion Tree with Fibonacci . . . . . . . . . . . . . . . . 122 Big(O) Notation for Recursive Fibonacci . . . . . . . . . . 124 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 Logarithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Logarithm Time Complexity in Binary Search . . . . . . 127 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Optimized Bubble Sort . . . . . . . . . . . . . . . . . . . . 134 Big (O) Notation Complexity . . . . . . . . . . . . . . . . 135 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 Big(O) Notation . . . . . . . . . . . . . . . . . . . . . . . . 140 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 Selection Sort By Comparing Element Lowest Value . . . 145 Big (O) Notation Complexity . . . . . . . . . . . . . . . . 146 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 Choosing the pivot with the Quicksort Algorithm . . . . 148 Creating Partitions with the Quicksort Algorithm . . . . 148 Creating Partition with Left and Right Pointers . . . . . . 151 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Merge Sort Code with Java . . . . . . . . . . . . . . . . . . 156 When to Use Merge Sort? . . . . . . . . . . . . . . . . . . 158 When to NOT Use Merge Sort? . . . . . . . . . . . . . . . 159 Pros and Cons of Merge Sort . . . . . . . . . . . . . . . . . 160 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

Depth-first-search . . . . . . . . . . . . . . . . . . . . . . . . 162 Preorder Traversal . . . . . . . . . . . . . . . . . . . . . . . 165 Recursive Preorder Traversal without Lambda . . . . . . 165 Recursive Preorder Traversal with Lambda . . . . . . . . 166 Preorder with Looping . . . . . . . . . . . . . . . . . . . . 167 Postorder Traversal . . . . . . . . . . . . . . . . . . . . . . 168 Recursive Postorder traversal without Lambdas . . . . . . 168 Recursive Postorder traversal with Lambda . . . . . . . . 169 Postorder traversal with looping . . . . . . . . . . . . . . 169 Inorder Traversal . . . . . . . . . . . . . . . . . . . . . . . 171 Recursive In-order Traversal . . . . . . . . . . . . . . . . . 171 In-order Traversal with Looping . . . . . . . . . . . . . . . 173 Big (O) Notation for Depth First Search . . . . . . . . . . 174 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . . 176 Breadth-First Search with a Tree . . . . . . . . . . . . . . 177 Breadth-First Search Traversal with Graph . . . . . . . . 180 Breadth-First Search Big(O) Notation . . . . . . . . . . . . 183 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 Next Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 Fundamentals are the Key . . . . . . . . . . . . . . . . . . 185 Be Risk Taker . . . . . . . . . . . . . . . . . . . . . . . . . 186 Don’t Focus Only On Technical Skills . . . . . . . . . . . 186 Interview Mindset . . . . . . . . . . . . . . . . . . . . . . . 186 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

Java Interview Process Interviews are difficult and many times tricky, and if we don’t know what the rules are to pass in an interview, we are very likely to fail. One important point to remember when doing interviews is that they don’t necessarily test your skills as a software engineer. The interviews have their gaps, and they could be better. For example, if it’s been a while since we don’t practice algorithms and need to know some data structures, we will likely fail the interview. Therefore, understanding the rules of the game is very important. Otherwise, we won’t pass on those interviews. Being rejected inmany interviews and feeling frustrated is a normal feeling. I’ve been rejected in many interviews and felt frustrated, but we need to remember all the time that interviews will not define how good we are as software engineers. It will test some skills, but the day-to-day work is completely different. That’s why I created this chapter so you can understand the rules of the interview game so you can pass on those interviews. Interview Mindset Don’t be intimidated by the amount of technologies you see in a job spec because no one really knows all of those technologies in depth. Instead, knowing what those technologies do is usually enough. Also, see failing in an interview as a necessary step for your growth. Failure is just a stepping stone to bring you success. The crucial point is to learn why we failed, improve and try again.

Java Interview Process 2 The more we do interviews, the better we get at them. Keep that in mind and never stop learning to pass in the interview. The good news is that after reading this book you will have a strong foundation to solve any kind of algorithm and a broad understanding of systems design. You will also have some insights to leverage your career! CV Your CV has to have relevant information regarding what the market is asking for. Suppose you put in your CV that you know Struts or any other obsolete technology. That won’t matter. That’s why you must align your CV with the market’s requirements. That doesn’t mean that you must lie on your CV. You need instead to be honest because they will ask you about the concepts you included in your CV during the interview. They might disqualify you immediately if you don’t know the technology because the interviewer will notice that. Make sure to put the biggest highlights you had in your job experience. On the top of your CV, include how many years of experience you have and the results you got for previous companies. Try to use numbers. For example, if you refactored lots of code from a previous company, you can state on your CV the following. • Increased developer’s productivity by 25% by Refactoring code and creating generic components. If you think about your previous experiences, you will have plenty of ideas about the results you brought.

Java Interview Process 3 Market Yourself Your CV is a way to market yourself, but an even stronger way to market yourself is to share your knowledge. You build trust with people who never met you by sharing your knowledge. You can also combine your knowledge sharing with your CV. You can include links from your blog, Youtube channel, or talks you gave. Also, you can skip interviews entirely if you arewell known to solve a specific problem that companies need very much. If a person needs the problem you solve to be solved, they will ask you to join their company, and they will ask you how much you want to solve this problem. Having a blog Having a blog is a great investment in yourself and your career. That’s because you will be improving your communications skills and will be filling out the knowledge gaps you have. The ultimate way to learn anything is by sharing what you know. If you decide to create a blog, make sure you are consistent. You will also need to determine a focus. Meaning what problem you will solve that will make you stand out for companies. Let’s see some problems: • Performance • Bugs • Security • Data • Cloud Resilience You can also share your knowledge on something you are learning. Let’s suppose you are learning AWS concepts; you can share this

Java Interview Process 4 knowledge since that will be the most powerful way for you to really master this content. Decide how often you will post a new article. You can post an article per week, bi-weekly, or monthly. Once you decide on it, it’s crucial to stick to it. To stick to it, create a list of 20 article titles, and you will have articles for almost half a year if you decide to develop weekly articles. You can get started creating articles on: • https://dev.to • https://medium.com • https://www.linkedin.com/1 Once you have some content, I recommend creating your own WordPress blog with the following service: • https://www.bluehost.com Youtube Channel If you prefer videos, create your Youtube channel and share what you know. Having a focus on a problem that companies face is also powerful because then the people who see your video and understand you can help then you will probably be hired without going through several interview steps. Giving Talks You have the option of also giving talks. Giving talks is a great way for you to market yourself and get visibility. When you give a talk, 1https://www.linkedin.com

Java Interview Process 5 even if you are not an expert on the subject, you will be perceived as an expert. If you want to start giving talks, start small. Give a talk to a friend of yours, give a talk online, and then expand gradually. Also, get involved in Java user groups from your city and help them in some way. Gain influence and trust, and once you have something to present, ask them to do a lighting talk of 5 or 15 minutes. That will be a powerful way for you to build up your confidence, share your knowledge, and gain exposure. Open Source Projects Contributing to open-source projects is a powerful way to market yourself and refine your software development skills. By doing so, you will massively boost your CV and might even get hired by big companies. For example, Red Hat (IBM) hires developers according to their contributions to their open-source projects. Getting started on the open-source project world is hard, but you can start small. Start by changing something very small, maybe a typo in the documentation, fixing some unit tests, or doing something that nobody else wants to do. Then, your chances of having a pull request merges are much higher. The other benefit of starting with documentation is that you will have a better understanding of the project. The more small pull requests you get approved and merged, the more trust you gain in that project. Then, you are far more likely to create feature pull requests and make more important contributions. You can take a look at the following open-source projects: • https://github.com/eclipse/jnosql

Java Interview Process 6 • https://github.com/quarkusio/quarkus • https://github.com/elastic/elasticsearch • https://github.com/square/okhttp • https://github.com/google/guava • https://github.com/spring-projects/spring-boot • https://github.com/jenkinsci/jenkins • https://github.com/google/guice • https://github.com/mockito/mockito Create your pull request and get your software engineering skills to a whole new level! Interview Modalities I’ve done many interviews throughout my career, and they were very different from each other. When I was starting my career, knowing Object-Oriented programming and basic sort algorithms was enough Obviously, as my career progressed, the interviews for higher levels were more difficult. The interview for an intermediate developer some time ago was enough to know Java EE, now called Jakarta EE. Nowadays, the market has gone almost entirely to the cloud, and nearly all companies are asking for Microservices concepts. Therefore, it’s crucial to know what a Microservice is and explain that during the interview. We also need to know why tests are important because that will also be asked. Let’s see now each interview style inmore detail. Before we explore the interview styles, every interview will have the following: • Screening call: They will ask questions about your past experiences to check if you are a good candidate for the

Java Interview Process 7 opportunity. If your experience matches what they are looking for, you will pass this one. • Behavioral Interview: Checks if you behave in a suitable way that aligns with the company’s values. They will usually see if you complain about your previous company, if you work well in a team if you are friendly, and if you communicate clearly. • Culture Fit: In this interview, it’s important for you to check what are the company values, then you show those values in this interview. In short, you need to be friendly, communicate clearly, and show that you want to bring value to the company with your work. Take Home Project Sometimes companies will opt to give you a take-home project. They will access your skills to create a robust and performant system using fundamental concepts of a web application usually. In one interview I did, they wanted me to create a manual job application with a Thread pool and a queue. Sometimes, they will ask you to create something even if there are already several frameworks that do the job. Other takeaway tests will ask you to create a normal application with the problem they are presenting, and your job is to create the project in a way that is robust, performant, and has a good code design. They are expecting an application that is production-ready, which means well tested, with logs, containerized ready to be deployed in the cloud, well documented, and with different profiles to deploy in multiple environments such as dev, stage, qa, and production. Obviously, they are expecting you to solve the problem they presented in an optimized way.

Java Interview Process 8 Code Quality It’s crucial to know how to create good quality code, not reinvent the wheel with technologies, and understand what you do with software development. One of the most important principles is to create cohesive code (code that does ONE thing very well) and code with low coupling (code that doesn’t have strong dependency). Another crucial point is correctly naming projects, packages, classes, methods, and variables. Avoid acronyms and use the name conventions for the Java language. Mastering paradigms like Object-Oriented Programming (OOP) and Functional Programming will help develop good-quality code. SOLID principles are powerful in guiding you to create high-quality code. Therefore, it’s crucial to learn those concepts well. The last component to help you create high-quality code is to master the most essential design patterns. We can’t overuse design patterns. We should use them only in suitable situations instead. Otherwise, the code will only get more complicated. Code Design We need to have a basic understanding of code design to develop systems and also to pass on interviews. :) Sometimes, there will be interviews that will ask you how you design your code and how many layers you use. In Java, it’s common to have the controller layer (the one that has the API endpoints), then the service that has business requirements implementations, the repository that interacts with the database, the data objects, and the database entities objects.

Java Interview Process 9 Design patterns and Domain-Driven Design will also help you to create a good code design. Knowing the frameworks you are working with and using their features also helps you create good code. For example, if you are using Spring, it’s better to stick with Spring nomenclatures to be consistent with the framework. Java Application Interview Style In this interview, usually two senior developers and maybe one manager will ask the following questions: • Java features (Concurrency, Collection, Exception, OOP) • Tests • Microservices concepts • SQL • Database Model To learn the Java core concepts, get the Java Challengers book and stay sharp for the Java interview: https: //leanpub.com/javachallengers They will also ask about your previous experiences, so only tell the experience from the three last companies you worked for. Otherwise, it’s too much. Also, highlight your accomplishments when you are talking about your experiences. They also might ask you about your previous experiences and model the system you were working with. Algorithms Interview This interview is nowadays very popular. A lot of companies (small, large companies) are following the same process for inter- views.

Java Interview Process 10 Similarly to the Java application interview, there will usually be two senior developers interviewing you for a code challenge. In the algorithm interview, you will be accessed the following: • Your ability to understand the problem • Your ability to communicate your thought process • You must communicate your thought process while you solve the problem • Your ability to communicate clearly • Your code quality • Data Structures • Big O Notation • Algorithms techniques such as recursion or memoization Systems Design Interview In the Systems Design interview, you will be assessed in the ability to design a system according to the requirements. This interview is tricky if you don’t know the rules of the game. In this interview, they will usually give you a vague problem, such as “Design Instagram.” Then you must ask questions about where you can reasonably design a system in 45 minutes. Don’t ever start designing the system without asking questions. You must assume things during this interview. So if they tell you to design Instagram, you say, “I assume you just want the basic features, such as the possibility to post photos and stories, right?”. They will probably say yes, then you start it. Make questions to the interviewer directing the system to be simple; the simpler you can make the system, the better for you. They might ask you to design any system. They might ask you, for example, to design an internal system they have. Then you will

Java Interview Process 11 have to read and understand their problem and then design the system explaining why of your choices. In the Systems Design interview, it’s crucial that you have some knowledge of how to create a system. Summary Interviews are annoying, but it’s necessary to know what are the rules of those interviews. Otherwise, we will fail no matter how good of software engineers we are. A good motivation, though, is to think that by getting good with data structures, algorithms, and Systems Design, we will become better software engineers. Therefore, let’s see what were the main points of this article: • Your CVmust be polished, but it is not the only way tomarket yourself. • Sharing your knowledge is a powerful way to market your- self. • You can use links from the knowledge you shared on your CV. • You can create your blog to market yourself. • Decide the focus you want to explore to share your knowl- edge. • Decide how often you will create an article. Weekly, bi- weekly, monthly. • Share your knowledge on blogs, Youtube, or giving talks. • Contribute with open source projects, create a PR for a documentation typo, and anything else that is small. • There are different interview modalities. • Screening call only check if your experience is enough.

Java Interview Process 12 • Behavioral interviews focus on how friendly you are, how good you communicate, and how well you work in a team. • Culture fit interview evaluates if your values are similar to the company’s values. • Take home project. They will test your ability to create a production-ready system. • Code quality will see how well you can use the best program- ming practices to make your code simple. • Code design will check how you divide your code into layers. In Java, it’s usually Controller, Service, Repository, Entity data, and transfer data. • Java Application interview will test your knowledge in the Java language. A few concepts about Microservices and databases as well. • Algorithms, you will solve a code challenge, and you need to know about data structures, Big O notation, and how to communicate your thinking process. • Systems Design, you will have a vague problem such as “design Youtube” and you will have to ask questions assum- ing that they want only the main features. Then you use your expertise to design the system, considering what the requirements are.

Memory Allocation Every time we create a variable, invoke a method, or create an instance memory allocation will happen in Java and any other programming language. Data is stored in the form of bits, each memory slot can hold 1 byte which is the same as 8 bits. Let’s see the chart of how many bits each variable from Java uses: boolean 1 bit false, true byte 1 byte -128 to 127 short 2 bytes 0 (‘\u0000’) to 65535 (‘\uffff’) char 2 bytes -32768 to 32767 int 4 bytes -2147483648 to 2147483647 long 8 bytes 1-9223372036854775808 to 9223372036854775807 float 4 bytes 1.40239846e-45f to 3.40282347e+38f double 8 bytes 4.94065645841246544e-324 to 1.79769313486231570e+308 Type Data Size Data Value Range Data in Binary Number Computers only understand binary numbers, therefore, every data stored in memory will be transformed into a binary number. A binary number is a number with a base 2 which means that the data must be represented by only 0 or 1. The int number for example has 4 bytes which translates to 32 bits.