Saturday, 29 October 2016
5 Coding Interview Tips!
5 Coding Interview Tips
How to get better at technical interviews without practicing
ATTITUDE
Before you begin, you need to approach your practice sessions with the right attitude. Think of programming interviews as a form of standardized testing. Don't whine and think to yourself, "but I'll never have to manually reverse a linked list in my job, so these questions are lame!"
Ph.D. students are especially elitist because they somehow think that they are "above" preparing for petty programming interviews. That is a fine attitude if you are applying for pure research or academic jobs, but if you are interviewing at a company that uses programming interviews, then you've gotta prep!
As an analogy to high school standardized testing, I raised my SAT scores by 400 points (back when they were still out of 1600) through a few months of intense practice; there is no way that I could've gotten into MIT with my original scores.
So before you even start practicing, you've gotta just view these interview questions as yet another standardized test, another game that you need to play well and beat.
PRACTICING
I don't care how smart you are; there is simply no substitute for practicing a ton of problems. Work on problems for as long as you can before your brain explodes, then take a long break to reflect and internalize the lessons you learned through your struggle. And then repeat!
I practiced in front of the whiteboard for 1 to 2 hours at a time and did 1 to 3 practice sessions per day for two full weeks right before my interviews. That was around 40 hours of focused practice, which felt about right to me. You might need to practice more if you have less programming experience.
I used these two books as my main sources of practice problems:
- Programming Interviews Exposed
- Cracking the Coding Interview
In addition, the Stanford lecture notes on linked lists and binary trees were also a great source of problems:
Even if you are not familiar with the programming languages used in these solutions, you can still code up solutions in your own language of choice and write tests to verify that they are correct.
Getting physical
- Buy your own whiteboard markers and practice using them. I personally like "MARKS-A-LOT low-odor markers", since the markers found in most office conference rooms make me nauseous.
- Always practice by writing code on a whiteboard. If you are in school, then there should be plenty of whiteboards around campus for you to use. If you are working in an office, then you can use conference rooms after-hours.
- If you cannot practice in front of a whiteboard, then practice by writing code on blank pieces of white paper.
- After you write out your code by hand, type it into your computer to see if it actually compiles and runs correctly. This is an easy way to check for syntax or logical errors in your code. After you have practiced for a few weeks, you should be able to write error-free code on the whiteboard.
- After a week or two of intense practice, you should be able to hand-write legible, well-indented, well-aligned code on the whiteboard. If you cannot do that during your actual interview, then that will make a bad impression. Messiness is a turn-off.
- If you are doing a phone interview where you need to write code in Google Docs (or some other shared document), then practice writing code in that medium! Remember, you will never have a compiler during your interview, so you need to get good at writing compilable, runnable, and correct code even without a compiler handy.
AT THE INTERVIEW
When the interviewer presents a question to you, immediately sketch out a bunch of examples and ask a ton of clarifying questions to make sure you understand exactly what the interviewer is asking you to do.
Draw several examples and ask your interviewer questions of the form, "for this case, you want the result to be X, right?" Do not make any assumptions without first checking them over with your interviewer.
And whatever you do, don't flip out or try to jump straight to coding up an answer. Chances are, you either
- have no idea how to solve the problem, so you flip out and panic,
- or you think you have heard the problem before, so you want to jump the gun and sketch out a solution right away.
The former is obviously bad, but the latter might actually be worse, since you might have seen a similar problem that does not exactly match the problem you have been given. You will look like an idiot if you try to solve the wrong problem by recalling it from memory!
COMMON PROGRAMMING INTERVIEW IDIOMS
Here are some common idioms and patterns that I have observed from doing hundreds of practice interview problems.
Strings
- Get comfortable manipulating a string as an array of characters, one character at a time (like C-style strings).
- Numerical arrays
- Think about iterating backwards over the array elements as well as forwards. Backwards iteration is useful for, say, merging the contents of two arrays "in-place" (i.e., using O(1) outside storage).
- Would the problem be easier if your array were sorted? If so, you can always tell the interviewer that you'd first do an O(n lg n) sort. Heapsort is an asymptotically optimal "in-place" sort. Once your array is sorted, think about how you can use a variant of binary search to get O(lg n) performance rather than O(n) for an algorithm based on linear scanning.
Mappings and sets (hash tables)
- Always think of mapping keys to values to make your life easier. If you can scan through your dataset and create an auxiliary hash table to map keys to values, then you can do O(1) lookups in a latter part of your algorithm.
- For some array-based problems, you might find it useful to create a "reverse mapping" between array elements and their indices. e.g., "the number 42 appears at index 6 in the array" is represented as a mapping of "42 -> 6".
- You can use a hash table as a set to do O(1) membership lookups. If you are being tested on low-level skillz, use bitsets and the proper bit-level operations to operate on them.
Linked lists
- Linked list problems almost always involve singly-linked lists.
- If you are implementing an iterative algorithm to operate on a singly-linked list, chances are that you'll need to walk two pointers, which I like to call
cur and prev, down the list until one is null.
- Some problems require you to keep a gap of N elements between your
cur and prev pointers.
- Some problems requires your
cur and prev pointers to advance at different speeds. e.g., moving prev up by one element while moving cur up by two elements.
- For most recursive algorithms, the base case is when the pointer is null.
- Sometimes you might need to keep a pointer to the final (tail) element of the list as well as to the head.
cur and prev, down the list until one is null.cur and prev pointers.cur and prev pointers to advance at different speeds. e.g., moving prev up by one element while moving cur up by two elements.Binary trees
- Remember that not all binary trees are binary search trees, and know the difference between the two.
- Know about the idea of a balanced binary search tree (e.g., AVL tree or red-black tree), but don't worry about being able to implement one during an interview.
Graphs
- Whenever you need to represent binary relationships, think about using a graph. e.g., X is friends with Y, or X has a crush on Y, or Task X needs to be done before task Y.
- Now that you have a graph representation, what can you do with it? Chances are, you won't be asked to implement any sort of sophisticated graph algorithm since you simply don't have time in a 1-hour interview to do so.
- Definitely know how to implement a depth-first search using a stack data structure (or using recursion, which implicitly uses your function call stack)
- Definitely know how to implement breadth-first search using a queue data structure.
- Draw a few examples of graphs for your particular problem and see what common structure arises, then tailor your algorithms to that type of structure. For example, you might find that the graphs for your problem are all a cyclic, or that they always have one unique source and sink node, or that they are bipartite (e.g., for 'matchmaking' problems), or that they are actually trees in disguise :)
- Know about the idea of topological sort.
Edge cases
Always test your algorithm on edge-case examples. e.g., what if the user passes in an empty list or tree, or a list/tree with a single node?
Stickey Widget For Blogger
///paste this code above </head> tag
//change the id
<script src='http://ajax.googleapis.com/ajax/libs/jquery/1.3/jquery.min.js' type='text/javascript'/>
<script type='text/javascript'>
$(function() {
var ks_widget_top = $('#HTML1').offset().top;
var ks_sticky_widgets = function(){
var ks_current_top = $(window).scrollTop();
if (ks_current_top > ks_widget_top) {
$('#HTML1').css({ 'position': 'fixed', 'top':0, 'z-index':999999 });
} else {
$('#HTML1').css({ 'position': 'relative' });
}
};
ks_sticky_widgets();
$(window).scroll(function() {
ks_sticky_widgets();
});
});</script>
Best Blogger Template For Coding
Check Out This Website You Just Visited!
Go To Home Page .
OR
Check Out Our Programmes Section.
Download This Template :
4 Reasons why Your Program Crashes
1. Our program may depend on some element of randomness: user input, randomly generated number, time, etc
2. If our program is using an uninitialized variable, it could be accessing data it isn't supposed to (same with accessing something outside of an arrays indices)
3. Our program may be using an external library that crashes all the time.
4. Stack overflows
2. If our program is using an uninitialized variable, it could be accessing data it isn't supposed to (same with accessing something outside of an arrays indices)
3. Our program may be using an external library that crashes all the time.
4. Stack overflows
Program to remove middle character from a string
import java.util.*;
public class DeleteMiddle {
public static class Node {
Node next;
char val;
public Node(char val) {
this.val = val;
}
public String toString() {
StringBuilder sb = new StringBuilder();
Node temp = this;
while (temp != null) {
sb.append(temp.val);
temp = temp.next;
}
return sb.toString();
}
}
public static boolean deleteMiddle(Node node) {
if (node == null || node.next == null) {
return false;
} else {
node.val = node.next.val;
node.next = node.next.next;
return true;
}
}
public static void main(String[] args) {
Node a = new Node('a');
Node b = new Node('b');
Node c = new Node('c');
Node d = new Node('d');
Node e = new Node('e');
a.next = b;
b.next = c;
c.next = d;
d.next = e;
System.out.println(a);
deleteMiddle(c);
System.out.println(a);
}
}
public class DeleteMiddle {
public static class Node {
Node next;
char val;
public Node(char val) {
this.val = val;
}
public String toString() {
StringBuilder sb = new StringBuilder();
Node temp = this;
while (temp != null) {
sb.append(temp.val);
temp = temp.next;
}
return sb.toString();
}
}
public static boolean deleteMiddle(Node node) {
if (node == null || node.next == null) {
return false;
} else {
node.val = node.next.val;
node.next = node.next.next;
return true;
}
}
public static void main(String[] args) {
Node a = new Node('a');
Node b = new Node('b');
Node c = new Node('c');
Node d = new Node('d');
Node e = new Node('e');
a.next = b;
b.next = c;
c.next = d;
d.next = e;
System.out.println(a);
deleteMiddle(c);
System.out.println(a);
}
}
Program to remove duplicate Character from a String
import java.util.*;
public class RemoveDups {
public static class Node {
Node next;
char val;
public Node(char val) {
this.val = val;
}
public String toString() {
StringBuilder sb = new StringBuilder();
Node temp = this;
while (temp != null) {
sb.append(temp.val);
temp = temp.next;
}
return sb.toString();
}
}
public static void removeDupes(Node node) {
Set<Character> set = new HashSet<Character>();
set.add(node.val);
Node prev = node;
Node temp = node.next;
while (temp != null) {
if (set.contains(temp.val)) {
prev.next = temp.next;
}
else {
set.add(temp.val);
prev = temp;
}
temp = temp.next;
}
}
public static void main(String[] args) {
Node a = new Node('F');
Node b = new Node('O');
Node c = new Node('L');
Node d = new Node('L');
Node e = new Node('O');
Node f = new Node('W');
Node g = new Node(' ');
Node h = new Node('U');
Node i = new Node('P');
a.next = b;
b.next = c;
c.next = d;
d.next = e;
e.next = f;
f.next = g;
g.next = h;
h.next = i;
System.out.println(a);
removeDupes(a);
System.out.println(a);
}
}
public class RemoveDups {
public static class Node {
Node next;
char val;
public Node(char val) {
this.val = val;
}
public String toString() {
StringBuilder sb = new StringBuilder();
Node temp = this;
while (temp != null) {
sb.append(temp.val);
temp = temp.next;
}
return sb.toString();
}
}
public static void removeDupes(Node node) {
Set<Character> set = new HashSet<Character>();
set.add(node.val);
Node prev = node;
Node temp = node.next;
while (temp != null) {
if (set.contains(temp.val)) {
prev.next = temp.next;
}
else {
set.add(temp.val);
prev = temp;
}
temp = temp.next;
}
}
public static void main(String[] args) {
Node a = new Node('F');
Node b = new Node('O');
Node c = new Node('L');
Node d = new Node('L');
Node e = new Node('O');
Node f = new Node('W');
Node g = new Node(' ');
Node h = new Node('U');
Node i = new Node('P');
a.next = b;
b.next = c;
c.next = d;
d.next = e;
e.next = f;
f.next = g;
g.next = h;
h.next = i;
System.out.println(a);
removeDupes(a);
System.out.println(a);
}
}
Friday, 28 October 2016
Program to Add two number without using Plus Sign | Java
public class AddWithoutPlus {
public static int add(int a, int b) {
if (b > a) {
int temp = b;
b = a;
a = temp;
}
int carry = 0;
while (b != 0) {
carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
public static int recursiveAdd(int a, int b) {
if (b == 0)
return a;
else
return recursiveAdd(a ^ b, (a & b) << 1);
}
public static void main(String[] args) {
int a = 12;
int b = 34;
System.out.println(add(a, b));
System.out.println(recursiveAdd(b, a));
}
}
public static int add(int a, int b) {
if (b > a) {
int temp = b;
b = a;
a = temp;
}
int carry = 0;
while (b != 0) {
carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
public static int recursiveAdd(int a, int b) {
if (b == 0)
return a;
else
return recursiveAdd(a ^ b, (a & b) << 1);
}
public static void main(String[] args) {
int a = 12;
int b = 34;
System.out.println(add(a, b));
System.out.println(recursiveAdd(b, a));
}
}
Program to rotate string | java
import java.util.*;
public class StringRotation {
public static boolean isRotation(String s1, String s2) {
if (s1.length() != s2.length())
return false;
String s3 = s1 + s1;
return s3.contains(s2);
}
public static void main(String[] args) {
System.out.println(isRotation("waterbottle", "erbottlewat") ? "True" : "False");
System.out.println(isRotation("waterbottl", "erbottlewat") ? "True" : "False");
System.out.println(isRotation("pandeesh", "deeshpand") ? "True" : "False");
}
}
public class StringRotation {
public static boolean isRotation(String s1, String s2) {
if (s1.length() != s2.length())
return false;
String s3 = s1 + s1;
return s3.contains(s2);
}
public static void main(String[] args) {
System.out.println(isRotation("waterbottle", "erbottlewat") ? "True" : "False");
System.out.println(isRotation("waterbottl", "erbottlewat") ? "True" : "False");
System.out.println(isRotation("pandeesh", "deeshpand") ? "True" : "False");
}
}
program to Convert All 1 into Zero Matrix | Java
import java.util.*;
public class ZeroMatrix {
public static void zero(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
col[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] == true || col[j] == true)
matrix[i][j] = 0;
}
}
return;
}
public static void main(String[] args) {
int[][] matrix = new int[][]{
{0, 1, 1, 1, 0},
{1, 0, 1, 0, 1},
{1, 1, 1, 1, 1},
{1, 0, 1, 1, 1},
{1, 1, 1, 1, 1}
};
for (int i = 0; i < matrix.length; i++)
System.out.println(Arrays.toString(matrix[i]));
zero(matrix);
System.out.println();
for (int i = 0; i < matrix.length; i++)
System.out.println(Arrays.toString(matrix[i]));
}
}
public class ZeroMatrix {
public static void zero(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
col[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] == true || col[j] == true)
matrix[i][j] = 0;
}
}
return;
}
public static void main(String[] args) {
int[][] matrix = new int[][]{
{0, 1, 1, 1, 0},
{1, 0, 1, 0, 1},
{1, 1, 1, 1, 1},
{1, 0, 1, 1, 1},
{1, 1, 1, 1, 1}
};
for (int i = 0; i < matrix.length; i++)
System.out.println(Arrays.toString(matrix[i]));
zero(matrix);
System.out.println();
for (int i = 0; i < matrix.length; i++)
System.out.println(Arrays.toString(matrix[i]));
}
}
program to Rotate Matrix | Java
import java.util.*;
public class RotateMatrix {
public static void rotate(int[][] matrix) {
int n = matrix.length;
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - layer;
for (int i = first; i < last; i++) {
int offset = i - first;
int top = matrix[first][i];
// left -> top
matrix[first][i] = matrix[last-offset][first];
// bottom -> left
matrix[last-offset][first] = matrix[last][last-offset];
// right -> bottom
matrix[last][last-offset] = matrix[i][last];
// top -> right
matrix[i][last] = top;
}
}
}
public static void main(String[] args) {
int[][] arr = new int[][]{
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20},
{21, 22, 23, 24, 25}
};
rotate(arr);
for (int[] a : arr)
System.out.println(Arrays.toString(a));
}
}
public class RotateMatrix {
public static void rotate(int[][] matrix) {
int n = matrix.length;
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - layer;
for (int i = first; i < last; i++) {
int offset = i - first;
int top = matrix[first][i];
// left -> top
matrix[first][i] = matrix[last-offset][first];
// bottom -> left
matrix[last-offset][first] = matrix[last][last-offset];
// right -> bottom
matrix[last][last-offset] = matrix[i][last];
// top -> right
matrix[i][last] = top;
}
}
}
public static void main(String[] args) {
int[][] arr = new int[][]{
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20},
{21, 22, 23, 24, 25}
};
rotate(arr);
for (int[] a : arr)
System.out.println(Arrays.toString(a));
}
}
program to compress string | Java
import java.util.*;
public class StringCompression {
public static String compress(String str) {
StringBuilder sb = new StringBuilder();
int count = 1;
for (int i = 0; i < str.length() - 1; i++) {
if (str.charAt(i) != str.charAt(i + 1)) {
sb.append(str.charAt(i));
sb.append(count);
// reset count to 1
count = 1;
} else
count++;
}
// add last set of characters
sb.append(str.charAt(i));
sb.append(count);
String x = sb.toString();
if (x.length() > str.length())
return str;
else
return x;
}
public static void main(String[] args) {
System.out.println(compress("aabccccaaa"));
System.out.println(compress("abcdef"));
}
}
public class StringCompression {
public static String compress(String str) {
StringBuilder sb = new StringBuilder();
int count = 1;
for (int i = 0; i < str.length() - 1; i++) {
if (str.charAt(i) != str.charAt(i + 1)) {
sb.append(str.charAt(i));
sb.append(count);
// reset count to 1
count = 1;
} else
count++;
}
// add last set of characters
sb.append(str.charAt(i));
sb.append(count);
String x = sb.toString();
if (x.length() > str.length())
return str;
else
return x;
}
public static void main(String[] args) {
System.out.println(compress("aabccccaaa"));
System.out.println(compress("abcdef"));
}
}
Program to check palindrome permutations of a string | java
import java.util.*;
public class PalindromePermutation {
public static boolean permuteHash(String str) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
Character c = Character.toLowerCase(str.charAt(i));
if (!Character.isLetter(c))
continue;
if (map.containsKey(c))
map.put(c, map.get(c) + 1);
else
map.put(c, 1);
}
int odd = 0;
for (Character key : map.keySet())
if (map.get(key) % 2 != 0)
odd++;
if (odd > 1)
return false;
else
return true;
}
public static void main(String[] args) {
System.out.println(permuteHash("Tact Coa") ? "True" : "False");
System.out.println(permuteHash("test") ? "True" : "False");
}
}
public class PalindromePermutation {
public static boolean permuteHash(String str) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
Character c = Character.toLowerCase(str.charAt(i));
if (!Character.isLetter(c))
continue;
if (map.containsKey(c))
map.put(c, map.get(c) + 1);
else
map.put(c, 1);
}
int odd = 0;
for (Character key : map.keySet())
if (map.get(key) % 2 != 0)
odd++;
if (odd > 1)
return false;
else
return true;
}
public static void main(String[] args) {
System.out.println(permuteHash("Tact Coa") ? "True" : "False");
System.out.println(permuteHash("test") ? "True" : "False");
}
}
program to put HTML links around URLs strings | java
import java.util.*;
import java.io.*;
public class URLify {
public static char[] URLify(char[] chars, int len) {
int spaces = countSpaces(chars, len);
int end = len - 1 + spaces * 2;
for (int i = len - 1; i >= 0; i--) {
if (chars[i] == ' ') {
chars[end - 2] = '%';
chars[end - 1] = '2';
chars[end] = '0';
end -= 3;
} else {
chars[end] = chars[i];
end--;
}
}
return chars;
}
static int countSpaces(char[] chars, int len) {
int count = 0;
for (int i = 0; i < len; i++)
if (chars[i] == ' ')
count++;
return count;
}
public static void main(String[] args) throws IOException {
char[] chars = "Mr John Smith ".toCharArray();
System.out.println(URLify(chars, 13));
}
}
import java.io.*;
public class URLify {
public static char[] URLify(char[] chars, int len) {
int spaces = countSpaces(chars, len);
int end = len - 1 + spaces * 2;
for (int i = len - 1; i >= 0; i--) {
if (chars[i] == ' ') {
chars[end - 2] = '%';
chars[end - 1] = '2';
chars[end] = '0';
end -= 3;
} else {
chars[end] = chars[i];
end--;
}
}
return chars;
}
static int countSpaces(char[] chars, int len) {
int count = 0;
for (int i = 0; i < len; i++)
if (chars[i] == ' ')
count++;
return count;
}
public static void main(String[] args) throws IOException {
char[] chars = "Mr John Smith ".toCharArray();
System.out.println(URLify(chars, 13));
}
}
program to find permutation of string | java
import java.util.*;
import java.io.*;
public class CheckPermutations {
public static boolean isPermutation(String s1, String s2) {
char[] a = s1.toCharArray();
char[] b = s2.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
if (a.length != b.length) return false;
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
public static void main(String[] args) {
System.out.println(isPermutation("abc", "cba") ? "It is a permutation" : "It is not a permutation");
System.out.println(isPermutation("test", "estt") ? "It is a permutation" : "It is not a permutation");
System.out.println(isPermutation("testt", "estt") ? "It is a permutation" : "It is not a permutation");
}
}
import java.io.*;
public class CheckPermutations {
public static boolean isPermutation(String s1, String s2) {
char[] a = s1.toCharArray();
char[] b = s2.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
if (a.length != b.length) return false;
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
public static void main(String[] args) {
System.out.println(isPermutation("abc", "cba") ? "It is a permutation" : "It is not a permutation");
System.out.println(isPermutation("test", "estt") ? "It is a permutation" : "It is not a permutation");
System.out.println(isPermutation("testt", "estt") ? "It is a permutation" : "It is not a permutation");
}
}
program to check unique number in java | IsUnique
import java.util.*;
import java.io.*;
public class IsUnique {
public static boolean isUniqueUsingHash(String word) {
char[] chars = word.toCharArray();
Set<Character> set = new HashSet<Character>();
for (char c : chars)
if (set.contains(c))
return false;
else
set.add(c);
return true;
}
public static boolean isUniqueUsingSort(String word) {
char[] chars = word.toCharArray();
if (chars.length <= 1) return true;
Arrays.sort(chars);
char temp = chars[0];
for (int i = 1; i < chars.length; i++) {
if (chars[i] == temp) return false;
temp = chars[i];
}
return true;
}
public static void main(String[] args) throws IOException {
System.out.println(isUniqueUsingHash("Word") ? "Unique" : "Not Unique");
System.out.println(isUniqueUsingSort("Nootunique") ? "Unique" : "Not Unique");
}
}
Subscribe to:
Posts
(
Atom
)