## SDE1 Interview Questions

- 0of 0 votes
Given a BST of memory sizes. Find best fit for a memory block of size M.

- 0of 0 votes
Given 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).

- 0of 0 votes
For Amazon SDE-1 On Campus Interview, what are the topics I should study in Database Management ?

Just don't name the topics. Please elaborate too.

- 0of 0 votes
For Amazon SDE-1 On Campus Interview, what are the topics I should study in Computer Networking ?

Just don't name the topics. Please elaborate too.

- 0of 0 votes
You have been given a task of reordering some data from a log file. Every line in the log file is a space delimited list of strings and all lines begin with an identifier that is alphanumeric. After the identifier, a line will consist of either a list of words using only English letters or only a list of integers. There will be no lines that consist of only an identifier.

Your task is to reorder the data from the log file such that all the lines with words are at the top in the log file. in lexicographical order. Words are ordered lexicographically ignoring the identifier except in the case of ties. In the case of ties (if there are two lines that are identical except for the identifier), the identifier is used to order lexicographically. Alphanumerics should be sorted in ASCII order (numbers come before letters). The identifiers must still be part of the lines in the output Strings. Lines with integers do not need to be sorted relative to other lines with integers.

Write an algorithm to reorder the data in the log file.

The input to the function/method consists of two arguments -

logFileSize: an integer representing the number of lines in the log file,

logLines: a list of strings representing the log file.

Output:

Return a list of strings representing the reordered log file data.

Note:

Identifier consists of only English letters and numbers. The lines with words are not required to match case and the sort needs to be case insensitive.

Example:

Input:

logFileSize = 5

logLines =

[al 9 2 3 1]

[g1 Act car]

[zo4 4 7]

[abl off KEY dog]

[a8 act zoo]

Output:

[gl Act car]

[a8 act zoo]

[ab1 off KEY dog]

[al 9 2 3 1]

[zo4 4 7]

Explanation:

Second, fourth. and fifth lines are the lines with words. According to the lexicographical order, the second line will be reordered first in the log file, then fifth, and the fourth comes in the log file. Next, the lines with numbers come in the order in which these lines were in the input.

- 0of 0 votes
Reorder Data in log file

You have been given a task of reordering some data from a log file. Every line in the log file is a space delimited list of strings and all lines begin with an identifier that is alphanumeric. After the identifier, a line will consist of either a list of words using only English letters or only a list of integers. There will be no lines that consist of only an identifier.

Your task is to reorder the data from the log file such that all the lines with words are at the top in the log file. in lexicographical order. Words are ordered lexicographically ignoring the identifier except in the case of ties. In the case of ties (if there are two lines that are identical except for the identifier), the identifier is used to order lexicographically. Alphanumerics should be sorted in ASCII order (numbers come before letters). The identifiers must still be part of the lines in the output Strings. Lines with integers do not need to be sorted relative to other lines with integers.

Write an algorithm to reorder the data in the log file.

The input to the function/method consists of two arguments -

logFileSize: an integer representing the number of lines in the log file,

logLines: a list of strings representing the log file.

Output:

Return a list of strings representing the reordered log file data.

Note:

Identifier consists of only English letters and numbers. The lines with words are not required to match case and the sort needs to be case insensitive.

Example:

Input:

logFileSize = 5

logLines =

[al 9 2 3 1]

[g1 Act car]

[zo4 4 7]

[abl off KEY dog]

[a8 act zoo]

Output:

[gl Act car]

[a8 act zoo]

[ab1 off KEY dog]

[al 9 2 3 1]

[zo4 4 7]

Explanation:

Second, fourth. and fifth lines are the lines with words. According to the lexicographical order, the second line will be reordered first in the log file, then fifth, and the fourth comes in the log file. Next, the lines with numbers come in the order in which these lines were in the input.

- 0of 0 votes
Most Frequently used words (after excluding common words)

Amazon is partnering with the linguistics department at a local university to analyze important works of English literature and identify patterns in word usage across different eras. To ensure a cleaner output. the linguistics department has provided a list of commonly used words (e.g., "an", "the". etc.) to exclude from the analysis. In the context of this search, a word is an alphabetic sequence of characters having no whitespace or punctuation.

Write an algorithm to find the most frequently used word in the text excluding the commonly used words.

Input:

The input to the function/method consists of two arguments -

literatureText: a string representing the block of text,

wordsToExclude: a list of strings representing the commonly used words to be excluded while analyzing the word frequency.

Output:

Return a list of strings representing the most frequently used word in the text or in case of a tie, all of the most frequently used words in the text.

Note:

Words that have a different case are counted as the same word. The order of words does not matter in the output list. All words in the 'wordsToExclude' list are unique. Punctuation should be treated as white space.

Example

Input:

literature Text = "Jack and Jill went to the market to buy bread and cheese. Cheese is Jack's and Jill's favorite food."

wordsToExclude = ["and", "he", "the", "to", "is". "Jack", "Jill"]

Output: ["cheese", "s"]

Explanation: The word `and" has a maximum of three frequency but this word should be excluded while analyzing the word frequency. The words "Jack'. 'Jill", "s", "to" and "cheese" have the next maximum frequency(two) in the given text but the words "Jack", "to" and "Jill' should be excluded as these are commonly used words which you are not interested to include.

So the output is ["cheese", `s"] or ["s", "cheese"] as the order of words does not matter.

- 0of 0 votes
Given k, and a binary string, determine if this contains all permutations of length k.

For example, 11001 contains all possible binary sequences with k=2 (00,01,10,11)

- 0of 0 votes
You 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.)

eg.

Input: aabbab

Output: valid

Input: abbaab

Output: Invalid

I could not come up with a algorithm less than O(N*N)

- 0of 0 votes
Given a multiple tree, and multiple nodes that need to be deleted,

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.

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

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.

- 1of 1 vote
Let’s say you have two input arrays with sorted elements. Find the union.

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

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

Union = {2, 9, 10, 14, 19, 40, 51}

- 0of 0 votes
A 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.

- 0of 0 votes
To push dominoes, find out how many dominoes are standing in the end

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

- 0of 0 votes
The question is that there are a lot of vm, what is the total vm consumption max. For example, (2,4,8), (3,5,3) this input,

This means that 2 to 4 seconds have a memory usage of 8 and 3 to 5 seconds of 3, so the answer is 11 at 3 seconds.

Return 11 to it. Note that (1,2,3) and (2,3,4) such that the middle 3+4=7 is good.

Follow up is usage is not constant, such as (1,2,1,2) the first second usage is 1,

The second second is 2, the linear increase, the highest is how much.

- 0of 0 votes
Given as list of movies in a csv file, extract the movie name and genre and be able to return a query based on the years and the genre.

Basically, Parsing a CSV input file and build an indexed data storage to allow search the data in time manner.

- 0of 0 votes
Given a list of tasks each with memory requirements and time, only one machine has K memory.

Do not consider the context switch, page swap, virtual memory, (for example, the machine has only 20mb memory, a task that requires 25MB of the task can only wait until there is enough memory to run it.) The running task cannot be suspended.

Ask how long it takes to complete all these tasks. . .

- 1of 1 vote
How many squares are inside a m*n rectangle where some grids in the rectangle were grey and the gray grid could not appear in the small squares.

- 1of 1 vote
Given an int array, check if all the numbers can be divided into 5 consecutive numbers.

Eg: [1,2,2,3,3,4,4,5,5,6] Yes: (1,2,3,4,5) (2,3,4,5,6)

Followup: ask if you know that all the numbers are between 1 and 13,

what's a good optimization.

- 1of 1 vote
You have two matrixs, how to move the first matrix

(move up, down, left, and right) so that the two matrix in the two matrixs match most.`eg: matrix 1: matrix 2: 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0`

Then, after taking matrix1 (1 left shift + 1 down),

the number of 1 in the match with matrix2 is 3

- 0of 0 votes
how to check if two graphs are structurally identical

class UndirectedGraphNode {

List<UndirectedGraphNode> neighbors;

UndirectedGraphNode() {

neighbors = new ArrayList<>();

}

}

- 1of 1 vote
convert a Sorted array to complete BST

- 0of 0 votes
Give a connected graph, no cycle,

Find the node where the average distance from all other nodes is the smallest

- 0of 0 votes
Input: an int array without sorting, then do a binary search on it, and find the number of digits that cannot be found by binary search.

- 0of 0 votes
<key = "a"; val = "3"; depend_list = null;/>; <key = "b"; val = "a * a";

Depend_list = {a};/>; <key = "c"; val = "a * b"; depend_list = {a,b};/>;

Lets output a map<key, value>,a -> 3, b -> 9, c -> 27

Follow-up questions: Make a statistic for all keys and corresponding map entries with the same value.

- 0of 0 votes
Given an array, find an x such that all numbers less than x are equal to themselves. Numbers greater than it are equal to x, and all numbers add up to a target

For example, [1 3 5 7 9] target=24, answer is8. Because when x=8, the array has only 9>8, so 1+3+5+7+8=24 is the closest to the target.

- 0of 0 votes
Give an N-length array with only 0 and 1 inside

Requires to find the minimum number of conversions needed to convert the array to 0 before all 1.

The conversion is to change a 0 to 1 or a 1 to 0,

And the number of 0 and 1 in the converted array can be arbitrary.

Just find the minimum conversion step

- 0of 0 votes
Given list of schedules for different flights in a month, determine maximum number of flights that can be in the air anytime in that month.

Input : list of schedules for flights.- spread over a month.

output: a number - maximum flights that can be in the air

Assumptions: 1. All the given times are in a specific timezone( like GMT).

2. Given Schedules can be any time in the month

- 0of 0 votes
To an array and K, each element in the array can only move K positions to the left at most, no limit to the right, try to sort the array under the limit of K

a = [5, 2, 4, 3, 1], k = 2

Return [2, 3, 1, 4, 5]

- 0of 0 votes
Given a function rand32() (random number range 0-2**32-1) that randomly generates a 32-bit int, design a new random function:

Randn(n) generates a random distributed random number (0 - 2**n-1)

Rand3n(n) generates (0 - 3**n-1) the uniformly distributed random number