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.
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.
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 application 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 confidence 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.
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 confidence 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 diagnostic 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?
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
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 combination 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.
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:
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 É. Tardos: Algorithm Design
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein: Introduction to Algorithms
- The design of algorithms
- 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 É. 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.
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.
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.
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.
Sunday, January 19, 2020
How to Solve New Problems During Coding Interview
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.
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.
Growth Mindset : Perspective on Failure
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.
Reference
https://www.youtube.com/watch?v=_X0mgOOSpLU
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.
A great book: Algorithms for Interviews - A Problem Solving Approach
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
Thursday, January 09, 2020
Coding Interview Preparation Useful Links
1. A general guide to preparing for a technical interview.
2. Useful for language specific questions
3. How to Determine Complexities
4. HiredInTech Free Course
5. Sorting Algorithms Cheatsheet
6. Coding Interview University
7. Retaining Computer Science Knowledge
8. My Process for Coding Interview Book Exercises
9. Dynamic Programming – From Novice to Advanced
10. MIT Interview Materials
11. Dynamic Programming – From Novice to Advanced
12. Dissect Problem Statement
2. Useful for language specific questions
3. How to Determine Complexities
4. HiredInTech Free Course
5. Sorting Algorithms Cheatsheet
6. Coding Interview University
7. Retaining Computer Science Knowledge
8. My Process for Coding Interview Book Exercises
9. Dynamic Programming – From Novice to Advanced
10. MIT Interview Materials
11. Dynamic Programming – From Novice to Advanced
12. Dissect Problem Statement
Saturday, January 04, 2020
Coding Interview Success Blueprint
The following notes is based on the book: The 4 Disciplines of Execution by Chris McChesney.
There are some goals that are so important or require such significant change that simply trying harder isn't going to get it done. If you have one of those important goals, if you are dedicated to getting breakthrough results, this approach is for you.
For example, if you want to achieve an ambitious career goal, the challenge is usually not one of capability. It's not that they're incapable. It's not that people are lazy. It's not that they're stupid. The problem is they're busy.
There are rules for doing this. We call those rules, disciplines and there are four of them. When you hear them, they're going to seem very simple, almost obvious. But I assure you, they are the key to achieving breakthrough results.
Discipline 1: Focus on the Wildly Important Goal
Focus
Discipline one is focus on the wildly important. And what that means is to select a single, wildly important goal, in addition to everything else that has to happen in your life. Think about when you achieved something truly significant. How many things were you focused on? Focus is the first irrefutable law of execution.
There are two key aspects to the first discipline. They both begin with the letter F. The first we've talked about that's focus.
Finish Line
The second is finish line. The wildly important goal has to have a finish line. You have to know how you won. The easiest way to do that is to put it in the form of from X to Y by when. For example, you wouldn't want the goal of coding better, right? Even if that was really important to you. There's no specific finish line associated with that. So you might think of a result associated with coding better and define the goal around that, for instance, getting your dream job by the end of the year. If you wanted to gain coding skills, you wouldn't just say gain coding skills, you put it in the form of going from Software Engineer to say Software Engineer at Google by March 1. There's a specific finish line for people to really succeed. There's a switch in our heads we call the game on switch and we want to throw the game on switch. The first discipline of execution requires that we narrow the focus and define the finish line.
Discipline 2: Act on the Lead Measures
Identify the Lever
Discipline two, act on the lead measures. This is the discipline of leverage. The wildly important goal that you identified and discipline one is like a big heavy rock. It's like a big rock, because you haven't moved it yet. The discipline two is all about identifying the lever that we're going to use to move the rock. If you've got a rock, you're going to need a lever, and all levers share two characteristics. First, you can move a lever, it's influenceable. Unlike the rock, it moves. And second, it's predictive, you can predict that when the lever moves, the rock is also going to move.
Influenceable and Predictive
Those are the same two characteristics of a lead measure. If your goal is to get your dream job, going from Software Engineer to Software Engineer at Google, if that was the big rock, we had to move. What's the lever? What could we measure that is both influenceable and predictive of gaining coding skills. If you said study and practice, you're on exactly the right page. We can influence our study and our number topics mastered, our number of coding problems practiced much more directly than we can influence getting the dream job, and it is predictive of gaining coding skills. Now you may at this point, be saying to yourself, wow, this is brilliant. How do you guys do it? Are you telling me that if I want to get my dream job, I should study and practice? There's a huge difference between knowing that we should study and practice and knowing how many topics we've mastered, and how many coding problems we have practiced. The only people that know that data are the people that are gaining coding skills.
Discipline 3: Keep a Compelling Scoreboard
Discipline of Engagement
Discipline three is keep a compelling scoreboard. It is the discipline of engagement. It's what keeps us in the game. People play differently when they are keeping score. If you are watching group of kids play basketball from a block away. Could you tell even if you couldn't hear them, just by watching them whether or not they were keeping score? What would you look for? What would give it away? Would there be a change in intensity? Would there be more celebration? Would they be more likely to play by the rules, if they're keeping score, you're going to see all that more. There's a huge difference in people's behavior. There is a huge difference in your behavior when you're keeping score.
Characteristics of a Compelling Scoreboard
A scoreboard that's going to keep you engaged are fairly straightforward.
- It has to be very simple.
- It has to be visible.
- You've got to see both the lead measure, the thing you're acting on, as well as the results you're hoping for.
- And finally, just by looking at it, you have to be able to tell whether you are winning or losing.
Create a Winnable Game
What you've done is you've turned that goal, that breakthrough result into something that feels like a game. There is no greater driver of engagement than feeling like you're winning.
Discipline 4: Create a Cadence of Accountability
Discipline four is how we play that game. Discipline four is the discipline of accountability, create a cadence of accountability. This requires a weekly rhythm of public accountability and will require you to recruit a coach or a partner, somebody that you will feel accountable to. And you'll need to visit with this person every week for at least a few minutes. This is one of the reasons why it's essential to pick a wildly important goal because we are talking about a serious commitment here. It's best if this meeting happens at the same time every single week. During this meeting, there are three things that need to happen.
- Report on the commitments that you made last week, every week. You're going to make a few commitments to move the lead measure.
- Review and update the scoreboard.
- Finally, make a commitment for what you're going to do to move the lead measures next week.
There's a reason that we call these the four Disciplines of Execution. These require discipline, this delivers, breakthrough results, in the words of Jim Rohn: "We must all suffer from one of two pains, the pain of discipline, or the pain of regret". We really like the pain of discipline.
Customized Action Plan
I can guide you in creating a customized action plan for your situation. Sign up here https://go.oncehub.com/BalaParanj for your FREE session and we will figure it all out. Why is this free? Because I believe in Zig Ziglar's quote:
You can get everything in life you want if you will just help enough other people get what they want.
Subscribe to:
Posts (Atom)