A superpower guide on how to pass any technical interview

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:
5. Graph algorithms such as: BFS/DFS/Dijikstra/Kruskal/BellmanFord/Brim/…
6. Dynamic Programming and Greedy algorithms
7. NP-Hard/NP-Complete problems such as: The traveling salesman, Graph coloring problem
8. 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.
9. Sort algorithms with emphasis on Bucket sort vs Radix sort
10. Fibonacci heap
11. 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
12. Read about the Hungarian algorithm and try to solve the Assignment problem
13. 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.

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 picked some 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²))=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=19-Knuth-Morris-Pratt KMP String Matching Algorithm
9. Morris Traversal — inorder tree traversak without stack or recursion — only by using inorder predessesor
10. rotate a matrix 90 degrees: transpose the matrix(column becomes a row) and then reverse every column
11. 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.
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 accordinglybidirectional 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: 111111002’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 problemBoolean
11. satisfiability problem (SAT)
12. 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 occurrences of the digit. then it iterates the original array and places the numbers in the proper place

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.

Leetcode top-picks

Geeks4Geeks top picks with notes:

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

Originally published at http://exhesham.wordpress.com on March 16, 2021.