careercup / ctci-6th-edition Goto Github PK

I ran the program without memoization with the input

Amount: 4
Denominations are [3,2].

Program returns answer 2. But there is only one way to do is which 2,2.

What is the point to separate the first row and column with the rest ones ? why not just check at once:

for (int i = 0; i < rowCount; i++) { for (int j = 0; j < columnCount; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } }

Should we add the permutation returned for (n-1) to the list that is being returned.

permutations.addAll(words);

In the quick sort implementation here the partition function is incorrect. Test the partition function function with the input
{1, 4, 5, 2, 8, 9}; and manually set the pivot to third element pivot=arr[3] it returns the result as 2 which is incorrect if you check the resulting array

Hello!

I would like to offer Ruby solutions, and would like to be a contributor.

Please check out my repo below.
https://github.com/jasonsutter87/CtCI-6th-Edition-Ruby

Thanks!

• Jason

Hello team,

I have started implementing the solutions in Scala. Would you be interested in promoting these?

The repo is here: https://github.com/aashishdattani/CtCI-6th-Edition-Scala

Thanks.

The following answer has a bug. I've submitted a pull request to the 5th Edition since that's where I originally found it but the 6th Ed also has the same code.

careercup/ctci#171

The 6th Ed code with the bug:

Ch 04. Trees and Graphs/Q4_08_First_Common_Ancestor/QuestionD.java

The memoization of the solution in
CtCI-6th-Edition/Java/Ch 08. Recursion and Dynamic Programming/Q8_11_Coins/QuestionB.java
can be further optimised by additionally caching the results as shown below:

// Same as previous solution.....

public static int makeChange(int amount, int[] denoms, int index, int[][] map) {
    if (map[amount][index] > 0) { // retrieve value
        return map[amount][index];
    }
    if (index >= denoms.length - 1){
                //Start of Suggested  Changes
               //Cache this result as well...
                    map[amount][index] = 1;
               //End of Suggested  Changes
                    return 1; // one denom remaining -> one way to do it
            }
    int denomAmount = denoms[index];
    int ways = 0;
    for (int i = 0; i * denomAmount <= amount; i++) {
        // go to next denom, assuming i coins of denomAmount
        int amountRemaining = amount - i * denomAmount;
        ways += makeChange(amountRemaining, denoms, index + 1, map);
    }
    map[amount][index] = ways;
    return ways;
}

// Same as previous solution.....

Newly added statements are as follows:

if (index >= denoms.length - 1){
                //Start of Suggested  Changes
               //Cache this result as well...
                    map[amount][index] = 1;
               //End of Suggested  Changes
                    return 1; // one denom remaining -> one way to do it
            }

ht

The recursive git clone terminates abnormally at the Swift submodule so you can't get Swift and the following submodules. I'm not a git master, so I'm not sure where the problem is.
Error:
error: Server does not allow request for unadvertised object 7afac9bc7848ff460128225686657c9daedd28cc
Fetched in submodule path 'Swift', but it did not contain 7afac9bc7848ff460128225686657c9daedd28cc. Direct fetching of that commit failed.

You can successfully download the ZIP files for the remaining modules however.

I have a repo that I have created that I will be working on implementing the problems in the CtCI book in Objective-C. Please see the attached repo

Request to create new repo for C solutions

https://github.com/gaylemcd/CtCI-6th-Edition/blob/master/Java/Ch%2008.%20Recursion%20and%20Dynamic%20Programming/Q8_02_Robot_in_a_Grid/Point.java

This is making the optimization fail in

https://github.com/gaylemcd/CtCI-6th-Edition/blob/master/Java/Ch%2008.%20Recursion%20and%20Dynamic%20Programming/Q8_02_Robot_in_a_Grid/QuestionB.java

Hi there,
I tried understanding the Python code for URLify with Python but it appears to me that there is a mistake. The code works with the test code but for example if you try

print(urrlify(list('hello hello'), 11) )

it yields

['2', '%', '2', '%', '2', '0', 'h', 'e', 'l', '2', '%']

I propose the code below, which seems to work for all cases:

def urlify(string, length):
    '''function replaces single spaces with %20 and removes trailing spaces'''
    counter = 0
    for i in (range(length)):
        if string[i] == ' ':
            counter+=1

    new_index = len(string) + 2*counter
    new_string = []

    for i in reversed(range(length)):
        if string[i] == ' ':
            # Replace spaces
            new_string.insert(0,'%20')
            new_index -= 3
        else:
            # Move characters
            new_string.insert(0,string[i])
            new_index -= 1

    return new_string

This should also have a runtime of O(N). Let me know if I've missed something!

Just realised if we wanted the '%20' as individual elements we could change

new_string.insert(0,'%20')

to

new_string.insert(0,'0')
new_string.insert(0, '2')
new_string.insert(0, '%')

On this line in the Othello code:

https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2007.%20Object-Oriented%20Design/Q7_08_Othello/Board.java#L40

We have the some code that looks a bit like this (condensed slightly to fit in this tiny edit box):

int flipped = 0;
for (int result : results)
	if (result > 0) flipped += result;
if (flipped < 0) return false;

It seems to me that there is no way the "return false" can be reached here, because the sum of positive numbers is never negative (assuming no integer overflow).

Granted, these kind of details aren't really the point of Chapter 7, which is more "big picture stuff" it's still nice if demo code actually works. (The code that centers the initial 4 pieces on the board is also wrong, but that's relatively cosmetic.)

Solution B for 10.11 (Peaks and Valleys) is given as the optimized solution in the book, but it seems to give incorrect results if you have duplicate consecutive elements.

Example input: [5, 1, 3, 3, 2]
Example output: [1, 5, 3, 3, 2]

Expected output: [5, 1, 3, 2, 3]

Hi,
Would you be interested in ports of the Solutions to Objective-C? I'm reading the book and porting it to Objective-C.

Hello, Ms. McDowell

I'm always amazed how simple and elegant your solutions are. For this question, however, I felt like you could simplify it more by passing in the "previous" node in the recursive calls.

private BiNode convertOptimized(BiNode current, BiNode prev) {
    if (current.node1 != null)
      prev = convertOptimized(current.node1, prev);
    if (prev!= null)
      prev.node2 = current;
    current.node1 = prev;
    if (current.node2 != null)
      return convertOptimized(current.node2, current);
    return current;
  }

where initial call would pass in the root node of BST as current and null as prev.
This way, we don't need to worry about returning head or tail of sub-trees.

Please correct me, if I'm wrong.

Regards,
Stephen

Hi,

I am implementing the solutions in Common Lisp. As you may know, in Lisp, there is no sharp, predetermined border between code and data and I think programming in Lisp opens one's mind to the power of computing models. Programming in Lisp makes you see concepts from different angle.
Enough of me advertising lisp for more info please refer to: http://www.paulgraham.com/icad.html

The repo is here: https://github.com/mahyaret/CtCI-6th-Edition-CommonLisp

Thanks.
Mahyar

Hi Gayle,

I believe I might have found a faster, simpler solution to exercise 4.9. If you think it is valid and want to incorporate it to next editions of your book, here it is in Python:

def sequences(bst):
    all_seqs = list()
    build_seqs(bst.root, list(), list(), all_seqs)
    return all_seqs

def build_seqs(x, building, seq, all_seqs): # building is a queue (append left, remove right)
    seq.append(x.key)
    if x.left:
        building.insert(0, x.left)
    if x.right:
        building.insert(0, x.right)
    if len(building) == 0:
        all_seqs.append(seq)
    for i in range(len(building)):
        x = building.pop()
        build_seqs(x, building.copy(), seq.copy(), all_seqs)
        building.insert(0, x)

Best,
Bruno

This code will fail for input "Mr John Smith"

I am referencing the file, Entry.java, as part of the Q7_11_File_System problem.

I do appreciate the CTCI book. I purchased it. It is a great help. I do not mean to troll with my question, but rather understand what the design decisions were for this solution. Please do not take offense.

I do not believe I have ever seen an abstract class have a field in it of one of the classes that inherits from it, in this case, "protected Directory parent," is a field in the abstract class "Entry." "Directory" is a class that extends from the abstract class "Entry," as shown in the code below.

`
public abstract class Entry {
protected Directory parent;
... more code
}

public class Directory extends Entry {
... more code
}
`

I have never seen this approach to designing classes. As I am writing this code in my project, I have compilation errors when I create the "Entry" class because I have not created the "Directory" class. I cannot create the "Directory" class because it needs to extend the "Entry" class. To me this seems like a violation of SRP.

Can you help me understand why you designed it this way and if this is some new approach to OO design that I have not seen before?

Thank you.

Hello,

I'm trying to understand code from MultiStack.java file.
Everything seems to be good, except one thing.
Please, take a look at line 24. In what cases if clause could be true?

According to your code, method isWithinStackCapacity called only at line 116 with param index, which came from lastCapacityIndex function call. But lastCapacityIndex function did not return negatives values or values that more or equal than values.length.
So maybe if clause at line 24 is redundant?

Thank you!

Why does the solution of checking values of binary/hexadecimal numbers not consider signed numbers?

With the solution written as it currently is, doesn't it imply that there are no negative numbers in either binary or hexadecimal? Which is not true.

Wrong solution

preOrderTraversal() should recurse into preOrderTraversal (instead of inOrderTraversal())
postOrderTraversal() should recurse into postOrderTraversal (instead of inOrderTraversal())

Note: it is correct in the book (6th Edition)

Thanks for this GitHub project. It really helps!

There is a flaw in demo example for Question 1 Sorted Merge of Chapter 10 Sorting and Searching. The demo array that is supposed to be sorted as a pre-condition is not actually sorted. This leads to the fact that the demo result is not sorted as well.
See CtCI-6th-Edition/Java/Ch 10. Sorting and Searching/Q10_01_Sorted_Merge/Question.java:

Line 34: int[] b = {1, 4, 7, 6, 7, 7};

Same goes to C# Demo.
See Issue #17 there - Ch 10 / Q 1 - Sorted Merge / Input demo array is not sorted.
See CtCI-6th-Edition-CSharp/Ch 10. Sorting and Searching/Q10_01_Sorted_Merge.cs

Line 42: int[] b = new int[] { 1, 4, 7, 6, 7, 7 };

At the same time, in PHP solutions, this example is modified to be sorted and used in demo unit tests.
See CtCI-6th-Edition-php/test/chapter10/question10.01/SortedMergeTest.php

Line 48: $b = [ 1, 4, 6, 7, 7, 7 ];

If this unsorted sample is not introduced intentionally to check if the reader is attentive, this should be fixed, I believe. Preparing Pull Requests for this:

• #192 - here in CtCI-6th-Edition
• in CtCI-6th-Edition-CSharp - #18

Gayle, Can you please check below solution with O(n) time complexity and O(1) space.
`
public static int computeVolume(int[] arr) {
MaxElemAndPos mp = getMax(arr);

    int sum = 0;
    int curMax = 0;
    // Calculate volume till the max.
    for (int i = 0; i < mp.elemPos; i++) {
        if (arr[i] > curMax) {
            curMax = arr[i];
        }

        sum += (curMax - arr[i]);
    }

    curMax = 0;
    for (int i = arr.length - 1; i > mp.elemPos; i--) {
        if (arr[i] > curMax) {
            curMax = arr[i];
        }

        sum += (curMax - arr[i]);
    }

    return sum;
}

private static MaxElemAndPos getMax(int[] arr) {
    MaxElemAndPos mp = new MaxElemAndPos();
    mp.elemPos = 0;
    mp.maxElem = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > mp.maxElem) {
            mp.maxElem = arr[i];
            mp.elemPos = i;
        }
    }

    return mp;
}

public static class MaxElemAndPos {
    int maxElem;
    int elemPos;
}

`

A c++ code with use of a java code is in use without any conversion.
The important part of getting the table of frequency hasn't been implemented.
This looks very strange

std::vector<int> table = Common::buildCharFrequencyTable(phrase);

as soon as Coomon is a java file

If the last element is duplicate, then will be java.lang.NullPointerException.

There is a line if (trueLength < str.length) str[trueLength] = '\0';.
I wonder it should be if (index < str.length) str[index] = '\0'; instead.

No need to separate first column with the rest columns to check if there is zero.

public class QuestionB {

	public static void main(String[] args) {
		int[][] matrix = { { 1, 0, 3, 4 }, { 5, 0, 7, 8 }, { 9, 10, 11, 12 } };
		setZeros(matrix);

		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void nullifyRow(int[][] matrix, int row) {
		for (int j = 0; j < matrix[0].length; j++) {
			matrix[row][j] = 0;
		}
	}

	public static void nullifyColumn(int[][] matrix, int col) {
		for (int i = 0; i < matrix.length; i++) {
			matrix[i][col] = 0;
		}
	}

	public static void setZeros(int[][] matrix) {
		boolean rowHasZero = false;

		// Check if first row has a zero
		for (int j = 0; j < matrix[0].length; j++) {
			if (matrix[0][j] == 0) {
				rowHasZero = true;
				break;
			}
		}

		// Check for zeros in the rest of the array
		for (int i = 1; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				if (matrix[i][j] == 0) {
					matrix[i][0] = 0;
					matrix[0][j] = 0;
				}
			}
		}

		// Nullify rows based on values in first column
		for (int i = 1; i < matrix.length; i++) {
			if (matrix[i][0] == 0) {
				nullifyRow(matrix, i);
			}
		}

		// Nullify columns based on values in first row
		for (int j = 0; j < matrix[0].length; j++) {
			if (matrix[0][j] == 0) {
				nullifyColumn(matrix, j);
			}
		}

		// Nullify first row
		if (rowHasZero) {
			nullifyRow(matrix, 0);
		}
	}
}

Is there also a place/file where one can just find the questions chapter wise?

That would be really helpful in my humble opinion for someone trying to practice them without peeking into the answer already.

You can solve 17.23 in N^2logN time using a trick from the ICPC World Finals problem triangles.
It will be helpful to read the problem and watch the solution video first

https://icpc.kattis.com/problems/triangles3
https://www.youtube.com/watch?v=0LqHpmzRHzk

So we apply the same trick as the triangles, except in this case we aren't looking to count the number of results but instead find the largest square that connects to a given bottom right index. As a result, we'll use a binary search tree instead of a segment tree.

First lets calculate the length of 0's in each direction from each square and store them. I'll refer to these by their direction (up, etc).

Now lets walk a diagonal from the top left to the bottom right and keep a tree that contains the top left corners that could possibly make a square with the current bottom right corner based on their lengths right and down. Each time we step on a new square we will need to do three things:

1. Do a search in our tree for the smallest coordinate greater than or equal to min(up, left) of this square. That coordinate (if it exists) forms the largest possible square with this as the bottom right endpoint. If this is the largest square so far, save it.
2. Add the current coordinates into the tree and set a marker in our array right and down min(right, down) of this square. This will tell us when we should remove these coordinates from the tree.
3. Take all the markers at these coordinates and remove them from the tree, as they will not be able to form a square with the next coordinate on this diagonal.

If we do this for each diagonal we have O(N^2) to preprocess the directional lengths, O(N^2 * log(N)) for the searches in our tree, O(N^2 * log(N)) for the inserts into our tree, and O(N^2 * log(N)) for the removals from our tree. This is O(N^2 * log(N)) time total.

Hi, I have started implementing the solutions in Dart.
I would like to be a contributor.

The repo is here: https://github.com/sensuikan1973/CtCI-6th-Edition-Dart

Thanks,

Could this bit manipulation question be solved in the following way?

int mask = ~((Math.pow(2,(j-i+1)) - 1)<<i);
return (n&mask)|(m<<i);

Hi, Would you be interested in ports of the Solutions to C++? I just bought the book and I am reading through it and porting it to C++ (language I will use for interviews) would be a great exercise for me.

Your intention of hosting it (if it's good) would be an additional motivation so to speak.

Hi,

I have started implementing the solutions in Kotlin. Would that be interesting?

The repo is here: https://github.com/PedramVeisi/CtCI-6th-Edition-Kotlin

Thanks.

I have solutions in Rust here: https://github.com/modulitos/CtCI-rust/tree/master/src/bin

I did my best to write the solutions clearly and in idiomatic Rust, but I'm open to feedback :)

Chapters 1-4 are completed. Planning to finish chapters 5, 7, and 8 next. PR's are welcome 🎉

If you try points

int[][] coordinates = {
                {1, 0}, {1, 2},
                {0, 1}, {2, 1}};

It gives No intersection.

This is because the code does not handle the case when one line is vertical and the other is not; it still tries to determine intersection based on the slope and y-intercept of both lines, even though for the vertical lines the slope and y-intercept will be Infinity.

Hi, I'm working on a Julia version of solutions here CtCI-6th-Edition-Julia.

[...url].map((char) => char === ' ' ? '%20' : char).join('');
Is there something wrong with the above?

Requesting that my solution repo be promoted to join the careercup GitHub organization and referenced from the main repo as a git submodule.

Currently only partially completed an upgrade from Edition 5 and porting Edition 6 questions from Java solution. Work in progress, but better than nothing.

https://github.com/dww84/CtCI-6th-Edition-CSharp

Hello team,

I have started implementing the solutions in F#. Would you be interested in taking ownership, to make them available for other contributors?

The repo is here: https://github.com/moudrick/CtCI-6th-Edition-FSharp

Thanks.

I am using IDEA, how to run the java source file?

import CtCILibrary.LinkedListNode;
It seems that this statement could not be available.

This solution can be improved from O(n*m) to O(n + m), where n is the size of the big tree t1 and m is size of the small tree t2. We can get the size of every subtree of t1 in O(n) and size of t2 in O(m), and then only compare the subtrees of size m in t1 with t2. There are at most n/m subtrees of size m, and each compare costs O(m), so the total cost is O(n/m * m) + O(n) + O(m) = O(n + m).

    public static boolean containsTree(TreeNode t1, TreeNode t2) {
        if (t2 == null) {
            return true; // The empty tree is a subtree of every tree.
        }
        
        boolean[] result = new boolean[1];
        // Get the size of t2
        int m = treeSizeAndMatch(t2, null, -1, null);
        // Get the size of t1 and do the match for subtrees of size m
        int n = treeSizeAndMatch(t1, t2, m, result);
        return result[0];
    }
    
    private static int treeSizeAndMatch(TreeNode r1, TreeNode r2, int matchSize, boolean[] result) 
    {
        if(r1 == null) return 0;
        int leftSize = treeSizeAndMatch(r1.left, r2, matchSize, result);
        int rightSize = treeSizeAndMatch(r1.right, r2, matchSize, result);
        int size = 1 + leftSize + rightSize;
        if(size == matchSize && !result[0]) {
            result[0] = matchTree(r1,r2);
        }
        return size; 
    }
    
    //The same as Q4_10_Check_Subtree/QuestionB.matchTree
    public static boolean matchTree(TreeNode r1, TreeNode r2) { ... }

Vertical lines don't get their ends swapped (x0 and x1 are always the same), so two vertical segments, one going up, and one going down, can be miscategorized. for instance, {0,0}->{0,2} and {0,3}->{0,1} tests whether 3 is between 0 and 2, concludes that it's not, and does not check the other end.

(more generally, slope+intercept is an awful way to do line segment interception precisely because of all the weird special cases.)

The solution which is given does not work for "aaaabbaa".

public static String compressBad(String str) {
String compressedString = "";
int countConsecutive = 0;
for (int i = 0; i < str.length(); i++) {
countConsecutive++;
/* If next character is different than current, append this char to result.*/
if (i + 1 >= str.length() || str.charAt(i) != str.charAt(i + 1)) {
compressedString += "" + str.charAt(i) + countConsecutive;
countConsecutive = 0;
}
}
return compressedString.length() < str.length() ? compressedString : str;
}

I have provided below solution .

private static final HashMap<Character, Integer> map = new HashMap<Character, Integer>();
public static String getCompressString(String str) {
StringBuilder stringBuilder = new StringBuilder();
HashMap<Character, Integer> map = getMap(str.toCharArray());
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
stringBuilder.append(entry.getKey());
stringBuilder.append(entry.getValue());
}
String finalStr = stringBuilder.toString();
if (finalStr.length() <= str.length()) {
return finalStr;
}
return str;
}

private static HashMap<Character, Integer> getMap(char[] a) {
	if (null == a || a.length == 0) {
		return null;
	}
           for (int i = 0; i < a.length; i++) {
		char ch = a[i];
		if (map.containsKey(ch)) {
			int count = map.get(ch);
			map.put(ch, ++count);
		} else {
			map.put(ch, 1);
		}
	}
      return map;
}

which works for any input "aabb" , "aaabbaaa" etc.
Any suggestion please provide.

You're solution is great. But I found a small issue, please correct me if I was wrong. Suppose, we have a tree as below:
4
/ \
2 6
/ \ / \
1 3 4 7

Based on the problem stated, it is supposed to return "false" in this case. However, the code returned "true".