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 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

by anonymous   2019-01-13

As the question already states that the left and right input arrays are sorted, this gives you a hint that you should be able to solve the problem without requiring a data structure other than an array for the output.

In a real interview, it is likely that the interviewer will ask you to talk through your thought process while you are coding the solution. They may state that they want the solution implemented with certain constraints. It is very important to make sure that the problem is well defined before you start your coding. Ask as many questions as you can think of to constrain the problem as much as possible before starting.

When you are done implementing your solution, you could mention the time and space complexity of your implementation and suggest an alternative, more efficient solution.

For example, when describing your implementation you could talk about the following:

  • There is overhead when creating the queues
  • The big O notation / time and space complexity of your solution
  • You are unnecessarily iterating over every element of the left and right input array to create the queues before you do any merging
  • etc...

These types of interview questions are common when applying for positions at companies like Google, Microsoft, Amazon, and some tech startups. To prepare for such questions, I recommend you work through problems in books such as Cracking the Coding Interview. The book covers how to approach such problems, and the interview process for these kinds of companies.

by Wonderful_Safety   2019-01-13

leetcode.com

hackerrank.com

&gt;Best seller in Hacking and in Computer Security & Encryption

https://toptalkedbooks.com/amzn/0984782850

by yiliu   2019-01-13

Well, it was my fear too. When I was getting close to graduation, I was sure nobody would be interested. Then I got an interview, and then got a job, and then I was away.

Generally, at least in my experience, it's not hard to get interviews (or at least phone screens) because companies are all looking for talent and a phone screen is pretty low-cost for the company. If you're worried, warm up with some interview questions (from this kind of book for example). If you can get an interview, and if your interview goes well...well, that's all it takes.

by cool_anna   2019-01-13

Depends on the companies you're applying for. For the top 20-30 tech companies in the US ( in terms of revenue/popularity etc.), familiarity with algos and DS is must.

However, the difficulty of questions is dependent on how good a company is.

I would suggest Cracking the coding interview and leetcode are really very useful to get into top tech companies

by mindcrime   2018-11-17
If it were me, I'd probably consult Cracking The Coding Interview[1], and the Robert Sedgewick Algorithms in C++ [2][3] books. That and maybe spend some time practicing on Leetcode, Hacker Rank, Project Euler, etc. Skiena's Algorithm Design Manual[4] could also be good.

[1]: https://www.amazon.com/Cracking-Coding-Interview-Programming...

[2]: https://www.amazon.com/Algorithms-Parts-1-4-Fundamentals-Str...

[3]: https://www.amazon.com/Algorithms-Part-Graph-3rd-Pt-5/dp/020...

[4]: https://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena...