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

26 comments:

  1. Sir main gate 2021 k liye prepare kr rha , meri programming weak hai toh kaise manage and kahan se krun please guide

    ReplyDelete
    Replies
    1. For Gate, You hardly require that advanced coding skills. You can do the basic classical coding examples, not this advanced. Later after joining IIT you can manage and develop coding skills.

      Delete
    2. Thanks alot sir, so for the basic ones what should I reffer and from where should I practice?

      Delete
    3. https://iamruturaj.blogspot.com/2018/06/competitive-programming-path-you-always.html

      Delete
  2. Sir an average person can sustain in iit course work

    ReplyDelete
    Replies
    1. Average person only will sustain iit course work. haha. too dull person will collapse. Too bright person will also collapse. This sounds weird but it's true. Imagine you scoring 100 in every single exam and now getting a 0 in some exam. Can you tolerate it? ofcourse not. The competition will kill you. But the average person knows well how to manage at all times. He/She has seen the best and also the worst.

      Delete
  3. Hello Sir. I am doing Mtech in Structural Engg(Civil) at IIT Hyderabad. So,in one or two months my placement will start and I want to shift to IT companies for placement for better growth. I have little knowledge of C,C++. And I feel , I can learn DS and Algo in 1.5 to 2 months.

    So, Should I try for Companies which are hiring for Developers or for ML/AI companies? And Which companies come in more numbers which allow other branch mtech students? Is it ML or Developer companies?

    Will be highly obliged if you reply.

    ReplyDelete
    Replies
    1. Developer. ML/AI are very specific and also even if you get selected you won't feel great working there as you don't have much ml/ai background. SO go for developer roles. Ask you coordinator to open the company for your branch. Even if it doesn't just go and give the coding test. This is another way to prove yourself. Many have done it this way in IIT's and got selected too.

      Delete
    2. Okay. Thank you.

      And as it is almost september now, I just have maximum 1.5 months to prep with thesis going on . So do you think ,with 4-5 hours of Algo n Ds everyday, I will be able to do it ?

      And Is Aptitude and puzzles also required for Screening tests?

      Delete
    3. And Please tell me if it is mandatory to make any project? And what should be written in Cv?

      I have to submit my Cv in September. Till then at max, I will be able to learn Algo and Ds.

      So, can I write things which i Can do after the Screening Tests i.e. ,before interviews?

      I know it is too much to ask you. Sorry for that. It will be really helpfull if you can answer.

      Delete
    4. Yes it should be fine. People have done it in 3 months of time so yes it's fine. Aptitude is required in few companies tests, not all. A basic overlook on aptitude is fine(2-3 days). Puzzles only 1-2 asked during interview. So you can skip it.

      You can check my resume here:- http://www.cse.iitd.ac.in/~mcs182012/

      One good project should do. Which you can discuss and talk upon. You can write things if the college allows. No issues. Generally they don't allow to modify CV but you can request if there is some major issue.

      Delete
  4. Okay. Thanks a Lot. Really appreciated.

    ReplyDelete
    Replies
    1. Wow! You Cv is exceptional.

      Can a CV containing , only this much fetch a job

      C, C++, Python, Algo, Ds, two courses in ML, one small project in C++ ???

      Delete
    2. Yes more than enough..haha..people dont have even this much...Just be confident and proficient in communication. that's the key. The better you advertise yourself the better price you are sold !!!

      Delete
    3. Okay. Thank you for Motivating. 😃

      Delete
  5. I came to know that samsung conduct coding interview without using stl. Now in bfs and dfs I use queue stack stl to solve. Similarly in question like frequency counting or grouping similar elements I used map or sets. Similarly for priority queue or for sort or search. I highly depend upon stl for problem solving. So how to solve questions without them?

    ReplyDelete
    Replies
    1. A good news for you. Samsung has upgraded its platform and now you can use STL. In our time we used it too !!!

      Delete
  6. May i know: on what basis you prepared these must do questions?

    ReplyDelete
    Replies
    1. These were our direct placement questions !!!

      Delete
    2. cool... If possible, can you please name them company wise?

      Delete
    3. Sorry !!! No one can do that because of non-disclosure agreement signed by us. I even had to remove placement salary details. Strict rules of iits !!!

      Delete
  7. Hello. Do you have idea on how is the 2nd phase of placement in IIT's? Do good IT companies come in 2nd phase too?

    Thanks in Advance.

    ReplyDelete
    Replies
    1. Some good companies visit in 2nd phase. But is quite rare because most of the good companies visit in December only. If any company couldn't make it in December then only they come in January else not. Also as all good students are already hired so they sometimes reluct to come for the 2nd phase also.

      Delete
    2. Lot of good startups do visit in 2nd phase though. Salary wise pretty good too!!!

      Delete
    3. Okay. Thank you!

      Delete
  8. Affordable laptop repair service in bhubaneswar.
    Laptop Hospital

    ReplyDelete