## Friday, June 19, 2020

### Clarification Questions

Strings, Arrays and Numbers

• How many elements can be in the array?
• How large can each element be? If it’s a string, how long? If it’s a number, what is
the minimum and maximum value?
• What is in each element? If it’s a number, is it an integer or a floating point? If it’s a string, is it single-byte or multibyte (unicode)?
• If the problem involves finding a subsequence, does “subsequence” mean that the elements must be adjacent, or is there no such requirement?
• Does the array contain unique numbers or can they be repeated (this is sometimes relevant)?

Grids/Mazes

• For problems where some actor (e.g. a robot) is moving in a grid or maze, what moves are allowed? Can the robot move diagonally (hence 8 valid moves), or only horizontally/vertically (hence only 4 valid moves)?
• Are all cells in the grid allowed, or can there be obstacles?
• If the actor is trying to get from cell A to cell B, are cells A and B guaranteed to be
different from each other?
• If the actor is trying to get from cell A to cell B, is it guaranteed that there’s a path between the two cells?

Graphs

• How many nodes can the graph have?
• How many edges can the graph have?
• If the edges have weights, what is the range for the weights?
• Can there be loops in the graph? Can there be negative-sum loops in the graph?
• Is the graph directed or undirected?
• Does the graph have multiple edges and/or self-loops?

Return Values

• What should my method return? For example, if I’m trying to find the longest subsequence of increasing numbers in an array, should I return the length, the start index, or both?
• If there are multiple solutions to the problem, which one should be returned?
• If it should return multiple values, do you have any preference on what to return? E.g. should it return an object, a tuple, an array, or pass the output parameters as input references? (This may not be applicable in languages allowing you to return multiple values, e.g. Python)
• What should I do/return if the input is invalid / does not match the constraints? Options may be to do nothing (always assume the input is correct), raise an exception, or return some specific value.
• In problems where you’re supposed to find something (e.g. a number in an array), what should be returned if the element is not present?

## Friday, May 29, 2020

### Stitching Videos Using FFMPEG

1. On Mac 10.13.6 (17G12034). To install ffmpeg:

brew install ffmpeg

2. Create the stitch.txt with files to be stitched. The command needs a slight modification to avoid silent video:

ffmpeg -f concat -safe 0 -i stitch.txt -c:v copy adjacent-duplicates-f.mp4

## Tuesday, May 26, 2020

### Problem Solving Tools

The three important problem solving tools are:

1. Data Models
2. Data Structures
3. Algorithms

Data models are abstractions used to describe problems. Graphs is an example of a data model.

Use abstractions to formulate solutions to problems. For example, graphs are a way to model data and provide data abstraction to manipulate data effectively to solve problems.

Data structures are programming language constructs used to represent data models. For example, built-in abstractions such as structs and pointers. This can be used to construct data structures to represent complex abstractions such as graphs.

Algorithms are techniques used to obtain solutions by manipulating data as represented by the abstractions of a data model, by data structures or by other means.

## Wednesday, May 13, 2020

### Questions on N Queens Problem

1. Why matrix is inefficient?
2. How is recursive calls made in preorder traversal of the tree?
3. How to generate all of the permutations and all of the subsets of n distinct elements?
4. Print all of the subsets of the elements in a list. Input: [a, b, c]
5. Which part of the code does backtracking?
6. What does the solution space tree look like?
7. Why it is DP? Does it satisfy optimality? Subproblem?
8. When to use backtracking?
9. How call stacks are called with for loop? What is returned?
10. What happens when we backtrack?
11. How to determine the base case?
12. What is the time complexity?
13. What is the space complexity?
14. What data structures to use?
15. How to check if a position is in a diagonal?
16. How to identify a backtracking problem?
17. When do we stop making choices?
18. When does the undo happen? (only when the choice is invalid?)
19. How many wrapper functions do we need? What parameters are needed?
20. What are the subproblems?

## Wednesday, May 06, 2020

### Mastering Recursion Course Outline for Module 1

## 1. Head and Tail Recursion

- How to replace a loop with recursion?
- What is tail recursion?
- Differences between head and tail recursion?
- Tail recursion call tree

- How to find base cases?
- Problem decomposition
- How to determine the size of the problem?
- Recursion diagram as a tool to design recursive programs
- What to do in the combine step?
- How to find the recursive case?
- Mathematical representation of recursive function
- How choice of reduction affects performance
- Recursive rule for efficient solution
- Translating mathematical function into recursive code

## 3. Multiplication

- How to derive recurrence relation?
- How to reassemble the result of subproblems to get the result for original problem?
- Improving the efficiency of the recursive solution
- How to determine the number of base cases?

## 4. Division

- Using a counter
- How to create a trace table
- Concrete case analysis using recursion diagram
- Reducing the problem size by more than one unit
- Recognize implicit counter in recursive code

## 5. Summation

- Expressing the problem mathematically
- Determine the size of the problem
- Using induction in the recursion diagram
- Translating recursion diagram into recursive solution
- Comparison of iterative and recursive solutions
- Recursion call stack
- Time and space complexity
- Linear recursion

## 6. Array Sum

- How data handled by base case affects recursive case
- Choosing what to reduce when you have many options
- Trace table showing the computations occurring when recursive calls terminate

## 7. Modulo

- Deriving equation to solve a problem
- Time complexity for equation based implementation
- Solving the problem by hand (brute force)
- Solving the problem by translating manual steps to iterative code
- Recognizing nothing to be done in combine step using recursion diagram
- Trivial combine step in recursion leads to tail recursion
- Comparison of iterative and recursive solution to see how terminating condition maps to base case, result and reduced value are the same in this case

## 8. Even

- Without using % operator
- Time and space complexity
- Iterative Solution
- Using multiply and divide
- Recursion diagram
- Recursive solution
- Fixing stack overflow error
- Reduction step
- Trivial combine step
- Tail recursion
- Two base cases
- How many base cases are required?
- Time and space complexity
- Linear recursion

## 9. Exponent

- Powers of 2 (warmup)
- Exponentiation operator
- Implement without using exponentiation operator
- Iterative solution
- Product accumulator
- Powers of a given base
- Recursive implementation in linear time
- Size of the problem
- Base cases
- Reduce and combine
- Allow negative integer exponents
- Problem decomposition
- Recursive case
- Relationship between reduction step and base case
- Function to express recursive case
- Multiple recursive cases
- Powers in logarithmic time
- Handling multiple cases and its effect on recursion diagram
- Recursive function with multiple recursive cases
- Direct translation of mathematical function to code

## 10. Sum Digits

- Extracting right most digit
- Chopping off right most digit
- Iterative solution
- Accumulator variable
- Time and space complexity
- Recursion diagram
- Reduce and combine
- Problem decomposition
- Recursive solution
- Time and space complexity

## 11. Guess a Number Game

- Game
- Computational complexity
- Derive the time complexity

## 12. Square Root

- Iterative solution
- Recursive solution using a wrapper function
- Comparison of iterative and recursive function
- Using bisection to improve performance

## 13. Reverse a String

- Recursive solution
- Multiple options in reduction step
- Combine step requires language builtin function
- Performance implications of concatenating strings
- Iteration solution using inplace modification of string
- Using two pointers
- Recursive solution with string inplace modification
- Using a wrapper function

## 14. Palindrome

- Problem size
- Multiple base cases
- Using two pointers
- Comparison with reverse a string problem
- Problem decomposition and its relationship to base cases
- Recursive solution

## 15. Print digits in reverse

- Size of the problem
- Base case
- Problem decomposition
- Recursion diagram: Reduction and combination
- Recursive solution

## 16. Find largest

- Problem decomposition
- Recursion diagram
- Combine step is a custom function
- Reducing by half
- Recursive function
- Two recursive calls
- Recursive solution
- Comparison of two versions

## 17. Contains Digit

- Problem Statement
- Program interface
- Assumption on input
- Linear recursive algorithm
- Recursion diagram
- Tail recursive algorithm
- Short circuit evaluation
- Relationship between base cases and recursive case
- One base case vs Two base cases
- Time complexity
- Similar problem

## 18. Equal Strings

- Interface (input and output)
- Base case
- Size of the problem
- Linear recursive algorithm
- Recursion diagram
- Problem decomposition
- Boolean function
- Recursive solution
- Tail recursive algorithm
- Short circuit evaluation
- Recursion diagram
- Comparison of linear and recursive solution

## 19. Factorial

- Problem definition
- Mathematical representation
- Translating mathematical function to recursive code
- Recurrence relation
- Deferred operation
- Subproblem with reduced argument
- Minimizing base cases
- Iterative solution
- Product accumulator
- Factorial call trace
- Factorial call and return table
- Pending multiplication direction
- Stack growth
- Time and space complexity
- Comparison of iterative and tail recursive solution

## 20 Fibonacci

- Problem Statement
- Recursive solution
- Two base cases
- Two recursive calls
- Recursive call tree
- Redundant calculations
- Binary Tree
- Level and number of nodes
- Total number of nodes
- Binary recursion runtime
- Improving performance by dynamic programming
- Time and space complexity
- Iterative solution
- Time and space complexity

## Outline

• Using a counter
• How to create a trace table
• Concrete case analysis using recursion diagram
• Reducing the problem size by more than one unit
• Recognize implicit counter in recursive code

## Wednesday, April 29, 2020

### Summation - Using Recursion

You can now easily write the code to add numbers up to a given number.

## Wednesday, March 11, 2020

### How to teach coding the right way

It would be great if you spend some more time to highlight how you digested the problem and formulated the solution.

It would be good for me to learn about your thinking process so that I can replicate the same pattern or reason about the problem in a similar way.

Apart from that, it would be awesome to go through the process of writing the code. It might help folks like me to understand the flow and how you are solving the problem.

It would be better if you go through problem and write solution step by step with your thought process as you already don't know solution in spite of copy and paste. Otherwise internet has all solution of all problems.

I have trouble with implementing and understanding recursive solutions on data structures like Trees (I understand and can implement simple recursion). I tried practicing and solving problems but I feel like I'm missing something.. Any tips specifically for that?

## Friday, February 07, 2020

### Create a New Post Type in Jekyll

Create a directory called _stories.

Update _config.yml file:

collections:
stories:
output: true

Create a story.html file in the _layouts directory.

---
layout: default
---

# {{ title }}

{{ content }}

Page

---
layout: story
title: Story Title Goes Here
description: "The story description text goes here"
---

Create a stories.html page in the site root to act as the index page for the stories.

{% for item in site.stories %}

## {{ item.title }}

{{ item.description }}
{{ item.title }}
{% endfor %}

## Wednesday, February 05, 2020

### Making a Good Last Impression

What to do in the last 5 minutes, in order to leave a good impression?

You need to remember this is a Two-Way interview. If you're good, I will need to sell you on the company because you could have multiple competing offers. So, I usually have a little spiel prepared to explain why it's so great to work at my company, that I'd love to give. If you can get me to try to sell you on joining the company, my mindset is already being altered towards bringing you in.

Your questions are the last impression that you make. If you have no questions, it indicates that perhaps you're not all that interested in the role.

Q&A doesn't need to last long -- 2 minutes is plenty. Just a quick, Hey before we end this, can I ask you a question?"

- What makes you want to work here?
- What are the primary challenges of your current team?

Share a quick comment about how you've also faced similar challenges. End with "Thanks for sharing, it was a pleasure talking to you and that was an interesting question. I enjoyed tackling it."

It is a great chance to learn about something interesting regarding their stack or internal processes, such as:

- How do they run their CI/CD pipeline?
- How does requirements go from conceptual phase to production?
- How do they deal with critical production issues?
- Do engineers debate and have an active voice on requirements prioritization, and functional requirements?
- How much test coverage do they have for their products?
- How does the company embrace innovation?
- Do the engineers have a chance to research and apply technologies that improve the product?

If you are not just looking for a place to get bills paid, it is really important to match the company's internal processes and goals with your career goals.

### Researching a Company

What you should know about the company when researching it?

- Mission Statement
- All their products or at least the product area you're applying to
- What are they working on / new innovation
- What kind of culture they have, so you can mimic it
- What interview questions they ask

It is generally common norm to have a 1-pager resume. Put your highlights in the 1-pager. Less is more. You can use Google Docs to create your resume.

Use black and white, with clean professional formatting. Don't go overboard with fonts & colors. It's the content that matters here, pack it with content. Go as far back as will fit.

Understand the mindset of an employer when crafting a resume. The following tips are from: "Knock em Dead Resumes" by Martin Yates.

Search

Search and collect 6 online job posting for the job. See how the employer describes behavioral profile, technical skills, problems you'll be solving on the job, etc. Use these to craft the story of your resume.

Keywords

Add technical, behavioral and other keywords employers and recruiters database searching algorithms will rate with high scores.

Problem Solver

Think of about the problems you will typically need to identify, solve and prevent in the role and work your resume narrative to highlight familiarity and ability to identify, solve and prevent these problems. Present yourself as someone who solves these problems.

### Smoke Screen Questions

The smoke-screen questions are language dependent. Search for "common interview questions in {your language of choice}" and there are usually plenty of articles on lists.

Javascript

https://www.softwaretestinghelp.com/javascript-interview-questions/
https://www.toptal.com/javascript/interview-questions

Python

https://www.edureka.co/blog/interview-questions/python-interview-questions/

Objective-C

https://www.educba.com/objective-c-interview-questions/

A lot of these may be quite language-specific, and since they're quick yes/no questions they don't make for great meaty interview questions. If you're going into an interview, and you know it's going to be for something language-specific like "javascript frontend developer," "Objective-C iOS developer," or "Python backend developer" then it'll be good to brush up on these. You could be developing in a language like Javascript and never use closures. But that's still a very common question for Javascript roles so don't let those catch you off guard.

Smoke screen test is usually domain specific. If it's a startup, they ask a lot about language specific things depending on the language they use. For larger companies, these questions are rarer, they usually just ask you to do a coding interview. If they do ask you yes/no or definition questions, make sure you know about object oriented programming concepts, OS concepts, concurrency, networking, and language specific questions.

## Thursday, January 30, 2020

### Imposter Syndrome and Stereotype Threat

If you have the feeling of you're not good enough, you're not alone.  So in this article we're going to
talk about the Imposter Syndrome and Stereotype Threat.

We will see what contributes to Stereotype Threat and the Imposter Syndrome. We will also discuss strategies for overcoming them. In particular talking about growth mindset as a strategy for overcoming Stereotype Threat and the Imposter Syndrome.

So let's imagine a situation where you've been given some task. And you start to work on it and then you look around and you start feeling like wait a minute, I don't feel like I'm the same as everybody else here. I feel like people are seeing me as something I'm not. I'm maybe not qualified to be doing what they want me to be doing. How did I get here? This was a mistake, somebody made a mistake. How did I get in this position? My gosh, I'm an imposter, and they're going to figure me out. So, if you've ever felt like that, you're not alone.

This is a very common phenomenon called the Imposter Syndrome. This is this idea that you get into some position, and you feel like you're not qualified to be there, that you're an imposter, and you're going to be found out. And, it can be very stressful. The Imposter Syndrome can be detrimental to your performance. It can hurt you. So it can keep you from applying for positions that you are qualified for, because you feel like in those positions you'll feel like an imposter, and won't really fit in.

It can make you not take appropriate credit for your work, because you'll be found out that you didn't really do the work well enough. You've somehow snuck it by, and nobody else really figured out. So you won't stand up and take appropriate credit. It can make you doubt your abilities in high pressure situations.

For example, interview situations, you definitely don't want these Imposter Syndrome thoughts running through your head, when you're trying to focus on technical explanations and technical content. And then at the end of the day, it's extremely stressful. It can  make you very unhappy. So the Imposter Syndrome is real. And unfortunately, it's not always just in your head, external factors can also influence these thoughts that are running through your head.

You may be hearing it externally as well. You shouldn't be there, you should be somewhere else. You are experiencing Stereotype Threat. There's these expectations, these external expectations for what you should and shouldn't do

The external pressure can make you feel like you made the wrong choice. It can happen in more subtle situations, as well. So, there are many stereotypes out there, and one in particular in the Western world is that men are better than women at math. So, when you're asked to think about somebody who's good at math, typically a Western person thinks about white guy, nerdy, pocket protector, with a sheet full of equations. And that's just kind of the stereotype that exists. So, let's say that I, being a woman, am going to go in and take a very challenging math test.

Now, I'm good at math. The other people who are taking the test are good at math. But when I walk into the room, here's what I see. I see a bunch of people who uphold the stereotype that I have in my head that men are good at math, and women aren't as good. Now what happens to me when I walk into that room is that, that stereotype activates in my head. When women are put into these situations and they're reminded of this stereotype, that men are better than women at math, they perform worse on the test. It's not that they are worse at math.

It's just that their performance is hindered by being reminded of these stereotypes. And this again, is what's known as Stereotype Threat. It's the idea that, I am now a representative of this class of people, of women. And so I have this added pressure to do well on this test. Because I worry that if I don't do well on this test, I'm going to be upholding this stereotype, this negative stereotype that I really don't want to uphold. And that thinking just gets in my way of my ability to think about the mathematical problems that I would need to be working on.

And for people who are in the majority group, they've shown that they don't have this extra thinking that they have to cope with. They're not worried about upholding some stereotype, because it's just sort of that's the norm, that's what everybody accepts. And so they do better on the test itself. So, we want to combat this in a job situation. Because when you're in a job, you might have some stereotype. There might be stereotypes about who fits into that job.

For example, again, in the Western world, there's a stereotype that men are more competent than women in technical jobs. It's not true, but that stereotype exists. So when I walk into an interview, and I happen to see a bunch of men sitting around in the position that I'm going for, that stereotype is going to be activated. So how do we combat both the feeling of the Imposter Syndrome and the Stereotype Threat?

Well, one way is to find good role models. So, when you see people like yourself, that you can relate to, that are in high positions and doing very well, that helps you believe that you can do it. And, speaking of which,  the more you can focus on yourself and your own accomplishments, the more you're going to distance yourself from those stereotypes, and be able to perform without thinking of all those negative thoughts that kind of come into play. The other thing that really helps is shared experiences with peers and mentors. When you realize that you're not alone, and that other people go through this too, that can help you take some of the pressure off that  you're putting on yourself.

## Wednesday, January 29, 2020

### In Person Interview Tips

In this article, we will discuss the format of the in-person interview as well as a number of tips to help you succeed during that interview.

If you get that in-person interview, it means that they were happy with your resume and you succeeded during the technical phone screen. At this point, they think you could be a potentially good fit for the job, and now it really comes down to the in-person interview.

The format of the in-person interview consists of a number of interviews with engineers or managers.

In the software engineer interviews, whether you have three or five of them during the course of the day, are all going to be around 45 minutes. And they're all going to consist of an introduction, just a quick hello. And then almost immediately you're going to dive right into programming on a whiteboard and or trying to solve a large complex problem by making a large complex algorithm.

In solving the problem, you're going to use data structures and you'll probably do some kind of runtime analysis of the problem. Other CS topics may include bitwise manipulation, logic problems or testing.

The other piece that's fair game, is anything you've got on your resume. So if you said you're an expert at something, and you're proficient at something, this is their opportunity to ask you about it, and they will.

They're interested in engineers who solve new problems. That's what you do during the job as a software engineer. But I know that also puts more stress on you.

So now we know what they're looking for. How are you going to succeed? So first off, it's completely okay
to question your interviewer. A number of candidates come in, and they think that it's supposed to be a one-way street. The interviewer asks them questions, and they answer, but they can't ask back.

You can ask questions and you should do so. Whenever you are asked to provide a solution, you should first define and frame the problem as you understand it. Doing so will help clarify the problem and also make sure that you are solving the problem you've been asked.

If you don't understand the problem or you get stuck at any point, you can ask for help or clarification. They're happy to clarify the problem that you're trying to solve.

If you feel like you need to assume anything, you need to check with them before you make those assumptions. It's important to do so because you may be making assumptions that aren't fair game, and just by having a conversation with them about the assumptions, they get a better feel for what you're thinking.

You also want to describe before you start coding how you plan on tackling the problem. It may be that through that process of saying, well I plan on solving this problem using data structure x. And as you talk through how data structure x is going to be used you'll realize well, maybe data structure x wasn't the right fit. Or they may even prompt you, well, maybe you should try thinking about other data structures.

It's important to give them that high level overview before you start coding. As you are working through the problem, the more you can talk to the interviewer about your thinking process, the better.

In a way they're testing you more on your thinking process, and how you go about solving problems than they are about solving specific problems during the interview.

If you get stuck they may provide hints. They may try to help you. But they can only do this if you're thinking aloud. If you are talking loud and it's clear where you get stuck, that's where they can help you. If you're not talking aloud, they don't know where you're stuck, they can't help you.

And finally, you've to listen to the interviewer. I know it's a high-pressure situation. I know the interviewer is asking you questions, and you're trying to think it through. But if the interviewer makes comments or adds suggestions, listen to them. They're often trying to help you, and you can't afford to miss those hints.

I also want to give you just a couple of practical tips. And these may seem really obvious, but for all of these I can tell you a scenario where I know the student who went to an interview and forgot to do these. For example sleeping. You need to take care of yourself. You want to sleep before the interview.

I've heard of students cramming in an algorithms text the whole night before their interview and then walking into the interview totally sleepy. That's a huge mistake, don't ever do that.

You also need to eat. Make sure you eat foods that are going to make you feel energetic, not sluggish, and just take care of yourself in general.

You also want to be prepared. Make sure you put your bag that has your interview clothes in as a carry-on. And the second piece is wear clothes you'd be comfortable in the interview with on the plane. I know it's a little less comfortable, but you'll feel a lot better knowing that you have a pair of back-up clothes for
the interview.

Other things to bring. Bring any projects that you've done in the past that you want to showcase, if they are potable. Obviously bring a note pad and pen to take notes. The last piece is important, and that is talk to your recruiter so your recruiter can give you your schedule for the day, and may also give you some tips about who you're going to meet with and what they're looking for.

And that leads to the third tip, which is relax and mentally prepare for the interview. Now this is going to vary by person. Whatever's appropriate, you want to relax, put yourself in a good state of mind before you start the interview.

So the four pieces of interview are to introduce yourself, write code, describe prior projects, and solve new problems. Those are the four things you're going to be asked to do during interviews.

### Technical Phone Screen Tips and Tricks

In this article we will discuss some tips and tricks to succeed in the technical phone screen. You should be comfortable with what's involved in technical phone screen, as well as how to succeed and set yourself up for success.

If you got a Technical Phone Screen, that's fantastic. You've already gone through the first hurdle in the process. So by having a Technical Phone Screen, recruiters think you have promise and that you might be a good fit for this position.

If you succeed in the Technical Phone Screen, you would go on to an in-person interview. Now, in-person interviews are expensive for companies. They bring you out, they spend a whole day's worth of time with you, and they are trying to avoid a mistake in that process. They want to make sure that you match your resume quite well in terms of your skills.

So Technical Phone Screen exist, mainly to make sure that you are as good as you sound on paper and that it won't be a waste of time to bring you out for the in-person interview. The format of Technical Phone Screen is going to consist of an introduction of you introducing yourself to the interviewer and vice versa followed by questions.

Now these questions may take a number of different flavors. They might be a programming questions where you are going to be coding in a shared Google Doc. They could be questions about Data Structures, Big-O analysis or Algorithm analysis, object oriented principles. They can also get into some other computer science topics like Bitwise manipulation, how do you write scripts, proper use of libraries for your language, as well as the right way to test your code.

These tips came from experience. They are from interviewers who interviewed candidates who weren't able to succeed through the technical phone screen.

Make sure you have a good Internet connection and a phone connection. You want to make sure you have a back up as well. So maybe the land line fails and you have a cell phone as a back up or vice verse. You also want to make sure the Internet connection is solid. The last thing you want during your interview is to have your Internet connection cutting in and out while you're trying to do a programming exercise.

So it'd be great if you could have that wired and it'd be great if you could test it during the same time-frame as you're going to be having your interview. You'll also want to make sure you already have your Google Hang-out and your Skype Account set up, to make sure that when you first fire up Skype, it doesn't do the update. So make sure it's already up and running before your interview starts.

Now if you are going to be using Google Hang-out or Skype for your interview, make sure that you
look at the camera, not yourself. It's much more genuine to the person seeing you if you're looking at the camera. You'll also want to avoid small, non-verbal cues. You don't want slight nod of the head because if you do that, it may not come through, depending on the Internet connection.

If you're going to do non-verbal cues, do big things like thumbs up, or really long exaggerated nods. Or just use a verbal cue and say, oh yeah, I understand, or okay. And then all of this, your Skype, your Internet connection, you phone connection has to be tested before the interview. I strongly recommend you grabbing a friend who is somewhere else. They set up Skype, you set up Skype, and try to mimic the exact phone interviews setting, to find out, well oh, the Internet isn't actually very good in the office this time of day, or things like that.

If you're going to be working in a non-visual environment, so you're just doing a telephone, it's okay to have notes. I recommend having notes, either if you have Skype or you're working on a telephone. And those notes could be something like a resume, as well as some other things to take notes on. But if you have completely non-visual you can have even more notes.

Your notes about the company or other things you want to highlight. Some talking points for the interview that you want to hit on. But don't rely on those too much. Every time they ask a question and if you're shuffling through papers they're going to catch on and it won't come out very well. You'll also want to make sure you have some way of relaxing beforehand. It's really easy to get stressed out before a phone interview.

One of the keys to being relaxed is knowing that you're prepared. And the best way to be prepared is to practice and know your technical knowledge.

Let's look at a couple of pitfalls. They're very common in the technical phone screen. The first is not talking. A surprising number of candidates will be asked a question, and it goes dead silent for five minutes. And there's still nothing. And the interviewer will say, well, could you tell me what you're thinking now? And they'll get a quick, okay, yeah, just one sec. Another five minutes of no talking. This is not good.

You want to make sure you have a dialogue with your interviewer. Now even if you have said just a couple things with the interviewer you want to make sure it's a full two-way dialogue. An example of a mistake here would be, they ask you a question, and you immediately start coding. You don't want to do that. You don't fully understand the question yet.

You want to make sure you go back to the interviewer, ask some followup questions, make sure you understand the question properly, so they could give you hints. They could say, oh, no, it's not actually this problem. And you're trying to think about trying to solve this. We're trying to solve this instead. And that way when you do actually go to solve a problem, you're solving the right one.

Likewise, you'll want to give them some high level ideas about what you're going to do with your coding. And then they can give you feedback, that seems like a reasonable direction or they might say, I think you might want to be thinking about this differently. You haven't thought about this scenario. So the more you have a conversation with them, the better.

One of the other big mistakes is just not being prepared. Not having your Skype connection set up beforehand. Not having the technology knowledge you're supposed to have and just not being ready for the interview.

The last piece is actually a bit more subtle and that's not having your resume highlight your strengths. So you might have thought when you're writing your resume, that it would be a good idea to put in any language you've ever touched as a language you're proficient in. But this is a great way to make a mistake.

Let's say you've coded just a little bit in PHP. You used it once for a project four years ago. And now, during the actual phone screen, they're going to say, could you code up this algorithm in PHP. That can be really bad if you can't program in PHP. You're going to have to say something like, well, I'm actually not that proficient in PHP, let's switch to another language.

And if you do that a couple of times, that's going to be problematic, because they're going to ask what part of this resume is accurate and what part isn't? But it's also a mistake because you've just shown a weakness, because you didn't know a language that was on your resume. That if you just had proof, if you put it on your resume that you weren't proficient in PHP, that you had some knowledge of it, but that you were proficient in Java, you would have set yourself up for success. So this is where the resume really ties in well when the technical phone screen.

## Friday, January 24, 2020

### Gaining Deeper Understanding

Concepts build on one another. The basic concepts must be deeply understood to master more advanced concepts. Connect what you have studied to questions. Relate topics to their eventual appli­cation in the real world.

Graph­ like structures on paper can illustrate which concepts are pre­-requisites. Devise a hierarchy or web of concepts that the system itself could advise students what to work on next.

The confi­dence and self-esteem will be boosted and they will look forward to the challenge of the next, more difficult concept.

People who are skilled at explaining concepts to others probably understand them deeply. Teach the subject to others so that you develop a deeper understanding. As you progress, keep revisiting the core ideas through the lenses of different, active experiences.

### Identifying Gaps in Learning

Coding problems can be used as diag­nostic tools to identify gaps in learning that needs to be addressed. The time spent on finding and fixing the gaps will save you time and deepen learning in the longer term.

If your grasp of core material falls short of deep conceptual understanding, you will not be sure what is being asked or which conceptual tool should be used to solve the problem. Are the connections between concepts missing?
Told to hammer, they could hammer. Told to put in a screw, they could use a screwdriver. But told to build a shelf, they’d be paralyzed even though it was just a combina­tion of concepts that they should have learned.
- Salman Khan

Fixing gaps and lapses: Go back and revisit your study material. Read different books on the same topic. You will see the explanations from different angles and the material will make more sense. Work on actively applying the concept in a new context.

Reference

The One World Schoolhouse by Salman Khan

## Tuesday, January 21, 2020

### Third Solution

We're going to iterate and find a third algorithm,  Let's go through our arsenal of sorting algorithms, what else is useful? We have an interesting sorting algorithm from Quick sort where we use a pivot and we recursively sort different parts of the array based on partitioning the array into the smaller than the pivot and larger than the pivot.

We can recognize that sorting is useful for solving our new problem. Maybe we can modify a sorting algorithm and design a new algorithm that's useful for the current problem. The problem of finding the k'ths smallest element.

So what if we picked a pivot in our elements, in our array of elements and thought through what happens when we sort the, not sort, partition the array into the elements that are smaller than the pivot and those that are bigger than the pivot. Now, we're not looking for fully sorted array at the end of this procedure, what we want is the k'ths smallest element.

What's useful here is that if we partition the array into those that are smaller than the pivot and those bigger than the pivot, than if we only have say three elements that are smaller than the pivot. Then the third smallest element over all is going to be the maximum of those three elements because the pivot's going to be bigger and all of the other elements in the array are going to be bigger than those bottom three elements.

So they're not going to be the third smallest and so the beauty of this approach is going to be that we only need to recursively look at only roughly half of the elements each time if we're lucky with our choice of pivot. And so what we can do is at each stage pick some random element of the array. Partition the array into those elements that are smaller than the pivot, those elements that are bigger than the pivot. And then look at the size of the set of elements, is it smaller than the pivot and compare that size to the ring.

Because that size of that set is going to tell us whether the k'th smallest element belongs in that set of elements that are smaller than the pivot, or maybe that k'th smallest element is the pivot. Or maybe that case smallest element is bigger than the pivot and so we need to look in the rest of the elements in the array.

We can code this strategy and notice that this is going to be a recursive method. It's great if we can come up with a recursive solution to our problem strategy. We're demonstrating yet another skill in programming and algorithmic development in our interview, we're demonstrating our breadth of knowledge. As we go through this recursive function development, it's going to be very important to test the code, which is why we had that base example that we can keep tracing through.

Now as we develop this new strategy, we still want to think about performance. The performance is going to depend on the fact that when we compare to the pivot at each recursive function call. We hope that we're going to divide our array of elements into the smaller thans and the bigger thans and those are going to be hopefully, roughly the same size to one another and so we get to reduce our problem size exponentially by reducing the array size in half each time.

We're hoping for on average at least,  linear time. A careful analysis of the recursive performance of that function would get us at its expected on time. Now in an interview situation this might seem a little daunting to come up with such an elaborate algorithm and to do its performance analysis. But we need to keep improving the solution.

We never want to be content with the solution that we have at hand. And so when we do have a solution, it's important to think about, does it match the assumptions that we made at the beginning? How will we change it if we had different assumptions? If for example, repeated elements are allowed in the array, what do we have to do differently in our logic? We want to consider performance every time we come up with a new problem solving strategy. Have we made progress or not? Are we coming up with better solutions or are we coming up with just different solutions? Are there tradeoffs for time versus memory?

Think of ways that we can bring in our tools. What we want to do is through our practice, have a wide array of tools that we can apply to new problems.

And when we are approaching a new problem, if we've  practiced a lot, we can go through a mental checklist of all the useful data structures and all of the known algorithms that we've worked through. This can help us solve the new problem using what we've done before.

### Solving Programming Problems

Solving programming problems requires two skills:

1. The design of algorithms
2. The implementation of algorithms

The design of algorithms consists of problem solving and mathematical thinking. This demands skills for analyzing problems and solving them creatively. An algorithm must be both correct and efficient and the core of the problem is often about inventing an efficient algorithm.

Theoretical knowledge of algorithms is an important prerequisite to design algorithms. Typically, a solution to a problem is a combination of well-known techniques and new insights.

The implementation of algorithms requires good programming skills. The solution must be tested using a set of test cases. The implementation must be correct to pass all the test cases.

Coding style must be straightforward and concise. The coding interview programs are short - usually less than 50 lines of code.

Books

Programming Challenges: The Programming Contest Training Manual
Competitive Programming 3: The New Lower Bound of Programming Contests
S. S. Skiena: The Algorithm Design Manual
J. Kleinberg and É. Tardos: Algorithm Design
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein: Introduction to Algorithms

### Second Solution

When you're practicing algorithmic problem solving on the fly, it's important to make the situation as realistic as possible. We are not used to white boarding. We don't often write out code on the whiteboard when we're developing a new program.

Practice problems away from a computer. Either a whiteboard or a piece of paper taped up on the wall, and write out what you would be doing as though you were in the interview situation with someone next to you.

We're now going to go further in the algorithm design. We sorted the array before picking out the kth smallest element. Can we  think about optimizations? Maybe we don't need to sort the whole array, maybe the array is a huge chunk of memory, but we only care about k that is on
the order of millions, not billions. And so what could we do if we were in that sort of a situation?

Now it's time to brainstorm for other strategies to find the kth smallest element. And one data structure that keeps elements in a somewhat organized fashion is a max-heap. We know that in a max-heap, we have this tree structure whose root is the maximum element. If we're looking for the kth smallest element in a group, and we have all k smallest elements arranged in a heap, then the root of that heap will be the kth smallest. It will be the biggest amongst the k smallest. We can build a heap of size k, where we want to make sure that the elements in that heap are the k smallest overall.

Let's think about how that would work with an example. We don't want to have all of the elements in our array in the heap. The heap would be too big. We just want to focus on the k smallest, and we're taking advantage of the difference in magnitude between k, which is the rank that we're looking for,
and the overall size of the array. And so if we restrict our heap to just three elements, say if k = 3.

Then we might walk along our array and insert elements into the heap. And so we insert 17, that first element, into the heap. And then we insert the next element 42. And of course 42 becomes the root because it's bigger than 17. And then we insert 0 as well because we need three elements in our heap. We now look at 5. We want 5 to be in our heap as well because it's smaller than 42, it's smaller than 17. And so it is a candidate for being one of the three smallest elements and that will be captured in the heap, the three smallest elements overall that we've seen so far.

So what we're going to do is to swap out the current maximum element in the heap, remove it from the heap and put 5 in instead. And so 5 goes in and it has to go in, in its correct location so we still have a heap structure. And the advantage of that is now the 17 gets put to the root and so if we find some small element later on then we know that we're going to remove the biggest element in our current heap and put in the smallest element.

So that at each stage we have, the heap is containing the three smallest elements that we've seen so far, and the root is the maximum of those. And so, we continue, we look at 10, and it's gotta go in instead of 17. We look at -3, it's gotta go in, but now 5 becomes the root, and we keep on going with 2 and with 9. And at this point we notice that our heap has three elements and so the third smallest element in our whole array is going to be the root of that heap, and that's beautiful because we can just read off the root of the heap.

We've used a somewhat fancy data structure, but a very standard one that we have in our back pocket. We've used the property that the root is the maximum element of all of the elements in the heap. And that's helping us to solve this problem. We're demonstrating creative problem solving and flexibility. So we're not focused on one particular problem solving strategy, but we're demonstrating that we're thinking about different avenues.

We can now code the solution. When implementing a max-heap, we need to reverse the order of the competitor and so we're demonstrating that we are sophisticated programmers. We also need to test and analyze our new strategy. Check if it performs any better than our very simple sort and then pick off the kth element strategy. So, we can check our code and look for where we have function calls that take some time and how does the performance depend on k and on n.

We notice that at the beginning stage for the first k elements of the array, we're just adding each one of them into the heap. Afterwards, we're only adding into the heap if the current array element that we're looking at is smaller than the maximum element at the root of the heap. And only at that point do we swap the current element into the heap. Now in each of those situations, we have to do some heap operations we are adding into the heap and we're removing the root of the heap as well.

So here it's important to know that heap operations like insert and remove take time that's logarithmic in the size of the heap. Because we might have to traverse all the way down to the bottom of a path and the maximum length path, it could be at worse log the size of the heap log, the size of the tree. And so we see that we're doing these operations. We're doing a constant number of these operations for each array element that we're looking at and so all in all, this algorithm is going to have performance that's O(n log k). We can compare this performance to previous solution.

We're demonstrating our critical thinking by analysis of the two alternate algorithmic approaches. Previous algorithm was O(n log n), and now we have O(n log k). And so we've made some improvement if, in particular, k is going to be much smaller than n but still grows, and so we still want to take that into account. So this is a very different problem solving strategy from the first one we saw.

And we might go even further and that's what we'll do next.

### Working at the Whiteboard

So now that we have a strategy in mind, we're ready to move to the white board and start implementing it.

You'll be talking with an interviewer and you'll be working with them next to a white board. Let's work with the example we have so far. Our strategy for finding the k'th smallest element and the array is to first sort the array, and then just pick out the k'th element. And so, let's go ahead and implement that.

We know that we're supposed to be returning the value of the k'th smallest element, and so we're returning an int. And we want a descriptive method name, and so we call this kthSmallest. And as inputs, we have both the array of elements that we started with, as well as the rank. And so we have int array and we have the rank that we want to return.

And so, here's our head method header. Now, the first thing we want to do in our method is validate the arguments. So check if (K i<=0 || K> array.length. In which case, it doesn't make any sense to ask for the k'th smallest. So in this situation, we want to thrown an exception, because the arguments were bad. And so, we're going to throw a new IllegalArgument Exception.

If we do have good arguments and then our plan was to sort, and we can use a library method for that. We've got arrays.sort(array) and then we're going to return the element in the kth position after we've sorted the array. We're assuming k is indexed by starting with index 0. Then what we want to return is the element of the array[k-1], rather than k. And so what we have now on the board is a description of the algorithm that we've articulated for solving the problem. And what we would do now is walk through with an example.

They might ask us to implement this sorting method instead of using a library call. They might ask us to go further with the algorithm.

### First Solution

So we've worked through this example and now we understand the problem. It's good to reaffirm the assumptions that we're making before we move on to the solution.

We know that array may have some duplicate elements. We're allowed to change the array.

To find the kth smallest element, we build up to the kth smallest element by looking for the smallest element and then the next smallest element and then the next smallest element after that and then keep on going until we've gone to the kth one.

We notice that this is somewhat similar to the procedure for selection sort. And with selection sort, we find the smallest element and we swap that to a first position of the array so that we can think about ignoring it afterwards or discarding it. And then we focus on the rest of the list and find the smallest element among those remaining elements, swap that to the beginning, and then just keep on focusing on the remaining elements. And this would give us an algorithm that's a variant of selection sort that we already know. We can use our previous knowledge to design algorithm for the given problem.

But before we code this solution, let's analyze it to see if it's worth coding. Because it was our first stab at how we might solve this problem. So it's good to stop and think to evaluate before we go further in this direction. If we evaluate the performance of this approach, what we're doing at each point is finding the minimum element of an array of numbers. If we wanted to find the minimum amongst an array of elements, we have to look at each one of those elements. That takes linear time.

And so even though the number of elements that we are considering each time decreases by one, we are still doing this k many times. And so, for really small k, if we just need to find the very smallest element or the second smallest element, in that situation, this would give a linear algorithm. But in the more general situation, where k maybe is n/ 2, and we're finding the element that is right in the middle, the median, then if we have to do this approach, say n/2 many times or any O(n)many times, then all of a sudden our algorithm becomes quadratic.

And that's a problem. Because quadratic algorithms are slow, especially if our problem has something to do with sorting. And so we've already seen how the algorithm that we are devising is related to sorting, how it's related to the selection sort algorithm. Maybe we can use that insight to come up with a better solution.

And so what if we sorted the array before doing anything in terms of finding the kth element? And as a preprocessing step, let's just apply our favorite sorting algorithm and organize all the elements from smallest to biggest. And the advantage of doing that is that, at this point, the element that we care about, the kth smallest element, is in position k in the array. And accessing an element in a particular position in the array is a constant time operation.

So overall, we've now come up with an algorithm that takes however long a sorting takes for the preprocessing step. And then O(1) time for the second step which is retrieving the kth smallest element. The advantage of having these two separate steps is that sorting is a well studied problem and we know that in the worst case there are algorithms that solve sorting with nlog(n) time. That's a big improvement to quadratic time.

And so we're feeling pretty good that we've made a pretty dramatic improvement to our original naive approach to solving the problem, and now we have a slightly better approach. And at this point, we might be feeling comfortable enough with this approach to go and code it on the whiteboard.

## Algorithmic Problem Solving

This is the strategy to use when you're faced with a new problem that you've never solved before and you're being asked to work through during the interview.

Let's look at a step by step approach to solve a new problem so that you feel empowered when you're dealing with the question that you've never thought about before.

### Step 1

So the first step is to make sure that you really understand the question.

• What the parameters involved?
• What is the goal for the solution?

Your first task is to ask lots of questions. When faced with a hard question, ask as many questions as you can think of to tease out the relevant assumptions that the interviewer has in mind or that might be relevant for your solution to tease out the scope of the problem.  Understand what you're trying to analyze and solve.

### Step 2

Now once you've asked a lot of questions to make sure that you clarify the problem and know where to go, then the next step is to confirm your understanding by working through an example.

Working through an example is really useful because both it lets you get those creative juices flowing and start thinking towards a solution.

It also lets you take some time and think through the problem very concretely about what difficulties might be involved, where are the sticking points of any solution we'd have to solve. And also if there are any hidden assumptions or implicit questions that you might need to address again and go back to that first step of asking more questions to the interviewer to make sure that you've mapped out the scope of the solution that you need to come up with.

Okay, so at this point we have a very good sense of the task at hand and we're ready to solve it.

### Step 3

So in the next stage of the strategy we try to come up with a first solution. You want to make sure that at least you got some approach to solving the problem, even if it's not a good approach. This is the brute force approach.

You've got some way of tackling it. And this approach does not have to be clever or elegant. But you want to make sure that you've got a correct solution.

### Step 4

And so as you're developing this brute force approach as first naive solution to the problem, the next step is to test it. Now, that means testing it with normal input as well as edge cases. Make sure that your brute-force approach can handle both.

And then think through a little bit if you were to implement this first solution, how would you do it? What data structures would be useful? How would those data structures interact with the problem that you're working with? In particular, what performance would you get out of this implementation? And any trade-offs that you might be thinking about in terms of maybe using more memory to speed up the performance, or vice verse. So, we've got a solution. But we didn't spend very much time trying to make it clever or elegant.

### Step 5

So our next step of the strategy is to iterate this whole process of coming up with a candidate approach to solving the problem. Evaluating, testing and poking at it, making sure that it does what you want it to do or if it doesn't, thinking about ways to fix it and refine your solution as much as you can.

And you'll notice when you're in the interview that often, the interviewer will try to guide you towards iterating your solution, asking you if it could be made better, asking you if there are any trade-offs that have in mind. And you want to think through this checklist of how you evaluate your strategy at each stage of the problem solving process.

Now when we iterate, we come up with a great solution, that we think at the high level will do a pretty good job. We've done an asymptotic analysis. We have a sense of how long asymptotically, so in the Big O notation each of the operations involved will take.

### Step 6

Finally in Step 6 of our strategy, we finally write some code. And so only once we've done this very thorough analysis of the problem, you have a very good sense of what you want to implement, now you can start writing some code on the whiteboard.

Programming on a white board in the interview situation is quite different from typing it out in a computer. It's a good idea to practice on whiteboard during preparation.

### Becoming Intelligent

What determines our intelligence?

One school of thought is that you are either just born with it or you don't. The truth is that your intelligence can be changed. Our brains are a lot like a muscle.

We know that you can grow your muscles by going into the gym and doing exercise and straining your muscles.

You don't just work on things that are easy for your muscles to do; you do things that your muscles have to struggle with, that your muscles have to strain with and then they rebuild themselves and they come back stronger.

By struggling, its a signal to your body to devote more resources to that part of the body.  And we see that exact same thing with the brain. that is constantly being challenged. Your brain is like a muscle the more you use it, the stronger it gets and that the best way to grow it isn't to do things that are easy for you. What helps your brain is when you struggle with things.

Research shows that your brain grows the most not when you get a question right, but when you get a question wrong. When you are facing those times of little bit of adversity or frustration, you can feel good about the fact that those are actually the times that your growing the most.

Research tells us that when you get something wrong, when you challenge your brain, when you review why you got it wrong, when you really process that feedback, that's when your brain grows the most.

And then if you keep doing that, you are well on your way to having a stronger, more able, and smarter brain.

## Learning Curve

When you face failure, do you understand that you're on a learning curve? If so, this gives you a path into the future.

## Coping with Challenge

How do you cope with challenge and difficulty? What if you were given problems that is slightly too hard for you? You may say, "I love a challenge," Do you think your abilities can be developed? If you answered yes, this is the growth mindset.

If you feel it is tragic or catastrophic, this is fixed mindset. From this perspective your intelligence has been up for judgment and you failed. Do you run from difficulty? Engage with error. Engage deeply. Process the error. Learn from it and correct it.

## Process vs Outcome

Are you obsessed with the outcome? Do not praise intelligence or talent. But praise the process you engage in, your effort, your strategies, your focus, your perseverance, your improvement. This process praise creates individuals who are hardy and resilient. Reward for effort, strategy and progress.

The usual games rewards you for getting answers right, right now, but if the game rewards the process, you get more effort, more strategies, more engagement over longer periods of time, and more perseverance when you hit hard problems.

Every time you push out of your comfort zone to learn something new and difficult, the neurons in your brain can form new, stronger connections and over time, you can get smarter. This happens because the meaning of effort and difficulty were transformed.

Before, effort and difficulty made you feel dumb, made you feel like giving up, but now, effort and difficulty, that's when your neurons are making new connections, stronger connections.

That's when you're getting smarter. You put more effort into your preparation. You believe that abilities are capable of such growth.

## Sunday, January 12, 2020

### Programming Interview Books

Read first: Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition It's a good warm-up, and you'll discover quickly where you are weak and need to focus more.

Read second: Cracking the Coding Interview, 6th Edition  I found the Moderate and Hard sections at the end to be way too much for what a new software engineer should expect in an interview.

If you have more time,  here is a good book on problem-solving in general.
But don't expect to do them all. See this as a supplement for getting a little extra practice in problem areas.

A great book: Algorithms for Interviews - A Problem Solving Approach