Giter Club home page Giter Club logo

cracking-the-coding-interview-e6's Introduction

Cracking the Coding Interview, 6th Ed.

In order to stay sharp, I try to solve a few of these every week. The repository is organized by chapter. Each chapter contains a number of problems. There is a subdirectory for each problem. Generally speaking, I approach a problem by solving it all by myself, then I consult the solution or hints to see ways I could improve upon it. Rather than overwriting my current work when checking the solution, I will create a new package and adjust from there. I will then benchmark and compare my original version to the version I created after viewing the solution or hints. You can view aggregated benchmarks in the table below, but keep in mind that they're only relatively valid -- one solution may be faster than another, but that could change on a more cpu- or memory-constrained machine.

Additionally, in all cases, I recommend actually running the benchmarks for the package in question. I only include the benchmarks for the "base case" in the table, but oftentimes (as mentioned in my comments), there are other benchmarks that test inputs of increasing length or complexity to see how the algorithm scales.

Benchmarking

# Assumes you're in the probject root

# Run all tests, including benchmarks
go test -bench . ./...

# Run tests for a specific subdirectory
DIR='ch1/1.1'
go test -v ./$DIR/...

Results

Chapter 1 - Arrays and Strings

Problem Name Problem Description First Solution Benchmarks Revision Benchmarks Comments
ns/op B/op allocs/op ns/op B/op allocs/op
Is Unique Implement an algorithm to determine if a string has all unique characters. 397.5 96 1 N/A N/A N/A My solution was so close to the book solution that I didn't bother revising.
Check Permutation Given two strings, write a method to decide if one is a permutation of the other. 1984 496 6 3844 1731 6

The benchmarks on this one are a bit misleading -- run the full package benchmarks to see the full story. My original solution was to sort both strings and compare them, exiting early if a rune comparison failed. In the best case (strings of unequal length), this runs in O(1) time. In the normal case, it bottlenecks at the sort step with O(log(N)) time, since both sorts have to run before starting comparison.

The revised solution uses a rune-int map to count the character occurrences of the first string and compare them to the character occurrences of the second string, exiting early if there are any differences. With small strings, this performs worse. However, with larger strings, it begins to shine: As with the first solution, with strings of unequal length, it runs in O(1). With equal-length strings, it runs in O(N) time, where N is the length of both strings.

Urlify

Write a method to replace all spaces in a string with '%20'. You may assume that the given string has sufficient space at the end to hold the additional characters, and that you are given the "true" length of the string.

        EXAMPLE
        Input:   "Mr John Smith    "
        Output:  "Mr%20John%20Smith"
      
116.6 48 2 105.5 0 0

This is one of those cases where I would really advocate for the less-efficient but much more readable algorithm. Using strings.Replace and strings.Trim on the input is two lines and is really fast. That's how it's done in the "clean" version. The "clever" version, using no libraries, avoids allocations by using a rune array and looking backwards through the string. It's so eerily close to the solution the book proposes, I'm not writing a "revised" version.

cracking-the-coding-interview-e6's People

Contributors

elliott-with-the-longest-name-on-github avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.