Saturday 23 May 2020

Interview Preparation guide, Must Do ThingS and Questions Before Coding Interviews and Tests

I WOULD BE SHARING TIPS,  TOPICS, TRICKS, BOOKS AND SOME MUST DO QUESTIONS IF YOU ARE SITTING FOR CODING TESTS OR INTERVIEWS OR CAMPUS PLACEMENTS.

THESE ARE MOST RECOMMENDED FOR IIT'S CAMPUS PLACEMENTS ALTHOUGH YOU CAN GENERALISE IT FOR TOP MOST COMPANIES PLACEMENTS (GOOGLE, MICROSOFT, AMAZON, UBER, ETC).


BOOK (MUST READ):-
https://drive.google.com/open?id=1_tsFl24zGhfxSMAtzqxr1heyS5FobSJQ

This book is in C++ but can be used by Java and other language programmers too. Awesome book !!! I myself am a Java programmer and used this to help myself during placements.

VIDEOS (MUST WATCH):-
https://www.youtube.com/results?search_query=tushar+roy

TOPICS (MUST KNOW):-

1. Disjoint Sets
In the above shared book, Page No. 146.

2. Fenwick Tree (Binary Indexed Tree)
https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/

3. Mo's Algorithm / Sqrt Decomposition
https://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/

3. Map Usage
This will come through practice, I will share below some questions for that.

4. Merge Sort (Divide and Conquer Approach) & Quick Sort (Selection Algorithm)
https://www.programiz.com/dsa/merge-sort
https://www.programiz.com/dsa/quick-sort

5. Binary Search
https://www.geeksforgeeks.org/binary-search/

6. BFS/ DFS
https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/tutorial/
https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/
https://www.geeksforgeeks.org/0-1-bfs-shortest-path-binary-graph/ (0-1 BFS, See a related question below)

7. Priority Queues
https://www.programiz.com/dsa/priority-queue

8. Nim Game Theory
In the above shared book, Page No. 235.


QUESTIONS (MUST DO):-


1. Common Sense
Easy - https://www.hackerrank.com/contests/codebusters-finals/challenges/one-palindrome/problem
Easy - https://leetcode.com/problems/excel-sheet-column-number/

2. String Manipulation
Easy - https://www.hackerrank.com/contests/codebuster-prelims/challenges/omega-decoder
Easy - https://leetcode.com/problems/unique-email-addresses/

3. Mathematics
Easy - https://www.hackerrank.com/contests/codebuster-prelims/challenges/jab-harry-met-sejal/problem

4. Advanced GCD
Medium - https://www.codechef.com/problems/GCD2

5. Number Theory, Sieve of Eratosthenes, Segmented Sieve
Easy - https://leetcode.com/problems/count-primes/
Medium - https://www.spoj.com/problems/PRIME1/
Medium - https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050edb/00000000001707b9
Medium - https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e02/000000000018fd0d

6. Priority Queue
Medium - https://leetcode.com/problems/campus-bikes/

7. Ordered Map
Hard - https://leetcode.com/problems/odd-even-jump/

8. Ordered Map & Priority Queue
Hard - https://www.hackerrank.com/contests/codebuster-prelims/challenges/priority-scheduling/problem

9. Arrays, Kadanes Algorithm
Medium - https://www.hackerrank.com/contests/codebusters-finals/challenges/the-proudy-array/problem
Medium - https://leetcode.com/problems/maximum-subarray/
Medium - https://leetcode.com/problems/maximum-product-subarray/
Hard - https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/

10. Power Set, Subsets, Permutations
Medium - https://leetcode.com/problems/subsets/
Medium - https://leetcode.com/problems/permutations-ii/

11. Graph, BFS
Medium - https://www.hackerrank.com/contests/codebusters-finals/challenges/ant-race/problem
Hard - https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/ (0-1 BFS Concept, Very Useful, Djikstra will give TLE on such problems)

12. Graph, DFS
Medium - https://leetcode.com/problems/number-of-islands/

13. Graph, Connected Components
Hard - https://www.hackerrank.com/contests/codebusters-finals/challenges/lets-permute/editorial

14. Greedy
Hard - https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/

15. Greedy, DP
Medium - https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/

16. Recursion, Memoization
Medium - https://leetcode.com/problems/generate-parentheses/
Hard - https://leetcode.com/problems/different-ways-to-add-parentheses/
Hard - https://www.codechef.com/problems/SANSKAR

17. Map, Tries, Backtracking
Hard - https://leetcode.com/problems/word-squares/
(Try to do this question using map + backtracking instead of tries + backtracking)

18. Map
Medium - https://leetcode.com/problems/find-and-replace-in-string/
Medium - https://leetcode.com/problems/subarray-sum-equals-k/

19. 2 Pointer Approach
Medium - https://leetcode.com/problems/container-with-most-water/
Hard - https://leetcode.com/problems/trapping-rain-water/

20. Map, 2 Pointer Approach
Medium - https://leetcode.com/problems/longest-substring-without-repeating-characters/
Hard - https://leetcode.com/problems/3sum/

21. Stack
Medium - https://leetcode.com/problems/valid-parentheses/
Medium - https://www.interviewbit.com/problems/nearest-smaller-element/

22. Divide and Conque, Usage of Merge Routine
Medium - https://leetcode.com/problems/merge-k-sorted-lists/

23. Selection Algorithm, Quick Sort, Priority Queue
Medium - https://leetcode.com/problems/kth-largest-element-in-an-array/
(Do it in O(n) using selection algorithm, using priority queue it would be O(nlogk) )

24. Activity Selection
Medium - https://www.interviewbit.com/problems/activity-selection/

25. Dealing with Ranges and Intervals
Hard - https://leetcode.com/problems/meeting-rooms-ii/

26. Trees, Vertical Traversal, Lowest Common Ancestor
Medium - https://leetcode.com/problems/binary-tree-vertical-order-traversal/
Medium - https://leetcode.com/problems/binary-tree-maximum-path-sum/
Hard - https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

27. Topological Sort + Cycle Detection
Medium - https://leetcode.com/problems/course-schedule-ii/

28. DP
Medium - https://leetcode.com/problems/word-break/
Medium - https://leetcode.com/problems/coin-change/
Hard - https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
Hard - https://leetcode.com/problems/wildcard-matching/
Hard - https://leetcode.com/problems/longest-palindromic-substring/
Hard - https://leetcode.com/problems/cherry-pickup/

29. DP and DFS
Hard - https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

30. Disjoint Sets
Medium - https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/
Medium - https://www.codechef.com/problems/FIRESC
(Do the above problems with disjoint sets, although you can do it using graphs + dfs traversal)

31. Binary Search
Medium - https://www.interviewbit.com/problems/rotated-sorted-array-search/
Medium - https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

32. Binary Search + Greedy
Hard - https://leetcode.com/problems/split-array-largest-sum/

33. DP + Binary Search
Hard - https://leetcode.com/problems/longest-increasing-subsequence/
(Do the optimal one using DP + binary search O(nlogn) instead of DP solution O(n^2))

34. DP + Bit Masking
Hard - https://www.spoj.com/problems/ASSIGN/
(Alternatively you can do it using recursion but it would be too hard, so learn dp + bit masking)

35. Prefix sum, 2D DP
Medium - https://leetcode.com/problems/range-sum-query-2d-immutable/

37. Double array usage, DP
Hard - https://leetcode.com/problems/candy/

38. Bit Manipulation
Hard - https://www.interviewbit.com/problems/single-number-ii/

39. Double ended queue, Sliding Window
Hard - https://www.interviewbit.com/problems/sliding-window-maximum/

40. Linked List, Cycle Detection
Medium - https://www.interviewbit.com/problems/reverse-linked-list/
Medium - https://www.interviewbit.com/problems/list-cycle/
Hard - https://leetcode.com/problems/reorder-list/

41, Tries, DP, Queries
Hard - https://leetcode.com/problems/xor-queries-of-a-subarray/

42. Fenwick tree
Hard - https://leetcode.com/problems/count-of-smaller-numbers-after-self/
Hard - https://www.spoj.com/problems/RATING/

43. Range Query, Sqrt Decomposition, Segment Tree, Fenwick Tree
Medium - https://leetcode.com/problems/range-sum-query-mutable/
Hard - https://codeforces.com/contest/220/problem/B

44. Minimum Spanning Tree, Krushkal
Medium -https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050edb/0000000000170721

45. Djikstra
Medium - https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/practice-problems/algorithm/irctc/description/
Medium - https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/benny-and-the-universe/description/

46. Game Theory
Medium - https://www.hackerrank.com/contests/codebusters-finals/challenges/the-game-of-nim/problem

47. Recursion
Hard - https://leetcode.com/problems/different-ways-to-add-parentheses/
(Very Important and frequently asked question)


TIPS/TRICKS :-

1. Always look at the given input constraints first. If they are in a small or narrow range, try to exploit it !!!

2. During campus placements, go for problems similar to the ones you have done earlier or have experience of doing. Try new problems only if you have time left in the end.

3. Don't bring your ego during the test. Say you have done 100 DP problems and the DP question is not getting solved during the test, better skip it and try other questions.

4. In case you are not confident with DP, go for recursion. You will pass 70% test cases. Then try recursion + memoization to get full points.

5. Use shortest way out, i.e. use of Maps instead of building Tries, Fenwick tree instead of Segment tree, Disjoint Sets instead of building Graph, etc.

6. Solve the questions properly after the test. Questions repeat a lot !!! Around 3 to 4 times !!!

7. Try out every platform so that you don't have platform issues. Common test platforms are Hackerrank, Hackerearth, InterviewBit, Codechef, Mettl.

PAST QUESTIONS LINK:-

 SAMSUNG
at 26 comments:
Labels: ,
Subscribe to: Posts (Atom)