## SDE1 Interview Questions

- 0of 0 votes

AnswersA string can contain only a, b or c. There cannot be 2 consecutive same character. First and the last character cannot be the same. Now given a string with ‘a’, ‘b’, ‘c’ or ‘?’. We need to find the string replacing ‘?’ that satisfy the above conditions. For multiple-answer display lexicographically smallest string. For no answer possible display “Not Possible”.

- anoophky August 31, 2019 in India| Report Duplicate | Flag | PURGE

Directi SDE1 String Manipulation - 0of 0 votes

AnswersA co-ordinate plane was given. On each point (x, y) there are x+y number of apples on it. A person is standing on (0, 0) and he wants to buy a square plot having N number of apples inside it (including the periphery). Question was to return the value of perimeter of that square plot given N.

- 200MITTALGAUTAM August 26, 2019 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersGiven a list of sentences and a list of phrases. The task is to find which sentence(s) contain all the words in a phrase and for every phrase print the sentences number that contains the given phrase.

- Rising star August 07, 2019 in India

Constraint: A word cannot be a part of more than 10 sentences.

Examples:

Input:

Sentences:

1. Strings are an array of characters.

2. Sentences are an array of words.

Phrases:

1. an array of

2. sentences are strings

Output:

Phrase1 is present in sentences: 1,2

Phrase2 is present in sentences: None

Since each word in phrase 1 exists in both the sentences,

but all the words in second phrase do not exist in either.| Report Duplicate | Flag | PURGE

Flipkart SDE1 Algorithm - 0of 0 votes

AnswersSteps to get out of complete binary tree

- bibhuprasadpala107 July 02, 2019 in India

You are given two integers A and B. A describes the number of nodes in complete binary tree.

You are B steps away from your destination in the worst case.

Initially, you can be at:

The root node of the tree and can only move bottom of the tree.

Any leaf node of the tree and can only move up the tree.

Find and return an array of integers C of size 2

where

C[0]: The number of nodes which are at B steps from the root, i.e. the number of nodes such that,

starting at that root, you have to take

B steps downwards to reach the node.

C[1]: The number of nodes such that the maximum distance from the node to any leaf in the subtree of the node is B.| Report Duplicate | Flag | PURGE

xyz SDE1 - 0of 0 votes

AnswersIn a garden, there are several apples trees planted in a grid format. Each point (i,j) in the grid has |i| + |j| apples.

Allie can buy a square plot centred at (0,0). Find the minimum perimeter of the plot (1 unit having length = 1) such that she can collect at

least X apples. All plants on the perimeter of the plot are also included.

Sample:

- bertram_gilfoyle June 27, 2019 in India`Input = 1 Output = 8 input = 11 Output = 8 Input = 13 Output = 16`

| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 2 votes

AnswersGiven an array of integers A. calculate the sum of A[i] %A[j] for all possible i,j pair. return sum%(10^9+7) as an output solve this problem on o(n).

- Dhioyt June 19, 2019 in India

input :-

A=[1,2,3]

Output:-

5

Explanation:-

(1%1)+(1%2)+(1%3)+(2%1)+(2%2)+(2%3)+(3%1)+(3%2)+(3%3)| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswerQuestion 2: Optimize the problem for total project cost and total project days to minimal.

- ratneshtr09 June 15, 2019 in United States

Given the cost/hour of each worker:

[ 30, 25, 40 ]| Report Duplicate | Flag | PURGE

Intel SDE1 - 0of 0 votes

AnswersQuestion 1:

- ratneshtr09 June 15, 2019 in United States

There is a bunch of tasks, each task has a code with different time to complete and task dependencies. There are few workers, how to allocate the task to these workers to minimize the total time taken to complete the task.

Example:

No of worker: 3

Task id, Task Time, Task dependency:

1, 2, 0

2, 4, 1

3, 7, 0

4, 12, 1

Question 2: Optimize the problem for total project cost and total project days to minimal.

Given the cost/hour of each worker:

[ 30, 25, 40 ]| Report Duplicate | Flag | PURGE

Intel SDE1 C++ - 1of 1 vote

Answers"Good Range"

- Mit25 May 29, 2019 in United States

There is a number space given from 1 to N. And there are M queries followed by that. In each query, we were given a number between 1 to N (both inclusive). We add these number one by one into a set.

Good range: A range in which there is exactly one element present from the set.

For each query, we need to find the good ranges. We need to return the sum of boundry of all good ranges.

Input:

First line will take two integer for input N and M.

Then following M lines would be numbers between 1 and N (both inclusive).

Output:

Following M lines contains sum of boudaries of good ranges.

Note:

Range can consist of single element and represented as (x-x) where boundary sum will be x+x.

Example:

Input:

10 4

2

5

7

9

Output:

11

18

30

46

Explaination:

step-1) set: 2

good range: (1-10)

sum: 1+10=11

step-2) set: 2 5

good range: (1-4), (3-10)

sum: 1+4+3+10=18

step-3) set: 2 5 7

good range: (1-4), (3-6), (6-10)

sum: 1+4+3+6+6+10=30

step-4) set: 2 5 7 9

good range: (1-4), (3-6), (6-8), (8-10)

sum: 1+4+3+6+6+8+8+10=46| Report Duplicate | Flag | PURGE

Amazon SDE1 Coding - 0of 0 votes

AnswersLCA of directed graph.

- shushantsharan May 20, 2019 in India| Report Duplicate | Flag | PURGE

Flipkart SDE1 Algorithm - 0of 0 votes

AnswersDesign Movie Review system using OOP concepts. Code should pass all test cases.

- shushantsharan May 20, 2019 in India| Report Duplicate | Flag | PURGE

Flipkart SDE1 Coding - 0of 2 votes

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 - 1of 1 vote

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 - 4of 4 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

AnswersGiven 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

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

Open Chat in New Window