Cracking The Coding Interview 189 Programming Questions And Solutions

Crackingthecodinglnterviewcom I 6th Edition 279

I Be careful with how you express the runtime. For example, if you say the runtime isO, what is n? It is not correct to say that this algorithm is O. This algorithm is O. For this reason, when you have potential ambiguity in what n might mean, it’s best just to not use n. Then neither you nor your interviewer will be confused. Pick a different variable name. We used “b’ for the number of bits. Something logical works well.

Can we do better? Recall the concept of Best Conceivable Runtime. The B.C.R. for this algorithm is 0, so we know we can’t optimize the time. We can,however, reduce the memory usage.

Optimal Algorithm

To reduce the space usage, note that we don’t need to hang on to the length of each sequence the entiretime. We only need it long enough to compare each 1 s sequence to the immediately preceding 1 s sequence.Therefore, we can just walk through the integer doing this, tracking the current 1s sequence length and theprevious ls sequence length. When we see a zero, update previous Length: If the next bit is a 1, previous Length should be set to current Length. If the next bit is a 0, then we can’t merge these sequences together. So, set previous Length to 0.Update max Length as we go.1 int flipBit The runtime of this algorithm is still O , but we use only O additional memory.

5.4 Next Number: Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation. pg 116

SOLUTION

Crackingthecodinglnterviewcom 6th Edition 273

Let’s isolate a given path and treat it as just an array. Consider a path like: 10 -> 5 -> 1 -> 2 -> -1 -> -1 -> 7 -> 1 -> 2What we’re really saying then is: How many contiguous subsequences in this array sum to a target sum suchas 8? In other words, for each y, we’re trying to find the x values below.

index: 0 1 2 3 4 5 6 7 8 value: 10 -> 5 -> 1 -> 2 -> -1 -> -1 -> 7 -> 1 -> 2 sum: 10 15 16 18 17 16 23 24 26The value of runningSum7 is 24. lf targetSum is 8, then we’d look up 16 in the hash table. This would havea value of 2 . As we can see above, indexes 3 through 7 and indexes6 through 7 have sums of 8.Now that we’ve settled the algorithm for an array, let’s review this on a tree. We take a similar approach.We traverse through the tree using depth-first search. As we visit each node:

Cracking The Coding Interview 189 Programming Questions And Solutions

M.L.King

• 179 Pages·2017·1.22 MB·119,772 DownloadsProof_of_Heaven_-_Eben_Alexander.pdf Proof of Heaven …
• 708 Pages·2015·53.81 MB·29,586 Downloads·New!and hiring process. Cracking the CodingInterview: 189ProgrammingQuestions …
• 712 Pages·2015·87.84 MB·17,805 Downloads·New!and hiring process. Cracking the CodingInterview, 6th Edition: 189ProgrammingQ …
• 310 Pages·2016·3.18 MB·6,087 Downloads·New!Cracking the CodingInterview, Fourth Edition: 150 ProgrammingInterviewQuestion …
• 510 Pages·2011·118.71 MB·7,288 Downloads·New!/ programminginterviews. Cracking the CodingInterview: 150 ProgrammingQ …
• 310 Pages·2010·2.05 MB·82,794 DownloadsCracking the CodingInterview, Fourth Edition: 150 ProgrammingInterviewQuestio …
• 445 Pages·2014·3.54 MB·22,857 Downloads·New!solution with deep Questions-Answers explanations with different interview complexities for each …
• 310 Pages·2011·1.36 MB·3,166 DownloadsInterviewQuestions and Solutions 4e Small.pdf Cracking the CodingInterview, …
• 708 Pages·2016·53.81 MB·211,658 DownloadsCRACKING the. CODINGINTERVIEW. 6th Edition. 189ProgrammingQuestions and …
• 457 Pages·2017·1.35 MB·54,078 Downloads·New!to become a great programmer! –Codinginterview tips. –Programming Quotes! java interview …

Read Also: Interview Question What Do You Know About Our Company

Cracking The Coding Interview

Cracking the Coding Interview: 189 Programming Questions and Solutions is a book by Gayle Laakmann McDowell about coding interviews. It describes typical problems in computer science that are often asked during coding interviews, typically on a whiteboard during job interviews at big technology companies such as , Apple, Microsoft, , and Palantir Technologies.

First published in 2008, it has been translated into seven languages: Russian, Simplified Chinese, Traditional Chinese, Japanese, Polish, Spanish, and Korean. It describes solutions to common problems set in coding job interviews. The sixth edition of the textbook was published in 2015.

Cracking The Co Ding Interview 6th Edition

3.6 Animal Shelter: An animal shelter, which holds only dogs and cats, operates on a strictly”first in, first out” basis. People must adopt either the “oldest” of all animals at the shelter, or they can select whether they would prefer a dog or a cat . They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog, and dequeueCat. You may use the built-in Linkedlist data structure.

pg99

SOLUTION

We could explore a variety of solutions to this problem. For instance, we could maintain a single queue.This would make dequeueAny easy, but dequeueDog and dequeueCat would require iteration throughthe queue to find the first dog or cat. This would increase the complexity of the solution and decrease theefficiency.An alternative approach that is simple, clean and efficient is to simply use separate queues for dogs andcats, and to place them within a wrapper class called An imalQueue. We then store some sort of timestampto mark when each animal was enqueued. When we call dequeueAny, we peek at the heads of both thedog and cat queue and return the oldest.1 abstract class Animal {

60 public class Cat extends Animal 62 }It is important that Dog and Cat both inherit from an Animal class since dequeueAny needs to be ableto support returning both Dog and Cat objects.

You May Like: What Questions Are Asked In Citizenship Interview

How Do You Find The Start Of The Loop

We now know that CollisionSpot is K nodes before the start of the loop. Because K = mod , it is also correct to say that it isk nodes from the loop start. For example, if node N is 2 nodes into a 5 node loop, it is also correct to say thatit is 7, 12, or even 397 nodes into the loop.Therefore, both CollisionSpot and LinkedlistHead are k nodes from the start of the loop.

Int Top= Matrix Ii Save Top

1.8 Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0. pg91

SOLUTION

At first glance, this problem seems easy: just iterate through the matrix and every time we see a cell withvalue zero, set its row and column to 0. There’s one problem with that solution though: when we comeacross other cells in that row or column, we’ll see the zeros and change their row and column to zero. Prettysoon, our entire matrix will be set to zeros.One way around this is to keep a second matrix which flags the zero locations. We would then do a secondpass through the matrix to set the zeros.This would take O space.Do we really need O space? No. Since we’re going to set the entire row and column to zero, we don’tneed to track that it was exactly cell . We only need to know that row 2 has azero somewhere, and column 4 has a zero somewhere.We’ll set the entire row and column to zero anyway,so why would we care to keep track of the exact location of the zero?The code below implements this algorithm. We use two arrays to keep track of all the rows with zeros and allthe columns with zeros. We then nullify rows and columns based on the values in these arrays.1 void setZeros {

Don’t Miss: How To Say Thank You For An Interview

Solution #: The Min / Max Solution

In the second solution, we leverage the definition of the binary search tree.

What does it mean for a tree to be a binary search tree? We know that it must, of course, satisfy the conditionleft. data < = c urrent. data < right. data for each node, but this isn’t quite sufficient. Considerthe following small tree:

Although each node is bigger than its left node and smaller than its right node, this is clearly not a binarysearch tree since 25 is in the wrong place.More precisely, the condition is that a// left nodes must be less than or equal to the current node, whichmust be less than all the right nodes.

Using this thought, we can approach the problem by passing down the min and max values. As we iteratethrough the tree, we verify against progressively narrower ranges.

Crackingthecodinglnterviewcom / 6th Edition 211

Note that this problem cannot be solved if the node to be deleted is the last node in the linked list. That’sokay-your interviewer wants you to point that out, and to discuss how to handle this case. You could, forexample, consider marking the node as dummy.

2.4 Partition: Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. If x is contained within the list the values of x only need to be after the elements less than x . The partition element x can appear anywhere in the”right partition” it does not need to appear between the left and right partitions. EXAMPLE

20 // The head has changed, so we need to return it to the user.21 return head 22 }There are many equally optimal solutions to this problem. If you came up with a different one, that’s okay!

Recommended Reading: How To Reply To Interview Questions

Crackingthecodinglnterviewcom I 6th Edition 223

An astute reader may wonder if FastRunner might “hop over” SlowRunner completely, withoutever colliding. That’s not possible. Suppose that FastRunner did hop over SlowRunner, such thatSlowRunner is at spot i and FastRunner is at spot i + 1. In the previous step, SlowRunner wouldbe at spot i – 1 and FastRunner would at spot – 2), or spot i – 1. That is, they wouldhave collided.

To Summarize We Move Fastpointer Twice As Fast As Slowpointer When Slowpointer Enters

56 /* Returns index of the top of the stack. */57 private int indexOfTop 62 }If we had additional information about the expected usages of the stacks, then we could modify this algorithm accordingly. For example, if we expected Stack 1 to have many more elements than Stack 2, we couldallocate more space to Stack 1 and less space to Stack 2.

Also Check: How To Boost Confidence Before An Interview

Set Bits 0 Through Cl

A quick and dirty way to perform steps 1 and 2 is to set the trailing zeros to 1 , andthen add 1. Adding one will flip all trailing ones, so we wind up with a 1 at bit p followed by p zeros. We canperform this arithmetically.2 /* … same calculation for c0 and cl as before */3 return n + + ) – 1 4 }

Crackingthecodinglnterviewcom I 6th Edition 257

Observe that we don’t need to re-check the entire subtree. As we move from a node x to its parent y, all thenodes under x have already been checked for q. Therefore, we only need to check the new nodes “uncovered’ which will be the nodes under x’s sibling.For example, suppose we’re looking for the first common ancestor of node p = 7 and node q = 17.When we go to p.parent , we uncover the subtree rooted at 3. We therefore need to search thissubtree for q.Next, we go to node 10, uncovering the subtree rooted at 15. We check this subtree for node 17 andvoila-there it is.

To implement this, we can just traverse upwards from p, storing the parent and the sibling node ina variable. At each iteration, sibling gets set to the old parent’s sibling node and parent gets set to parent.parent.1 TreeNode commonAncestor {2 /* Check if either node is not in the tree, or if one covers the other. */3 if 11 !covers) {4 return null

Recommended Reading: What Questions To Ask In A Phone Interview

Crackingthecodinglnterviewcom I 6th Edition 213

2.5 Sum Lists: You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order,such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list. EXAMPLE

24 return result 25 }In implementing this code, we must be careful to handle the condition when one linked list is shorter thananother. We don’t want to get a null pointer exception.

Follow Up

Part B is conceptually the same , but has some additional complications when itcomes to implementation:

1. One list may be shorter than the other, and we cannot handle this “on the flY:’ For example, suppose we were adding and . We need to know that the 5 should be”matched”with the 2, not the 1. We can accomplish this by comparing the lengths of the lists in the beginning and padding the shorter list with zeros.2. In the first part, successive results were added to the tail . This meant that the recur sive call would be passed the carry, and would return the result . In this case, however, results are added to the head . The recursive call must return the result, as before, as well as the carry. This is not terribly challenging to implement, but it is more cumbersome. We can solve this issue by creating a wrapper class called Partial Sum.

Whats Inside The Book

Aside from the obvious 189 questions and answers, there is a lot more content that can further help you. Practicality will tell you that you it would be hard to have actually memorized all the 189 question and answers to ace that interview. However, you do not need to do all that.

The book provides a walkthrough teaching you how to think about an answer for each question. This should teach you to provide your own answer which does not necessarily have to be exactly the same as the book. Hints are even provided when browsing through the Q& A. To mention the rest of its contents, the book gives 5 strategies when tackling algorithm questions, an insider look on how big companies like Google hire their developers, and techniques to prepare for before finally going to the interview.

Read Also: Interview Questions For Financial Planner

Solution #: With Links To Parents

If each node has a link to its parent, we could trace p and q’s paths up until they intersect. This is essentiallythe same problem as question 2.7 which find the intersection of two linked lists. The “linked list” in this caseis the path from each node up to the root. 1 TreeNode commonAncestor {2 int delta= depth – depth // get difference in depths3 TreeNode first = delta > 0? q : p // get shallower node4 TreeNode second= delta > 0? p : q // get deeper node5 second= goUpBy) // move deeper node up6

Imagine We Have The Following Stacks Where S2 Issorted And Sl Is Not:

12 10 3 7 1

When we pop 5 from s 1, we need to find the right place in s2 to insert this number. In this case, the correctplace is on s2 just above 3. How do we get it there? We can do this by popping 5 from sl and holding itin a temporary variable. Then, we move 12 and 8 over to s 1 and then push 5 onto s2.

Recommended Reading: What Are Good Questions To Ask Your Interviewer

Else Returns The Common Ancestor Of P And Q

Finding the common ancestor of p and q in the final case is easy. When commonAncestor and commonAncestor both return non-null values ,then n will be the common ancestor.

The code below offers an initial solution, but it has a bug. Can you find it?1 I* The below code has a bug. *I2 TreeNode commonAncestor {3 if return null 4 if return root 5

Suppose we call commonAncestor.0f course,node 7does not existand that’s where the issue will come in. The calling order looks like:1 commonAnc II–> s2 calls commonAnc II–> null

Crackingthecodinglnterviewcom I 6th Edition 285

So, we have our answer: ) == 0) checks if n is a power of 2 .

5.6 Conversion: Write a function to determine the number of bits you would need to flip to convert integer A to integer B. EXAMPLE

6 return count 7 }The above code is one of those bit manipulation problems that comes up sometimes in interviews. Thoughit’d be hard to come up with it on the spot if you’ve never seen it before, it is useful to remember the trickfor your interviews.

5.7 Pairwise Swap: Write a program to swap odd and even bits in an integer with as few instructions as possible . pg 716

SOLUTION

Like many of the previous problems, it’s useful to think about this problem in a different way. Operating onindividual pairs of bits would be difficult, and probably not that efficient either. So how else can we thinkabout this problem?We can approach this as operating on the odds bits first, and then the even bits. Can we take a number nand move the odd bits over by 1? Sure. We can mask all odd bits with 10101010 in binary ,

Recommended Reading: Interview Questions For Senior Web Developer

This Problem Can Be Approached In Three Key Steps:

The trickiest part is Step 1. How do we clear the bits in N? We can do this with a mask. This mask will have all1 s, except for Os in the bits j through i. We create this mask by creating the left half of the mask first, andthen the right half.1 int updateBits if else if This is pretty good. It’s O time and O memory, where b is the length of the sequence.