Career Programmer, or Cracking Coding Interview

For one of our first review posts, we chose a wonderful book that we recommend to every programmer who wants to improve and develop as a professional. This is the fifth edition of one of the western bestsellers among the books on programming - Cracking the Coding Interview: 150 Programming Interview Questions and Answers , received in the Russian edition the title “Programmer Career. How to get a job at Google, Microsoft or another leading IT company . ”







For a book on IT, this book has an absolutely incredible rating on Amazon’s site (as of September 6 it’s # 388 in the overall book rating and No. 1 for the Computers & Technology section), so as the curator of this project I was just happy when "Peter" received exclusive rights to publish this bestseller in Russia.



A little about the author of the book. Gail Luckman is a nice American IT-girl who, however, during the preparation of the Russian edition managed to get married and get a second name McDowell. For several years, Gale interviewed applicants at Google, Microsoft, and Apple, and then founded her own company, CareerCup, which helps programmers prepare for interviews at major IT companies. And, of course, Gale is also famous as the author of the book Cracking Coding Interview, which has been republished in the West for many years and does not descend from the top lines of the book bestseller charts. Gayle Lackman also speaks about enterprise that she personally acts as a publisher of her own books, and we even conducted negotiations on licensing a book in Russia directly (in general, nonsense, for the modern publishing business).

')

What is this book about?



The title may give the impression that it is devoted to describing the interview process and hiring in large corporations: how to dress, how to behave, what is the practice of conducting interviews with Google or Microsoft, and how they refuse to disagreeable candidates in each company. Not really.



By the way, an interesting story: our colleagues from the Ozon online store were also embarrassed by the name of the book, and they put it in the “Personnel records and records management” section, and we had some effort to return the publication to the correct branch of the classifier .



So, Cracking Coding Interview must be placed on a par with classic books on algorithms that make programmers think and improve themselves. The above topics are really given a little space (namely, 50 pages), but the main and most valuable part of the book is almost 400 pages of real questions and test tasks that applicants receive during interviews with the most famous IT companies in the world. Of course, this book will help you if you are really going to interview at Google, but by itself it will give any programmer the opportunity to take a fresh look at their skills and their development as a professional, offering not only abstract, but also very real tasks and solutions that can be used in practice.



In total, the book contains 150 tasks (and the correct answers to them!) On topics such as OOP, testing, recursion, trees and graphs, databases, streams and probability theory, etc. Similar content of the book you can see on this link (PDF file on the publisher's website).



And as a seed, we suggest you try one of the test tasks from the book in the section “Advanced Tasks”.

The task

Write a method that generates a random sequence of m integers from an array of size n. All items are selected with the same probability.

The answer from the book will be published in the comments tomorrow, September 7, at 18:00. Please book owners do not give hints.



And below, as an example, we give another task from the section "Recursion and dynamic programming" with the correct answer.

The task.

Implement the paint fill function, which is used in many graphic editors. Given a plane (two-dimensional array of colors), a point and a color, which you need to fill in all the surrounding space, painted in a different color.



Decision

First of all, let's visualize how the method works. When we call paintFill (“press” the fill button in the graphic editor), being, for example, on a green pixel, we want to expand the boundaries. We move further and further by calling the paintFill for the surrounding pixels. If the color of the pixel is different from green, we stop.



You can implement this algorithm recursively:



1 enum Color {

2 Black, White, Red, Yellow, Green

3}

four

5 boolean paintFill (Color [] [] screen, int x, int y, Color ocolor,

6 Color ncolor) {

7 if (x <0 || x> = screen [0] .length ||

8 y <0 || y> = screen.length) {

9 return false;

ten }

11 if (screen [y] [x] == ocolor) {

12 screen [y] [x] = ncolor;

13 paintFill (screen, x - 1, y, ocolor, ncolor); // left

14 paintFill (screen, x + 1, y, ocolor, ncolor); // right

15 paintFill (screen, x, y - 1, ocolor, ncolor); // top

16 paintFill (screen, x, y + 1, ocolor, ncolor); // bottom

17}

18 return true;

nineteen }

20

21 boolean paintFill (Color [] [] screen, int x, int y, Color ncolor) {

22 return paintFill (screen, x, y, screen [y] [x], ncolor);

23}



Pay attention to the order of x and y in the array screen [y] [x] and remember that when you solve a problem related to computer graphics, you need to use such an order. Since x corresponds to the horizontal direction, this variable describes the column number, not the row number. The value of y corresponds to the line number. In this place it is very easy to make a mistake, both at the interview and during daily programming.

• Book on the publisher site
• Book on Ozon