## SDE1 Interview Questions

- 0of 0 votes

AnswersWe are given a undirected tree with N (1 to N) nodes rooted at node 1. Every node has a value assigned with it, represented by array - A[i] where i:[1:N].

- khatribalak December 03, 2021 in United States

We need to answer Q queries of type : -> V X : longest length of the common prefix between V and any ancestor of X including X, in their binary representation of 62-bit length.

Common prefix between 2 numbers is defined as:

Example :

4: 0..................0100 (62-bit binary representation)

6: 0..................0110

Considering both as 62-bit in it's binary representation.

Longest length of the common prefix is: 60 (as 60 left most bits are same.)

Now we are given the N (num nodes), edges, nodes values (A[i]) and queries, and we need to answer each query in optimal time.

Constrains :

N <= 10^5, number of nodes

A[i] <= 10^9, value of each node

Q <= 10^5 ,number of queries

Edge[i] = (i, j) <= N

Approach :

Create tree and track the immediate parent of each node.

for Each Query : [V, X], traverse each node n(in the path from X to root) and XOR each node's values with V and find the most significant set bit for each of the XOR operation and pick the minimum one among all of them.

So the result for Query : [V, X] : 62 - (1 + Step-2 result).

Is there any other efficient way to solve this problem? As the above approach in worst case takes O(n^2) time.| Report Duplicate | Flag | PURGE

Hi5 SDE1 - 0of 0 votes

AnswersSum of series (n/1) + (n/2) + (n/3) + (n/4) +…….+ (n/n). 1 <= n <= 10^12

- kritirohilla567 September 25, 2020 in India| Report Duplicate | Flag | PURGE

Student SDE1 - 0of 0 votes

AnswersBob and Alice have teamed up on a game show. They won the first

- shashankesh July 23, 2020 in India

round, allowing them access to a maze with hidden gold. If Bob can

collect all the gold coins and deliver them to Alice's position, they can

split the gold. Bob can move North⇆South or East⇆West as long as he

stays in the maze and the cell is not blocked. The task is to determine

the shortest path Bob can follow to collect all gold coins and deliver

them to Alice. If it is not possible, return -1.

You will be given an n × m array where each of the values ∈ {0, 1, 2}

representing open, blocked and open with a gold coin. Alice's position is

given as (x,y) = (row, column). Bob starts at the top left in cell (0, 0).

For example, maze = [[0,2,1],[1,2,0],[1,0,0]] with Alice at (2,2) is

represented as follows:

0 2 1

1 2 0

1 0 0

minMoves has the following parameter(s):

maze[maze[0][0],...maze[n-1][m-1]]: a 2D array of integers

x: an integer denoting Alice's row coordinate

y: an integer denoting Alice's column coordinate

Constraints

1 ≤ n, m ≤ 100

0 ≤ the number of coins ≤ 10

1 ≤ x < n

1 ≤ y < m

The first line contains an integer n, the numbers of rows in maze.

The second line contains an integer m, the number of columns in

maze.

Each of the next n lines contains m space-separated integers

describing the cells of each row in maze.

The next line contains an integer x.

The next line contains an integer, y.

Sample Input 0

3

3

0 2 0

0 0 1

1 1 1

1

1

Sample Output 0

2

Explanation 0

The shortest path Bob can take is (0, 0) → (0, 1) → (1, 1).

Sample Input 1

3

3

0 1 0

1 0 1

0 2 2

1

1

Sample Output 1

-1

Explanation 1

It is not possible for Bob to reach Alice, so we return −1.

Sample Input 2

3

3

0 2 0

1 1 2

1 0 0

2

1

Sample Output 2

5

Explanation 2

The shortest path Bob can take is (0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2) → (2, 1).| Report Duplicate | Flag | PURGE

Adobe SDE1 Algorithm - 0of 0 votes

AnswersIntelligent Substrings:

- himatNIT February 09, 2020 in United States for Hacker rank test

There are two types of characters in a particular language: special and normal. A character is special if its value is 1 and normal if its value is 0. Given string s, return the longest substring of s that contains at most k normal characters. Whether a character is normal is determined by a 26-digit bit string named charValue. Each digit in charValue corresponds to a lowercase letter in the English alphabet.

Example:

s = 'abcde'

alphabet = abcdefghijklmnopqrstuvwxyz

charValue = 10101111111111111111111111

For clarity, the alphabet is aligned with charValue below:

alphabet = abcdefghijklmnopqrstuvwxyz

charValue = 10101111111111111111111111

The only normal characters in the language (according to charValue) are b and d. The string s contains both of these characters. For k = 2, the longest substring of s that contains at most k = 2 normal characters is 5 characters long, abcde, so the return value is 5. If k = 1 instead, then the possible substrings are ['b', 'd', 'ab', 'bc', 'cd', 'de', 'abc', 'cde']. The longest substrings are 3 characters long, which would mean a return value of 3.| Report Duplicate | Flag | PURGE

Linkedin SDE1 - 0of 0 votes

AnswersThere are N cars parked in a row in a parking lot of the newly constructed club. as it is demonstrated in the picture below.

- shivanandtripathi02 October 27, 2019 in India

There is a gasoline and diesel fueling station installed.at the left and right side of the park.

An automatic fueling robot carries the fuel from station and fill up the parked car with fuel.

The cars are divided into 2 types depending on whether it is a gasoline or diesel car.

1 is denoted as gasoline cars and 2 is denoted as diesel cars.

The automatic robot will be used to provide a cost free fueling service which is filling up

all cars with 1 litre of each corresponding fuel.

The robot will move in between the 2 fuelling stations as below :

1) The robot carries 2 litre of gasoline at the gasoline station and starts moving from there.

2) The robot can fill up the cars of the same type of gas it carries 1 litre each.

3) The robot can go back to the fuelling station at any time, Independent from the current amount of fuel it carries.

4) When the robot arrives at the fuelling station, it gets 2 litre of supply of the corresponding fuel.(If the robot has some remaining fuel it will be discarded).

the picture is not there. so, i will explain how the arrary must look like. suppose the arrary is arr od

size x. then at index = 0, there is gas station and at index = x - 1 there is dielsel station. Remaining all indexes are filled with vehicle type. 1 represents gas type and 2 represents diesel type.| Report Duplicate | Flag | PURGE

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

AnswersCreate Valid html from below input.

- samfriendcom1234 September 18, 2019 in United States

String str="abcde"

points:- [{0,2,b},

{2,4,u}]

output : <b>ab<u>c</u></b><u>de</u>

Explanation:- character from 0 to 2 index should be bold, 2 to 4 index should be underline. Tricky point is that character at index 2 should be both bold and underline.| Report Duplicate | Flag | PURGE

xyz SDE1 - 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

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

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 - 1of 3 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 - 2of 2 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 - 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 - 6of 6 votes

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

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