Between 2012-2021, I worked on 5 different companies; Amazon, Microsoft, General Motors, CheckPoint and IBM. Add to that, 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 steps is to master the basics which are:

- The programming language you are going to use throughout your interviews, preferably Java 8+ or C++. I personally choose Java.
- Introduction to computer science, bound and calculate time/space complexity.
- Data-structures: Review your undergraduate data-structure materials with emphasis on: Lists/Set/ Heap/Binary trees/Balanced Trees
- Algorithms:
- Graph algorithms such as: BFS/DFS/Dijikstra/Kruskal/BellmanFord/Brim/…
- Dynamic Programming and Greedy algorithms
- NP-Hard/NP-Complete problems such as: The traveling salesman, Graph coloring problem

**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.**- Sort algorithms with emphasis on
**Bucket sort vs Radix sort** - Fibonacci heap
**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- Read about the Hungarian algorithm and try to solve the
*Assignment problem* - 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.

## 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.

- When you read a problem, assure yourself that you didn’t get it and think of it again
- Whiteboard a sample or more without thinking of code
- Think of edge cases
- 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.
- 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(); - Don’t submit, review the code and run it with the examples and edge cases of step 2 and 3
- Submit and re-iterate if needed
- 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.

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.

## Review what you learnt constantly (1+ Hour)

Always take notes. I took many for you:

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.

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 Elements | nice 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 Array | Quick 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 Squares | Lagrange’s Four Square theorem | |

Letter Combinations of a Phone Number | IMPORTANT | |

Number of Islands | ||

Search a 2D Matrix II | Amazing 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 Tree | There 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 Array | Asked 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 Subarray | I 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 Equations | a 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 Water | i 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 Sequence | i 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 set | LEATHER PANTS |

Remove Invalid Parentheses | I 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 call | LEATHER PANTS |

Sliding Window Maximum | ||

Edit Distance | ||

Merge k Sorted Lists | I 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 Histogram | My 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 Substring | VERY 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 movement | asked by google |

Binary Tree Maximum Path Sum | ||

Longest Valid Parentheses | a 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 Matching | i 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 Balloons | Failed to solve it/ wrap my head around the solution | |

Serialize and Deserialize Binary Tree | ||

Subarrays with K Different Integers | Ok, 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 K | Asked by google |

K Empty Slots | ||

Longest Substring with At Most Two Distinct Characters | ||

Smallest Range | My 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 Subsequence | nice question, solved with DP possibly. | |

Shortest Distance from All Buildings | ||

skyline problem | ||

Next Closest Time |

### Geeks4Geeks top picks with notes:

GeeksForGeeks Google problems | Solution Comment |

Assignment Problem | Learn hungarian algorithm |

Find all four sum numbers | nice trick |

Word Boggle | |

Min cut Square | Read the solution |

Replace O’s with X’s | it 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 pages | Found greedy algorithm – Done |

Check for BST | Done |

Number of Coins | Done |

Smallest Positive missing number | Done |

Longest K unique characters substring | the 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 Tree | We 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 Problem | Done |

Max absolute difference | Done |

Stock buy and sell | Done |

(Leather pants) Find median in stream | We 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 Sequence | I 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 pairs | nice 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 Dictionary | Topological sort – I found the trick by writing dependency arrows between the letters and by that i reached the topological sort idea |

Word Break – Part 2 | Done( interesting DP solution for easier true/false problem) |

The Celebrity Problem | |

Kth element in Matrix | Nice 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 Numbers | Nice DP problem |

Topological sort | |

Overlapping Intervals | |

Longest Prefix Suffix | KMP Algorithm |

Egg Dropping Puzzle | |

Distinct Transformations | |

Merge two BSTs with limited extra space | Summarize all the 3 methods |

Rotten Oranges | |

Form a palindrome | |

Stock span problem | Done with STACK |

Maximum sum Rectangle | |

Coin Change | |

Reverse a Linked List in groups of given size. | |

k-th smallest element in BST | Remember that it uses Morris algorithm |

Count ways to N’th Stair(Order does not matter) |