## SDE1 Interview Questions

- 4of 4 votes

AnswersGiven an non-negative int array and target number, check if the target can be equal to the sum of non-negative multiples of the numbers in the array.

- ajay.raj March 17, 2017 in United States

For example, I have three numbers 6,9,20. Ex: n = 47 then it can be determined that 47 = 9*3 + 20

n=23 then there are no combinations.

public boolean combinationSum(int[] nums, int target) {

}| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswerWe have a List of FlightRoute

`public static class FlightRoute { String from; String to; int time; .... }`

and write a function to find Shortest Path: findShorestPath(String start, String end, List<FlightRoute>routes)

- ewrhoqpqheow March 16, 2017 in United States| Report Duplicate | Flag | PURGE

Facebook SDE1 Data Structures - 2of 2 votes

AnswersGiven an int array without repeated elements and a target, count the total number of subset that can be generated from the array such that min (subset) + max (subset) < target

- ajay.raj March 13, 2017 in United States

public int countSubSet(int[] nums, int target){

}| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersData structure design, N horse races, there are 10 checkpoints, whenever a horse through a check point will produce a (horse number, check point number) message, then design a data structure and algorithm to update the messages and then get the top 3 horse efficiently.

- ajay.raj March 13, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersInput friend’s relation {{1,2}, {2,3}, {3,4}}, could you split all the users into two groups and for the user in each group, all the users do not know each other. So the expected output should be group1 {1,3}, group2 {2,4}. If it is cannot be spitted into two group, just return “impossible”

- ajay.raj March 12, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answers/**

- ajay.raj March 10, 2017 in United States

* Definition for an interval.

* public class Interval {

* int start;

* int end;

* Interval() { start = 0; end = 0; }

* Interval(int s, int e) { start = s; end = e; }

* }

*/

Given a list of intervals, and a target interval

Our goal is to merge these intervals, so that the results of the merge can cover the target interval, return the minimum number of the original interval required for this merge

For example

IntervalList: [-1, 9] [1, 10] [0, 3] [9,10] [3, 14] [2, 9] [10, 16]

Target interval: [2, 15]

we find that there are several ways to cover [2,15], such as:

[-1, 9] + [9,10] + [10, 16] or [1, 10] + [10, 16].

We want to merge the least number of ways, so here should return 2| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersGiven a decendents of nodes, write an algorithm to find whether it is a tree or a graph?

- optimisticsuperman March 07, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswerCaeser;s Cipher is a very famous encryptiontechnique used in crptography.It is a type of substitution cipher in which each letter in the plaintext is replaced by letter some fixed number of positions down the alphabet.For example,with a shift of 3 ,D would be replaced bt G,E would become H,X would become A and so on.

- ruchitraj93 March 03, 2017 in India

Encryption of a letter x by a shift k can bedescribed mathematically as Ek(X)=(X+K)%26.

Given a plain text and it's corresponding ciphertext,output the minimum no negative value of shift that was used to encrypt the plaintext or else output -1 if it is no possible to obtain the given ciphertext from the given plaintext using caeser's cipher technique.

Input

The first line of the input contains Q,denoting the number of queries.

The next Q lines contain two strings s and t consisting of only uppercase letters

output::

For each test case,output a single non negative integer denoting the minimum value of shift that was used to encrypt the the plaintext or else print -1 if the answer does not exist.

Sample Input OUTPUT

2 3

ABC -1

DEF

AAA

PQR| Report Duplicate | Flag | PURGE

Persistent Systems SDE1 - 0of 0 votes

Answercount Number of balanced Binary Tree given Preorder Sequence length

- ajay.raj March 02, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersGiven an array arr and a number n, you have to find whether there exist a subset in arr whose sum is n. You have to print length of the subset.

- mohit February 17, 2017 in India

1. There exists only one subset like that

2. All number in arr are positive| Report Duplicate | Flag | PURGE

Amazon SDE1 Dynamic Programming - 1of 1 vote

AnswersFind largest sub-array?

- xyz February 16, 2017 in United States| Report Duplicate | Flag | PURGE

Huawei SDE1 Algorithm - 0of 0 votes

AnswersI have a file which has a number of 10 digit numerals and 10 digit alphanumeric characters. Write a UNIX basic command to print distinct 10 digit alphanumeric charters

- priyanka.mandal1691 February 08, 2017 in India

Sample Input

1234567890

1234567890

123456789X

0974385495

Expected O/P

123456789X| Report Duplicate | Flag | PURGE

Amazon SDE1 Unix - 0of 0 votes

AnswerDelete files of size more than 100mb in a folder which are older than 90 days.

- priyanka.mandal1691 February 08, 2017 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Unix - 0of 0 votes

AnswersGiven a comma separated file print the last but one column of every line.

- priyanka.mandal1691 February 08, 2017 in India

e.g:

a,b,c,d,e,f

1,2,3,4

w,x,y,z

output should be

e

3

y| Report Duplicate | Flag | PURGE

Amazon SDE1 Unix - 0of 0 votes

AnswersA binary tree and a number, say k are given. Print every path in the tree with sum of the nodes in the path as k.(A path can start from any node and end at any node, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree)

- SIVA R February 07, 2017 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Data Structures - 1of 1 vote

AnswersGiven an integer target and binary tree (not a binary search tree!) each of whose nodes contains an integer (which may be positive or negative), find the set of all subtrees whose sum equals the given target. The sum of a subtree is just the sum of the integers contained in its nodes. Note that the subtree does not have to contain all child nodes - it can be any set of connected nodes.

- Aloo February 03, 2017 in India| Report Duplicate | Flag | PURGE

SDE1 Data Structures - 1of 1 vote

AnswerYou are given an array A[] with n elements. You are given S[], E[] and H[] array with each M elements.

- Richa Tibrewal February 01, 2017 in India

Apply an operation such that all the elements from A[ S[i] ] and A[ E[i] ] will be less than H[i].

Example :

given array A[] = [2,4,8,6,7]

S[0] = 1

E[0] = 4

H[0] = 5

So, after doing an operation, the resulting array is A[] = [ 2,4,5,5,5]

Thus, u need to do the same thing for all i.

After doing this, find out the maximum element in the array.| Report Duplicate | Flag | PURGE

Directi SDE1 Algorithm - 0of 0 votes

AnswersPrint elements of a matrix in spiral form.

- yasharonline January 12, 2017 in United States for Azure| Report Duplicate | Flag | PURGE

Microsoft SDE1 Matrix - 0of 0 votes

AnswersIt was an over email interview:

- yasharonline January 11, 2017 in United States

Write a program that takes as input a sufficiently large text document (several are available online for testing; e.g. via Project Gutenberg), and produces as output (via stdout) an alphabetical listing of each unique word in the document (case insensitive and space separated, though be careful to consider hyphenated words), along with the lines from the input document that the word appears on. Each unique word (and the list of lines that it appears on) should be on a separate line in the output.

For example, taking the following text as input:

This is

some kind OF text it

Is an example of text

The following would be the output:

an 3

example 3

is 1 3

it 2

kind 2

of 2 3

some 2

text 2 3

this 1| Report Duplicate | Flag | PURGE

Apkudo SDE1 Sorting - -2of 2 votes

AnswersC++ Questions

- anony December 23, 2016 in United States| Report Duplicate | Flag | PURGE

Morgan Stanley SDE1 - -1of 3 votes

AnswersFind sum of n elements after kth smallest element in BST. Tree is very large, you are not allowed to traverse the tree.

- gvikram244 December 06, 2016 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersGiven a nxn matrix, with partially filled cells of numbers from 1..n and the rest with 0's. Fill the cells such each row and column has numbers 1 to n without any repetition.

- faizvf November 14, 2016 in United States

Eg:

[

[1, 2, 0],

[0, 1, 0],

[0, 0, 1]

]

[

[1, 2, 3],

[3, 1, 2],

[2, 3, 1]

]| Report Duplicate | Flag | PURGE

Yahoo SDE1 Algorithm - 1of 1 vote

AnswersGiven an NxN grid with an array of lamp coordinates. Each lamp provides illumination to every square on their x axis, every square on their y axis, and every square that lies in their diagonal (think of a Queen in chess). Given an array of query coordinates, determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on,…

- ad09 October 16, 2016 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswerFunction to print shortestpathsum between start and end node of given weighted undirected graph

- Anirudha October 13, 2016 in India

Comlite the function:

ShortestPathSum(graph g,start,end)

Node(1)----wieght--->node(2)

Node(2)--weight-->node(3)

Node(2)----W----node(4)

Node(3)-----w----->node(5)

Node(4)---w--->node(5)

suppose node(1) is stat node and node(5) is end node

Please write the complite function| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersYou are a string conscious guy. You categorise strings into 3 types: good, bad, mixed. If a string has 3 consecutive vowels or 5 consecutive consonants or both, it is bad. Else it is good. If a string has ‘?’, that can be replaced with any character. Thus, string ‘?aa’ can be bad if ‘?’ is vowel or good if consonant. Thus, it is mixed. Implement function which takes string s as input and returns good, bad or mixed

- novicedhunnu October 11, 2016 in India| Report Duplicate | Flag | PURGE

Adobe SDE1 Algorithm - 0of 0 votes

AnswersYou are a musician who plays different songs at different volumes. You have a particular difference that needs to be present for new song, but you don't care if it is more or less. You are given initial volume l, array of volume changes where arr[i] is volume change required after i-th song, max_vol h (min vol always 0), array size n. You need to find the max possible volume for the last song. But if at any point change is not possible, return -1. Format: n, arr[n], l, h. Ex: 3, 1 1 1, 0, 5. Ans: 3. Ex: 4, 9 1 5 4, 8, 15. Ans: -1. Ex: 3, 5 3 7, 5, 10. Ans: 10.

- novicedhunnu October 11, 2016 in India

Input explanation :

First number = size of array,

then next ‘n’ numbers of array.

Then ‘l’ means initial volume

Then ‘h’ means max volume.

Eg. 3, 1 1 1, 0, 5 means n = 3, arr = {1,1,1}, l = 0, h = 5,

Output explanation: initially you play music at vol 0, then for first arr element. Arr[0] inc. by 1,

Arr[1] inc. by 1, arr[2] inc by 1 total = 3| Report Duplicate | Flag | PURGE

Adobe SDE1 Algorithm - 0of 0 votes

AnswersImplement method:

`Lìst<Range> getRanges(Lìst<Shard> shards, Lìst<Key> keys)`

That returns list of ranges. Each range represents multiple keys aggregated over a shard:

n-keys —> 1-shard —> l-range

Method should return no more than 1 range per shard that spans all keys or their parts belonging to this shard.

Each of the ‘Range` , 'Shard’ and ‘Key’ classes have ‘end’ and ‘start’ fields of int type, where ‘start’ is inclusive and ‘end’ is exclusive.

Example:

- ermilanardeshana September 21, 2016 in United States`1—9, 12—59, 100—999 <— shards (input) 2—3, 6—8, 11—20, 200—220 <— keys (input) 2—8, 12—20, 200—220 <— ranges (output)`

| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm - 1of 1 vote

AnswersA list of words is given and a bigger string given how can we find whether the string is a permutation of the smaller strings.

- novicedhunnu September 15, 2016 in India

eg- s= badactorgoodacting dict[]={'actor','bad','act','good'] FALSE

eg- s= badactorgoodacting dict[]={'actor','bad','acting','good'] TRUE

The smaller words themselves don't need to be permuted. The question is whether we can find a ordering of the smaller strings such that if concatenated in that order it gives the larger string

One more constraint - some words from dict[] may also be left over unused| Report Duplicate | Flag | PURGE

Microsoft SDE1 Algorithm - 0of 0 votes

AnswersGiven the following inputs, return a list of rooms that are available and large enough:

- MM August 04, 2016 in United States

# of people

Start Time

End Time

You should return

total list of rooms

capacity of each rooms

availability| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersThe stepping number:

- abhishek.agar2 July 31, 2016 in India

A number is called as a stepping number if the adjacent digits are having a difference of 1. For eg. 123,121,9878 are all stepping numbers. While 890, 098,012 are not i.e. a number should not start with 0.

Also all 1-digit numbers are stepping numbers.

Find out how many stepping numbers exist with number of digits =N (input given)| Report Duplicate | Flag | PURGE

Toppr SDE1 Algorithm

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

Open Chat in New Window