SDE-2 Interview Questions
- 3of 3 votes
AnswersI was asked this during my onsite google interview but was unable to come up with an optimization for it. Here is the question:
- Jaysun October 26, 2019 in United States
There's a list of (x,y) points and a method getCircle with the following signature:
/**
* Given three points returns a circle (Radius, and center) such that all three points lie in its circumference
* or it returns null if no such circle is possible.
*/
Circle getCircle(point1, point2, point3);
getCircle method is already implemented and given to you as a black box. The problems asks you to find the Circle with most points in its perimeter.
The obvious answer is to get all possible triplets of points and find all possible circles and keep track of which one appears most often O(n^3) . Any ideas on how to further optimize this?| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 1of 1 vote
AnswersThere are cards and each card has an identity. e.g. HC1 has ID 1, this ID also represents the cost of the card. Your sister already have some cards and you want to gift her cards which she do not have already. Program is to return the max number of cards you can buy for her.
- acharyashailendra1 September 19, 2019 in India
Constraint : You have amount d, and want to buy as many distinct card as you can.
e.g. Sister Cards = [2, 3, 5], D : 7 Card you buy : 1, 4
Output : 2| Report Duplicate | Flag | PURGE
SDE-2 - 0of 0 votes
AnswersYou have been given a special and normal status of alphabets.
- acharyashailendra1 September 19, 2019 in India
e.g. “01111001111111111011111111” represents “abcdefghijklmnopqrstuvwxyz”. Here 0 represents normal character and 1 represents special character.
Given an Input String S and a number k, find the maximum continuous sub array with maximum k number of number elements. There is no constraint on special character.
e.g.
S = “giraffe”, K = 1, “011110011111111110111111”
Output : 3
How ?
normal characters : a, g, f
one of the possible solution : gir (as this has only one normal character)| Report Duplicate | Flag | PURGE
SDE-2 - 0of 0 votes
AnswerGiven a binary String which represents the target state. Minimum number of flips needed to convert a same size Binary String (with all 0’s) to target state. A flip also causes all the right bits to be flipped.
- acharyashailendra1 September 19, 2019 in India
e.g.
Input : 00101 (Represents Target)
Output : 3
Explanation :
00000 -> 00111 -> 00100 -> 00101| Report Duplicate | Flag | PURGE
SDE-2 - 0of 0 votes
AnswersN cows are standing at the origin on x-axis, each cow has some appetite, in other word hunger index. A cow can sleep of 1 unit of time or eat for one unit of time or move left or move right. There are some vessels placed on the x-axis, they are having infinite supply of fiod. Find minimum time in which all cows appetite would be filled.
- xyz September 15, 2019 in United States
Input:
cow Apetitte = {1,1}
Vessle locations = {-1,1}
Answer would be 2 since both cow can go in different direction they would eat for one seconds. One second for moving and one second for eating.
This problem looks to be similar to rotten eggs/tomatoes.| Report Duplicate | Flag | PURGE
Allegient SDE-2 Algorithm - 0of 0 votes
AnswerDesign and implement rate limiter for limiting api calls for a service distributed multiple users.
- acharyashailendra1 August 27, 2019 in India| Report Duplicate | Flag | PURGE
SDE-2 - 0of 0 votes
AnswerDesign data structures which support millions of products coming in streaming manner, we need to find at any moment what are top n products at any day
- acharyashailendra1 August 27, 2019 in India| Report Duplicate | Flag | PURGE
SDE-2 - 2of 2 votes
AnswerA dictionary is combination of characters from a-z. let's say a=1,b=2.. and so on z=26. you are given n and k. you have to find sum of length k from given combination.
- acharyashailendra1 August 21, 2019 in India
for example n=51 and k=3 then your answer should be =axz
as there can be many combination for given sum so it is suggested to print those string which comes first in dictonary| Report Duplicate | Flag | PURGE
LendingKart SDE-2 Data Structures - 1of 1 vote
Answersbeautiful numbers are those numbers which contains digit only 4 and 5 also they are palindrome.length of number can't be odd. for example
- acharyashailendra1 August 21, 2019 in India
44,55,4554 are beautiful numbers where as 38, 444 are not.
your task is to find nth number in this series. let's say if n=4 then output should be 4554. for n=1 output will be 44 always.| Report Duplicate | Flag | PURGE
LendingKart SDE-2 Data Structures - 0of 0 votes
AnswerMake a system that returns the average number of hits on the site per minute from the past 5 minutes
- neer.1304 August 15, 2019 in United States| Report Duplicate | Flag | PURGE
Indeed SDE-2 Software Design - 0of 0 votes
AnswerYou're given an array of integers sorted ( [1,2,3,5,6,7,10]) you need to serialize and compress this array into a string (1-3, 5-7,10)
- neer.1304 August 15, 2019 in United States| Report Duplicate | Flag | PURGE
Indeed SDE-2 Algorithm - 0of 0 votes
AnswerGiven two points on a directed acyclic graph determine their least common ancestor, give it's time complexity, and describe any improvements you could make (if possible).
- neer.1304 August 15, 2019 in United States| Report Duplicate | Flag | PURGE
Indeed SDE-2 Algorithm - 1of 1 vote
AnswersUse synchronized, wait() and notify() to write a program such that below mentioned conditions are fulfilled while reading and writing data to a shared resource.
- neer.1304 July 26, 2019 in United States
When a write is happening, no read or other write should be allowed(read and write threads should wait)
When a read is happening, no write should be allowed (write threads should wait) but. other read threads should be able to read.
Donot use any API classes e.g. ReadWriteLock, AtomicInteger etc..| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Java - 0of 0 votes
AnswersDesign election voting system. Election would be country wide. System should be scalable, available and consistent.
- neer.1304 July 26, 2019 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 0of 0 votes
AnswersImplement following method of ScheduledExecutorService interface in Java
- neer.1304 July 23, 2019 in United States
schedule(Runnable command, long delay, TimeUnit unit)
Creates and executes a one-shot action that becomes enabled after the given delay.
scheduleAtFixedRate(Runnable command, long initialDelay, long period, TimeUnit unit)
Creates and executes a periodic action that becomes enabled first after the given initial delay, and subsequently with the given period; that is executions will commence after initialDelay then initialDelay+period, then initialDelay + 2 * period, and so on.
scheduleWithFixedDelay(Runnable command, long initialDelay, long delay, TimeUnit unit)
Creates and executes a periodic action that becomes enabled first after the given initial delay, and subsequently with the given delay between the termination of one execution and the commencement of the next.| Report Duplicate | Flag | PURGE
Uber SDE-2 Algorithm - 0of 0 votes
AnswersGiven a string select two non-overlapping strings that are same and remove them. Perform this operation recursively till there are no desired strings.
- neer.1304 July 20, 2019 in United States
Print the number of possible substring after completing above operation.
Ex - abcc
Duplicate non-overlapping substring - abc
After removing abc from we are left with 1 substring abc.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersIn a 2-D matrix of m*n select m-1 elements from each row such that that the resulting sum is minimum and each column is selected atleast once.
- neer.1304 July 20, 2019 in United States
Ex -
2 3 5
3 2 5
4 4 7
Selecting (2,3) from 1st row, (2,5) from 2nd row and (4,4) from 3rd row would result in minimum sum of 20| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersFind LCA for list of nodes of a tree
- neer.1304 July 17, 2019 in United States
Function defined as below -
TreeNode findLCA(TreeNode root, List<TreeNode> nodes)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven two numbers m and n. Find all numbers between these two numbers such that difference between adjacent digit is 1
- neer.1304 July 01, 2019 in United States
For ex m =0 n =22
O/p - 0,1,2,3,4,5,6,7,8,9,10,12,21| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersCode an algorithm for a game consisting of two players. The input is a positive integer x. Each round, a player deducts a perfect square from the number. The player can choose any perfect square as long as it is less than or equal to the current number and greater than 0. The current player wins if the number becomes 0 after his deduction.
- Thomas June 19, 2019 in United States| Report Duplicate | Flag | PURGE
Salesforce SDE-2 Dynamic Programming - 0of 0 votes
AnswersP0, P1, ...., Pn players in tournament. In first level, P0 plays with P1, P2 plays with P3 and so on. In level 2, Winner of P0,P1 plays with winner of P2,P3. For i,j output level in which they will face each other assuming they win all games.
- neer.1304 June 11, 2019 in United States| Report Duplicate | Flag | PURGE
Curefit SDE-2 Algorithm - 0of 0 votes
AnswersGiven a nested list of integers, return the sum of all integers in the list weighted by their depth.
- koustav.adorable June 09, 2019 in United States
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Different from the question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.
Example 1:
Input: [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's at depth 1, one 2 at depth 2.
Example 2:
Input: [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 13 + 42 + 6*1 = 17.| Report Duplicate | Flag | PURGE
SDE-2 Algorithm - 0of 0 votes
AnswersUse the location data getting generated from multiple delivery boys moving on the ground to estimate time which a delivery boy will take to move from point A to point B in an area. Additionally, try to do this in real time so that it can be used in assigning delivery boys and minimising delivery time in real time.
- neer.1304 May 31, 2019 in India| Report Duplicate | Flag | PURGE
Swiggy SDE-2 design - 0of 0 votes
AnswersIn a binary tree if the neighbours are set on fire for every node , find the path to optimally set the entire tree on fire.
- neer.1304 May 31, 2019 in India| Report Duplicate | Flag | PURGE
Swiggy SDE-2 Algorithm - 0of 0 votes
AnswersGiven an input stream of Swiggy order timestamps and costs, at any instant find the costliest order in the last X mins
- neer.1304 May 31, 2019 in India| Report Duplicate | Flag | PURGE
Swiggy SDE-2 Algorithm - 0of 0 votes
AnswerDesign a system to upload images with tags. The tags should be searchable and search should return images linked to those tags.
- arnold086 May 25, 2019 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 System Design - 0of 0 votes
AnswerI dont remember the exact problem anymore. but the problem's solution included going through an array and at every step taking 2 minimum element and adding the result. this also includes the result itself.
- Desi May 13, 2019 in United States for Robotics
so lets say for following array:
2,54,4,10,1,7
you first take 1 and 2 and add
then add the result 3 to the array
so now your array looks like :
3,54,4,10,7
then you take 3 and 4 and add them and add result back
I basically used a heap where i take two mins and add them and add the result back to heap.
I have give amazon online test twice in last 8 months and both the times the first question was about heaps and second something about finding shorted path in a grid between two cells| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersThe problem was very similar to the problem from geeksforgeeks:
- Desi May 13, 2019 in United States for Robotics
Shortest distance between two cells in a matrix or grid
Given a matrix of N*M order. Find the shortest distance from a source cell to a destination cell, traversing through limited cells only. Also you can move only up, down, left and right. If found output the distance else -1.
instead of source and destination, they asked for robot to be able to get rid of obstacle at a certain cell.
I have give amazon online test twice in last 8 months and both the times the first question was about heaps and second something about finding shorted path in a grid between two cells| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersDesign amazon online book store.
- Desi May 13, 2019 in United States for Robotics| Report Duplicate | Flag | PURGE
Amazon SDE-2 System Design - 0of 0 votes
AnswersI am given jobs with starttime and end time and we unlimited VMs. at any point a VM can only take one job. so bascially I had to find overlapping jobs and assign them to different machines and those that are not overlapping could be assigned to same machines. The tricky part was when there are two different overlaps and they could be assigned to 2 machines instead of all overlapping jobs being assigned to different machines.The method should return minimum number of VMs used to finish all jobs.
- Desi May 13, 2019 in United States for Robotics
I mentioned sorting the jobs based on start time. and then returning number_of_overlapping jobs +1. but again in some cases if there are two different overlaps which could be assigned to two machines then we need to take care of that.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm