Skip to content

Latest commit

 

History

History
1967 lines (1648 loc) · 138 KB

README-fr.md

File metadata and controls

1967 lines (1648 loc) · 138 KB
Raw

Coding Interview University

Traductions:

Become a sponsor and support Coding Interview University!

Special thanks to:

Gitpod

Dev environments built for the cloud

Natively integrated with GitLab, GitHub, and Bitbucket, Gitpod automatically and continuously prebuilds dev environments for all your branches. As a result team members can instantly start coding with fresh dev environments for each new task - no matter if you are building a new feature, want to fix a bug, or work on a code review.

C'est quoi?

C'est un plan d'études de plusieurs mois pour aller d'un développeur web (Autodidacte, sans diplôme en informatique) à ingénieur logiciel google.

Coding at the whiteboard - from HBO's Silicon Valley

Cette longue liste a été extraite et étendue de Google's coaching notes, ce sont donc des choses que vous devez savoir. En bas, j'ai rajouté des unités supplémentaires qui peuvent être soulevées pendant l'entretien, ou qui peuvent être utiles pour résoudre des problèmes. Plusieurs unités proviennent de "Get that job at Google" par Steve Yegge, et sont parfois reflétées mot pour mot dans les notes de coaching de google.

J'ai épuré ce que vous devez savoir de ce qui est recommendé par Yegge. J'ai modifié les prérequis de Yegge. D'après les informations reçues de la part des contact travaillant à Google. Ceci est destiné aux new software engineers ou aux developpeur logiciel/web qui souhaitent devenir des ingénieurs en génie logiciel (où la science de l'informatique est requise). Si vous avez plusieurs années d'expérience et vous déclarez plusieurs années d'éxperience en génie logiciel attendez vous à un entretien plus dur. Read more here.

Si vous avez plusieurs années d'experience en development web/logiciel, notez que google font une distinction entre le développement logiciel et l'ingénieurie en génie civil.

Si vous souhaitez devenir ingénieur de fiabilité, ou ingénieur systèmes, suivez plus de cours de la liste optionelle (Réseau, sécurité)

Table of Contents

---------------- Everything below this point is optional ----------------

Pourquoi l'utiliser?

Je suis ce plan pour préparer mon entretien chez Google. J'ai construit le web, construit des services, et lancé des startups depuis 1997. J'ai un diplôme en économie, non pas d'informatique. J'ai eu beaucoup de succès dans ma carrière , mais je veux travailler chez Google. Je veux progresser sur de larges systèmes, et avec une réelle compréhension des systèmes informatiques, de l'efficacité algorithmique, de la performance des structures de données, de langages bas-niveau, et de comment ça marche. Et si vous ne connaissez rien de tout cela, Google ne vous engagera pas.

Quand j'ai commencé ce projet, je ne savais pas distinguer une pile d'un tas, ne connaissais rien sur le Grand O, rien sur les arbres, ou comment traverser un graphe. Si je devais coder un algorithme, je peux vous dire que ça n'aurait pas été très bon. Chaque structure de données que j'ai utilisée était construite dans le langage, et je ne savais pas du tout comment elles fonctionnaient sous le capot. Je n'avais jamais eu à gérer de mémoire sauf si un processus que j'exécutais donnais une erreur "Out of memory", et je devais alors trouver une parade. J'ai utilisé quelques tableaux multidimensionnels dans ma vie et des milliers de tableaux associatifs, mais je n'ai jamais créé de structures de données de zéro.

Mais après avoir suivi ce plan d'études, je suis confiant que je serai embauché. C'est un long plan. cela me prendra des mois. Si vous êtes déjà familier avec beaucoup de points, cela vous prendra beaucoup moins de temps.

Comment s'en servir?

Tout ce qui suit est très important et vous devriez attaquer ces points dans l'ordre de haut en bas.

J'utilise la typologie Markdown de GitHub, incluant les listes de tâches pour suivre les progrès.

  • Créez une nouvelle branche afin de vérifier les éléments comme ceci, mettez juste un "x" entre crochets : [x]

    Effectuez un fork d'une branche et suivez les commandes suivantes

git checkout -b progress

git remote add jwasham https://github.com/jwasham/coding-interview-university

git fetch --all

Mark all boxes with X after you completed your changes

git add .

git commit -m "Marked x"

git rebase jwasham/main

git push --force

Plus sur Markdown à la sauce Github

Get in a Googley Mood

Print out a "future Googler" sign (or two) and keep your eyes on the prize.

future Googler sign

Comment j'ai eu le job ?

I'm in the queue right now. Hope to interview soon.

Thanks for the referral, JP.

Follow moi ailleurs

My story: Why I Studied Full-Time for 8 Months for a Google Interview

I'm on the journey, too. Follow along:

John Washam - Coding Interview University

Ne vous sentez pas stupide

À propos de Google

À propos des ressources vidéos

Certaines vidéos sont disponibles uniquement en s'inscrivant à une classe Coursera, EdX ou Lynda.com. Ce sont des MOOC. Parfois, les cours ne sont pas en session, alors vous devez attendre quelques mois, donc vous n'y avez pas accès. Les cours sur Lynda.com ne sont pas gratuits.

J'apprécierais votre aide pour ajouter des sources publiques gratuites et toujours disponibles, telles que des vidéos YouTube pour accompagner les vidéos de cours en ligne.
J'aime utiliser les cours universitaires.

Processus pour l'entrevue et Préparation

Choisis une langue pour l'Entrevue

Je l'ai écrit cet article à propos de cela : Important: Choisis une langue pour l'entrevue Google

Tu peux choisir une langue avec laquelle vos êtes comftortable pour fair la partie de codage, mais pour Google, celles-ci sont les bons choix:

  • C++
  • Java
  • Python

Tu pourrais aussi faire celles-ci, mais fait de la recherche avant. Il y aurait peut-être des problèmes:

  • JavaScript
  • Ruby

Tu dois être très comfortable avec la langue et tu dois aussi savoir beaucoup à propos la langue.

Lis à propos vos choix:

Regarde les ressources pour chaque langue ici

Vous voyiez C, C++ et Python en dessous, parce que j'apprends. Il y a quelques livres qui va t'aider, regarde en dessous.

Liste de livres

Voici une liste que j'ai réduite afin de vous faire gagner du temps.

Préparation de l'entretien

Si vous avez beaucoup de temps libre:

  • Elements of Programming Interviews
    • Tout le code est en C++, très utile si vous cherchez à utiliser du C++ pendant l'entretien
    • Un très bon livre sur la résolution de problème dans son ensemble

Architecture de l'ordinateur

Si vous n'avez pas beaucoup de temps :

  • Write Great Code: Volume 1: Understanding the Machine
    • Le livre est un peu dépassé car il a été publié en 2004, mais il reste intéressant pour comprendre brièvement comment marche un ordinateur.
    • L''ateur a inventé HLA, prenez donc ses remarques et ses exemples sur le HLA avec scpetisme. Il n'est pas souvent cité mais propose de nombreux exemples sur ce à quoi un assembleur ressemble
    • Ces chapitres vous donneront des fondations :
      • Chapitre 2 - Réprésentation numérique
      • Chapitre 3 - Arithmétique binaire et les opérations bit à bit
      • Chapitre 4 - Floating-Point Representation
      • Chapitre 4 - La représentation de la virgule flottante
      • Chapitre 5 - Représentation characterielle
      • Chapitre 6 - Organisation et accès de la mémoire
      • Chapitre 7 - Type de données composites et les objets de mémoire
      • Chapitre 9 - Architecture CPU
      • Chapitre 10 - Jeu d'instructions
      • Chapitre 11 - Organisation et architecture de la mémoire

Si vous avez plus de temps (Je veux ce livre):

Sur les langages

Vous avez besoin de choisir un langage pour l'entretien (voir au-dessus). Voici mes recommendations sur les différents langages. Je n'ai pas des ressources pour tous les langages alors n'hésitez pas à en rajouter.

Si vous lisez un d'eux, vous devez d'abord avoir toutes des connaissances sur les structures de données et les algorithmes pour pouvoir faire des problèmes de codage. Vous pouvez passer toutes les vidéos de cours de ce projet, à moins que vous voulez un avis.

Additional language-specific resources here.

C++

Je n'ai pas lu ces deux-là mais ils sont bien notées et écrit par Sedgewick. Il est incroyable.

Si vous avez une meilleure recommendation pour le C++, dites le moi. Je recherche des ressources plus compréhensive.

Java

OU:

  • Data Structures and Algorithms in Java
    • par Goodrich, Tamassia, Goldwasser
    • utilisé pour du texte optionnel dans les cours d'introduction à l'informatique à l'UC Berkeley
    • allez voir le raport que j'ai fait sur le Python proposé en-dessous. Ce livre couvre les mêmes sujets.

Python

Livres optionnels

Plusieurs personnes les recommandes, cependant je pense qu'ils vont trop loin, à moins que vous ayez plusieurs années dans le dévleoppement logiciel and que vous vous attendez à un entretien bien plus difficile

  • Algorithm Design Manual (Skiena)

    • En tant qu'examen et reconnaissance de problème
    • Le catalogue algorithmique est bien plus difficile que ce que vous aurez pendant l'entretien.
    • Ce livre est divisé en deux parties :
      • class textbook on data structures and algorithms
        • pour:
          • est une bonne critique comme n'importe quel manuel le serait
          • des histoires intéressantes venant de son expérience dans la résolutionde problèmes dans l'industriel et l'académique
          • des exemples de code en C
        • contre:
          • peut être aussi dense ou impénétrable que CLRS, et dans plusieurs cas, CLRS peut être une meilleure alternative sur certains sujets
          • chapters 7, 8, 9 can be painful to try to follow, as some items are not explained well or require more brain than I have
          • les chapitres 7, 8, 9 peuvent être difficiles à suivre, comme certains points ne sont pas bien expliqués ou requiert une plus grande concentration pour comprendre
          • ne vous méprenez pas, J'aime bien Skiena, sa pédagogie et ses manières mais je ne suis pas fais pas Stony Brook
      • algorithm catalog:
        • this is the real reason you buy this book.
        • about to get to this part. Will update here once I've made my way through it.
    • To quote Yegge: "More than any other book it helped me understand just how astonishingly commonplace (and important) graph problems are – they should be part of every working programmer's toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. But the gold mine is the second half of the book, which is a sort of encyclopedia of 1-pagers on zillions of useful problems and various ways to solve them, without too much detail. Almost every 1-pager has a simple picture, making it easy to remember. This is a great way to learn how to identify hundreds of problem types."
    • Can rent it on kindle
    • Half.com is a great resource for textbooks at good prices.
    • Answers:
    • Errata

  • Introduction to Algorithms

    • Important: Reading this book will only have limited value. This book is a great review of algorithms and data structures, but won't teach you how to write good code. You have to be able to code a decent solution efficiently.
    • To quote Yegge: "But if you want to come into your interviews prepped, then consider deferring your application until you've made your way through that book."
    • Half.com is a great resource for textbooks at good prices.
    • aka CLR, sometimes CLRS, because Stein was late to the game

  • Programming Pearls

    • The first couple of chapters present clever solutions to programming problems (some very old using data tape) but that is just an intro. This a guidebook on program design and architecture, much like Code Complete, but much shorter.

  • "Algorithms and Programming: Problems and Solutions" by Shen

    • A fine book, but after working through problems on several pages I got frustrated with the Pascal, do while loops, 1-indexed arrays, and unclear post-condition satisfaction results.
    • Would rather spend time on coding problems from another book or online coding problems.

Before you Get Started

This list grew over many months, and yes, it kind of got out of hand.

Here are some mistakes I made so you'll have a better experience.

1. You Won't Remember it All

I watched hours of videos and took copious notes, and months later there was much I didn't remember. I spent 3 days going through my notes and making flashcards so I could review.

Read please so you won't make my mistakes:

Retaining Computer Science Knowledge

2. Use Flashcards

To solve the problem, I made a little flashcards site where I could add flashcards of 2 types: general and code. Each card has different formatting.

I made a mobile-first website so I could review on my phone and tablet, wherever I am.

Make your own for free:

  • Flashcards site repo
  • My flash cards database: Keep in mind I went overboard and have cards covering everything from assembly language and Python trivia to machine learning and statistics. It's way too much for what's required by Google.

Note on flashcards: The first time you recognize you know the answer, don't mark it as known. You have to see the same card and answer it several times correctly before you really know it. Repetition will put that knowledge deeper in your brain.

An alternative to using my flashcard site is Anki, which has been recommended to me numerous times. It uses a repetition system to help you remember. It's user-friendly, available on all platforms and has a cloud sync system. It costs $25 on iOS but is free on other platforms.

My flashcard database in Anki format: https://ankiweb.net/shared/info/25173560 (thanks @xiewenya)

3. Review, review, review

I keep a set of cheat sheets on ASCII, OSI stack, Big-O notations, and more. I study them when I have some spare time.

Take a break from programming problems for a half hour and go through your flashcards.

4. Focus

There are a lot of distractions that can take up valuable time. Focus and concentration are hard.

What you won't see covered

This big list all started as a personal to-do list made from Google interview coaching notes. These are prevalent technologies but were not mentioned in those notes:

  • SQL
  • Javascript
  • HTML, CSS, and other front-end technologies

The Daily Plan

Some subjects take one day, and some will take multiple days. Some are just learning with nothing to implement.

Each day I take one subject from the list below, watch videos about that subject, and write an implementation in:

  • C - using structs and functions that take a struct * and something else as args.
  • C++ - without using built-in types
  • C++ - using built-in types, like STL's std::list for a linked list
  • Python - using built-in types (to keep practicing Python)
  • and write tests to ensure I'm doing it right, sometimes just using simple assert() statements
  • You may do Java or something else, this is just my thing.

You don't need all these. You need only one language for the interview.

Why code in all of these?

  • Practice, practice, practice, until I'm sick of it, and can do it with no problem (some have many edge cases and bookkeeping details to remember)
  • Work within the raw constraints (allocating/freeing memory without help of garbage collection (except Python))
  • Make use of built-in types so I have experience using the built-in tools for real-world use (not going to write my own linked list implementation in production)

I may not have time to do all of these for every subject, but I'll try.

You can see my code here:

You don't need to memorize the guts of every algorithm.

Write code on a whiteboard or paper, not a computer. Test with some sample inputs. Then test it out on a computer.

Prerequisite Knowledge

Algorithmic complexity / Big-O / Asymptotic analysis

Data Structures

  • Arrays

    • Implement an automatically resizing vector.
    • Description:
    • Implement a vector (mutable array with automatic resizing):
      • Practice coding using arrays and pointers, and pointer math to jump to an index instead of using indexing.
      • new raw data array with allocated memory
        • can allocate int array under the hood, just not use its features
        • start with 16, or if starting number is greater, use power of 2 - 16, 32, 64, 128
      • size() - number of items
      • capacity() - number of items it can hold
      • is_empty()
      • at(index) - returns item at given index, blows up if index out of bounds
      • push(item)
      • insert(index, item) - inserts item at index, shifts that index's value and trailing elements to the right
      • prepend(item) - can use insert above at index 0
      • pop() - remove from end, return value
      • delete(index) - delete item at index, shifting all trailing elements left
      • remove(item) - looks for value and removes index holding it (even if in multiple places)
      • find(item) - looks for value and returns first index with that value, -1 if not found
      • resize(new_capacity) // private function
        • when you reach capacity, resize to double the size
        • when popping an item, if size is 1/4 of capacity, resize to half
    • Time
      • O(1) to add/remove at end (amortized for allocations for more space), index, or update
      • O(n) to insert/remove elsewhere
    • Space
      • contiguous in memory, so proximity helps performance
      • space needed = (array capacity, which is >= n) * size of item, but even if 2n, still O(n)

  • Linked Lists

    • Description:
    • C Code (video) - not the whole video, just portions about Node struct and memory allocation.
    • Linked List vs Arrays:
    • why you should avoid linked lists (video)
    • Gotcha: you need pointer to pointer knowledge: (for when you pass a pointer to a function that may change the address where that pointer points) This page is just to get a grasp on ptr to ptr. I don't recommend this list traversal style. Readability and maintainability suffer due to cleverness.
    • implement (I did with tail pointer & without):
      • size() - returns number of data elements in list
      • empty() - bool returns true if empty
      • value_at(index) - returns the value of the nth item (starting at 0 for first)
      • push_front(value) - adds an item to the front of the list
      • pop_front() - remove front item and return its value
      • push_back(value) - adds an item at the end
      • pop_back() - removes end item and returns its value
      • front() - get value of front item
      • back() - get value of end item
      • insert(index, value) - insert value at index, so current item at that index is pointed to by new item at index
      • erase(index) - removes node at given index
      • value_n_from_end(n) - returns the value of the node at nth position from the end of the list
      • reverse() - reverses the list
      • remove_value(value) - removes the first item in the list with this value
    • Doubly-linked List

  • Stack

    • Stacks (video)
    • Will not implement. Implementing with array is trivial.

  • Queue

    • Queue (video)
    • Circular buffer/FIFO
    • Implement using linked-list, with tail pointer:
      • enqueue(value) - adds value at position at tail
      • dequeue() - returns value and removes least recently added element (front)
      • empty()
    • Implement using fixed-sized array:
      • enqueue(value) - adds item at end of available storage
      • dequeue() - returns value and removes least recently added element
      • empty()
      • full()
    • Cost:
      • a bad implementation using linked list where you enqueue at head and dequeue at tail would be O(n) because you'd need the next to last element, causing a full traversal each dequeue
      • enqueue: O(1) (amortized, linked list and array [probing])
      • dequeue: O(1) (linked list and array)
      • empty: O(1) (linked list and array)

  • Hash table

More Knowledge

Trees

Sorting

If you need more detail on this subject, see "Sorting" section in Additional Detail on Some Subjects

Graphs

Graphs can be used to represent many problems in computer science, so this section is long, like trees and sorting were.

You'll get more graph practice in Skiena's book (see Books section below) and the interview books

Even More Knowledge

System Design, Scalability, Data Handling

Final Review

This section will have shorter videos that can you watch pretty quickly to review most of the important concepts.
It's nice if you want a refresher often.
  • Series of 2-3 minutes short subject videos (23 videos)
  • Series of 2-5 minutes short subject videos - Michael Sambol (18 videos):

Coding Question Practice

Now that you know all the computer science topics above, it's time to practice answering coding problems.

Coding question practice is not about memorizing answers to programming problems.

Why you need to practice doing programming problems:

  • problem recognition, and where the right data structures and algorithms fit in
  • gathering requirements for the problem
  • talking your way through the problem like you will in the interview
  • coding on a whiteboard or paper, not a computer
  • coming up with time and space complexity for your solutions
  • testing your solutions

There is a great intro for methodical, communicative problem solving in an interview. You'll get this from the programming interview books, too, but I found this outstanding: Algorithm design canvas

My Process for Coding Interview (Book) Exercises

No whiteboard at home? That makes sense. I'm a weirdo and have a big whiteboard. Instead of a whiteboard, pick up a large drawing pad from an art store. You can sit on the couch and practice. This is my "sofa whiteboard". I added the pen in the photo for scale. If you use a pen, you'll wish you could erase. Gets messy quick.

my sofa whiteboard

Supplemental:

Read and Do Programming Problems (in this order):

See Book List above

Coding exercises/challenges

Once you've learned your brains out, put those brains to work. Take coding challenges every day, as many as you can.

Challenge sites:

Maybe:

Once you're closer to the interview

Your Resume

Be thinking of for when the interview comes

Think of about 20 interview questions you'll get, along with the lines of the items below. Have 2-3 answers for each. Have a story, not just data, about something you accomplished.

  • Why do you want this job?
  • What's a tough problem you've solved?
  • Biggest challenges faced?
  • Best/worst designs seen?
  • Ideas for improving an existing Google product.
  • How do you work best, as an individual and as part of a team?
  • Which of your skills or experiences would be assets in the role and why?
  • What did you most enjoy at [job x / project y]?
  • What was the biggest challenge you faced at [job x / project y]?
  • What was the hardest bug you faced at [job x / project y]?
  • What did you learn at [job x / project y]?
  • What would you have done better at [job x / project y]?

Have questions for the interviewer

Some of mine (I already may know answer to but want their opinion or team perspective):
  • How large is your team?
  • What does your dev cycle look like? Do you do waterfall/sprints/agile?
  • Are rushes to deadlines common? Or is there flexibility?
  • How are decisions made in your team?
  • How many meetings do you have per week?
  • Do you feel your work environment helps you concentrate?
  • What are you working on?
  • What do you like about it?
  • What is the work life like?

Once You've Got The Job

Congratulations!

Keep learning.

You're never really done.

*****************************************************************************************************
*****************************************************************************************************

Everything below this point is optional. These are my recommendations, not Google's.
By studying these, you'll get greater exposure to more CS concepts, and will be better prepared for
any software engineering job. You'll be a much more well-rounded software engineer.

*****************************************************************************************************
*****************************************************************************************************

Additional Books

Additional Learning

--

Additional Detail on Some Subjects

I added these to reinforce some ideas already presented above, but didn't want to include them
above because it's just too much. It's easy to overdo it on a subject.
You want to get hired in this century, right?

Video Series

Sit back and enjoy. "Netflix and skill" :P

Computer Science Courses