SDE1 Interview Questions
- 0of 0 votes
Answershow does java implement priority queue?
- ajay.raj April 25, 2017 in United States
i answered min heap, the interviewer seemed it was not right| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
Answer
- ajay.raj April 23, 2017 in United Statesclass Log{ String fun_name; String enterOrExit;// enter or exit int time; public Log(String fun_name, String enterOrExit, int time){ this. fun_name = fun_name; this. enterOrExit = enterOrExit; this.time = time; } } public void printInclusiveAndExclusiveTime (List<Log> logs){ } Log for some functions, calculate the inclusive time and exclusive time for each function E.g Fun_name enter / exit time F1 enter 1 F2 enter 2 F2 exit 3 F1 exit 4 F1: inclusive time = 4-1 = 3, exclusive time = 3-1 = 2 F2: inclusive time = 3-2 = 1, exclusive time = 1
| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersI have a series of strings sort {"A","B","C","D"....}
- Anusri April 22, 2017 in United States for Java
Sort them and display them in 4 columns.Instead of displaying horizontally they should be display vertical if the string size is greater than 4.
Important:null should be in last row alone
eg
A C D E
B
If string size is less than 4
A B C D
Also,the program should be production ready and reusable,readjust the values upon deletion.| Report Duplicate | Flag | PURGE
SDE1 technical - 0of 0 votes
Answerstokenize string, "" and [] are token flags, such as
- ajay.raj April 17, 2017 in United States
mytable "foo" [bar] "" [[[[]]].
"" Turned into ",]] turned into], [[not escaped
The results of the example given above:
mytable
foo
bar "
[[]
public List<String> tokenizestring(String s){
}| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersF (n) = 3n + 1 (if n is odd) or n / 2 (if n is even)
- ajay.raj April 16, 2017 in United States
Collapse sequence refers to each number according to this formula
until the sequence becomes equal to 1,
Find the number (which is not greater than 10000), which will have the longest Collapse sequence.
public int getlongestCollapsesequence(int n){
}| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answerswrite a function to generate a random 4 digit unique even number, the four digits cannot be the same, 1234 is valid, but 1134 is not valid
- ajay.raj April 13, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersYou've escaped Commander Lambda's exploding space station along with numerous escape pods full of bunnies. But - oh no! - one of the escape pods has flown into a nearby nebula, causing you to lose track of it. You start monitoring the nebula, but unfortunately, just a moment too late to find where the pod went. However, you do find that the gas of the steadily expanding nebula follows a simple pattern, meaning that you should be able to determine the previous state of the gas and narrow down where you might find the pod.
- Anon April 11, 2017 in United States
From the scans of the nebula, you have found that it is very flat and distributed in distinct patches, so you can model it as a 2D grid. You find that the current existence of gas in a cell of the grid is determined exactly by its 4 nearby cells, specifically, (1) that cell, (2) the cell below it, (3) the cell to the right of it, and (4) the cell below and to the right of it. If, in the current state, exactly 1 of those 4 cells in the 2x2 block has gas, then it will also have gas in the next state. Otherwise, the cell will be empty in the next state.
For example, let's say the previous state of the grid (p) was:
.O..
..O.
...O
O...
To see how this grid will change to become the current grid (c) over the next time step, consider the 2x2 blocks of cells around each cell. Of the 2x2 block of [p[0][0], p[0][1], p[1][0], p[1][1]], only p[0][1] has gas in it, which means this 2x2 block would become cell c[0][0] with gas in the next time step:
.O -> O
..
Likewise, in the next 2x2 block to the right consisting of [p[0][1], p[0][2], p[1][1], p[1][2]], two of the containing cells have gas, so in the next state of the grid, c[0][1] will NOT have gas:
O. -> .
.O
Following this pattern to its conclusion, from the previous state p, the current state of the grid c will be:
O.O
.O.
O.O
Note that the resulting output will have 1 fewer row and column, since the bottom and rightmost cells do not have a cell below and to the right of them, respectively.
Write a function answer(g) where g is an array of array of bools saying whether there is gas in each cell (the current scan of the nebula), and return an int with the number of possible previous states that could have resulted in that grid after 1 time step. For instance, if the function were given the current state c above, it would deduce that the possible previous states were p (given above) as well as its horizontal and vertical reflections, and would return 4. The width of the grid will be between 3 and 50 inclusive, and the height of the grid will be between 3 and 9 inclusive. The answer will always be less than one billion (10^9).| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersFor a string chemical formula like “C6H2(NO2)3CH3”, and output a map with key as element and value as its count.
- ajay.raj April 11, 2017 in United States
element can have two chars, for example Fe2(SO4)3
public HashMap<Character, Integer> getCount(String chemicals){
}| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersA "derangement" of a sequence is a permutation where no element appears in its original position. For example ECABD is a derangement of ABCDE, given a string, may contain duplicate char, please out put all the derangement
- ajay.raj April 10, 2017 in United States
public List<char[]> getDerangement(char[]){}| Report Duplicate | Flag | PURGE
Facebook SDE1 - -2of 2 votes
Answersthree sum with duplicate, pirnt all indexes, for example:
- ajay.raj April 08, 2017 in United States
0 2 -2 -2
(0)(1)(2)(3)
print (0, 1, 2) (0, 1, 3)
can you do it use n^2 (or less) time complexity with as less space as possible?
public List<List<Integer>> threeSum(int[] nums) {}| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 2 votes
AnswersGiven an array of task and k wait time for which a repeated task
- ajay.raj April 06, 2017 in United States
needs to wait k time to execute again. please rearrange the task
sequences to minimize the total time to finish all the tasks.
Example
Tasks = 111222, k = 2,
One possible task sequence is
12_12_12,
another possible task sequence is 21_21_21
thus you shoud return 8
public int getMiniTime(int[] nums, int k){
}
follow up, output one of the sequence 12_12_12, or 21_21_21| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersGiven a number of tasks (T) and servers (S), find out if the tasks can be accommodated on the servers. Each Task has a number of Units and each server has a number of Slots on which Units can run.
- ajay.raj April 04, 2017 in United States
The only condition is that two Units of the same Task "cannot" run on the same Server.
Servers
S[0] = "SS1", "SS2", "SS3", SS4 //Slots // 4 -> 3 -> 2 -> 1
S[1] = "SS1", "SS2" // 2 -> 1 -> 0 -> false
S[2] = "SS1", "SS2", SS3, SS4, SS5 // 5 -> 4 -> 3 -> 2
S[3] = "SS1", "SS2", SS3, SS4, SS5 // 5 -> 4 -> 3 -> 2
Example:
S[0] = 4
S[1] = 3
S[2] = 5
S[3] = 5
...
Tasks
T[0] = U0, U1, U2, U3 //Tasks
T[1] = U0, U1
T[2] = U0, U1, U2
...
Example:
T[0] = 4
T[1] = 2
T[2] = 3
implement
boolean boolean CanRunTasks(S[], T[]){
}| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answersclass UndirectedGraphNode { int label; List<UndirectedGraphNode> neighbors; UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<>(); } } public boolean isBipartite(List<UndirectedGraphNode> nodes){ }
use DFS algorithm to check the bipartite-ness of a graph
- ajay.raj April 04, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersDelhi Route Traffic Optimizer
- raghunitb March 30, 2017 in India for Workflow
Traffic congestion is an annoying issue in Delhi, the capital of India. Every morning thousands of people drivea residential area to the International Technology Park (ITPL). There are various routes one can take to reach ITPL and each route takes its own time making some routes faster than the others. People obviously take faster routes which causes congestion on those roads too. Congestion results into increased travel time, air pollution and wastage of fuel. As a Traffic commissioner of Delhi, you are asked to optimize the traffic by putting toll to various roads so that resultant cost of every route (driving time cost and toll cost) ends up the same. This has to be done in such a way that any driver pays toll only once no matter which route he/she takes.roads have one-way traffic and there is no cycle in any of the routes. You need to create a toll plan for a given road layout.
The toll plan must adhere to following rules:
1. Toll should be levied in such a way that perceived cost (base road cost and toll cost) remains same forroads.
2. The tolls should be levied such that the total cost for each route is minimized.
3. A route cannot have more than one toll.
4. In case of multiple solutions for a route, add toll to a road that is closer to destination.
In some use cases, it might be impossible to impose tolls that satisfy the above conditions.
http://qa.geeksforgeeks.org/11340/delhi-route-traffic-optimizer| Report Duplicate | Flag | PURGE
Groupon SDE1 Algorithm - 0of 0 votes
AnswersGive a Runable interface, and then give a scheduler post method. This post is parallel, for example:
- ajay.raj March 23, 2017 in United States
Method header:
public void post (Runable r) {};
Call 5 times:
Scheduler.post (r1);
Scheduler.post (r2);
Scheduler.post (r3);
Scheduler.post (r4);
Scheduler.post (r5);
The five runables are allocated to five threads and run at the same time. And then asked: how to achieve these five tasks one by one run,| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersThere are two integer array arrayA and arrayB in the same size and two integer countA and countB. If arrayA[i] > arrayB[i], then we increase countA by 1, if arrayB[i]>arrayA[i], then we increase countB by 1. We will do nothing otherwise. Now you are given arrayA and arrayB, write a function to shuffle arrayA and so you can get countA > countB. Assume the input array are always valid, not empty and the input is guaranteed to have answer.
- gzyeli123 March 20, 2017 in United States
For example:
arrayA = [12, 24, 8, 32]
arrayB = [13, 25, 32, 11]
After shuffle:
arrayA = [24, 32, 8, 12]
arrayB = [13, 25, 32, 11]| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm - 4of 4 votes
Answersthere is a bunch of tasks, each have different time to complete, task is independent, and then there are some workers,
- ajay.raj March 18, 2017 in United States
How to allocate tasks to these workers to minimize the total time to complete all the task. The tasks can be randomly picked from the task list.
Example
Task: 2,2,3,7, 1
Worker: 2.
Return 8, because the first worker can work on the first three tasks : 2 + 2 + 3 = 7, and the second worker can work on the last two tasks : 7 + 1 = 8, so the total time to finish all the task is 8.
public int getMini(int[] tasks, int k)| Report Duplicate | Flag | PURGE
Facebook SDE1 - 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 - 1of 1 vote
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