Cracking the Coding Interview: 150 Programming Interview Questions and Solutions

The book “Cracking the Coding Interview” is a comprehensive guidebook designed to help individuals prepare for technical interviews at top-tier technology companies such as Google, Microsoft, and Facebook. The book covers a wide range of topics, including data structures, algorithms, system design, and more.

Each chapter includes a series of coding problems and detailed explanations of how to solve them. The book also includes tips and tricks for approaching coding problems, as well as guidance on how to optimize code for performance.

Throughout the book, the author emphasizes the importance of practicing coding problems regularly and provides resources for additional practice. Additionally, the book includes real-life interview questions from top technology companies and provides detailed solutions to each question.

What is covered in Cracking the Coding Interview?

• 150 Programming Interview Questions and Solutions: From binary trees to binary search, this list of 150 questions includes the most common and most useful questions in data structures, algorithms, and knowledge based questions.
• Ten Mistakes Candidates Make And How to Avoid Them: Don’t lose your dream job by making these common mistakes.  Learn what many candidates do wrong, and how to avoid these issues.
• Steps to Prepare for Behavioral and Technical Questions: Stop meandering through an endless set of questions, while missing some of the most important preparation and programming techniques.  Follow these steps to more thoroughly prepare in less time.
• Interview War Stories: A View from the Interviewer’s Side: Humorous but instructive stories from our interviewers show you how some candidates really flopped on the most important question – and how you can avoid doing the same.

Overall, “Cracking the Coding Interview” is an essential resource for anyone preparing for technical interviews in the technology industry. The book provides a comprehensive overview of technical concepts and coding problems, as well as practical advice for preparing for and acing the interview process.

A sample interview question from the book

Question:

Given a string s and an array of smaller strings T, design a method to search s for each small string in T.

One approach to solve this problem is to use a Trie data structure. A Trie is a tree-like data structure used to store a dynamic set of strings. Each node in the Trie represents a single character in a string. We can start by constructing a Trie for the larger string s.

Then, for each string in the array T, we can traverse the Trie to check if it exists in s. If it does, we add it to our results.

Here is some sample Java code that implements this approach:

class TrieNode {
    boolean isEndOfWord;
    Map<Character, TrieNode> children;

    public TrieNode() {
        this.isEndOfWord = false;
        this.children = new HashMap<>();
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        this.root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = this.root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = this.root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!node.children.containsKey(c)) {
                return false;
            }
            node = node.children.get(c);
        }
        return node.isEndOfWord;
    }
}

public List<String> search(String s, String[] T) {
    Trie trie = new Trie();
    for (String str : T) {
        trie.insert(str);
    }

    List<String> results = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
        TrieNode node = trie.root;
        for (int j = i; j < s.length(); j++) {
            char c = s.charAt(j);
            if (!node.children.containsKey(c)) {
                break;
            }
            node = node.children.get(c);
            if (node.isEndOfWord) {
                results.add(s.substring(i, j + 1));
            }
        }
    }
    return results;
}

In this code, the Trie class represents a Trie data structure with an insert method to insert words and a search method to search for words.

The search method takes the larger string s and the array of smaller strings T as input, and returns a list of strings that exist in s.

The implementation uses two nested loops to traverse the Trie and search for each string in T in s. The outer loop iterates over the characters in s, and the inner loop traverses the Trie to check if the substring from i to j exists in s.

Overall, this approach has a time complexity of O(n * k), where n is the length of s and k is the total length of strings in T. This solution is optimal, as we must examine each character in s and each string in T at least once to find all occurrences of the strings in T in s.

User Reviews about Cracking the Coding Interview?

Another user writes a review from a student’s perspective and explains how this book helped to secure a job.

This book is great for computer science students or for anyone in a similar situation looking for a graduate job.
I’ve used it to help me in securing jobs for my placement module as part of my degree (penultimate year) .
It covers everything you would need to learn to prepare you for a serious interview with a large organisation such Google, Microsoft, IBM and Oracle etc…
I’ve read it all and seen most of the examples come up in real interviews. Its very useful, I recommend reading it if you are serious in securing a role within a large software based organisation.
Not only does it help with interviews but it will help you within university itself, considering you are a student. It covers various algorithms that most students will cover within university.

Zel – Amazon User

About the Author

Gayle Laakmann McDowell is the founder and CEO of CareerCup and the author of Cracking the PM Interview and Cracking the Tech Career.

Her background is in software development. She has worked as a software engineer at Google, Microsoft, and Apple. At Google, she interviewed hundreds of software engineers and evaluated thousands of hiring packets on the hiring committee. She holds a B.S.E. and M.S.E. in computer science from the University of Pennsylvania and an MBA from the Wharton School.

Cracking the Coding Interview: 150 Programming Interview Questions and Solutions