Month: March 2017

CodeFights Solves It, Interview Practice Edition: productExceptSelf

CodeFights Solves It, Interview Practice Edition: productExceptSelf

If it’s been asked as an interview question at Amazon, LinkedIn, Facebook, Microsoft, AND Apple, you know it’s got to be a good one! Have you solved the challenge productExceptSelf in Interview Practice yet? If not, go give it a shot. Once you’re done, head back here. I’ll walk you through a naive solution, a better solution, and even a few ways to optimize.

…Done? Okay, let’s get into it!

The object of this problem is to calculate the value of a somewhat contrived function. The function productExceptSelf is given two inputs, an array of numbers nums and a modulus m. It should return the sum of all N terms f(nums, i) modulo m, where:

f(nums,i) = nums[0] * nums[1] * .... * nums[i-1] * nums[i+1] * ... * nums[N-1]

Whew!

We can see this most easily with an example. To calculate productExceptSelf([1,2,3,4],12) we would calculate:

  • f([1,2,3,4], 0 ) = 2*3*4 = 24
  • f([1,2,3,4], 1 ) = 1*3*4 = 12
  • f([1,2,3,4], 2 ) = 1*2*4 = 8
  • f([1,2,3,4], 3 ) = 1*2*3 = 6

The sum of all these numbers is 50, so we should return 50 % 12 = 2.

A naive solution

The explanation of the code suggests an implementation:

This is technically correct, but the execution time is bad. Each call to the function f(nums, i) has to do a scan (and multiplication) in the array, so we know the function is O(N). We call f(nums,i) a total of N times, so this function is O(N2)!

Sure enough, this function passes all the test cases. But it gives us a time length execution error on test case #16, so we have to find a more efficient solution.

Division is a better solution (but still not good enough)

A different way of approaching this problem is to find the product of all the numbers, and then divide by the one you are leaving out. We would have to scan to see if any of the numbers were zero first, as we can run into trouble dividing by zero. Essentially, we’d have to deal with that case separately, but it turns out that any array nums with a zero in it is easy to calculate. (This would be a good extension exercise!)

If we look under the constraints of the code, we are told that 1 <= nums[i], so we don’t have to worry about this case. We can simplify our problem to:

Again, we get a time execution error! Note that the running time is much better. We make a pass through the array once to get productAll, then a pass through the array again to get the f_i, and one more pass through the array to do the sum. That makes this is a O(N) solution!

Why is the interviewer asking this question?

In other words, what is this question testing? As I mentioned in the introduction, the function we’re calculating is a little contrived. Because it doesn’t seem to have any immediate applicability, the companies asking us this question in interviews are probably looking to see if we know a particular technique or trick.

One of the assumptions that I made when calling the algorithms O(N) or O(N2) was that multiplication was a constant time operation. This is a reasonable assumption for small numbers, but even for a computer there is a significant difference between calculating

456 x 434

and

324834750321321355120958 x 934274724556120

There are a couple of math properties of residues (the technical name for the “remainders” the moduli give us) that we can use. One is:

(a + b + c ) % m is the same as (a % m + b % m + c % m) % m

This is nice because a%m, b%m, and c%m are all small numbers, so adding them is fast.

The other property is:

(a * b) % m is the same as ((a % m) * (b % m)) % m

That is, I can multiply the remainders of a and b after division by m, and the result I get will have the correct remainder.

At first glance, this doesn’t seem to be saving us much time because we’re doing a lot more operations. We are taking the modulus three times per multiplication, instead of just once! But it turns out that the modulus operation is fast. We more than make up for it by only multiplying small numbers.

So we can change our calculation of f_i to

This still isn’t good enough to pass the test, but we’re getting there. The problems we still have are:

  1. The number productAll is still very large
  2. Integer division is (relatively) slow

Our next approach will eliminate both of these problems.

Note: NOT a property

The big number is productAll, so you might hope that we can find productAll % m, and _then_ do the division. This doesn’t work.

The mathematical problem is that non-zero numbers can be multiplied to give 0, so division is problematic. Looking at division, and then taking a modulus:

48 / 6 = 8_ so _(48 / 6) % 12 = 8

but reversing the order (taking the modulus, then doing the division) yields:

(48 % 12) / 6 = 0 / 6 = 0

So we can’t take the modulus of productAll and avoid big numbers altogether.

Prefix products (aka cumulative products)

We can speed up the execution by building by an array, prefixProduct, so that prefixProduct[i] contains the product of the first i-1 numbers in nums. We will leave prefixProduct[0] = 1.

The neat thing about this array is that prefixProduct[i] contains the product of all elements of the array up to i, not including i. If we also made a suffixProduct such that suffixProduct[i] was equal to all the product of all numbers in nums past index position i, then the productExceptSelf for number i would just be the product of all numbers except the ith one = prefixProduct[i] * suffixProduct[i]

We have eliminated one of the costly operations: division! We can also avoid seeing large numbers in the multiplication as well, by changing the step inside the loop to contain a modulus.

Our new solution is:

This finally works! We’ve eliminated all multiplication by big numbers (but still have multiplications by small numbers), and no divisions at all. But we can still do better…

For the technical interview, an even better solution

It turns out that we don’t need to have a suffixProduct. We can build it as we go! This is the accumulator pattern:

Takeaways

The main things you’re being asked to think about in this task are:

  • Arithmetic operations aren’t always constant time. Multiplying big numbers is much slower than multiplying small numbers.
  • Operations are not all the same speed. Integer modulus is very fast, addition and multiplication are fast, while division is (relatively) slow.
  • Some number theory: You can multiply the residues of numbers, instead of the numbers themselves. But you cannot divide by residues, or divide the residues unless you have certain guarantees about divisibility.
  • The idea of precomputing certain operations, which is where the prefixProduct comes in.

Other problems that use the cumulative or prefix techniques are finding the lower and upper quartiles of an array, or finding the equilibrium point of an array. (I cover prefix sums in a lot more detail in this article.)

Footnote: Horner’s Method

One of the solutions presented used a method of calculation known as Horner’s method. Take the cubic

f(x) = 2 x^3 + 3 x^2 + 2 x + 6

To evaluate f(3) naively would require 8 multiplications (every power x^n is n copies of x multiplied together, and then they are multiplied by a coefficient), and three additions. There is a lot of wasted calculation here, because when we calculate x^3 we calculate x^2 in the process! We could store the powers of x separately to reduce the number of multiplications.

Horner’s method is a way of doing this without using additional storage. The idea is, for example, that we can use operator precedence to store numbers for us:

3 x^2 + 2 x + 6 = (3 * x + 2) * x + 6

The left side has a (naive) count of 4 multiplications and 2 additions, while the right side has 2 multiplications and 2 additions. Moving to the cubic is even more dramatic:

f(x) = 2 x^3 + 3x^2 + 2 x + 6 = ( (2 * x + 3) * x + 2 ) * x + 6

This takes our 8 multiplications and 3 additions to only 3 multiplications and 3 additions!

The shortest solution so far, submitted by CodeFighter k_lee, uses Horner’s method, along with taking moduli at the different steps. See if you can decipher it.

Tell us…

Did your solution for this Interview Practice challenge look different than mine? How did you approach the problem? Let us know over on the CodeFights forum!

March Marathon Recap

March Marathon Recap

The March Marathon on March 25 was amazing! Over 700 CodeFighters signed up, but of course only one could win… And what a victory it was! Congratulations to CodeFighter urandom, who pulled off a stunning last-minute upset.

CodeFights Founder Tigran Sloyan and Content Engineer Damien Martin provided us with live commentary during the marathon. It was awesome to have them talk through the top solutions just minutes after they were submitted!

If you missed it the first time around, check out the recording here or on our YouTube channel.

You can also take a stab at the problems yourself on the archived page.

If you’re excited about the upcoming April marathon, well, join the club! We are too. Keep April 29 open on your calendar, and we’ll update you with the link to register soon. If you aren’t going to compete, Tigran and Damien will be doing another livestream so that you can watch the action as it unfolds!

Make Your Engineering Resume Stand Out

Make Your Engineering Resume Stand Out

Love ’em or hate ’em (and we’re guessing you don’t love them), resumes are still part of the typical job search process. But putting your resume together can feel like one of the hardest parts of the whole thing! What should you include? What should you leave out? And do you need to include your home address? (Hint: City and state? Sure. Street address? NO.)

A typical engineering job posting can generate hundreds of applications. Only a relatively small percentage of those resumes ever make it in front of a recruiter – and the percentage of those applications that lead to interviews is tiny.

Make your resume stand out
This monkey is having trouble with his resume.

With odds like those, you need to ensure that your resume stands out.

Caity Barnes, recruiter extraordinaire at CodeFights, is going to let you in on some insider knowledge: exactly what she looks for when she’s looking at resumes for engineering roles.

“In a lot of ways, writing a good engineering resume isn’t any different than writing any other kind of resume – make sure it’s well-formatted and that everything’s spelled right. But there are some really specific things that I look for when we’re trying to fill engineering roles.”

Format

  • Recruiters tend to scan resumes in a very specific order. They look at your geographic location, the last job you had, and your education, then the skills list. If they get past that point, that’s when they’ll dive into the other jobs that you’ve listed, and then at projects, achievements, and anything else you’ve included. 
  • If you try to get creative with formatting, fonts, or layout, Caity says that many recruiters will glance at it, decide that it’ll be too hard to scan, and toss it. Don’t let this happen to you! (This applies less if you’re applying for a design job, of course, but most CodeFighters are probably applying for engineering jobs.)
  • A one-page resume is best. If you just can’t cut it down that much, at least make sure that the most important stuff is on the first page. Many recruiters won’t make it further. Hook their attention by putting the most eye-catching stuff first.
  • For every job you list, make it easy for the recruiter to see the company’s name, your title, and how long you were there.
  • Bullet points are your friend! Instead of writing in paragraphs, use bullet points. They’re much easier for recruiters to scan.
  • Don’t talk about yourself in the third person – who are you, the Queen of England? Instead of saying “Bart designed and implemented a user feedback module using Django”, say “I designed and implemented…” Or better yet, since you’re using bullet points, say “Designed and implemented…”
  • In Caity’s opinion, it’s not necessary to include an objective statement at the top of your resume. They’re usually so generic that they’re not useful, and recruiters tend to gloss over them. If you do choose to include one, make it a statement about the kind of company culture that you’re looking for, instead of the kind of work you want to do.
  • Caity says, “I don’t care if you went to the best school in the country – your work experience is more important!” If you’re a very recent grad, you can put the Education section at the top, but otherwise put it at the bottom of the page.
  • Run your resume through spell check and grammar check, and get a few different people to proofread it. While it might seem unimportant – damn it, Jim, you’re an engineer, not an editor! – in some cases a typo or incomprehensible sentence might disqualify you immediately.
Jim, your resume is a mess.
Jim, your resume is a mess.

Content

  • Make sure that you include relevant keywords in your resume. Caity says that when a recruiter’s skimming, they need to be able to pick out important items immediately. And these keywords will change depending on the type of jobs you’re applying for. Think about the skills you’d be highlighting if you were applying for front end jobs vs Java engineering jobs.
  • Be thoughtful about how you include skill items like languages or frameworks. If you list Go, there’s a big difference having used it daily on the job vs having taken a 30 minute seminar on it 2 years ago. Recruiters want to be able to get a sense of how proficient you are. It’s also helpful if you can talk about what you did with these tools so that the recruiter can weight them accordingly.
  • Keep in mind that recruiters tend not to be super technical. From Caity: “We know more about impact than super technical details, so focus on business outcomes that you were a part of.” It’s also helpful to quantify your contributions. (For instance: Were you an individual contributor or part of a team? Was it a big or small team? How many concurrent users did your tool support? How much data did it process daily/weekly?)
  • Try to highlight solo projects or projects to which you contributed a lot, whether they’re for work or side projects. Creating something from scratch is huge and shows initiative, and it’s a great signal to recruiters that you’re a problem solver.
  • “Spell as much out for the recruiter as possible,” Caity says. They are not going to have time to do internet detective work, at least on the first pass. If you worked at a small startup, a short blurb about what the company is helpful. What industry is it in, what size is it, what sort of funding did it get? And if there’s a short tenure on your resume (less than a year), call it out and explain why you left – contract ended, company went under, etc.
  • Put links to your GitHub and your LinkedIn, because they give the recruiter a good overall picture of you. Including other social media can be a little tricker. What does your Twitter feed look like? If you tweet about work-appropriate and relevant topics, go for it. Otherwise, leave it off your resume. Same goes for your blog.
  • Speaking of GitHub, make sure that your profile is something that you’re proud of. Caity says that most recruiters will share it with their hiring managers or interviewing teams to review before taking next steps with candidates. So take some time to clean yours up. Repos that are your own work, rather than forks off other people’s, are good, as is a strong commit history.
  • For recent grads or students – if your GPA is lower than 3.5, don’t include it. If you’ve taken advanced courses on really relevant topics (especially if they were practical, rather than theoretical), you can list them in your Education section. And remember that class projects or coursework aren’t the same thing as side projects, and recruiters won’t weigh them the same.
  • Feel free to put your personality into the resume. What are your hobbies and special interests? Caity says that recruiters love being able to get a sense of who you are! But this stuff should go at the bottom of the page. Remember, recruiters scan top to bottom. You need to put all of the important, must-see stuff at the top of the page.

tl;dr

To boil all of these down into a few principles: Your resume should be clear, concise, and easy to digest. Keep the layout simple and easy to scan. In terms of content, include information that makes it so the recruiter doesn’t have to guess about your history or do extra digging on the internet.

Remember, recruiters aren’t maliciously ignoring your resume! They’re trying to optimize the number of resumes that they can look at for any given engineering job in order to quickly find the most qualified candidates. If you follow these guidelines, your resume stands a much better chance of making it into the “follow-up” pile.

Your resume looks amazing
Your resume looks amazing!

You’re reading an article about how to make your resume stand out, so my spidey senses tell me you might be looking for a job! Did you know that CodeFights can connect you with hundreds of tech companies that are actively seeking qualified engineers – all with only one application? Head to codefights.com/jobs and start finding that dream job today!  

Tell us…

Do you have any tried-and-true tips on how to make your resume stand out? Head over to the CodeFights forum and let us know!

CodeFights Solves It: hostnamesOrdering

CodeFights Solves It: hostnamesOrdering

The Challenge of the Week that ended on March 21 was hostnamesOrdering. Only 72 CodeFighters submitted solutions – this was a tricky one! In this breakdown, I’m going to walk you through my thought process in writing a solution.

In this database challenge, the task is to take a table of numeric ids and hostnames, and return a sorted version of the table. The challenge is that we have to order the hostnames by the reverse hostnameThe hostname is a string of domains separated by periods, such as codefights.com or www.github.com. The domains don’t include any protocols (such as http://), nor do they include any paths (such as codefights.com/forums). The general form of a hostname is domain1.domain2. … .domainN. The reversed hostname is domainN. … .domain2.domain1. For example:

Hostname...has the reverse hostname
www.codefights.comcom.codefights.www
dev.mysql.comcom.mysql.dev
web.mit.eduedu.mit.web
codepen.ioio.codepen

Note that the list above is ordered by the reverse hostname. We are told that there are at most 3 domains in any given hostname that appears in this challenge.

Getting started

Let’s start with an example of the table hostnames:

idhostname
1workbench.mysql.com
2codefights.slack.com
3codefights.com
4snarknews.info
5sololearn.com
6dev.mysql.com
7codepen.io
8com

Let’s suppose for a moment that we have a way of generating the reversed hostnames, which will actually be the hardest part of the challenge.

idhostnamereversed
1workbench.mysql.comcom.mysql.workbench
2codefights.slack.comcom.slack.codefights
3codefights.comcom.codefights
4snarknews.infoinfo.snarknews
5sololearn.comcom.sololearn
6dev.mysql.comcom.mysql.dev
7codepen.ioio.codepen
8comcom

The query we want to return is:

which would return:

idhostname
8com
3codefights.com
6dev.mysql.com
1workbench.mysql.com
2codefights.slack.com
5solonews.com
4snarknews.info
7codepen.io

Reversing the domain name

We won’t actually construct an explicit reversed column. Instead, we will generate the pieces of the domain we want on the fly. To do this, we will be using the SUBSTRING_INDEX function. From the documentation, we see that SUBSTRING_INDEX( string, delim, count) returns a substring.

If count is positive, SUBSTRING_INDEX( string, delim, count) returns the substring from the beginning to the countth occurrence of delim. For example:

If count is negative, SUBSTRING_INDEX finds the |count|th occurrence of delim from the right, and returns the substring from there to the end of the string. For example:

Using the same example we’ve been working with, here is a query that splits the hostname into three pieces. Using SUBSTRING_INDEX, we can extract the top level domain, the midlevel domain, and the lowest level of domain just by changing the index value.

This would work if every domain has exactly three pieces. Unfortunately, some domains only have one or two pieces. What is actually returned is:

idhostnametopmid
3codefights.comcomcodefights.com
8comcomcom
6dev.mysql.comcommysql.com
1workbench.mysql.comcommysql.com
2codefights.slack.comcomslack.com
5solonews.comcomsolonews.com
4snarknews.infoinfosnarknews.info
7codepen.ioiocodepen.io

The first two rows are in the wrong order. They match at the top level (i.e., they are both .com domains). The com domain has no lower level, but the SUBSTRING_INDEX just returns the entire string com again. Since codefights.com is earlier in the alphabet than com, the table puts codefights.com first. What should happen is that codefights should be compared to the empty string, and com should appear first.

One trick to fix this problem is to prepend the hostnames with ‘…’, guaranteeing that there are three periods in each domain. So our query is now:

Writing down just the first four rows, this query returns:

idhostnametopmid
8comcom.com
3codefights.comcomcodefights.com
6dev.mysql.comcommysql.com
1workbench.mysql.comcommysql.com
…….……..…….……..

This has everything in the right order!

A problem and a workaround

In principle, we just have to eliminate the top and middle column, so we are only reporting the id and hostname. Before making this change, we can try running this in CodeFights. When we do it, we run into a problem: the CodeFights MySQL engine returns workbench.mysql.com before dev.mysql.com!

This seems to be a bug; running MySQL on a local machine returns dev.mysql.com before workbench.mysql.com. However, ordering by the hostname on CodeFights returns the opposite. When using ORDER BY top, mid, hostname, workbench.mysql.com appears first. This seems wrong, since both these hostnames have identical top and mids, so the ordering should be determined by hostname.

Part of being a programmer is working around issues in any software! The problem we are encountering comes from doing multiple orderings. Our workaround will be to concatenate the top, middle, and hostname into one string. We will separate the top, middle, and hostname by a space, because spaces cannot occur in a domain and spaces appear earlier in ASCII than any letter.

So our workaround is:

This orders dev.mysql.com and workbench.mysql.com correctly.

Eliminating columns

Now we need to eliminate the top and mid columns. We could do a subquery, but instead we will actually construct the top and the middle strings as part of the ORDER BY clause.

Our solution ends up looking like this:

This solution only selects the desired columns. Notice that in the ORDER BY we have a single string, made from the “top” level domain, a space, the “middle level” domain, a space, and then the hostname. This gets around the implementation bug, and gets us a solution with 188 characters.

On a local MySQL database, we don’t need the final concatenation, and we could use multiple ordering to get:

Going further

As a code golfing exercise, we have some compact solutions. As a coding exercise, you might be interested in trying to solve the general case where we don’t have a limit on the maximum number of domains in a hostname!

This takes us back to our original solution:

where the interesting exercise is to create a custom function reverse_hostname. If you get stuck, this StackOverflow post might be useful.

Tell us…

How did you tackle this challenge? What do you think about the approach I took in solving it? Let us hear from you in the CodeFights forum!

CodeFights’ Top 5 Interview Tips for Developers

CodeFights’ Top 5 Interview Tips for Developers

Finding a new job can be a long process that takes weeks… or even months. This tedious process becomes amplified for software engineers. Since software engineering is a hard skill, most companies try to devise various ways of assessing that skill during the interview. This adds more time, layers of complexity, and obstacles to the job seeking process.

At CodeFights, we help software engineers practice and improve their skills through our gamified educational platform. We also connect them to hundreds of top companies when they’re ready for their next adventure. This means that we get to see what technical interviews are like across many different companies and what developers can do to increase their chances of success.

Top 5 tips for technical interviews

We’ve taken what we’ve learned and distilled it into 5 cardinal rules for engineers who want to make the interview process less painful and score their dream job:

  1. Practice using real interview questions! Great developers often think “This is what I do for a living and I’m good at it”. This makes it tempting to walk into an interview without having practiced much. But the reality is that the interview questions you’ll face at most companies are miles away from what you do at your day job. Doing some research and practicing using real questions that the company uses in its interviews will pay off big-time during the actual interview. There aren’t many high-quality free resources available for this, so we’ve tapped into the knowledge base of our large community to create Interview Practice. Interview Practice is a collection of real interview questions asked at top tech companies, categorized by company and by topic.
  2. Ask a lot of questions during the interview. Some engineers think that asking questions is a sign of poor skill or a lack of understanding, but in reality it’s the opposite. Most questions that you’ll be asked during technical interviews are intentionally vague. The interviewer’s goal is to see if you can ask the right questions before diving in. The worst thing you can do during a technical interview is solve something that you weren’t asked to solve! So ask questions until you are absolutely sure you have all the details.
  3. Use the collective knowledge of your own network and information from sites like Glassdoor to find out what the interview process at the company is like. At some companies (like Google), you interview with 4-5 people onsite and they all have to say “yes” for you to be hired. At others (like Oracle), you still interview with 4-5 people, but they are all on different teams. As long as one says “yes”, then you’re in. Knowing what you are dealing with and what the thinking process behind the scenes is will dramatically improve your chances of doing well in the interview.
  4. Apply to as many companies as you can. Some candidates make the mistake of only talking to a few select companies. They’re basically trying to hit a bullseye with only a few shots! This only works in theory. In practice, it’s very hard for you as an outsider to understand what a company is like and what they work on. So interviews are also a way for you to interview the company and see if it’s something you are ready to commit to. On top of that, doing more interviews provides you with much-needed practice. And when you finally get to the offer stage, having several offers helps you negotiate the best compensation package.
  5. Be mentally prepared for a negative outcome. Interviews are run by human beings, and human beings tend to be quite subjective. So no matter how good you are and how much you prepare, most of your interviews are going to have a negative outcome. You have to be mentally prepared for this. Many candidates take it very personally when a company comes back to them with a “no”. By setting realistic expectations at the outset and treating each interview as an experience to learn from, every “no” you receive – and you will get some! – won’t feel like the end of the world.

Job interviews are inevitably stressful. Engineering interviews are even more so because they try to directly evaluate your skills. It’s natural to be nervous, but the more you prepare, the better equipped you will be to ace whatever the interviewer throws your way.

Join us!

At CodeFights, we try our best to keep our interview process interesting and fun, and we’re actively growing our team. Are you passionate about changing the future of education and talent discovery? Check out our jobs page and apply!

Tell us…

What are your sure-fire interviewing secrets? Let us know what you think on the CodeFights forum!

Mastering the Basics for Technical Interviews

Mastering the Basics for Technical Interviews

It’s natural to want to focus on really tricky concepts when you’re preparing for interviews. You know you’re going to get some really hard problems, and so that’s the stuff that you want to practice! But we hear stories all the time about people who prepare for higher-level questions, only to completely blank out when they get questions about the basics. And we definitely don’t want that to happen to you!

You absolutely need to be able to answer questions about programming basics quickly and easily, because for most interviewers, this represents the baseline of what you should be able to do. And if you don’t perform well, this can automatically put you out of the running even if you’ve done well on the rest of the interview.

The basics

Consider the fizzBuzz conundrum that Imran Ghory and others have written about: A surprising amount of seemingly well-qualified applicants are unable to answer even trivial programming questions during technical interviews. An example of this sort of question is the old standby fizzBuzz, which asks the interviewee to write a program that takes a number n and print out the numbers from 1 to n, replacing multiples of 3 with fizz, multiples of 5 with buzz, and multiples of both 3 and 5 with fizzbuzz. (Go ahead, take a minute and do it. We know you want to.) While the odds that an interviewer actually asks you to solve fizzBuzz is pretty low since it’s well-trod territory at this point, it’s a good example of the level of this type of “basic” question.

Questions like this are aimed at making sure that you have a fundamental understanding of how to write code. The interviewer also wants to make sure that you can problem-solve in ways that take test cases and optimization into account. Since this sort of question is usually asked while you’re whiteboarding, interviewers also use this to gauge how you think while you’re working through a problem.

Know your tools

It’s also important that you actually know your favored interviewing language well. Can you write loops, use appropriate methods when they’re available to you, and use the right terminology when you’re discussing elements of the code you’re writing? If not, it’s going to show and the interviewer is going to pick up on it.

Technical interview topics

What basic things should you be really solid on in order to prepare for technical interviews? They tend to fall into a few basic categories:

  • String manipulation (Generate permutations, find substrings, reverse a string, substitute specific letters…)
  • Array manipulation or traversal
  • Number manipulation
  • Pattern matching (If necessary, be ready to write your own regular expression rather than using a regex library)
  • Condition matching (Find the largest/smallest/missing element)

Remember, this represents the baseline of what you should know in order to succeed in an interview (not to mention on the job). You’ll actually need to know a lot more advanced stuff to ace the interview – and don’t worry, Interview Practice has you covered on that front too. But even if you do well on more advanced topics, if you don’t wow the interviewer on the simple ones they’re going to question how capable you actually are. So don’t neglect the basics! Here are some great examples on Interview Practice to get you started:

String manipulation:

Array manipulation or traversal:

Number manipulation:

Pattern matching:

Condition matching:

Tell us:

Have you ever encountered a basic programming question in an otherwise hard interview? How did you handle it? Let us know on the CodeFights forum!

CodeFights Solves It: pastEvents

CodeFights Solves It: pastEvents

A little while back, our Challenge  of the Week was a tricky database challenge called pastEvents. 281 of our awesome CodeFighters solved it! I’ve created a walkthrough of the problem and a few different tactics for finding a solution. Here’s the problem, in case you need a refresher:

During the most recent social event you suddenly realized that you had forgotten your USB drive on one of the previous events. You are pretty sure that you had your flash drive with you just last week, which means that it was probably lost during one of the events of the last 7 days. So, you would like to find all the events you attended during this period.

And the output should be:

A table of all names and dates of events within 7 days of the most recent event, not including the most recent event, order from most to least recent.

The problem gives us a database with the table events, as well as a sample dataset:

idnameevent_date
1TGIF2016-11-07
2TGIF2016-11-28
3Weekly meeting2016-12-01
4Weekly meeting2016-12-02
5Client meeting2015-12-03

How would we construct the solution by hand?

  1. We would look for the most recent date, in this case the event with id 4 is the most recent with an event_date of 2016-12-02.
  2. We would then SELECT all dates that occur within 7 days before 2016-12-02. This would select the events with ids 2 and 3.
  3. Finally we would sort the returned events based on event_date with ORDER BY.

With this strategy in mind, let’s start putting the pieces together!

Step 1: Find the most recent event

For this, we need to find the maximum value of the event_date column:

The time taken for this query will scale linearly with the number of events we have stored, which is about the best we can hope for. After all, to find the maximum we have to look at the date of every single record!

Here is a different approach that also selects the most recent date:

This approach is to take all the dates, order them from latest to earliest, and then select the first one off the list. This approach isn’t as good, because it isn’t as clear what the code is trying to do. If you are reviewing this code, you have to get to the very end of the line to realize that we’re only picking one value. You have to carefully think if you want to order the list in ASCending or DESCending order. A naive implementation of this query would also be slower than our first attempt, because first the entire list would need to be sorted before the most recent event was selected (MySQL is almost certainly smart enough to optimize this away). Finally, if our goal is to get a short solution, this line is less clear and more verbose than our attempt based off the max function.

Now we need to write a query that uses the latest date and selects events in the 7 days prior to our event. We can either use our query above as a subquery, or store the results as a variable and use that. We will start by using the variable @recent, as it leads to more readable code, and then optimize once we’re done.

Our solution so far looks like this:

Step 2: Select events within 7 days of @recent

Given an event_date, we need to determine if it was within 7 days of @recent. MySQL provides 60 functions for dealing with date calculations. Some of the options relevant to us are:

DATE_ADD(event_date,INTERVAL 7 DAY) > @recentTrue if event_date + 7 is earlier than @recent.
Does include most recent event.
DATE_SUB(@recent, INTERVAL 7 DAY) <= event_dateTrue if event_date is 7 or fewer days earlier than @recent.
Does include most recent event.
DATEDIFF(@recent,event_date) <= 7Same as DATE_SUB, but does subtraction in days (which saves some characters).
Does include most recent event.

All of these include the most recent event. We can throw out the most recent event by adding another DATEDIFF, or by using BETWEEN to ensure that our DATEDIFF is also bigger than 1. Because we are assured that there is at most one event per day, eliminating the most recent one can be achieved with event_date != @recent.

We now add a SELECT with a WHERE clause to get the events within 7 days, so our code now takes the form:

There is a really sneaky way of eliminating the extra clause to see if the event is the most recent event. We are interested in selecting events where

 

Instead of using subtraction, what do we know about the reciprocal of date differences? We know that

 

 

We get the lower limit by @recent being 7 days ahead of event_date. If the difference between the dates is 8 days, then 1/(@recent-event_date) is . The cool part is the upper limit is achieved if @recent and event_date are one day apart. If we look at the case where @recent and event_date are the same day, then 1/(@recent-event_date) is undefined, so MySQL will return false for any comparison. This means we don’t have to worry about the upper limit, and instead we only care if

 

 

Writing this another way:

 

 

Our shorter (but conceptually harder to understand) solution is

Step 3: Order the output

Once we’ve gotten this far, it’s simply a case of adding an ORDER BY clause to the end. Finally we have something that passes the test cases and the hidden tests! Let’s call it a solution with 171 characters:

Refinement 1: Subclause

It’s clear that we could get shorter code by naming @recent something like @r. We can also eliminate some characters by running a subclause to get the maximum date:

This code JOINS every event with the single value from the subclause SELECT MAX(event_date) as r FROM Events, which is just the variable we stored in @recent in our previous example. We want to be careful with JOINS, because the number of rows in the returned table is the product of the rows in the two input tables. In this case, the derived table recent only has one row, so we only have to sort through the same number of events as we started with.

Refinement 2: Change >= to >; eliminate BEGIN and END

We can also eliminate a character by noting that DATEDIFF has to return an integer, so requiring 7/DATEDIFF(r,event_date) >= 1 gives the same dates as 8/DATEDIFF(r,event_date) > 1. MySQL doesn’t require BEGIN and END for procedures, so we can eliminate those too. This gets us to:

The shortest solution

The very short solutions to this challenge took a very different approach from the one I just demonstrated. Here’s the code submitted by CodeFighter gennadi_m:

The first step is taking the Event table, and taking the cartesian product (i.e. OUTER JOIN) with itself. In our case, this gives us a 25 row table:

e.ide.namee.event_datev.idv.namev.event_date
1TGIF2016-11-071TGIF2016-11-07
1TGIF2016-11-072TGIF2016-11-28
1TGIF2016-11-073Weekly meeting2016-12-01
1TGIF2016-11-074Weekly meeting2016-12-02
1TGIF2016-11-075Client meeting2015-12-03
2TGIF2016-11-281TGIF2016-11-07
..................

The columns are grouped by “column 2” in the output, e.event_date. The group by is only important when we are using an aggregate function, which is this case is max. The first group on this table is the group e.event_date = 2016-11-07, for example. Out of this group, we ask for the maximum v.event_date, which is 2016-12-02. We can only use aggregate properties, so our table becomes:

e.ide.namee.event_datemax(v.event_date)
1TGIF2016-11-072016-12-02
2TGIF2016-11-282016-12-02
3Weekly meeting2016-12-012016-12-02
4Weekly meeting2016-12-022016-12-02
5Client meeting2015-12-032016-12-02

The combination of using a self-join, grouping on event date,  and max aggregation is just a complicated way of adding the most recent date to every row.

While the query is a lot smaller, joining a table with itself squares the number of entries in it. MySQL might be able to optimize your query in some cases, but you want to be careful before trying this trick in production code!

Tell us…

How did you tackle this challenge? What do you think about the approach I took in solving it, and the refinements I added? Let us hear from you in the CodeFights forum!

Introducing Interview Practice

Introducing Interview Practice

Let’s not kid ourselves – preparing for interviews isn’t exactly fun. In fact, it can be downright nerve-wracking! The best way for you to be able to walk into an interview feeling poised and confident is to practice, practice, practice – and to know what to expect during the interview. But it’s hard to know what kind of questions you should practice when you’re preparing, and it can be even harder for you to gauge how well you’re doing when you’re practicing. That’s why CodeFights is giving you a new secret weapon to help you prepare for technical interviews – Interview Practice!

Introducing Interview Practice Mode!

Prepare for technical interviews

We created Interview Practice because we know that for you to succeed in a technical interview, you need to be able to solve real interview questions from real technical interviews. Interview Practice has 100+ real interview questions from 10+ top-rated companies (think Google, Facebook, and LinkedIn) on over 25 topics ranging from dynamic programming to hash tables to sorting algorithms. What – that’s not enough? Don’t worry, we’ll be adding more questions from even more companies over the next few months.

Interview Practice is on the same great CodeFights platform that you already know and love. It runs tests against your solutions in realtime, so you get instant feedback about how you’re doing. Since you get to choose challenges from specific companies that are about specific topics, you create a custom interview preparation experience instead of following a one-size-fits-all path. When you’re done with a challenge, compare your answer against solutions from other CodeFighters. And as always, you can ask questions and discuss strategies in the CodeFights forum.

Maybe you’re already looking for a new job. Or you’re considering looking for one. Or maybe you just want to know whether you can solve interview questions from a certain company – bragging rights are important! Whatever your goal, the CodeFights Interview Practice Mode is going to help you get there.

What are you waiting for? Start preparing for your next interview right now with CodeFights’ Interview Practice. You’ll walk in knowing that you’re prepared for anything the interviewer throws at you!  

Tell us…

Are you preparing for interviews right now? How are you going to integrate Interview Practice Mode into your interview prep routine? Let us know what you think on the CodeFights forum!