Cracking the Coding Interview: 189 Programming Questions and Solutions

Category: Programming
Author: Gayle Laakmann McDowell
4.6
All Reddit 123
This Year Reddit 55
This Month Reddit 4

Comments

by monkeyunited   2019-11-17

Cracking the Coding Interview is selling at $26.49, as a tangential reference

I wouldn't expect "proven techniques", just something that once you go through the book, you feel as prepared as you can ever be (whether true or not), then I would feel it's valuable.

by clawedjird   2019-11-17

After reading the title, I really did not expect your post to include "I have a BS in Computer Science." I can understand that you might be discouraged, but you're actually in a really good position. You won't need any specific certifications or experience to get a job (in your position), just some skills and a way to demonstrate them. Choose an accessible sub-field of programming - web development comes to mind (i.e. people without degrees and experience regularly get jobs after self-studying for a year or so, so it's definitely within your capabilities) - and work on developing a basic portfolio.

A good place to start would be any one of the multitudes of free resources online (ex. CodeAcademy or FreeCodeCamp). It shouldn't take you very long to get through an introductory course, and you should be able to start working on some basic projects pretty quickly. Once you have a few relatively simple website/app projects (they don't need to be profoundly complex or reflect your "passion" - whatever that would mean, they just need to demonstrate basic web dev. principles), you can start applying to jobs. Your CS degree is actually worth quite a lot here, as companies will be more comfortable hiring you with gaps in your knowledge than they would someone without your background (because you've already demonstrated the ability to learn advanced programming concepts).

Going to local coding meetups/networking and doing some interview prep (example) will also be helpful, as will reviewing the variety of online coding-oriented job-search resources on reddit and elsewhere. I wouldn't start thinking about moving yet, especially without a job. If there really are no opportunities within commuting distance or better job markets within a few hours drive (i.e. what you could realistically travel to an initial interview), then it might be worth considering relocation - but you don't need to start there.

Whatever else you do, you need to learn to manage your perspective. Your post exudes shame, self-blame, unworthiness, etc., and that's obviously a result of how you view yourself and your situation. You view yourself as a failure (or, at minimum, someone who's "not very successful") and you attribute this to never having been "motivated or focused" and making a "terrible" choice not to do an internship. I don't blame you for feeling this way - in fact, I would expect it. However, the fact that your culturally-derived perspective is predictable doesn't make it reasonable (or, more importantly, helpful). In fact, I think it could be very harmful. I'll try to explain why I think that may be in the theoretical rambling below. I see so many posts like yours, where the OP seemingly feels like they need to apologize for their perceived "failure," essentially belittling themselves, when asking reddit for advice, and it annoys me that our society leads people to feel this way (especially when redditors reinforce it by making unwarranted moral judgments - thankfully I haven't seen that here in this thread). If I'm misconstruing your tone, please forgive my assumption!


To understand what I'm getting at, let's start by observing that the US (of which I'm also a product) has a fairly "religious" culture. Now I'm not referring to a common belief in God/Allah/Yahweh or any other supernatural being. I'm referring to our inordinate reliance on myth in talking about ourselves and or society. An example of this can be found in our long-standing fascination with the Horatio Alger-style, pull-yourself-up-by-your-bootstraps, "rags to riches" narrative. Despite evidence to the contrary, Americans tend to believe (and frequently act accordingly) that social mobility is higher than it actually is (1, 2). Sidenote: I'm not trying to make a political point here, and I don't think the data implies any particular political orientation. The point I'm trying to make is that we don't always reflect on our existence in scientific or rational terms.

Instead, we tend to reduce the world around us into binary shades of black and white while inventing intangible concepts to fill the gap between the two. Some of this is simply pragmatic, as we have a limited capacity to fully discuss the world's infinite complexity within the finite timelines of our lives. It makes our lives simpler and easier to understand (if less accurately). This tendency may also be partially a vestige of past cultures that relied on the supernatural to explain the world around them. Whatever the cause may be, one manifestation of this is belief in the just-world-hypothesis or BJW (I don't mean to imply that this is a uniquely American phenomenon, by the way).

The just world fallacy leads its victims to believe that, essentially, people get what they deserve. Using the above-cited example of American beliefs regarding social mobility, one potential impact of this is that we tend to have a negative view of the poor. In particular, we ascribe negative characteristics onto (ex. laziness, irresponsibility, low intelligence) them as a means of morally justifying their disadvantaged position. It's important to clarify that this occurs independently of (or even in spite of) any demonstrable evidence. Social scientists can provide a variety of carefully researched explanations for the existence of poverty, but their findings have little influence on popular perspectives. Given cultural stereotypes surrounding the poor, perhaps it's not surprising that many Americans believe that there is actually a group of lazy, manipulative people living indefinitely off "welfare" benefits, despite the fact that there isn't even a welfare program which would enable this lifestyle. BJW is also implicated in the surprisingly common practice of rape-victim-blaming, wherein victims of rape are accorded (at least) some of the blame for their victim-hood.

by tatu_huma   2019-11-17

The book Cracking the Coding Interview is pretty good. It has sections for each type of questions: data structure, OOP, testing, etc.

You could also look at free sites like HackerRank or LeetCode which have similar problems.

by CamKen   2019-11-17

Cracking the Coding Interview: https://www.amazon.com/Cracking-Coding-Interview-Programming-Questions/dp/0984782850

by BigRonnieRon   2019-11-17

I remembered the books:

Cracking the Coding Interview, Gayle Laakmann McDowell https://www.amazon.com/Cracking-Coding-Interview-Programming-Questions/dp/0984782850

Coding Interview Questions, Narasimha Karumanchi https://www.amazon.com/Coding-Interview-Questions-Narasimha-Karumanchi/dp/1475293534/

Programming Interviews Exposed: Coding Your Way Through the Interview

Also: https://leetcode.com

by engineering_stork   2019-08-24

Lol, competitive coding is usually overkill for interview prep. Don't get me wrong--if you are good at competitions, you will almost certainly do well on interviews. Coding competitions focus much more on "finding an important insight"--usually beyond anything that you'll have to know for work--and then coding a solution, while interviews focus much more on your ability to hold many different moving parts in your head. Competitions also tend to focus on parsing inputs, which, if you are using a language like C++, is a pain in the ass and can be unnecessarily discouraging if you just starting off.

​

My advice is to check out the CTCI book and to write working code for as many problems as possible.

https://www.amazon.com/Cracking-Coding-Interview-Programming-Questions/dp/0984782850

​

Be able to crank out DFS in your language of choice. Code every day. Try and work on problems that are easier to solve theoretically but that require holding a lot of different components in your head while you write the solution. The bottleneck for most people is writing correct code even after they know the solution--not "solving the problem" with theoretical data structures.

​

Also, know your language well. Spend some time every day typing out the apis for the basic data structures into your lang's toplevel or interpreter.

by [deleted]   2019-08-24

Amazon has it for 30$ and free one day delivery in most cities:

Cracking the Coding Interview: 189 Programming Questions and Solutions https://www.amazon.com/dp/0984782850/ref=cm_sw_r_cp_api_i_3p22CbWQ5G46S

by [deleted]   2019-08-24

If it’s through Hackerrank than just sign up and do a bunch of practice questions. If you want to learn more about DSAs I’d recommend going on YouTube and searching Cracking the Coding Interview (CTCI). The author of that famous CS book has made some quick YouTube tutorials on Trees, graphs, stacks, queues, BFS, DFS, Sorting Algorithms, Big O notation and more. If you have more time, I’d highly recommend buying the book itself, as I give it credit for landing me 3 internships and a job at a FAANG. It’s on sale on amazon right now for 32$:

Cracking the Coding Interview: 189 Programming Questions and Solutions https://www.amazon.com/dp/0984782850/ref=cm_sw_r_cp_api_i_rqKZCbMH1F8CP

by eatstraw   2019-07-21

Here's a really good book by someone who used to conduct coding interviews at Microsoft, Amazon, etc.

Cracking the Coding Interview

Still, it's not likely that you'll see the same exact questions on an actual interview. Just practice a lot and get comfortable with solving problems. That will help you when it's time to code on-the-fly at an interview. Also, it's more important to talk through the solutions. Coming up with an innovative, elegant, or efficient solution with pseudocode is more important than getting the syntax exactly right in a particular programming language.

by Torber-Rade   2019-07-21

I give this advice to everyone on this sub who asks because it’s honestly the best advice ever. Buy this book (30$ rn on amazon):

Cracking the Coding Interview: 189 Programming Questions and Solutions https://www.amazon.ca/dp/0984782850/ref=cm_sw_r_cp_api_i_Ic6QCbQXY71DN

I give credit to the author and this book for landing me all my internships and a job at a FAANG. Read it, do what she says to do in the book, and if you still don’t get an internship, I’ll pay for the book.

by [deleted]   2019-07-21

For DSA I always recommend Cracking the Coding Interview (I think I’ve linked it at least 10 times on this sub... cause it works) it’s on amazon rn for 40$:

Cracking the Coding Interview: 189 Programming Questions and Solutions https://www.amazon.ca/dp/0984782850/ref=cm_sw_r_cp_api_i_QtjXCbCN7EEN4

For Big Data/Github Projects, you want to show you understand the pipeline from start to finish. Your projects should show you can find data, clean and prepare it, preprocess, train, test and then deploy. I’d say 99% of people start with the MNIST data set (people who know MNIST are probably laughing right now reading this). Most people you’ll be interviewing against will likely have an MNIST project on their github, so if you want to outshine them, follow this MNIST tutorial but DON’T put it on your GitHub (or do for now but remove it when you add more projects):

https://www.tensorflow.org/tutorials/keras/basic_classification

After following that tutorial, try to repeat the process but with other datasets. There are millions of free datasets available online, pick ones that are relevant to your hobbies outside of work, so when you interview you can start with “I really love blah blah in my personal time, so I decided to train a neural net to recognize blah blah, and so I found (or even better, created) a dataset for blah”

For example, I love going hiking and often wonder what kinds of birds I’m seeing in the forest, so I found a dataset of bird pictures that were labelled, trained a neural net to recognize them, and hooked it up to an app so I can now point my phone at birds when I’m hiking, and find out what species of bird I’m looking at.

As for the management/marketing thing, I can’t really give you any useful information so I’ll leave that to someone else.

Also, sorry for the formatting, I’m on mobile. Good luck!

by hunter2124025   2019-07-21

I recommend going through the book https://www.amazon.com/Cracking-Coding-Interview-Programming-Questions/dp/0984782850/ref=dp_ob_title_bk. It's got the technical stuff and also has sections on what to expect from a soft skills perspective.

by goodDayM   2019-07-21

There's a popular book I used that helped me get great job offers, and it was written by someone who interviewed many candidates at Google: Cracking the Coding Interview: 189 Programming Questions and Solutions. The questions are general enough that you could write solutions in whatever language you want.

> Is it just a balance between knowing the language, putting it to use and demonstrating the thought process to get there?

Syntax doesn't have to be perfect, but it should be mostly correct. I will say back when I was doing interviews sometimes they would be typing what I'm writing on the whiteboard into a compiler to try and find errors. And they might say "you have an error on line 3, do you see what it is?"

Another important thing is asking a candidate to design the big picture for something - let's say a phone app. That app has to send/receive data from a server, so what OS and webserver software would you use? And that server needs to store data in a database - what database would you use?

For things like that it's just drawings of boxes and arrows with names of existing tools you would use to build a project. (There's usually never one right answer, but some designs are better than others.)

> what do you look for when you hire someone? Impressive githubs?

I think it's great when someone puts a url to their github profile on their resume. I don't "deep-dive" into it, but I glance ahead of an interview to see what kinds of projects they've worked on, and how some of their recent code commits look. I might ask questions about that project in the interview.

> Also, is the market saturated or is it pretty easy to get a job?

Definitely not saturated. I would recommend staying away from the Bay Area and New York though. I considered job offers there myself, and I have friends who work still work there. But the cost of living has reached ridiculous levels there (e.g. a 2-bedroom home even 45 minutes from work can cost $900k or more).

Big companies like Google, Apple, Amazon, others have branches at other cities around the country. Find those smaller tech cities with more reasonable commute times and housing prices.

Check out page 11 of this report for average Software Engineer salaries by city in the US, keep in mind it's 3 years old now (and doesn't include cash/stock bonuses which can be significant): 2016 Tech Salary Report.

by goodDayM   2019-07-21

Best advice I can give is check out this book from a library (or buy): Cracking the Coding Interview: 189 Programming Questions and Solutions. It's written by someone who worked as a software engineer at Google & Microsoft and did interviews.

Doing problems out of that book helped me remember some important things that were actually asked about in interviews. I ended up getting two job offers at the same time which allowed me to tell the other company what my offer was and get them to raise it quite a bit.

by chef098   2019-07-21

A great resource to keep your interview skills sharp is Cracking the Coding Interview: 189 Programming Questions and Solutions https://www.amazon.com/dp/0984782850/ref=cm_sw_r_cp_apa_i_cLXGCbRGMVVAS

by thedeen17   2019-07-21

here u go

by Soreasan   2019-07-21

Master data structures and algorithms and become good with coding puzzles. Apply for jobs at FAANG [Facebook, Amazon, Apple, Netflix, Google] companies or Unicorn companies [Unicorns are companies with a 1 billion dollar valuation or more, companies like LinkedIn, Uber, or AirBNB].

​

Bookmark these resources once you've taken your Data Structures and Algorithms course in college and then begin practicing.

Cracking the Coding Interview

Firecode

HackerRank

Leetcode

​

​

by anonymous   2019-07-21

I was also going through this book Cracking the Code Interview and ended up googling for a clear explanations. Finally I understood the concept.

Here is the approach.

Note :

  1. We will assume, in the below code, that the string is only lower case ‘a’ through ‘z’. This will allow us to use just a single int.

  2. Java integer is of size 32

  3. Number of lower case alphabets is 26

So we can clearly set 0/1 (true or false) value inside one integer in decimal notation.

  1. It is similar to bool visited[32] . bool uses 1 byte. Hence you need 32 bytes for storing bool visited[32].

  2. Bit masking is a space optimization to this.

Lets start :

  1. You are looping through all the characters in the string.
  2. Suppose on i'th iteration you found character 'b' . You calculate its 0 based index.

int val = str.charAt(i) - 'a';

For 'b' it is 1. ie 66-65 .

  1. Now using left shift operator, we find the value of 2^1 => 2.

(1 << val) // 1<<1 => 10(binary)

Now let us see how bitwise & works

0 & 0 -> 0
0 & 1 -> 0
1 & 0 -> 0
1 & 1 -> 1

So by the below code :

(checker & (1 << val))

We check if the checker[val] == 0 . Suppose we had already encountered 'b'.

check = 0000 0000 0000 0000 0000 1000 1000 0010   &  
'b'   = 0000 0000 0000 0000 0000 0000 0000 0010 
 ----------------------------------------------
result= 0000 0000 0000 0000 0000 0000 0000 0010

ie decimal value = 2 which is >0

So you finally we understood this part.

 if ((checker & (1 << val)) > 0) 
                return false;
  1. Now if 'b' was not encountered, then we set the second bit of checker using bitwise OR.

( This part is called as bit masking. )

OR's Truth table

0 | 0 -> 0
0 | 1 -> 1
1 | 0 -> 1
1 | 1 -> 1

So

check = 0000 0000 0000 0000 0000 1000 1000 0000   |  
'b'   = 0000 0000 0000 0000 0000 0000 0000 0010 
 ----------------------------------------------
result= 0000 0000 0000 0000 0000 1000 1000 0010

So that simplifies this part:

checker |= (1 << val);  // checker = checker |  (1 << val);

I hope this helped someone !

by anonymous   2019-07-21

I am late to this party...

The question is also discussed in the book named Cracking the Coding Interview, 6th Edition on page number 70. The auther says there is a possiblity of finding all permutations using O(n) time complexity (linear) but she doesnt write the algorithm so I thought I should give it a go.

Here is the C# solution just in case if someone was looking...

Also, I think (not 100% sure) it finds the count of permutations using O(n) time complexity.

public int PermutationOfPatternInString(string text, string pattern)
{
    int matchCount = 0;
    Dictionary<char, int> charCount = new Dictionary<char, int>();
    int patLen = pattern.Length;
    foreach (char c in pattern)
    {
        if (charCount.ContainsKey(c))
        {
            charCount[c]++;
        }
        else
        {
            charCount.Add(c, 1);
        }
    }

    var subStringCharCount = new Dictionary<char, int>();

    // loop through each character in the given text (string)....
    for (int i = 0; i <= text.Length - patLen; i++)
    {
        // check if current char and current + length of pattern-th char are in the pattern.
        if (charCount.ContainsKey(text[i]) && charCount.ContainsKey(text[i + patLen - 1]))
        {
            string subString = text.Substring(i, patLen);
            int j = 0;
            for (; j < patLen; j++)
            {
                // there is no point going on if this subString doesnt contain chars that are in pattern...
                if (charCount.ContainsKey(subString[j]))
                {
                    if (subStringCharCount.ContainsKey(subString[j]))
                    {
                        subStringCharCount[subString[j]]++;
                    }
                    else
                    {
                        subStringCharCount.Add(subString[j], 1);
                    }
                }
                else
                {
                    // if any of the chars dont appear in the subString that we are looking for
                    // break this loop and continue...
                    break;
                }
            }

            int x = 0;

            // this will be true only when we have current subString's permutation count
            // matched with pattern's.
            // we need this because the char count could be different 
            if (subStringCharCount.Count == charCount.Count)
            {
                for (; x < patLen; x++)
                {
                    if (subStringCharCount[subString[x]] != charCount[subString[x]])
                    {
                        // if any count dont match then we break from this loop and continue...
                        break;
                    }
                }
            }

            if (x == patLen)
            {
                // this means we have found a permutation of pattern in the text...
                // increment the counter.
                matchCount++;
            }

            subStringCharCount.Clear(); // clear the count map.
        }
    }

    return matchCount;
}

and here is the unit test method...

[TestCase("encyclopedia", "dep", 1)]
[TestCase("cbabadcbbabbcbabaabccbabc", "abbc", 7)]
[TestCase("xyabxxbcbaxeabbxebbca", "abbc", 2)]
public void PermutationOfStringInText(string text, string pattern, int expectedAnswer)
{
    int answer = runner.PermutationOfPatternInString(text, pattern);
    Assert.AreEqual(expectedAnswer, answer);
}
by anonymous   2019-07-21

I will try to pass the idea using pseudo-code.

int CheckTreeHeight(Node root)
{
  if(root == null) return 0; // Height of 0.

  // Check if left is balanaced
  int leftChildHeight = CheckTreeHeight(root.left);
  if(leftChildHeight == -1) return -1; // Not Balanced

  // Check if right is balanaced
  int rightChildHeight = CheckTreeHeight(root.right);
  if(rightChildHeight == -1) return -1; // Not Balanced

  // Check if current node is balanced
  int heightDifference = leftChildHeight - rightChildHeight;

  if(Math.abs(heightDifference) > 1)
   return -1; // not balanaced
  else
   return Math.max(leftChildHeight, rightChildHeight) + 1; // Return Height
}

bool IsBalanced(Node root)
{
   if(CheckTreeHeight(root) == -1)
   {
      return false;
   }
   else
   {
      return true;
   }
}

This algorithm performs in O(n) time complexity and O(H) space complexity, where h is the height of the tree.

As mentioned by the algorithm's author, the idea is that we inspect the children of the root (that is left and right) recursively until we found unbalanced one, where we return -1.

With this technique, we return immediately if any of the sub-trees are unbalanced.

More information about this implementation you can find in the book mentioned in the reference bellow.

Reference
Cracking the Coding Interview 6th Edition