Master-the-Coding-Interview: Data Strucutre + Algorithms

Master the Coding Interview: Data Structures + Algorithms BY Andrei Neagoie Founder of Zero to Mastery

Section 1: Introduction

Interview Mind Map

Getting the Interview
Big O Notation
Technical Interviews
Non Technical Interviews
Offer + Negotiation

Technical Interview Mind Map

Data Structures
Algorithms

Fast Track

Getting The Interview
Non Technical Interview
Offer + Negotiation

Complete

Everything

Tech Track

Big O
How To Solve Problems
Data Structures
Algorithms
Extra Coding Exercises

⬆ back to top

Section 2: Getting More Interviews

Resume
LinkedIn
Portfolio
Email

⬆ back to top

Resume

Resources

Resume

One Page
Relevant Skills
Personalized
Online Link

Resume Cheetsheet

✅ Use a pre-designed resume template
✅ Make the resume fit on 1 page
✅ Include words from job description
✅ Include company name you are applying to
✅ Does your first item on your resume reflect what they are looking for?
✅ Experience titles demonstrate value
✅ Do you have an online link?
✅ Remove the word “I”
✅ No buzzwords describing how great you are
✅ Are you using Action words?
✅ Measure everything in terms of impact, don’t just describe your responsibilities
✅ Technical Knowledge/Skills should include what they are looking for. Only show years if it is impressive
✅ Include only sections/items that are impressive: Experience, Projects, Education, Technical Skills
✅ No typos or bad grammar

⬆ back to top

What If I Don't Have Enough Experience?

Creative Tim Free HTML templates Medium

Experience doen't come just from working at another company.
Maintain GITHUB graph.
Make your own website.
1 ~ 2 Big projects.
Instead of spending time on small little projects spend your time on one or two big projects
On those projects you will cover the mostly imortant concepts.
Recruiter just care about that you build things that are real, big and complicated and you solved hard problems.
Show those projects on your resume work experience section and mention what you've done in that.
Blog Post. (medium.com)

⬆ back to top

Linkedin

Update the linkedin profile with the skills you have and according to the jobs that you're targetting.
Include relevant skills and keywords.
Find a people, connect and message or get referals of those companies in which you want to work.
Update your linkedin profile after few days when you're searching for a job.

⬆ back to top

Portfolio

⬆ back to top

Email

Ask people in the company for referral.
Meet them, or message them, meet people in Meetups
People love talking about themselve, ask CTOs, lead developers and professionals for a chat in office or coffer & let them know you're interested in getting where they are professionally and learn from them.
The key in above mention point is just not ask him for a job.
Try to bypass the formalities in application process by trying to get in interview right away.

⬆ back to top

Email Sample

Hey $BOB, I saw your presentation at $CONFERENCE last year on Youtube (rr point to some work they have done). Great stuff; loved what you did with $FOO, in particular $COMMENT_PROVING_YOU_KNOW_WHAT_YOU'RE_TALKING_ABOUT. I'm also a $FOO developer. I noticed that your company is hiring or $ROLE. I’d love to be a part of your team. Do you have a few minutes to chat on Thursday about what you guys are doing?

Thanks, Yourname Your website or any public profile link.

⬆ back to top

Getting Email Extensions.

⬆ back to top

Where To Find Jobs?

Getting an interview is a number game, for getting a interview you need to apply 50 places.
Just applying to companies blindly is not a good idea.
If you have companies you love or you want to work for a specific company and targetting your approach and focus is a lot better more efficient way of spending your time.

Resources for finding a Job.

Resources for jobs

When should you start applying?

Now.
If you're applying to a job where you check all the requirements check boxes and you know everything then that means you are getting a where job where you already know what to do. You won't grow in this world.
A job description is simply a guideline of what type of work you will be doing not what type of work have you done in the past.
Giving interview use as practice just like with anything.
Remember, IF YOU NEVER ASK, THE ANSWER IS ALWAYS NO. So start applying now.

⬆ back to top

Section 3: Big O

Setting Up Your Environment

⬆ back to top

Python, C/C++, Golang, Swift and JavaScript Solutions!

⬆ back to top

Section Overview

Most important topics for any Software developer or Engineer.
Even if you're coding 10 years later from now this is a concept that will be around for a long time.
That will make truly make you a better developer.
Without Big-O you cannot encouter Big companies interviews like Google, Facebook, Alibaba, Amazon OR FAANG.
Big-O and official term is Big-O asymptomatic analysis.
Any coder given enough time can solve a problem. What matters is though how well the problem is solved. And this is where Big-O can help us.
Big-O can tell us how well a problem is solved.
WIth Big-O we can distinguish Good code and bad code.
This topic will come again and again.

⬆ back to top

What Is Good Code?

Readable
Scalable [Big O]
- Question: How can we measure the good and bad code?
- Answer : Big-O notation is the language we use for talking about how long an algorithm takes to run.
- X-axis: Elements/Inputs, y-axis: Operations
- Excellent, Good: O(log n), O(1)
- Fair: O(n)
- Bad: O(nlog n)
- Horrible: O(n^2), O(2^n), O(n!)

When we talk about Big-O and scalability of code we simply mean when we grow bigger and bigger with our input, how much does the algorithm or function slow down. The less it slows down the better it is.

Big O

⬆ back to top

O(n) (Linear time)

Linear rate - As our number of inputs increase the number of operations as well.
Keep in mind, Big-O doesn't measure things in seconds instead focusing on how quickly our runtime grows. By simply using the size of input (n) and compare to the number of operations that increase.
Scalability means, as things grow larger and larger does it scale?

// O(n): Linear time
const fish = ['dory', 'bruce', 'marlin', 'nemo']
const nemo = ['nemo']
const everyone = [
  'dory',
  'bruce',
  'marlin',
  'nemo',
  'gill',
  'bloat',
  'nigel',
  'squirt',
  'darla',
  'hank',
]
const large = new Array(100000).fill('nemo')

const findNemo = (fish) => {
  let t0 = performance.now()
  for (let i = 0; i < fish.length; i++) {
    if (fish[i] === 'nemo') {
      console.log('Found NEMO!')
    }
  }
  let t1 = performance.now()
  console.log('Call to find Nemo took ' + (t1 - t0) + ' milliseconds.')
}

findNemo(large) // O(n) --> linear time

Compression Example.

⬆ back to top

O(1) (Constant time)

O(1) is Excellent in Complexity chart.
No matter how much input grows, the number of operations remains same.

// O(1): Constant time
const boxes = [0, 1, 2, 3, 4, 5]

const logFirstTwoBoxes = (boxes) => {
  console.log(boxes[0])	// O(1)
  console.log(boxes[1])	// O(1)
}

logFirstTwoBoxes(boxes) // O(2)

⬆ back to top

Exercise: Big O Calculation

Assignment takes constant.

// What is the Big O of the below function?
// Hint, you may want to go line by line
const funChallenge = (input) => {
  let a = 10 // O(1)
  a = 50 + 3 // O(1)

  for (let i = 0; i < input.length; i++) {
    anotherFunction() // O(n)
    let stranger = true // O(n)
    a++ // O(n)
  }
  return a // O(1)
}

// 1 + 1 + 1 + n + n + n
// Big O(3 + 3n)
// O(n)
funChallenge()

⬆ back to top

Exercise: Big O Calculation 2

// What is the Big O of the below function? 
// (Hint, you may want to go line by line)
const anotherFunChallenge = (input) => {
  let a = 5 //O(1)
  let b = 10 //O(1)
  let c = 50 //O(1)
  for (let i = 0; i < input; i++) {
    let x = i + 1 //O(n)
    let y = i + 2 //O(n)
    let z = i + 3 //O(n)
  }
  for (let j = 0; j < input; j++) {
    let p = j * 2 //O(n)
    let q = j * 2 //O(n)
  }
  let whoAmI = "I don't know" //O(1)
}

// Big O(4 + 5n)
// Big O(n)
anotherFunChallenge(5)

⬆ back to top

Simplifying Big O

Rule Book

Worst Case
Remove Constants
Different terms for inputs
Drop Non Dominants

⬆ back to top

Big O Rule 1 - Worst Case

We'll always care about worst case, even if result in initial loops.

// Worst Case: n
const fish = ['dory', 'bruce', 'marlin', 'nemo']
const nemo = ['nemo']
const everyone = [
  'dory',
  'bruce',
  'marlin',
  'nemo',
  'gill',
  'bloat',
  'nigel',
  'squirt',
  'darla',
  'hank',
]
const large = new Array(100000).fill('nemo')

const findNemo = (fish) => {
  let t0 = performance.now()
  for (let i = 0; i < fish.length; i++) {
    console.log('running')
    if (fish[i] === 'nemo') {
      console.log('Found NEMO!')
      break
    }
  }
  let t1 = performance.now()
  console.log('Call to find Nemo took ' + (t1 - t0) + ' milliseconds.')
}

findNemo(large)

⬆ back to top

Big O Rule 2 - Remove Constants

Remeber, drop the constants.
You're never going to really see the numbers in Big O notation.

To prove that, if we look at at this function in our graph we see that the elements as the elements increase

2 elements 2 operations, 4 elements 4 operations, 6 elements 6 operations.
Even though line is increasing, the way line is increases still linear, That's the key.
In Big O we don't care about how steep the line is, we care about how the line moves as our inputs increase.

// Big O(1 + n/2 + 100)
// Big O(n/2 + 101)
// Big O(n/2)
// Big O(n)
const printFirstItemThenFirstHalfThenSayHi100Times = (items) => {
  // O(1)
  console.log(items[0])

  const middleIndex = Math.floor(items.length / 2)
  const index = 0

  // O(n/2)
  while (index < middleIndex) {
    console.log(items[index])
    index++
  }

  // O(100)
  for (let i = 0; i < 100; i++) {
    console.log('hi')
  }
}

⬆ back to top

Big O Rule 3 - Different terms for inputs

Both input lenght can be vary that's why it's O(a + b)
Different input should have different variables.

// boxes, boxes2 are 2 different terms for inputs
// Big O(a + b)
const compressBoxesTwice = (boxes, boxes2) => {
  boxes.forEach((box) => console.log(box)) // O(a)
  boxes2.forEach((box) => console.log(box)) // O(b)
}

compressBoxesTwice([1, 2, 3], [4, 5])

⬆ back to top

O(n^2)

O (n ^ 2) - Quadratinc time.
O (n ^ 2) is Horrible.
When loops are one after another we use addition e.g. O(n + n). And when loops are nested, we use multiplication e.g. O(n * n) OR O(n^2).

Every time the number of elements increase, number of operations increase quadratically.
In above example, when number of elements is 2 then number of operations is 3. When one element increase e.g. 3, the number of operation icreases to 9 OR 3^2.
Lot of interview questions that ask you to solve a problem initially is O(n^2) and make it faster by perhaps making it into something that in a bit lower e.g. BAD or FAIR.

// Big O(a * b) - Quadratic Time
const boxes = ['a', 'b', 'c', 'd', 'e']
const logAllPairsOfArray = (array) => {
  for (let i = 0; i < array.length; i++) {
    // O(a)
    for (let j = 0; j < array.length; j++) {
      // O(b)
      console.log(array[i], array[j])
    }
  }
}

logAllPairsOfArray(boxes)

⬆ back to top

Big O Rule 4 - Drop Non Dominants

Drop non dominant terms, just remain those terms which are impactful e.g. O(n + n^2) n^2 is the way more important than the n because n^2 is impacting more.
We always just keep the dominant term.
Another example: O(x^2 + 2 + 3x + 100 + x/2) here we just keep O(x^2).

// Big O(n + n^2)
// Drop Non Dominants -> Big O(n^2)
const printAllNumbersThenAllPairSums = (numbers) => {
  // O(n)
  console.log('these are the numbers:')
  numbers.forEach((number) => console.log(number))

  // O(n^2)
  console.log('and these are their sums:')
  numbers.forEach((firstNumber) =>
    numbers.forEach((secondNumber) => console.log(firstNumber + secondNumber))
  )
}

printAllNumbersThenAllPairSums([1, 2, 3, 4, 5])

⬆ back to top

Big O Cheatsheet.

To download cheatsheet click below.

Big O Algorithm Complexity

⬆ back to top

What Does This All Mean?

Scalable means we worry about large inputs.
If our function is only worry about really small inputs OR we know that our input are going to be only an array of five items, Big O won't matter as much..
See below image, if our input are small all these lines are bunch up together which means Big O won't affect on small inputs as much, but it's not real life.
When we write code, we want to write code that can scale so that we don't have to constantly go back and fix things Or when things get out of hand the code breaks.
That's why Big-O is so important to write scalable code.
In Javascript we have array methods e.g. push, pop, shift, unshift. All these methods which are functions have a cost associated with them.
Example: When we search in an array or access first item in array it's O(1) but when we use unshift it turns out to be O(n).
We use Big-O to measure why one Data structure might be better than others. Why should we use an array instead of object. Maybe object has better functions what we need for our data.
For better understanding of different operations of different Data Structures see below image. We have different Big-O notations for different Data Structures.

In above image, some DS have really good Big O for searching. Some DS good in deletion, insertion etc. Each DS have different pros and cons.
DS are simply ways to store data and algorithms are simply functions or ways to use Data Structures to write our programs. Instructions for our machines.
Data Structures + Algorithms = Programs
Great programmers have this knowledge where they pick the right data structure, right algorithm to write good programs.
In this section we lay our foundation for finding what is a good solution to a problem and what is a bad.
Most interviews have this core concept, what's the right data structure, what's the right algorithm to write good programs.
Google hires engineers and developers that know this, because they have a lot of scale that they have to think about, alot of inputs. And people know how to handle these programs are the ones that are going to be able to build great programs.
It's too much, but it Worths. 😛🌠

⬆ back to top

O(n!)

If you're writing code that has this Big O notation you're definitely doing something wrong.
It's the most expensive one and it's the steepest of them all in chart.
This is called Factorial time.
It means that we're adding a nested loop for every input that we have.

Example of O(n!)?

⬆ back to top

3 Pillars Of Programming

What is good code?

Readable
Scalable - Speed (Time Complexity)
Scalable - memory (Space Complexity)

⬆ back to top

Space Complexity

When a program executes it has two ways to remember things

When a program executes it has two ways to remember things
- Heap - Store variables
- Stack - Keep track of function calls

What causes Space Complexity?

Variables
Data Structures
Function Call
Allocations

⬆ back to top

Exercise: Space Complexity

The's one gotcha when it comes to space complexity is that when we talk about space complexity we're talking about additional space, so we don't include space taken by the inputs.
We don't really care how big the input is.
In short, we just care about the spaces that are used by us, not user.

// Space complexity O(1)
const boooo = n => {
  // space allocation for i is O(1)
  for (let i = 0; i < n.length; i++) {
    console.log('booooo');
  }
}
boooo([1, 2, 3, 4, 5])

// Space complexity O(n)
const arrayOfHiNTimes = n => {
  // space allocation for Data Structures hiArray is O(n)
  const hiArray = [];
  for (let i = 0; i < n; i++) {
    hiArray[i] = 'hi';
  }
  return hiArray;
}
arrayOfHiNTimes(6)

⬆ back to top

Exercise Twitter

Let's assume you're working at Twitter, your boss asked you to build a feature, that allows anybody to click a button and retrieve their most recent tweet any their oldest tweet.
Without coding anything we know we have to find first and the last or Nth element/item.
So the complexity will be.

const tweets = ["tweetOne", "tweetTwo", "tweetLast"]
tweets[0] // O(1)
tweets[tweets.lenght - 1] // O(1)

But now our boss come and say, I want to compare the dates of tweets. I want you to look at every tweet and compare their date with each tweet date. And return the latest one.

const tweets = [{
  tweet : "tweetOne",
  date : 2012
},
{
  tweet : "tweetTwo",
  date : 2014
},
{
  tweet : "tweetThree",
  date : 2016
}
]

In above code, we'll comparing each item with every item in array.
So, we'll be using Nested Loops. And this will be cost us O(N^2)
This operation might cost us a lot of money at Twitter.
So you might want to tell your boss, we might need to do something else perhaps store the information in a better format or do something different with our program in order to avoid something that might be ineffecient or might be expensive.
By thinking this way, now you have the ability to think long-term, think scalable code.

⬆ back to top

Section Summary

Time complexity, how long it takes to run the algorithm.
Space complexity, the memory is required by the algorithm
Big O says which function, algorithm or Code is best.
We learned that, when it comes to good code, we're concerned about readability and scalability.
Big O allow us to measure the idea of Scalable code.
Why you care? Because we need to save time and money for company.
Big O is a very important concept that you won't find in your day to day job, but it's something that should always be in the back of your mind and good developers and engineers always have this knowledge.
In this section we learn about time and space complexity. How we use Big O to measure both things.
But each one is a tradeoff between the other and Big O describes the upper bound of our estimates.
Big O is about how you can scale, it doesn't necessarily mean that O(N) is better than O(N^2), because scalibility wasn't the only factor. Readability is something that we are concerned with as well
Sometimes readability maybe matters more than scalibility. Maybe time complexity is less important than space complexity.
And that's something you want to be careful of now with this newfound knowledge.
PREMATURE OPTIMIZATION IS ROOT OF ALL EVIL - DONALD KNUTH
Sometimes optimizing for time and space can negatively impact the readability of code.

⬆ back to top

Section 4: How To Solve Coding Problems

Section Overview

In this section we're going to talk about the Technical Interviews, and how to succeed in them.
At the end of the day, an interview is a way for the company to find out, Can you solve a problem that the company or employer has. If you're able to solve their problems then you're valuable.
We can be smart and strategic about where we apply and how we apply to a company. And we learned about that in previous sections.
Here comes the big challeng, you got an interview, What would you do? Over the next couple of sections we're going to tacke this question.
Before dive into coding problems, data structures and algorithms we must first understand this one principle. HOW TO SOLVE PROBLEMS.
If we know every single algorithm in the world and know all the data structures, you're the best coder in the world. Well it doesn't guarantee that you will succeed in a technical interview.
This section is meant to prepare you so that you have the foundation laid out. You see it's not the smartest interviewer that gets hired most of the time. It's the interviewer that is able to answer this fundamental question. Will you solve the company's problem?
It's not necessarily about the solution to a problem in a coding interview, it's about the thought process and knowing the tradeoffs between DSA, space and time complexity.
Just like in real life coding, you don't memorize things, you have deeply understands them, understand the tradeoffs.
We need to understand WHY of each thing.
In this section we also cover, step by step what we need to do to solve problems in a way that companies really like, so that you succeed in this coding interview.
Once we have these foundations we can use DSA to solve our problems, because the interview isn't about your ability to memorize DSA. Most people make that mistake and *interviewers can detect right away who actually know these things VS just memorize them.

⬆ back to top

What Are Companies Looking For?

Analytic Skills
- How can you think through a problem and analyze things? Thought process, from not knowing the answer to solving the problem.
Coding Skills
- Do you code well, by writing clean, simple, organized, readable code?
Technical Skills
- Do you know the fundamentals of the job you're applying for?
- Do you understand the pros and cons of different solutions?
- When you should use a certain data structure over the other?
- Why should we use a certain algorithm over another?
Communication Skills
- Does your personality match the companies’ culture?
- Can you communicate well with others?
Most people get hung up on the idea of learning every single algorithm and data structure doing a thousand problems to practice before an interview. These are important but in most companies you don't actually need to know how to write a binary search tree or write a sorting alogrithm from scratch. Although we're going to go through that in this course but most of the time you learn it on the go on the job when you actually need it.
Companies are looking for those people who know how to look for answers and they want to know that you know your DSA and you know of their existence. That's the key
They want to know when you should use a certain DS over the other. Why should we use a certain algorithm over another.
At the end of the day companies want smart people. They want people that can solve problems that they cannot solve themselves.
Do all the excercises in this course, You need to understand the WHY of doing things. Why are we learning this? Why is this the answer to the problem. Why is this answer better than the other.

⬆ back to top

What We Need For Coding Interviews

Interview Cheat Sheet

[Data Structures](Top 8 Data Structures for Coding Interviews and practice interview questions)

Data Structures	Data Structures
Arrays	Queues
Hash tables	Trees
Linked Lists	Tries
Stacks	Graphs

Algorithms
Recursion
Sorting
BFS + DFS (Searching)
Dynamic Programming

⬆ back to top

Exercise Google Video

Google Interview Demo

⬆ back to top

Exercise: Interview Question

Given 2 arrays, create a function that let's a user know (true/false) whether these two arrays contain any common items.

When the interviewer says the question, write down the key points at the top. Make sure you have all the details. Show how organized you are.

const array1 = ['a', 'b', 'c', 'x'];
const array2 = ['z', 'y', 'i'];
should return false.

const array1 = ['a', 'b', 'c', 'x'];
const array2 = ['z', 'y', 'x'];
should return true.

Make sure you double check: What are the inputs? What are the outputs?

What are the inputs? 
2 parameters - arrays

What are the outputs?
return true or false

What is the most important value of the problem? Do you have time, and space and memory, etc.. What is the main goal?

2 parameters - arrays - no size limit

Don't be annoying and ask too many questions.
Start with the naive/brute force approach. First thing that comes into mind. It shows that you’re able to think well and critically (you don't need to write this code, just speak about it).

const array1 = ['a', 'b', 'c', 'x'];
const array2 = ['z', 'y', 'a'];

const containsCommonItem = (arr1, arr2) => {
  for (let i=0; i < arr1.length; i++) {
    for ( let j=0; j < arr2.length; j++) {
      if(arr1[i] === arr2[j]) {
        return true;
      }
    }
  }
  return false
}

containsCommonItem(array1, array2);

Tell them why this approach is not the best (i.e. O(n^2) or higher, not readable, etc...)

Time Complexity - O(a*b)
Space Complexity - O(1)

Walk through your approach, comment things and see where you may be able to break things. Any repetition, bottlenecks like O(N^2), or unnecessary work? Did you use all the information the interviewer gave you? Bottleneck is the part of the code with the biggest Big O. Focus on that. Sometimes this occurs with repeated work as well.
Before you start coding, walk through your code and write down the steps you are going to follow.

const array1 = ['a', 'b', 'c', 'x'];
const array2 = ['z', 'y', 'a'];

array1 = obj {
  a: true,
  b: true,
  c: true,
  x: true
}
array2[index] === obj.properties

Modularize your code from the very beginning. Break up your code into beautiful small pieces and add just comments if you need to.

const array1 = ['a', 'b', 'c', 'x'];
const array2 = ['z', 'y', 'a'];
const containsCommonItem2 = (arr1, arr2) => {
  // loop through first array and create object where properties === items in the array
  // can we assume always 2 params?
  let map = {};
  for (let i=0; i < arr1.length; i++) {
    if(!map[arr1[i]]) {
      const item = arr1[i];
      map[item] = true;
    }
  }

  // loop through second array and check if item in second array exists on created object. 
  for (let j=0; j < arr2.length; j++) {
    if (map[arr2[j]]) {
      return true;
    }
  }
  return false
}

containsCommonItem2(array1, array2)

// Time Complexity: O(a + b) 
// Space Complexity: O(a)

Start actually writing your code now. Keep in mind that the more you prepare and understand what you need to code, the better the whiteboard will go. So never start a whiteboard interview not being sure of how things are going to work out. That is a recipe for disaster. Keep in mind: A lot of interviews ask questions that you won’t be able to fully answer on time. So think: What can I show in order to show that I can do this and I am better than other coders. Break things up in Functions (if you can’t remember a method, just make up a function and you will at least have it there. Write something, and start with the easy part.

const array1 = ['a', 'b', 'c', 'x'];
const array2 = ['z', 'y', 'a'];
const arrToMap = arr1 => {
  const map = {};
  for (let i=0; i < arr1.length; i++) {
    if(!map[arr1[i]]) {
      const item = arr1[i];
      map[item] = true;
    }
  }
  return map;
}

const arrInMap = (map, arr2) => {
  for (let j=0; j < arr2.length; j++) {
    if (map[arr2[j]]) {
      return true;
    }
  }
  return false
}

const containsCommonItem2 = (arr1, arr2) => {
  const map = arrToMap(arr1);
  return arrInMap(map,arr2);
}

containsCommonItem2(array1, array2)

Think about error checks and how you can break this code. Never make assumptions about the input. Assume people are trying to break your code and that Darth Vader is using your function. How will you safeguard it? Always check for false inputs that you don’t want. Here is a trick: Comment in the code, the checks that you want to do… write the function, then tell the interviewer that you would write tests now to make your function fail (but you won't need to actually write the tests).
Don’t use bad/confusing names like i and j. Write code that reads well.
Test your code: Check for no params, 0, undefined, null, massive arrays, async code, etc… Ask the interviewer if we can make assumption about the code. Can you make the answer return an error? Poke holes into your solution. Are you repeating yourself?

const arrToMap = (arr1 = []) => {
  const map = {};
  for (let i=0; i < arr1.length; i++) {
    if(!map[arr1[i]]) {
      const item = arr1[i];
      map[item] = true;
    }
  }
  return map;
}

const arrInMap = (map, arr2) => {
  for (let j=0; j < arr2.length; j++) {
    if (map[arr2[j]]) {
      return true;
    }
  }
  return false
}

const containsCommonItem2 = (arr1 = [], arr2 = []) => {
  const map = arrToMap(arr1);
  return arrInMap(map,arr2);
}

containsCommonItem2()

Finally talk to the interviewer where you would improve the code. Does it work? Are there different approaches? Is it readable? What would you google to improve? How can performance be improved? Possibly: Ask the interviewer what was the most interesting solution you have seen to this problem

const containsCommonItem3 = (arr1, arr2) 
  => arr1.some(item => arr2.includes(item))

containsCommonItem3(array1, array2)

If your interviewer is happy with the solution, the interview usually ends here. It is also common that the interviewer asks you extension questions, such as how you would handle the problem if the whole input is too large to fit into memory, or if the input arrives as a stream. This is a common follow-up question at Google, where they care a lot about scale. The answer is usually a divide-and-conquer approach — perform distributed processing of the data and only read certain chunks of the input from disk into memory, write the output back to disk and combine them later.

⬆ back to top

Review Google Interview

// [1, 2, 3, 9] Sum = 8, No
// [1, 2, 4, 4] Sum = 8, Yes

// Naive Approach
const hasPairWithSum = (arr, sum) => {
  const len = arr.length;
  for(let i =0; i<len-1; i++){
     for(let j = i+1;j<len; j++){
        if (arr[i] + arr[j] === sum)
            return true;
     }
  }
  return false;
}

hasPairWithSum([1, 2, 3, 9], 8)
hasPairWithSum([1, 2, 4, 4], 8)

// Better Approach
const hasPairWithSum2 = (arr, sum) => {
  const mySet = new Set();
  const len = arr.length;
  for (let i = 0; i < len; i++){
    if (mySet.has(arr[i])) {
      return true;
    }
    mySet.add(sum - arr[i]);
  }
  return false;
}

hasPairWithSum2([1, 2, 3, 9], 8)
hasPairWithSum2([1, 2, 4, 4], 8)

⬆ back to top

Section Summary

One big misconception is that, you're either a good problem solver or you aren't?
But as with anything, it's a muscle that you can train, that you can practice.
So with enough practice and knowing the tips and tricks that we covered in this section you can solve problems alot better.
The key in this section was that cheatsheet. Step by step walk through of a problem.
The idea in Google video was,
- Show how you work with THINK OUT LOUD.
- Try to comment the steps as you go along to solve a problem
- Communicating throughtout the process as much as possible and not worrying about finishing a problem fast is the key to interviewing in solving problems.

⬆ back to top

Section 5: Data Structures Introduction

Section Overview

A Data structure is a collection of values, algorithms are the steps or processes we put into place to manipulate these collection of values.
A person who knows how DSA work and how to use them can write great programs.
The beauty of DSA is that these are timeless, no matter what programming language you use, whether you prefer one library over the other, whether you write code in angular or React, or you are a game developer. Underneath it all it's all DSA.
If you understand these, then you can really easily adapt and tackle all sorts of technical problems.
The longer you are in the field the more and more you realize that you need these fundamental principles or DSA in order to be a great devloper or Engineer.

⬆ back to top

How to choose the right Data Structure?

Choosing the Right Data Structure to solve problems

⬆ back to top

What is a Data Structure?

Again - A DS is a collection of values. The values can have realationships among them and they can have functions applied to them.
Each one is different in what it can do and what it is best used for.
Most important thing to take away is that each Data structure is good and is specialized for its own thing.
Like Fridge is foods, Bag is for books, folder is for files. Same as each Data structure is use for it's own purpose.
Data structure is like real life scenarios, we're modeling our programs like that.
The more advanced a developer you become, the more time you will start thinking and spending time talking about Data structures.
This is why interviewers love to talk about Data Structures.
There are always tradeoffs, every programming question has tradeoffs. Remember three pillars?
- Readability.
- Time complexity.
- Space complexity.
Like we have tradeoffs in above three pillars, same as there are tradeoffs between Data structures. One is better than other in some aspects and the other better than the other. That's why they exists.
There are two parts to understand Data structures.
- How to build one.
- How to use it.
The second part is most important. Because Data structures are usually just tools and most of them are already pre-built for us.
When to use one over the other.
The goal in this course to understand Data Structure so that you can pick the right DS for your problem.

⬆ back to top

How Computers Stores Data

Computer Memory
Registers and RAM
CPU: access RAM and Storage for information
RAM: fast but limited, non-persistent
Storage: more but slow, persistent

⬆ back to top

Data Structures In Different Languages

Data Structures — Language Support (Part 3)

⬆ back to top

Operations On Data Structures

Insertion
Deletion
Traversal
Searching
Sorting
Access

⬆ back to top

Section 6: Data Structures: Arrays

Arrays Introduction

Arrays are probably the simplest and most widely used data structures.

Array vs Object

Arrays for storing ordered collections.
Objects for storing keyed collections.

Real life examples

Cinema Book Challenge

Array

Operation	Big O
lookup	O(1)
push	O(1)
insert	O(n)
delete	O(n)

// 4 * 4 = 16 bytes of storage
const strings = ['a', 'b', 'c', 'd'];
strings[2]

const numbers = [1, 2, 3, 4, 5];

//push
strings.push('e');  // O(1)

//pop
strings.pop();  // O(1)
strings.pop();  // O(1)

//unshift
// 'x' will push all elements to their right
// ['x', 'a', 'b', 'c', 'd'];
//   0    1    2    3    4
strings.unshift('x')  // O(n)

//splice
strings.splice(2, 0, 'alien');  // O(n)

⬆ back to top

Static vs Dynamic Arrays

JavaScript Array is dynamic

Array Operation	Big O	Dynamic Array	Big O
lookup	O(1)	lookup	O(1)
push	O(1)	append*	O(1) or O(n)
insert	O(n)	insert	O(n)
delete	O(n)	delete	O(n)

⬆ back to top

Name		Name	Last commit message	Last commit date
Latest commit History 56 Commits
.gitconfig		.gitconfig
DS-operations.png		DS-operations.png
README.md		README.md
big-o-cheatsheet.pdf		big-o-cheatsheet.pdf
big-o-complexity.jpg		big-o-complexity.jpg
big-o-complexity.pdf		big-o-complexity.pdf
big-o-compression.png		big-o-compression.png
big-o-constants.png		big-o-constants.png
big-o-graph.png		big-o-graph.png
choose-data-structures.png		choose-data-structures.png
constant-proof.png		constant-proof.png
constant-time.png		constant-time.png
initial-input.png		initial-input.png
interview-cheatsheet.pdf		interview-cheatsheet.pdf
quadratic-time.png		quadratic-time.png
resourcesForJobs.html		resourcesForJobs.html

shahbaazkyz/Master-the-Coding-Interview-DSA

Folders and files

Latest commit

History

Repository files navigation

Master-the-Coding-Interview: Data Strucutre + Algorithms

Table of contents

Section 1: Introduction

Section 2: Getting More Interviews

Resume

Resume Cheetsheet

What If I Don't Have Enough Experience?

Linkedin

Portfolio

Email

Email Sample

Getting Email Extensions.

Where To Find Jobs?

Resources for finding a Job.

When should you start applying?

Section 3: Big O

Setting Up Your Environment

Section Overview

What Is Good Code?

O(n) (Linear time)

O(1) (Constant time)

Exercise: Big O Calculation

Exercise: Big O Calculation 2

Simplifying Big O

Big O Rule 1 - Worst Case

Big O Rule 2 - Remove Constants

Big O Rule 3 - Different terms for inputs

O(n^2)

Big O Rule 4 - Drop Non Dominants

Big O Cheatsheet.

What Does This All Mean?

O(n!)

3 Pillars Of Programming

Space Complexity

Exercise: Space Complexity

Exercise Twitter

Section Summary

Section 4: How To Solve Coding Problems

Section Overview

What Are Companies Looking For?

What We Need For Coding Interviews

Exercise Google Video

Exercise: Interview Question

Review Google Interview

Section Summary

Section 5: Data Structures Introduction

Section Overview

How to choose the right Data Structure?

What is a Data Structure?

How Computers Stores Data

Data Structures In Different Languages

Operations On Data Structures

Section 6: Data Structures: Arrays

Arrays Introduction

Static vs Dynamic Arrays

About

Resources

Stars

Watchers

Forks

Releases

Packages 0

Languages

Packages