Round duration - 60 minutes Round difficulty - Medium
1 Medium/Easy DSA questions were asked similar to Leetcode.
I was expected to come up with the most optimal solution for the same. I completed the code and explained in 45 mins.
In the remaining time, I was asked questions from Computer Science fundamentals and Java
Q1.
Unique Element In Sorted Array
Nobita wants to impress Shizuka by correctly guessing her lucky number. Shizuka provides a sorted list where every number appears twice, except for her lucky number, which a...
Ans.
As the array was sorted we can make use of this information to use Binary Search.
// EXPLANATION:- // Suppose array is [1, 1, 2, 2, 3, 3, 4, 5, 5] // we can observe that for each pair, // first element takes even position and second element takes odd position // for example, 1 is appeared as a pair, // so it takes 0 and 1 positions. similarly for all the pairs also.
// this pattern will be missed when single element is ...
Low-level system design round. Expected to come up with a running code.
Q1.
LRU Cache Implementation Problem
Design and implement a Least Recently Used (LRU) cache data structure. This cache must support the following operations efficiently:
get(key): Return the value associate...
Ans.
Tip 1 : Ask clarification questions Tip 2 : Try and think in terms of brute force and then gradually optimize your solution Tip 3 : Ensure to check for edge cases Tip 4 : Ensure to be thorough with data structures, algorithms and system design concepts.
Q1. Can you describe your past work experiences and projects from your previous company?
Ans.
Ensure that you are thorough with the design of your project at your current organization.
Answered
Anonymously
Add your answer
Interview Preparation Tips
Professional and academic backgroundI applied for the job as SDE - 2 in GurgaonEligibility criteriaAbove 1 years of experienceLenskart interview preparation:Topics to prepare for the interview - Data Structures, Algorithms, System Design, Aptitude, OOPSTime required to prepare for the interview - 2 monthsInterview preparation tips for other job seekers
Tip 1 : Break down the total topics based on your comfort and ease and try and master one topic at a time Tip 2 : Try and up solve Tip 3 : Always try and come up with multiple solutions for a DSA question starting from brute force to optimal solution.
Application resume tips for other job seekers
Tip 1 : Try to keep it short and crisp. Tip 2 : Always make the entries chronological with the most recent experiences coming first followed by past experiences.
Round duration - 60 minutes Round difficulty - Medium
It was a problem solving round where a hackerrank link was given containing 2 questions. You have to solve them within 90 minutes. I was asked to solve it within a week.
Q1.
Find Distinct Palindromic Substrings
Given a string 'S', identify and print all distinct palindromic substrings within it. A palindrome reads the same forwards and backwards. For example, 'bccb' is a pali...
Ans.
Step 1 : Find all the palindromic sub-strings Step 2 : Remove duplicate palindromes Step 3 : Print the distinct palindromes and number of such palindromes
2 questions was asked by the interviewer. You have to clearly explain your approach and write a working solution. He even asked me to run on some additional test cases
Q1.
Job Sequencing Problem Statement
You are provided with a N x 2 2-D array called Jobs consisting of N jobs. In this array, Jobs[i][0] represents the deadline of the i-th job, while Jobs[i][1] indicates the...
Ans.
Sort the jobs based on their deadlines. Iterate from the end and calculate the available slots between every two consecutive deadlines. Include the profit, deadline, and job ID of ith job in the max heap. While the slots are available and there are jobs left in the max heap, include the job ID with maximum profit and deadline in the result. Sort the result array based on their deadlines.
Answered
Anonymously
Add your answer
Q2.
Partition Equal Subset Sum Problem
Given an array ARR consisting of 'N' positive integers, determine if it is possible to partition the array into two subsets such that the sum of the elements in both sub...
Ans.
Let isSubsetSum(arr, n, sum/2) be the function that returns true if there is a subset of arr[0..n-1] with sum equal to sum/2
The isSubsetSum problem can be divided into two subproblems a) isSubsetSum() without considering last element (reducing n to n-1) b) isSubsetSum considering the last element (reducing sum/2 by arr[n-1] and n to n-1) If any of the above subproblems return true, then return true. is...
I was asked 1 system design question. The question was to design an online multiplayer game which can be scaled for more than 10 million users. The interviewer helped me to collect requirement and also helped me in choosing different low latency protocol to communicate between client and server.
Round 4 - Face to Face
(1 Question)
Round duration - 60 minutes Round difficulty - Medium
The interviewer asked few sql based questions and asked me to write the solution. He also gave 1 problem solving question.
Q1. Can you explain the different types of joins in SQL and how to calculate the average of all values from a given table?
Add your answer
Interview Preparation Tips
Professional and academic backgroundI applied for the job as SDE - 2 in BangaloreEligibility criteriaNAOla interview preparation:Topics to prepare for the interview - Linked List, Stacks, Queues, Tree, Graph, System Design, Dynamic Programming.Time required to prepare for the interview - 2 monthsInterview preparation tips for other job seekers
Tip 1 : Prepare Data Structures topic by topic and also solve at least 10 interview questions from each topic. The have a list of excellent questions. Tip 2 : For system design try to take few questions by yourself and think of what different scenarios can arise considering it as a distributed system. There are multiple topics like Consistent Hashing, Partition tolerance, Availability, Sharing etc which needs special attention. The interviewers will dig them deep and will try to see how much of it you actually understand. Tip 3 : Also please do focus on LLD. Sometimes they can ask you to write sample code for problems. Try solving 4-5 problems. Tip 4 : You should do and prepare properly 2 -3 projects and try deploying it. You will face a lot of new challenges which you do not face in normal day to day usage.
Application resume tips for other job seekers
Tip 1 : You can go for 1 page resume, though it is not necessary. Mention about your projects, your actual contribution, languages that you have used in that project etc. Tip 2 : You should always put your academic achievements. Sometimes it gains interviewers attention. Tip 3 : Make it a little bit colourful rather than plain white.
Round duration - 60 Minutes Round difficulty - Medium
Timing: 10AM-11AM Interviewer was quite supportive and helpful. Environment was normal as usual and it was morning time
Round 2 - Video Call
(2 Questions)
Round duration - 60 Minutes Round difficulty - Medium
Timing: 11AM-12PM The interviewer was SDE2 He was checking the code for edge cases and was hinting if required
Q1.
Implementing a Priority Queue Using Heap
Ninja has been tasked with implementing a priority queue using a heap data structure. However, he is currently busy preparing for a tournament and has requested yo...
Ans. Array representation of heap
Since the heap is maintained in the form of a complete binary tree, the heap can be easily represented in the form of an array.
To keep the tree complete and shallow, while inserting a new element insert it in the leftmost vacant position in the last level i.e., at the end of our array, and perform some operation to maintain the property of the heap.
Similarly, for deleting the maximum e...
Answered
Anonymously
Add your answer
Q2.
Ninja and the Bulbs Challenge
Ninja owns an electronic shop and possesses 'N' bulbs. To verify the quality of the bulbs, Ninja performs a unique technique. After 'N' rounds of this process, bulbs that rem...
Ans. Brute Force
Approach:
A brute force solution to this problem is to turn on and off the bulbs N time, then at last check the number of bulbs that are on.
Algorithm:
Take a boolean array of ‘BULBS’ of size N+1.
Itertate on ‘i’ from 1 to ‘N’
Iterate on ‘j’ form ‘i’ to ‘N’ and each time increment ‘j’ as ‘j’ += ‘i’.
if(BULBS[j] == true) then make it false.
If (BULBS[j]==false) then make it true.
Intialise a variable ‘COUNT’ =...
Answered
Anonymously
Add your answer
Round 3 - Video Call
(1 Question)
Round duration - 60 Minutes Round difficulty - Medium
Timing: 6PM-7PM The interviewer was not interactive and didn't gave any feedback whatsoever. It was Hiring Manager Round Interviewer was Software Development Manager at Amazon
Q1.
Maximize the Sum Through Two Arrays
You are given two sorted arrays of distinct integers, ARR1 and ARR2. If there is a common element in both arrays, you can switch from one array to the other.
Your task...
Ans. Recursive
In this problem, our primary focus is on the common elements i.e. an element that is present in both the arrays. Then, we have to decide whether we have to make a switch. So for that, first we store all the elements of ‘ARR1’ and ‘ARR2’ into ‘MAP1’ and ‘MAP2’ respectively.
Now we call our ‘maximiseSumHelper’ function. We call this function for both cases i.e starting with ‘ARR1’ and starting with ‘A...
Answered
Anonymously
Add your answer
Interview Preparation Tips
Professional and academic backgroundI completed Computer Science Engineering from A. C. Patil College of Engineering. I applied for the job as SDE - 2 in BangaloreEligibility criteriaAbove 2 years of experienceAmazon interview preparation:Topics to prepare for the interview - Linkedlist, BST, Heap, Queue, Pointers, Binary SearchTime required to prepare for the interview - 2 MonthsInterview preparation tips for other job seekers
Tip 1 : Focus on internals of Data structure on how it actually works Tip 2 : Implement the Data Structure from scratch, later you can use the inbuilt packages no problem but you must know the implementation Tip 3 : Understand System Design concepts
Application resume tips for other job seekers
Tip 1 : Highlight your contributions you made and how it impacted the business and be real Tip 2 : Mention the improvement figures like x% reduction in page load size, improved SEO ranking by x figure, reduce memory usage by y%
Round duration - 60 minutes Round difficulty - Medium
It was a telephonic interview at 10 in the morning. Interviewer seemed cool.
Q1.
Best Insert Position for a Target in a Sorted Array
You are provided with a sorted array A of length N consisting of distinct integers and a target integer M. Your task is to determine the position where ...
Ans. Brute Force
Iterate through the given array.
If at any position i, we get A[i] ≥ M, return i.
If there is no such position i, return N.
Space Complexity: O(1)Explanation:
O(1).
As there is no extra space required.
Time Complexity: O(n)Explanation:
O(N), where ‘N’ is the length of the given array.
We are traversing the array only once. Hence, the overall complexity is O(N).
Answered
Anonymously
Add your answer
Round 2 - Face to Face
(1 Question)
Round duration - 60 minutes Round difficulty - Medium
The interview was in the morning at 10 AM in the office meeting room.
Q1.
House Robber Problem Statement
Mr. X is a professional robber with a plan to rob houses arranged in a circular street. Each house has a certain amount of money hidden, separated by a security system that ...
Ans.
Didn't get enough time to code the solution but explained the approach We can do this using DP We can maintain 2 arrays - one represents the ans if we start from first house and the other represents the answer if we start. from the second house.Then simply looping over the array and calculating these array's elements.
Answered
Anonymously
Add your answer
Round 3 - Face to Face
(1 Question)
Round duration - 60 minutes Round difficulty - Medium
The interview was at 11 AM in the meeting office.
Q1.
Running Median Problem
Given a stream of integers, calculate and print the median after each new integer is added to the stream.
Output only the integer part of the median.
Example:
Input:
N = 5 Stre...
Ans.
Started with the brute force solution of insertion sort Interviewer asked to optimize. Gave the solution which uses two heaps - max heap and min heap. the difference in size of both heaps cannot be more than 1. And we might need to remove elements from one heap to other heap as more input numbers are added
Answered
Anonymously
Add your answer
Round 4 - Face to Face
Round duration - 60 minutes Round difficulty - Medium
Q1. Can you provide a deeper discussion about all the projects you completed in your previous company?
Ans.
Tip 1: Know well about the projects that you have done in the past
Answered
Anonymously
Add your answer
Interview Preparation Tips
Professional and academic backgroundI applied for the job as SDE - 2 in HyderabadEligibility criteriaNoUber interview preparation:Topics to prepare for the interview - Data Structures, Algorithms, Graphs, Dynamic programming, Trees, stack, queue, System DesignTime required to prepare for the interview - 3 monthsInterview preparation tips for other job seekers
Tip 1 : Be consistent in the preparation. Practice atleast one question everyday Tip 2 : Make relevant notes that you can go through on the day before the interview Tip 3 :Try to note your progress by giving timed contests
Application resume tips for other job seekers
Tip 1 : Clearly mention the details of the projects that are relevant to the company that you are applying for Tip 2 : Ensure that there are no grammatical mistakes and that you have highlighted the important keywords in your resume
This was coding round and was conducted on Google meet with code link shared. Their were 2 interviewers that gave questions and later ran code on sample test cases.
Q1.
Print Permutations - String Problem Statement
Given an input string 'S', you are tasked with finding and returning all possible permutations of the input string.
Input:
The first and only line of input ...
Ans. Backtracking
We can find all the permutations by Backtracking.
1: Fix a character then swap all the rest of the remaining character with a fixed character.
2: Then find all permutations for all remaining characters by the recursive call.
3: The base case for the recursion will be when there is only one character left unprocessed.
Below is the illustration to approach.
Space Complexity: O(n)Explanation:
O(N)...
Answered
Anonymously
Add your answer
Q2.
Find the Kth Row of Pascal's Triangle Problem Statement
Given a non-negative integer 'K', determine the Kth row of Pascal’s Triangle.
Example:
Input:
K = 2
Output:
1 1
Input:
K = 4
Output:
1 4 6 ...
Ans. Naive Approach
In this approach, we find the row elements of the previous row using recursion, and based on the values of previous row elements, we will evaluate the current row elements.
We are given a function kthRow() which takes an integer ‘K’ as the only parameter and returns an integer vector. This is the definition of our recursive function too.
As the base condition of our recursive function, we will check if ‘K’ ...
Answered
Anonymously
Add your answer
Round 2 - Video Call
Round duration - 2 hours Round difficulty - Medium
This was a Machine Coding Round/LLD round followed by HLD round which was taken by Video Conferencing and Screen Sharing.
Round 3 - HR
Round duration - 75 minutes Round difficulty - Medium
This was the last round. This was HM round followed by the HR round.
Interview Preparation Tips
Professional and academic backgroundI completed Civil Engineering from Netaji Subhas University Of Technology. Eligibility criteriaPrior Work ExperienceOla interview preparation:Topics to prepare for the interview - Data Structures, OOPS, Algorithms, Dynamic Programming, Aptitude, Computer Netwroks and System ArchitectureTime required to prepare for the interview - 3 monthsInterview preparation tips for other job seekers
Tip 1 : Solve previously asked questions. It tells you about the level of questions that the company asks. Check glass-door reviews it will help you to know what kind of questions company ask Tip 2 : Be real during the interview and don’t show off. Tip 3 : Prepare for theory subjects like Object-Oriented Programming System, Database Management System, Computer networks, etc.
Application resume tips for other job seekers
Tip 1 : Keep your resume simple with all work experience mentioned. Tip 2 : Any unwanted information on the resume leaves a bad impact on the interviewer. Tip 3 : You should be prepared to explain anything that’s written on your resume. Tip 4 : Keep it of 1 page or 2 pages only
Started with brief intro(5 mins) about interviewer. Problem solving question, question was already there in the codelink shared by the interviewer. He explained the problem again with sample testcase. The Interviewer was friendly.
Q1.
Course Schedule II Problem Statement
You are provided with a number of courses 'N', some of which have prerequisites. There is a matrix named 'PREREQUISITES' of size 'M' x 2. This matrix indicates that fo...
Ans. Breadth-First Search
Our current algorithm is based on the idea of the BFS approach. We first process all the courses with 0 in-degree implying no prerequisite courses required. If we remove all these courses from the graph, along with their outgoing edges, we can find out the courses/nodes that should be processed next. These would again be the nodes with 0 in-degree. We can continuously do this until all the courses h...
Answered
Anonymously
Add your answer
Q2. Design a live video broadcast platform.
Add your answer
Round 2 - Video Call
(2 Questions)
Round duration - 90 minutes Round difficulty - Medium
There were 2 interviewers(India HM and Seattle HM), India HM was just shadowing and didn't ask any questions. Started with intro, he asked in detail about what I do at current company(10 mins). Again, jumped into LP's(25 mins).
Q1.
Distance Between Two Nodes in a Binary Tree
Given a binary tree and the values of two distinct nodes, determine the distance between these two nodes in the tree. The distance is defined as the minimum num...
Ans. Naive Approach
In any rooted tree, the distance between two nodes 'U' and 'V' can be found by finding the lowest common ancestor (LCA), ‘x’ of two nodes. The lowest common ancestor (LCA) between nodes 'U' and 'V' is defined as the lowest node in the tree that has both 'U' and 'V' as descendants, where we define each node to be a descendant of itself (so if 'U' has a direct connection from 'V', 'V' is the lowest common a...
Answered
Anonymously
Add your answer
Q2.
Median in a Stream Problem Statement
Your task is to determine the median of integers as they are read from a data stream. The median is the middle value in the ordered list of numbers. If the list length...
Ans. Brute force approach
Store the incoming data elements in a vector. Sort the vector everytime you need to output the median.
Algorithm:
Store the incoming elements of the data stream in a vector.
Step by step insert one element and sort the vector as soon as any element is added in the vector.
If the size of the vector is odd, print the middle element of the sorted vector. If the size of the vector is even, return the mean of...
Answered
Anonymously
Add your answer
Round 3 - Telephonic Call
Round duration - 60 minutes Round difficulty - Medium
There was only 1 interviewer in this round and We had no video sharing in this round so it was becoming difficult to understand each other.
Interview Preparation Tips
Professional and academic backgroundI applied for the job as SDE - 2 in SeattleEligibility criteriaNAAmazon interview preparation:Topics to prepare for the interview - Data Structures - Trie, HashMap, Sets, Priority Queue, Stack, Advanced Topics like Fenwick Tree, Segment Trees, Game Theory, Dynamic Programming, Union Find,Graph Algorithms, BitmaskingTime required to prepare for the interview - 3 monthsInterview preparation tips for other job seekers
Tip 1 : Bookmark the GFG Amazon Archives. It helped me a lot during my preparations. Reading other’s interview experiences is one of the best ways to get yourselves ready for the next job interview. Practice daily atleast 5 questions. Tip 2 : Most commonly asked topics in Amazon Interviews ( as per the mail I received from my recruiter ) : BFS/DFS/Flood fill, Binary Search, Tree traversals, Hash tables, Linked list, stacks, queues, two pointers/sliding window Binary heaps, Ad hoc/string manipulations. Tip 3 : Highly recommended sites for practicing questions ( usually practice medium and hard level questions) : Leetcode (highly encouraged) Geeksforgeeks (highly encouraged) CodeZen( highly encouraged) Codeforces Tip 4 : This is a great bigocheatsheet that could be of great help https://www.bigocheatsheet.com/
Application resume tips for other job seekers
Tip 1 : Mention past working experience in detail as how you were important to your previous company. Tip 2 : Try to keep your resume to 1 page if work experience < 5 years Tip 3 : Update your resume according to role you are applying for and never put false things on resume.
Timing: evening Environment: Online round took at home
Q1.
Smallest Subarray with K Distinct Elements Problem
Given an array A consisting of N integers, find the smallest subarray of A that contains exactly K distinct integers.
Input:
The first line contains tw...
Ans.
At first sight this can be solved easily by using two loops to iterate over contiguous subarrays in O(n^2) and counting number of arrays and breaking the outer loop if number of odds exceed 'k'.
Optimised solution is to take two pointer approach where right pointer is incremented till num of odds not exceed 'k'. If limit is reached, increment left pointer and add number of arrays (right - left+1)*(right-left)/2 to the r
Answered
Anonymously
Add your answer
Round 2 - Face to Face
Round duration - 90 minutes Round difficulty - Medium
Machine coding round
Round 3 - Face to Face
(1 Question)
Round duration - 60 minutes Round difficulty - Medium
Q1.
Rat In a Maze Problem Statement
Given a N * N maze with a rat placed at position MAZE[0][0], find and print all possible paths for the rat to reach its destination at MAZE[N-1][N-1]. The rat is allowed to...
Ans. Backtracking Approach
Initialize, all the cells of the solution matrix used to print the path matrix to 0. First, you cannot make use of the existing maze to print the solution maze as you have to distinguish b/w 1 of maze or 1 of ‘SOLUTION matrix.
Form a recursive function, which will follow a path and check if the path reaches the destination or not. If the path does not reach the destination then backtrack and t...
Answered
Anonymously
Add your answer
Round 4 - Face to Face
Round duration - 60-90 minutes Round difficulty - Medium
Round 5 - HR
Round duration - 60 minutes Round difficulty - Medium
Hiring Manager round
Interview Preparation Tips
Professional and academic backgroundI applied for the job as SDE - 2 in BangaloreEligibility criteriaNone as such. Only eligible criteria for SDE-2 role is that one should have prior experience working as SDEUber interview preparation:Topics to prepare for the interview - Data structures and algorithms, Design patterns, System design, DatabasesTime required to prepare for the interview - 1 monthInterview preparation tips for other job seekers
Tip 1 : Do some basic research about the interview process and types of rounds while appearing for a company interview. Narrow down the topics and draft a realistic plan afterwards. Tip 2 : Try to solve as many problems as possible as this is primarily what you will be doing in live interview rounds.
Application resume tips for other job seekers
Tip 1 : Tailor your resume as per expectations from the role you are applying for. Tip 2 : Order your experiences and skills by relevance. Tip 3 : Try to fit the content in a single page.
Round duration - 45 minutes Round difficulty - Medium
This round was scheduled in the evening hours and all the participants were required to fill a form which was shared 15 minutes prior to the start of the online coding round. This form was filled out probably for the security reasons and to ensure that no one disinterested participant gives the test.
Q1.
Ways To Make Coin Change
Given an infinite supply of coins of varying denominations, determine the total number of ways to make change for a specified value using these coins. If it's not possible to make...
Ans. Recursion
The idea is to use recursion.
For a particular coin, we have two options either include it or exclude it.
If we include that coin, then calculate the remaining number that we have to generate so recur for that remaining number.
If we exclude that coin, then recur for the same amount that we have to make.
Our final answer would be the total number of ways either by including or excluding.
There will be two edg...
Answered
Anonymously
Add your answer
Q2.
Validate Binary Search Tree (BST)
You are given a binary tree with 'N' integer nodes. Your task is to determine whether this binary tree is a Binary Search Tree (BST).
BST Definition:
A Binary Search Tr...
Ans. BST property
The approach is based on the fact that the value of each node in a BST is greater than the value of all the nodes in the left subtree and smaller than the value of all the nodes in the right subtree.
Here is the complete algorithm-
For each node, we store the minimum and maximum value allowed for that node. Initially, for the root node, the minimum value would be -10^9 and the maximum value should be 10...
Answered
Anonymously
Add your answer
Round 2 - Telephonic Call
(1 Question)
Round duration - 60 minutes Round difficulty - Hard
This round was on call where I was just supposed to answer the tech questions that were asked. It started with a brief interview with one another and then moved to questions on DBMS, operating systems, computer networks and all. Almost 20-25 questions were asked and I probably answered 90% of them correctly.
Q1.
Reverse Linked List Problem Statement
Given a Singly Linked List of integers, your task is to reverse the Linked List by altering the links between the nodes.
Input:
The first line of input is an intege...
Ans. Recursive Approach
One way is to use recursion to reverse the list. Divide the linked list in two halves, the first node and the rest of the list. Reverse the second half using recursion and append the first half, that is the first node at the end of the reversed linked list. Return the head of the reversed linked list.
Algorithm
If the list contains only one node, return the head of the list.
Else, divide the ...
Answered
Anonymously
Add your answer
Round 3 - HR
Round duration - 30 minutes Round difficulty - Hard
There was only one interviewer for this round. He continuously interacted with me and was giving me some good situational problems that were not very easy to answer. Basically those were open-minded questions which can be answered oth ways and that's why I found it quiet hard as per my nature but at the end things went well for me.
Interview Preparation Tips
Professional and academic backgroundI completed Mechanical Engineering from Malaviya National Institute of Technology Jaipur. I applied for the job as SDE - 2 in HyderabadEligibility criteriaabove 7 cgpa, no backlogsAmazon interview preparation:Topics to prepare for the interview - Data Structures, hashmap, linked list, Pointers, OOPS, System Design, Algorithms, Dynamic Programming, array, 2-pointer problemsTime required to prepare for the interview - 8 monthsInterview preparation tips for other job seekers
Tip 1 : practice on gfg and coding ninjas Tip 2 : compete on codechef and codeforces Tip 3 : learn DSA and practice regularly
Application resume tips for other job seekers
Tip 1 : put your entire valuable experience in brief Tip 2 : put the handle of you competitive coding profiles Tip 3 : try to put those things that really attracts the recruiter, will be better if your past experiences relates to the company
Add office photos
Compare
Filter interviews by
Anonymous
