Between 2012-2021, I was employed by 5 different companies; Amazon, Microsoft, General Motors, CheckPoint and IBM. With that being said, I passed more than 40 interviews and received more than 15 offers. I gained experience on how to:

  • Prepare correctly for technical/behavioral job interview
  • Negotiate a job offer
  • Land your new job on the right foot
  • Handling office politics

I won’t keep my experience for myself, I will share it with you in my next posts.

Start right (1-4 days)

The goal of this step is to master the basics which are:

  1. The programming language you are going to use throughout your interviews, preferably Java 8+ or C++. I personally choose Java.
  2. Introduction to computer science, bound and calculate time/space complexity.
  3. Data-structures: Review your undergraduate data-structure materials with emphasis on: Lists/Set/ Heap/Binary trees/Balanced Trees
  4. Algorithms:
    1. Graph algorithms such as: BFS/DFS/Dijikstra/Kruskal/BellmanFord/Brim/…
    2. Dynamic Programming and Greedy algorithms
    3. NP-Hard/NP-Complete problems such as: The traveling salesman, Graph coloring problem
    1. Quick Select: used to select k’th smallest element with O(n). we can find the median with quick select by selecting sub arrays of size n/2 each split.
    2. Sort algorithms with emphasis on Bucket sort vs Radix sort
    3. Fibonacci heap
    4. Count Sort: say range of numbers is O(n), then you can allocate arr of size O(n) where the index is the number and the value is the count. a second array of size O(n) where the index is the count value and the value is the numbers that have that count
    5. Read about the Hungarian algorithm and try to solve the Assignment problem
    6. Knuth-Morris-Pratt KMP String Matching Algorithm

Solve basic problems (3-7 days)

You need to solve the Strings/Sets/Lists/Trees/Graphs/Bits/Operating systems/Data Structures/Recursion chapters of the book Cracking the code interview. Take your time and compare the book solution with your solution if you didn’t get it right the first time. Don’t forget to retry solving it.

NOW YOU ARE AN AVERAGE INTEREVIEWEE

Becoming a guru (1+ month)

LeetCode has top 100 problems, you need to solve most of the basic and medium problems and some of the hard problems. I will concentrate the top-picks for you down below.

Becoming a guru is a process which starts with mastering the basics of the right approach.

  1. When you read a problem, assure yourself that you didn’t get it and think of it again
  2. Whiteboard a sample or more without thinking of code
  3. Think of edge cases
  4. Take a step back and think of a generic algorithm. It doesn’t matter if you get it with high time/space complexity. You already learnt the data structures and you can use them to help the complexity case.
  5. Code it as it is a production code with right naming and methods. Write methods that you implement later. For example, if you need an array of 100 prime numbers, then write it as follows:
    final Array<Integer> first100Primes = getFirst100Primes();
  6. Don’t submit, review the code and run it with the examples and edge cases of step 2 and 3
  7. Submit and re-iterate if needed
  8. Head to the Discussion/FAQ to see what smart people did so you learn from them (it helped me a lot to get better).

Train those steps on the basic leetcode problems and when you feel you got better, try it with some medium problems. Thank me later.

Think of it while you can

After you mastered the steps I mentioned before, you may be a mother with children or a father with enough on his plate. Therefore, you can handle your daily concerns while thinking about a solution to the problem you just picked on your smartphone and chew steps 1-4 for hours. When you find the solution, hit the keyboard and pass the tests.

Advertisements

It doesn’t end with passing the tests which may take several iterations. Always head to the FAQ as there are people out there smarter than me and you.

Review what you learnt constantly (1+ Hour)

Always take notes. I took many for you:

Advertisements
1- Topological sort, both the DFS approach and the Set approach
2- traveling salesman problem
3- how balanced search trees work, what the common ways to implement them are, and the O() performance of operations
4- essentials of combinatorics and probability
5- Java, Compiler/Interfaces/inheritance/virtual…
6-kruskal – shortest spanning tree O(Elog(E))=O(Elog(V^2))=O(ElogV) – Greedy approach
7-Dijikstra- find min paths from given node. uses minheap O(E+VlogV) – Greedy
8-BFS is special cas of dijikstra on graphs with weight=1
9-Knuth-Morris-Pratt KMP String Matching Algorithm
10-Morris Traversal – inorder tree traversak without stack or recursion – only by using inorder predessesor
11-rotate a matrix 90 degrees: transpose the matrix(column becomes a row) and then reverse every column
12-Graph coloring problem
12- Quick Select: used to select k’th smallest element with O(n). we can find the median with quick select by selecting sub arrays of size n/2 each split.
13- Bucket sort vs Radix sort
14 – Review my other blog for links: https://exhesham.com/2018/04/27/cheat-sheet-for-the-software-engineer-interview/
15-Fibonacci heap
16-Bipartite graph: is a graph where we can split the nodes into two groups in a way that each edge in the graph connects nodes between A and B. no A to A or B to B.
גרף הוא דו-צדדי אם ורק אם אין בו מעגל באורך אי-זוגי.
גרף הוא דו-צדדי אם הוא 2-צביע.
משפט החתונה מספק אפיון של גרפים דו-צדדיים שבהם ניתן לבחור קבוצה של קשתות לא נוגעות שמכסות את כל צומתי הגרף.
כל עץ הוא גרף דו-צדדי.
17- Depth First Traversal can be used to detect a cycle in a Graph. DFS for a connected graph produces a tree
18- In Directed Graph: To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree.
19- In Undirected Graph: If we reach an adjacent that is already visited and it is not a direct parent to the node, then we have a cycle.
20- Count Sort: say range of numbers is O(n), then you can allocate arr of size O(n) where the index is the number and the value is the count. a second array of size O(n) where the index is the count value and the value is the numbers that have that count
21- java treeset and treemap. Regarding treeset: It stores unique elements
It doesn’t preserve the insertion order of the elements
It sorts the elements in ascending order
It’s not thread-safe.When compared to a HashSet the performance of a TreeSet is on the lower side. Operations like add, remove and search take O(log n) time while operations like printing n elements in sorted order require O(n) time.
22- MinHeap – if implemented via array then the CreateHeap time complexity is O(n). first we create the array with the elements and then from Math.floor(i/2) to 1, we do shiftDown. in total, it will cost us O(n)
23- Heap with a full binary tree: in order to insert a new element on the next empty index( say we have k elements in the tree then the next available index is k+1) then we navigate acoording to the binary representation of the index. starting from the second binary digit on the left: if zero, then go right, else then go 1. it is because the child of i is 2i and 2i+1
24. insert to heap: insert in the next available place and shiftUp
25. heap: if implemented by a tree, then we use post-order to create the heap as the shiftDown needs that both children trees be sorted accordingly
bidirectional search is finding the shortest path between two nodes by running bfs from both nodes at the same time. when they first reached then the shortest path was found.
bit manipulation a^(~a) = sequence of 1’s
~0 << 2 is 1s followed by 2 zeros: 11111100
2’s complement of a binary number is 1 added to the 1’s complement of the binary number.

Important problems

You may notice that I refer to some problems as leather-pants problems. Well, Leather pants is a story of a smart interviewer that pulled a problem’s trick during a weird from hell interviewer wearing a leather pants and passed thank to it.

Advertisements
1. Subset sum problem: Given array of ints, is there non-empty subset whose sum equals zero?
2. Graph Coloring problem
3. Dominating Set: dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is adjacent to at least one member of D. The domination number γ(G) is the number of vertices in a smallest dominating set for G
4. Independent set problem: Given a graph and K, find a subset in G with K or less nodes where there is no edge connecting two nodes in this subset
5. Vertex Cover: A set in G where each edge has at least on vertex in the set
6. clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph.
7. subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H
8. Travelling salesman problem: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” It is an NP-hard problem. Can be solved with greedy algorithm, when we are on node v, we choose the shortest path. it is by average gives 25% from the shortest path
9. Hamiltonian path problem: the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph
10. Knapsack problem
Boolean satisfiability problem (SAT) 11. בעיית הספיקות: באופן כללי, בעיית SAT היא הבעיה הבאה: בהינתן נוסחה בתחשיב הפסוקים שמכילה רק קשרים מסוג “גם”, “או” ו-“לא”, האם קיימת השמה של ערכי אמת למשתנים כך שהנוסחה תקבל ערך אמת?
bucket or rudex sort is used when the range of values is known. bucket sort run count sort for each digit. the count sort counts the occurances of the digit. then it iterates the original array and places the numbers in the proper place

Leetcode top-picks:

Hamming Distance
Merge Two Binary Trees
Maximum Depth of Binary Tree
Single Number
Invert Binary Tree
Move Zeroes
Reverse Linked List
Find All Numbers Disappeared in an Array
Majority Element
Convert BST to Greater Tree
Best Time to Buy and Sell Stock
Merge Two Sorted Lists
Diameter of Binary Tree
Climbing Stairs
Two Sum
Maximum Subarray
Symmetric Tree
Path Sum III
House Robber
Find All Anagrams in a String
Min Stack
Linked List Cycle
Valid Parentheses
Palindrome Linked List
Intersection of Two Linked Lists
Shortest Unsorted Continuous Subarray
Counting Bits
Daily Temperatures
LEATHER PANTS. The idea is that if the shortest person sees k equal or taller persons then that person must set at the k+1’th. Moreover, if there are, for example two shortest persons with the same height. The leather pants approach tells that you take the tallest first, place them and then start adding the shorter in between
Palindromic Substrings
Binary Tree Inorder Traversal
Product of Array Except Self
Permutations
Top K Frequent Elementsnice solution with buckets – using count sort.
Generate Parentheses
Subsets
Find the Duplicate Number
Binary Tree Level Order Traversal
Rotate Image
Combination Sum!
House Robber III
Unique Paths
Kth Largest Element in an ArrayQuick Select
Minimum Path Sum
Group Anagrams
Unique Binary Search Trees
Task Scheduler
Target Sum
Partition Equal Subset Sum
Subarray Sum Equals K
Decode String
Container With Most Water
Best Time to Buy and Sell Stock with Cooldown
Meeting Rooms II
Sort Colors
Perfect SquaresLagrange’s Four Square theorem
Letter Combinations of a Phone NumberIMPORTANT
Number of Islands
Search a 2D Matrix IIAmazing solution: We select the right upper corner. if the targer is greater, then we increase the row. if the target is smaller, we decrease the column. it is O(m+n)
Longest Increasing Subsequence
Construct Binary Tree from Preorder and Inorder Traversal
Implement Trie (Prefix Tree)
Course Schedule
Lowest Common Ancestor of a Binary TreeThere are three important approaches to this problem. first one is traversing the tree and updating global variable
Merge Intervals
Word Break
Sort List
Remove Nth Node From End of List
Find First and Last Position of Element in Sorted ArrayAsked by amazon interview
Search in Rotated Sorted Array
Maximal Square
Flatten Binary Tree to Linked List
Jump Game
Linked List Cycle II
Add Two Numbers
Word Search
Next Permutation
Coin Change
Maximum Product SubarrayI needed to notice that if i have odd negative number in a window then, i just need to resize the window to skip only the first one. which means, that if I run two iterations where each time i hit a zero, the product should be updated to 1. which gives the next solution:public int maxProduct(int[] nums) {
int result = nums[0];
int prod = 1;
for(int i = 0 ;i < nums.length;i++){
prod = prod*nums[i];
result = Math.max(result,prod);
prod = prod == 0? 1:prod;
}
prod = 1;
for(int i = nums.length-1;i>-1;i–){
prod = prod*nums[i];
result = Math.max(result,prod);
prod = prod == 0? 1:prod;
}
return result;
}
Longest Substring Without Repeating Characters
Longest Palindromic Substring
Validate Binary Search Tree
3Sum
Satisfiability of Equality Equationsa good example for Union/Find problem
Is Graph Bipartite?Very important question: a graph is bipartite if and only if it is 2-colorable or has odd length cycle.
Trapping Rain Wateri have learnt that when we have a stack, don’t tend to apply updates on peeks and push back. try to semplify maintainance by doing so at the end. i.e, emptying the stack and updating outside variables
Longest Consecutive Sequencei thought of doing a second iteration because of maintaining lately added objects. in this case, since the maintainance is because i didn’t know if the object exists or not, then need to think of a way to know this information ahead e.g. like adding to a setLEATHER PANTS
Remove Invalid ParenthesesI learnt how to handle the specific recurse call by adding void return after a recurs call that i don’t want to handle. this return will not reach the later recurs callLEATHER PANTS
Sliding Window Maximum
Edit Distance
Merge k Sorted ListsI learnt that we can first implement the merge of 2 lists and then start to call it for each two. after merging them we replace them with the merged. in my solution, i tried to do all this in one function which make me keep many pointers on the results. however, doing as described before will give me a cleaner code
Maximal Rectangle
Largest Rectangle in HistogramMy mistake was that AGAIN i tried to manipulate counters where there is no need as i can use the indices of the elements to do so.
Minimum Window SubstringVERY TRICKY: my approach was to count letters and compare to the given letters. so we reduced complexity by counting letters once and updating on each window movementasked by google
Binary Tree Maximum Path Sum
Longest Valid Parenthesesa good paranthesis trick used here is to use a counter. when the counter is negative, the expression is invalid and we need to delete a closing paranthesis. However, with positive, it is not the case. in order to find where we have additional positive that we should ignore or delete, we need to REVERSE the string and we need to decrease the paranthesisCounter on “(” and increase on “)”
Regular Expression Matchingi need to list all the cases correctly. first, when p[j] is . or letter or *
LRU Cache
Median of Two Sorted Arrays
Course Schedule III
Burst BalloonsFailed to solve it/ wrap my head around the solution
Serialize and Deserialize Binary Tree
Subarrays with K Different IntegersOk, So we decrease K until it is negative. then we start to increase the window until K is zero again and so on. The leather pants doesn’t end here. it is easier to calculate the problem for utmost K and subtract the solution for utmost K-1. which will give us exactly KAsked by google
K Empty Slots
Longest Substring with At Most Two Distinct Charactersgoogle
Smallest RangeMy Idea was to use priority queue for min values and max values, however, there is no need to use a queue for max values, each time we dequeue a min value, if it is bigger than the initial max, then update the max to be the poped value.
Minimum Window Subsequencenice question, solved with DP possibly.google
Shortest Distance from All Buildings
skyline problem
Next Closest Time

Geeks4Geeks top picks with notes:

GeeksForGeeks Google problemsSolution Comment
Assignment ProblemLearn hungarian algorithm
Find all four sum numbersnice trick
Word Boggle
Min cut SquareRead the solution
Replace O’s with X’sit is like the game of death, just replace all O’s with – and then flood the edge ‘-‘ with O’s and the final step is to replace what left of ‘-‘s with ‘X’s
Allocate minimum number of pagesFound greedy algorithm – Done
Check for BSTDone
Number of CoinsDone
Smallest Positive missing numberDone
Longest K unique characters substringthe trick is to use a window and when reaching count k, start increasing the start index and update the count, just like any window trick
Duplicate subtree in Binary TreeWe can serialize each subtree. For example, the tree

1
/ \
2 3
/ \
4 5
can be represented as the serialization 1,2,#,#,3,4,#,#,5,#,#, which is a unique representation of the tree.
Job Sequencing ProblemDone
Max absolute differenceDone
Stock buy and sellDone
(Leather pants) Find median in streamWe can use a max heap on left side to represent elements that are less than effective median, and a min heap on right side to represent elements that are greater than effective median. After processing an incoming element, the number of elements in heaps differ utmost by 1 element. When both heaps contain same number of elements, we pick average of heaps root data as effective median. When the heaps are not balanced, we select effective median from the root of heap containing more elements.
Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
Longest Zig-Zag Sub SequenceI could reach the trick again after manually solving two random long examples. The idea is that if the current number increased then we add 1 to the decrease-counter and vice versa
Pots of Gold Game
The Painter’s Partition Problem
Sum of bit differences among all pairsnice trick with O(n): The trick is to understand that taking the first binary digit of each number, all the ones will be with all the zeros. for each such a pairing, it will increase the final result by 2×1(2 because we have two pairs). if for the x’th digit of each number we have all ones or all zeros, then we have zero couples of different bits. Therefore, the final result is zero
Alien DictionaryTopological sort – I found the trick by writing dependency arrows between the letters and by that i reached the topological sort idea
Word Break – Part 2Done( interesting DP solution for easier true/false problem)
The Celebrity Problem
Kth element in MatrixNice problem solved with dijikstra’s. The idea is that with dijikstra, we use a priority queue. since any node which enters the priority queue and gets out, it won’t re-enter again. therefore, eachtime we dequeue a node, it is the next smallest one. means that on the k’th dequeue, it is our result. the neighbour of a given node are the right, down and diagonal – the increasing directions. no need to take other nodes thanks to the sorted matrix
Ugly NumbersNice DP problem
Topological sort
Overlapping Intervals
Longest Prefix SuffixKMP Algorithm
Egg Dropping Puzzle
Distinct Transformations
Merge two BSTs with limited extra spaceSummarize all the 3 methods
Rotten Oranges
Form a palindrome
Stock span problemDone with STACK
Maximum sum Rectangle
Coin Change
Reverse a Linked List in groups of given size.
k-th smallest element in BSTRemember that it uses Morris algorithm
Count ways to N’th Stair(Order does not matter)
Advertisements

If you went by my green book, I assure you can pass any technical interview.