## SDE1 Interview Questions

- 1of 1 vote

AnswersA graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted vertices given in K. If it creates a path, we have to discard the edge.

- setu April 01, 2019 in India

Example: N = 4; K = {(1,4)}; M = {(1, 2), (2, 3), (3, 4)}. Here, addition of edge (3, 4) will create a path between 1 and 4. Hence we discard edge (3, 4)| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 2 votes

AnswersPrint all possible combination by replacing special charecters from number.

- Rising star February 24, 2019 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersThere are N countries, each country has Ai players. You need to form teams of size K such that each player in the team is from a different country.

- crowdx February 12, 2019 in India

Given N and number of players from each country and size K. Find the maximum number of teams you can form.| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm - 0of 0 votes

AnswersGiven an array of edges between any two points in 2 dimensional space. A single edge is represented by the co-ordinates of two points it is connecting for example (2,3),(4,5) represents and edge connecting points (2,3) and (4,5).Find out the total number of squares possible if all edges are parallel to X or Y axis.

- jadonv January 26, 2019 in United States

NOTE : Include overlapping squares, squares having one side in common and squares contained within another square. Co-ordinates can have float values.

Example below -

I have considered a very simple input and output combination to keep it short.

Input

{

(0,0),(0,3)

(0,0),(3,0)

(0,3),(3,3)

(3,0),(3,3)

}

Output : 1

Possible Approach : Create a map as below -

Key(Slope of Edge in Degrees) - Value(Array of Edges)

0 - {(0,0),(3,0)},{(0,3),(3,3)}

90 - {(0,0),(0,3)},{(3,0),(3,3)}

While inserting edges in the map, make sure the edges are sorted by max(x1,x2) first and then max(y1,y2).

Pick 2 edges from one slope let's say slope 0, then pick 2 edges from slope 90 and see if square is formed or not. If square not formed, then look at next 2 edges of slope 90 and so on.

Sorting here is an expensive operation.

Please share any better solutions.| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 1of 1 vote

AnswersGiven an integer S, you have to count the total number of integral solutions of the equation a+b^2+c^3+d^4<=S, such that 0<=a,b,c,d<=10000 and 0<S<10^15

- Ankita January 13, 2019 in United States

Edit: Here value can be less than or equal to S, so if input S= 2 ,then output=12

i.e we can consider 0,0,0,1 and 0,0,0,0 etc also as sum will be less than S(i.e 2)| Report Duplicate | Flag | PURGE

SDE1 Algorithm - 2of 2 votes

AnswersGiven a Start Node and an End Node in a graph report if they are “necessarily connected”. This means that all paths from the start node lead to the end node. Report true all paths from start node lead to end node and false if at least one path does not lead to the end node. This is a directed graph which can have cycles

- nikki December 31, 2018 in United States

Does anyone know how to solve this? I had it in my interview at Google in CA and I still cant solve it| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm - 2of 2 votes

AnswersGiven a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n)

- Prateek Agrawal December 02, 2018 in United States

For example

s = 'ababac'

Then substrings are as follow:

1: s(1, 6) = ababac

2: s(2, 6) = babac

3: s(3, 6) = abac

4: s(4, 6) = bac

5: s(5, 6) = ac

6: s(6, 6) = c

Now, The lengths of LCP of all substrings are as follow

1: len(LCP(s(1, 6), s)) = 6

2: len(LCP(s(2, 6), s)) = 0

3: len(LCP(s(3, 6), s)) = 3

4: len(LCP(s(4, 6), s)) = 0

5: len(LCP(s(5, 6), s)) = 1

6: len(LCP(s(6, 6), s)) = 0

String contains only lowercase alphabates.| Report Duplicate | Flag | PURGE

Google SDE1 Data Structures - 0of 0 votes

AnswersThere are N nodes in a graph connected by exactly N-1 edges. There is exactly 1 shortest path from one node to any other node. The nodes are numbered from 1 to N. Given Q queries which tell source node and the destination nodes. Find the most visited node after traveling those Q paths. For example, say Q=3

- sudhiammula November 23, 2018 in India

and 3 queries are

1 5

2 4

3 1

So travel from node 1 to node 5, then from node 2 to node 4, then from node 3 to node 1. Finally, find what is the most visited node after the Q queries.

Finding every path and incrementing every visited node count is a naive solution. The interviewer asked me to optimize it.| Report Duplicate | Flag | PURGE

Samsung SDE1 Trees and Graphs - 0of 0 votes

AnswerRoulette -Gamblers Fallacy. start with $50, bet opposite color every time same color 4 in a row. loop 100 time or until $0. Suggest create roulette wheel object with history, a gambler object with maybe gamblingplan object. (you can find more detailed suggestions elsewhere)

- whoknows November 18, 2018 in United States| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm - 0of 0 votes

AnswersGiven k,n,m. where k is no. of coconuts you initially have. n is the some no. such that if you have >=n coconuts, you becomes stressed otherwise you become normal. m is the no. of shops.You go from 1st shop to m-th shop without skipping any shop. At i-th shop, either you buy Si coconuts or sell Si coconuts. If you are stressed then you must become normal at next shop. If you have less than Si coconuts and you want to sell then you must sell all the coconuts you have. The task is to calculate maximum possible changes of your mood from stressed to normal or vice-versa.

- mendela4cazz November 09, 2018 in India

ie: shop ={100,200,100,1,1} , k=1900 , n=2100 then answer should be 3 as initially mood is happy at first shop we buy 100 coco and total are 2000<n so still happy, at shop 2 coco 2200,now mood is stressed and so| Report Duplicate | Flag | PURGE

Adobe SDE1 - -2of 4 votes

AnswersHow should I prepare for the interview with Alexa team at Amazon?

- ihsihs005 October 17, 2018 in United States for Alexa| Report Duplicate | Flag | PURGE

Amazon SDE1 Data Structures - 0of 0 votes

AnswersIf you had n racers and m checkpoints, how would you list out the racers in the order in which they are in the race given that each checkpoint gets a notification when a specific racer crosses it?

- AnonyMous October 11, 2018 in United States

Your code should run in O(1).

Note: Players cannot cheat, i.e. they cannot miss a checkpoint

Example:

Assume 5 checkpoints(C1, C2, C3, C4, C5) and 10 racers(P1, P2,...P10).

Now once the race begins, lets say P2 first crosses C1. So the current race order is P2.

Now P1, P3, P4 cross C1; so the race order is P2, P1, P3, P4.

Now P1, crosses C2; so the race order becomes P1, P2, P3, P4

Now P3, crosses C2; so the race order becomes P1, P3, P2, P4

Now P5, crosses C1; so the race order becomes P1, P3, P2, P4, P5

Now P1 crosses C3; so the race order remains P1, P3, P2, P4, P5

and so on.

Assume that you get notified of players crossing a checkpoint by a function update(player name, checkpoint). Your task is to show the players in order in O(1) i.e return a vector of players in-order in O(1)| Report Duplicate | Flag | PURGE

Bloomberg LP SDE1 Data Structures - 1of 1 vote

AnswersGiven an array of integers, find out how many unique BST can be generated from the array.

- kieth October 07, 2018 in United States| Report Duplicate | Flag | PURGE

Google SDE1 Trees and Graphs - 1of 1 vote

AnswersGiven an array of Integers, find out how many combinations in the array, satisfy the equation x+y+z=w, where x,y,z and w belong to the array and idx(x)<idx(y)<idx(z)<idx(w). Elements are unique.

- kieth October 07, 2018 in United States| Report Duplicate | Flag | PURGE

Google SDE1 Arrays - 0of 0 votes

AnswerGiven 3 unsorted arrays A, B and C you need to find all possible combinations such that A[i] + B[j] = B[k] + C[l].

- venkataratnamkumar7777 September 22, 2018 in United States| Report Duplicate | Flag | PURGE

Walmart Labs SDE1 Algorithm Arrays - 0of 0 votes

AnswersThere are n number of stones. Each stone has a weight associated with it. 1st stone’s weight is 1, 2nd stone’s weight is 2.. and so on. You are given an integer x. You need to pick the maximum number of stones such that the total weight of stones picked is less than x.

- shivamdurani220 September 14, 2018 in India

You’re also given an array of stones which you can not pick.?| Report Duplicate | Flag | PURGE

Microsoft SDE1 - 0of 0 votes

AnswersRemove 3 or more consecutive characters from a string, repeat until there are no more.

- kqiann August 17, 2018 in United States

eg.

ABCCCCBBA => ABBBA => AA| Report Duplicate | Flag | PURGE

Bloomberg LP SDE1 String Manipulation - 0of 0 votes

AnswerGiven two arrays. One is for tasks (Processes) and each element depicts the amount of cores required to run the task. 2nd array is an array of CPU where each element depicts the no of cores in it.We have to tell how many maximum number of tasks can be allocated. Example: Task: [3, 5, 7], Cores: [1, 3, 5] . Here only task 0 and 1 can be allocated to CPU 1 and 2 . So, answer=2.

- Anil Kumar July 23, 2018 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 - -3of 3 votes

AnswersDid any one took Microsoft Online Technical Screen ?? What questions I can expect in this test ??

- Tom July 07, 2018 in United States| Report Duplicate | Flag | PURGE

Microsoft SDE1 - 0of 0 votes

AnswersGiven a BST of memory sizes. Find best fit for a memory block of size M.

- akisonlyforu June 11, 2018 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Data Structures - 0of 0 votes

AnswerGiven an infinitely large array and every element has tags associated with them, and there are about 10,000 tags (say) then sort the given array to get all tag-0’s first, tag-1’s next and so on in O(n).

- Ankita June 10, 2018 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 1of 1 vote

AnswersGiven k, and a binary string, determine if this contains all permutations of length k.

- ajay.raj May 24, 2018 in United States

For example, 11001 contains all possible binary sequences with k=2 (00,01,10,11)| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersYou have been given a generator string ab from which any number of strings can be generated recursively by inserting ‘ab’ at any location. You have been given an input string to check if that given string is valid or not.(i.e. generated by given with given string.)

- akisonlyforu May 22, 2018 in India

eg.

Input: aabbab

Output: valid

Input: abbaab

Output: Invalid

I could not come up with a algorithm less than O(N*N)| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswerGiven a multiple tree, and multiple nodes that need to be deleted,

- ajay.raj May 17, 2018 in United States

It is required to return a list of nodes so that the children of these nodes can be found after the nodes have been deleted.| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersGives you an int m, and a set of char (0,1,2,3,4,5,6,7,8,9)

- ajay.raj May 17, 2018 in United States

Lets you implement a function that generates a id based on the characters in the set. Each time you return a string, it must be unique. satisfying the same character can not appear consecutively more than m times, such as m = 3, "1000" is valid,

"0000" is not valid.

The smaller the string, the better.| Report Duplicate | Flag | PURGE

Amazon SDE1 - 1of 1 vote

AnswersLet’s say you have two input arrays with sorted elements. Find the union.

- prasad.hybris May 16, 2018 in United States

a[] = {2, 10, 14, 19, 51, 71}

b[] = {2, 9, 19, 40, 51}

Union = {2, 9, 10, 14, 19, 40, 51}| Report Duplicate | Flag | PURGE

Amazon SDE1 Java - 0of 0 votes

AnswersA group of friends are tracking the miles per gallon for each of their cars. Each time one of them fills up their gas tank, they record the following in a file: His or her name The type of car they drove How many miles driven since they last filled up How many gallons purchased at this fill up Date of the fill Their data is formatted as a comma separate value (csv) file with the following format for each row:(#person,carName,milesDriven,gallonsFilled,fillupDate) Miles are recorded as floating-point numbers and gallons as integers. Please create a program that allows members of this group to determine the miles per gallon (MPG) of each of their cars during a specific time range. Note: person may have more than one so a time range query might need to output data for one or more cars. A skeleton class will be provided; your job will be to complete the program. The principal function for querying MPG is of the form (the exact name, data types, etc., can be learned by inspecting the "solution" class in the skeleton code): GetRangeMPG(PersonName, StartDate, EndDate) Returns list of objects containing (CarName, MPG) MPG is calculated as (total miles traveled during time period)/ (total gallons filled during time period. The dates you receive in the query should be treated inclusively.

- pragramticProgrammer May 15, 2018 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 .Net/C# - 0of 0 votes

AnswerTo push dominoes, find out how many dominoes are standing in the end

- ajay.raj May 15, 2018 in United States

For example, the input is ".R...RL..R..L..", which means pushing the 2nd, 6th, and 12th dominoes to the right and pushing the 8th and 15th dominoes to the left. This example returns 4th. 1,7,16,17 blocks are standing| Report Duplicate | Flag | PURGE

Amazon SDE1

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window