Department : CSE
CGPA : 7.9
The online round was hosted on HackerEarth platform.
It had 2 coding questions and 20 MCQs.
Q1. Given an unsorted array A, find the largest value of i-j such that A[i]>A[j].
Q2. Given an unsorted array A and a number k, find the maximum sum sub string in the array such that its sum is divisible by k.
1 mark each and 0.25 negative mark.
Few MCQs were based on data Structures, algorithms, oops and operating Systems, 1 or 2 from logical reasoning, networking and DBMS each.
Design Question : Given a log file with product id and corresponding customer id for the products searched on amazon, you need to find the most viewed product at the end of the day. If a product is viewed multiple times by a single customer its view count is increased only by 1. Number of products are very large so sorting, heap or hashing of product Ids is not feasible.
Solution- Use Trie data structure. After 10 minutes of discussion I could come up this.
Production level code for insert and search in a trie was required.
What if k max viewed products were required.
During my discussion he also asked me to write a hashing function.
1. Dfs of a graph.
Dfs of a n array tree. (Code was required)
2. Given a string s and a file with each word on a separate line, find all the words in the file which are anagrams of the string s. The interviewer asked me tell all
the possible solutions irrespective of the complexity. This continued for 10 min. He asked me if the question can be solved with suffix tree or a trie.
3.Given a m*n matrix find number of paths from (0,0) to (m-1,n-1), at every block we either move 1 step down or 1 step right.
4. Print all paths for the above questions. A dp solution was required.
1. Given a n*n matrix with distinct elements from from 1 to n^2, find minimum number of bombs required to destroy all cells of the matrix. If we bomb a cell with
value i, a cell with value i-1 if 4 adjacent to it will also be destroyed. (Code was required)
What if the the numbers were not unique.
2. Find majority element in an unsorted array.
Find majority element in sorted array. (logN solution was required)
3. Print the elements of a tree diagonally.
4. Find shortest distance between two nodes of a tree where every node also has a pointer to its parent node and we can also directly jump from a node a to
node b, where b is the mirror image of a and a and b belong to the two sub trees rooted at the root of the given tree. The mirror image may or may not
exist. ( the interviewer wasn't very sure about this question so there wasn't much discussion about my solution)
5. Find the time required to pass information from root to all the nodes of the tree.
The interviewer then asked me which other non coding subject do I like. I said os.
So he asked me several basic questions on OS.
difference between threading and multiprocessing
The famous Amazon’s Bar Raiser Round
My internship experiences.
Detail discussion about my summer internship project.
What is your favorite algorithm and why.
Toughest thing you did in college.
What are some leadership principles you learnt during your summer internship.
What was the non technical thing you learnt at your internship.
Every interview round started with the cliche tell me about yourself and ended with do you have any questions.
I recommend every one to prepare from-
InterviewBit - Extremely extremely helpful for clearing online coding rounds. One should solve each and every problem on it.
Hackerearth CodeMonk - Very helpful to get command over ds based problems.
Hackerrank - Week of code and HourRank are helpful.
For design questions go through-
Go through previously asked questions.
And of course geeksforgeeks - Try to cover as many problems as possible. Most of the problems are asked from here. Its not a 1 week job, you should at least give yourself 2 months for this.
You should be able to write production level code for-
Graph algorithms like Dijkstras, kruskal, Prims etc.
For Bar raiser round go through amazon's leadership principles and other things they usually asked.
Not every company focuses on difficult coding questions in interviews. So the above is advisable for product based companies like Amazon, Microsoft, Directi, flipkart etc. Usually even big investment banks do not ask such difficult question but its always good to go through geeksforgeeks cliche problems and interviewbit.
Though aptitude questions are not asked in Amazon online round but they are heavily asked in other companies.
Here are some good sources to practice it-
Prepare well for subjects like-
Os, ioom, dbms, computer architecture.
Preparing from geeksforgeeks for these subjects will also be fine.
Common sql queries may be asked, like these- http://www.bullraider.com/database/sql-tutorial/7-complex-queries-in-sql
No matter how your internship interviews went last year, no matter how tough situations are for you right now, no matter how hard things might seem, never give up and work hard .
Today is hard, tomorrow will be worse, but the day after tomorrow will be sunshine - Jack Ma