Solutions for "Cracking the Coding Interview v5"
Adding equivalent solutions in Objective-C Adding my own solutions
Cracking the Coding Interview, 5th Edition
Hi @gaylemcd! It might be a good idea to open a gitter for this repository. Gitter is just a public chat room you can create for free on repositories. (Think Slack)
Coding Style is somehow much important in coding interview.
Python Coding interview is different from Java and C/C++.
I recommend following Google Python Style http://google-styleguide.googlecode.com/svn/trunk/pyguide.html
For example, naming of functions:
Functions lower_with_under() _lower_with_under()
The original Q asks for a solution to do the rotation in place but the current solution obviously created a new matrix to do that. Please consider the following code, which rotates the picture (image) matrix in place:
def rotate_pic(pic):
N = len(pic)
for r in range(int(N/2)):
for c in range(r, N-r-1):
p1 = pic[r][c]
p2 = pic[c][N-r-1]
p3 = pic[N-r-1][N-c-1]
p4 = pic[N-c-1][r]
pic[c][N-r-1] = p1
pic[N-r-1][N-c-1] = p2
pic[N-c-1][r] = p3
pic[r][c] = p4
Just run go fmt
on all the code. Especially section 1.8 looks frightening.
your code is beautiful :)
The question said both trees are very large. Does it mean we should not use a recursive way of doing this?
when input "^~" string.
The function isUniqueChars and isUniqueChars2 output is different.
result: ^~: false true
I think function isUniqueChars is not without considering that two different characters may use the same bit.
It doesn't even work.
As an example:
python2 Question2_4.py
LinkedList [ 27->32->24->15->50->17->19->22->2->30 ] , x=15
LinkedList [ 2->27->32->24->15->50->17->19->22->30 ]
The O(n) time and O(1) space solution for Chapter 2 Question 4 crashes when the input list doesn't contain the pivot value (dangerous assumption).
My solution to this failure is in the PartitionInPlace method below:
https://github.com/alibad/PlayGround/blob/master/Cracking/Chapter%202/Problem_2_4.cs
Let me know if you like my solution and I can add it as a Partition4 to the existing file in this repo.
Thanks
I might be wrong, but your method isPalindromeRecurse can be simplified like this:
public static Wrapper isPalindromeRecursive(Node<Integer> node, int length) {
if (length == 0) {
return new Wrapper(node, true);
} else if (length == 1) {
return new Wrapper(node.next, true);
}
Wrapper result = isPalindromeRecursive(n.next, length - 2);
result.palindrome = result.palindrome && node.data == result.node.data;
result.node = node.next;
return result;
}
The case when length == 2
will be covered by length == 0
if we return current node instead of null.
The return logic is also easier without conditionals.
Correct me, please, if there are flaws in my solution.
If one or more spots fail, it seems to still decrease the number of available spots, and also doesn't free the spots that succeeded. This should be an "all-or-nothing" kind of transaction. Potentially, if a level fails to park the vehicle, the following level should try, which then starts by clearing the spots on the given vehicle. To make sure we are clearing the correct number of vehicles vs. decreasing the correct number of available spots, a workaround would be to decrease the available spots by the actual number of spots that were filled rather than the vehicle's number of spots needed.
Is this a good practice to use a trinocular operator when the result itself is boolean as below:
boolean isAncestor = rx.node != null || ry.node != null ? true : false;
or we can just write
boolean isAncestor = rx.node != null || ry.node != null;
This solution uses clone
, but according to the documentation, the elements themselves are not copied.
It appears the Python recursive solution will not work if we are looking for the successor node of a leaf node of a BST.
Earlier when it was in svn i was able to import and run the full project.
I do not know how to import frim github and then run it properly
can you please any walkthrough or tutorial on how to do this ?
The question states that
"The path does not need to start or end at the root or a leaf but must in a straight line down"
So is left-left-right a valid path ? I would think it is a not a straight path when drawn on a binary tree.
I am not sure what could be a good way to describe it without using the phrase "straight line" but this phrase is surely confusing. At least the solution should contain a diagram which clears this ambiguity.
We could add simple checks to avoid unnecessary traversal in case of unbalanced tree.
For example if a node has no elements in its right subtree, it makes no sense to traverse its left subtree for levels higher than 1. So if we reach 2nd level in the left subtree, we already know that the tree is unbalanced.
Also after processing left subtree we have its height and we could limit the maximum depth of traversal for the right subtree to this value.
The code does not work with null values
The way at here and in the book can't find the path from leaf to leaf, or any path accrosses two PATH(from root to leaf), you can use your existing example, findSum(root, 9) and you will found the what I mean, your way outputs nothing, but there should be two paths where sum=9.
BTW, your book is awesome!
first 3 chapters seem to be implemented at https://github.com/apsun/CCIKotlin, fyi
Hey,the code of this maybe wrong:
public static boolean isUniqueChars(String str) {
if (str.length() > 128) {
return false;
}
int checker = 0;
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i) - 'a';
System.out.println(val);
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
}
return true;
}
when i try these :
String[] words = {"0p","1q","2r","3s","4t","5u","6v","7w","8x","9y"};
the result is false.
In the function print
the code used to print the path is wrong. In the question, it says path must go in a straight line down, but the implementation print the path straight line up.
for(int j=i; j <= level; j++) cout<<path[j]<<" "; cout<<'\n';
Hi,
I started to code solutions and unit tests with PHP here https://github.com/midorikocak/cracking-the-code-interview/ Please check. Any feedback is welcome.
Midori
In Chapter 10 and Question 10_3 , and few more questions have the same warning issued by IDE that the declarations doesn't have Generics. Nowadays even a naive Java programmer writes his code with Generics, which has the following advantages.
http://docs.oracle.com/javase/tutorial/java/generics/why.html
Are these very trivial ? If yes, the issue can be closed.
Hi
Can you provide installation screenshot for the below js...
never used node modules so that helpful in executing...
https://github.com/careercup/ctci/blob/master/java/Chapter%209/Question9_2/QuestionDP.java#L39
Using the cache (dynamic programming) doesn't help in this case, where you are only looking for the first working path. Only the first working path can have any partial results to be saved.
It would, however, help in the case where you want to find all paths.
Hi,
For the chapter 5, problem 7, in the solution, altough the last index stores the least significant k(the least significant is at INTEGER_SIZE - 1 th index), toInt() function seems to convert value reversely: INTEGER_SIZE - 1 th index becomes the most significant bit as the result of toInt() function.
Thanks,
İrem Özbek
In the Java solution for 8.10, if there is a collision in the bucket where the new element is to be placed, the current code uses collided.remove(c)
where collided
is the LinkedList
object and c
is the node in the bucket's list. But calling remove(...)
on the LinkedList object itself, and not the iterator, will remove the element by starting at the beginning of the list and traversing until it finds the element. This has 2 problems 1) If the item removed is the second to last element in the list, the loop will never visit the last element (In my opinion the LinkedList iterator should actually throw a ConcurrentModificiationException
here, but the check is in next()
, and not hasNext()
). 2) This eliminates the benefit of using a LinkedList. The for
loop should explicitly use the List's iterator, and then the remove should be done using the remove
method of the iterator. This will take O(1) time instead of O(n), where n is the number of items in the bucket.
int the book,the code is:
if (str.length() > 26) {
return false;
}
it's contains only the lowercase a to z characters.
but on github,the code is:
if (str.length() > 128) {
return false;
}
it's contains all ASCII.
public static boolean isUniqueChars(String str) {
if (str.length() > 128) {
return false;
}
int checker = 0;
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i) - 'a';
System.out.println(val);
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
}
return true;
}
char c1[]=s1.toCharArray();
char c2[]=s2.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
System.out.println("Permutations? = "+(new String(c1).equals(new String(c2))));
Hi
Can you provide installation screenshot for the below js...
never used node modules so that helpful in executing...
One Paragraph of project description goes here
Adding the list of contents it will easy of user.
These instructions will get you a copy of the project up and run on your local machine for development and testing purposes. See deployment for notes on how to deploy the project on a live system.
Explain how to run the automated tests for this system
Explain what these tests test and why
Give an example
This project is licensed under the MIT License - see the LICENSE.md file for details
And also you can add contribute.md file which is written in markdown language.
Please take a moment to review this document in order to make the contribution
process easy and effective for everyone involved.
Following these guidelines helps to communicate that you respect the time of
the developers managing and developing this open source project. In return,
they should reciprocate that respect in addressing your issue, assessing
changes, and helping you finalize your pull requests.
As for everything else in the project, the contributions to this project are governed by our team.
A bug is a demonstrable problem that is caused by the code in the repository.
Good bug reports are extremely helpful - thank you!
Guidelines for bug reports:
Use the GitHub issue search — check if the issue has already been
reported.
Check if the issue has been fixed — try to reproduce it using the
latest master
or next
branch in the repository.
Isolate the problem — ideally, create a reduced test case.
A good bug report shouldn't leave others needing to chase you up for more
information. Please try to be as detailed as possible in your report. What is
your environment? What steps will reproduce the issue? What OS experiences the
problem? What would you expect to be the outcome? All these details will help
people to fix any potential bugs.
Any other information you want to share that is relevant to the issue being
reported. This might include the lines of code that you have identified as
causing the bug, and potential solutions (and your opinions on their
merits).
Feature requests are welcome. But take a moment to find out whether your idea
fits with the scope and aims of the project. It's up to you to make a strong
case to convince the project's developers of the merits of this feature. Please
provide as much detail and context as possible.
Good pull requests - patches, improvements, new features - are a fantastic
help. They should remain focused in scope and avoid containing unrelated
commits.
Please ask first before embarking on any significant pull request (e.g.
implementing features, refactoring code), otherwise you risk spending a lot of
time working on something that the project's developers might not want to merge
into the project.
If you never created a pull request before, welcome: tada: : smile: Here is a great tutorial
on how to send one :)
Fork the project, clone your fork,
and configure the remotes:
# Clone your fork of the repo into the current directory
git clone https://github.com/<your-username>/<repo-name>
# Navigate to the newly cloned directory
cd <repo-name>
# Assign the original repo to a remote called "upstream"
git remote add upstream https://github.com/this projecthq/<repo-name>
If you cloned a while ago, get the latest changes from upstream:
git checkout master
git pull upstream master
Create a new topic branch (off the main project development branch) to
contain your feature, change, or fix:
git checkout -b <topic-branch-name>
Make sure to update, or add to the tests when appropriate. Patches and
features will not be accepted without tests. Run npm test
to check that all
tests pass after you've made changes. Look for a Testing
section in the
project’s README for more information.
If you added or changed a feature, make sure to document it accordingly in
the README.md
file.
Push your topic branch up to your fork:
git push origin <topic-branch-name>
Open a Pull Request
with a clear title and description.
Clone the repo and create a branch
git clone https://github.com/this projecthq/<repo-name>
cd <repo-name>
git checkout -b <topic-branch-name>
Make sure to update, or add to the tests when appropriate. Patches and
features will not be accepted without tests. Run npm test
to check that all tests
pass after you've made changes. Look for a Testing
section in
the project’s README for more information.
If you added or changed a feature, make sure to document it accordingly in
the README.md
file.
Push your topic branch up to our repo
git push origin <topic-branch-name>
Open a Pull Request using your branch with a clear title and description.
Optionally, you can help us with these things. But don’t worry if they are too
complicated, we can help you out and teach you as we go :)
Update your branch to the latest changes in the upstream master branch. You
can do that locally with
git pull --rebase upstream master
Afterward, force push your changes to your remote feature branch.
Once a pull request is good to go, you can tidy up your commit messages using
Git's interactive rebase.
Please follow our commit message conventions shown below, as they are used by
semantic-release to automatically
determine the new version and release to npm. In a nutshell:
Issue open :
It is not just fun.If there is really the bug or issue or suggestion the create an issue or make a pull request.
Is it good to check length of char to 128 if one can use like:
int i=234;
String word="s";
char c=(char)234
word+ss;
isUniqueChars(word)
If someone try this so should be check for that as well
As a scala fan, I hope I'm able to enjoy writing scala solutions to the whole CTCI solution sets.
nothing
When you try to pop, directly after creation, you will get Null Pointer Exception in int v = last.pop()
, since the list of stacks is empty.
public int pop() {
Stack last = getLastStack();
int v = last.pop();
if (last.size == 0) {
stacks.remove(stacks.size() - 1);
}
return v;
}
I was trying to understand why my implementation of quicksort was not working, and figured I'd look at this repo for some insights.
The array input that I am testing is:
int nbr[8] = {3, 1, 2, 0, 8, 9, 11, -1};
If I print the elements after sorting, I see:
nbr failed
-1 1 2 0 3 8 9 11
nbr_small passed
nbr_null passed
0 is at index 4, instead of index 2.
Following is main
with my modifications:
int main(void){
int nbr[8] = {3, 1, 2, 0, 8, 9, 11, -1};
int nbr_small[2] = {100, 2};
int *nbr_null = NULL;
quicksort(nbr, 8);
quicksort(nbr_small, 2);
quicksort(nbr_null, 10);
if(is_sorted(nbr, 8))
printf("nbr passed\n");
else
printf("nbr failed\n");
for (int i = 0; i < 8; i++) {
printf("%d ", nbr[i]);
}
printf("\n");
if(is_sorted(nbr_small, 2))
printf("nbr_small passed\n");
else
printf("nbr_small failed\n");
if(nbr_null == NULL)
printf("nbr_null passed\n");
else
printf("nbr_null failed\n");
return EXIT_SUCCESS;
}
Quick diff:
int main(void){ | int main(){
int nbr[8] = {3, 1, 2, 0, 8, 9, 11, -1}; | int i;
> int nbr[5] = {10, 1, 0, 5, 2};
quicksort(nbr, 8); | quicksort(nbr, 5);
if(is_sorted(nbr, 8)) | if(is_sorted(nbr, 5))
for (int i = 0; i < 8; i++) { <
printf("%d ", nbr[i]); <
} <
printf("\n"); <
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.