SDE1 Interview Questions
- 0of 0 votes
AnswersGas station problem, give you a starting point A and End B. An array of oil prices at each gas station index represents the location of each gas station. MPG = V, find the minimum cost of gas from A to B
- ajay.raj November 25, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
Answersgiven a string, and integer k, check if this string contain all the binary string of length k
- ajay.raj November 24, 2017 in United States
For example, k is 2, then 00,10,01,11.
Followup 1, find a string that can contain all binary string of length k.
Followup 2, find a shortest string that can contain all binary string of length k.| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersExpression evolution
- ajay.raj November 24, 2017 in United States
expr :: = int | '(' op expr + ')'
op :: = '+' | '*'
Cite a few examples:
"3" -> 3
"(+ 1 2)" -> 3
"(+ 3 4 5)" -> 12
"(+7 (* 8 12) (* 2 (+ 9 4) 7) 3)" -> ...
Public int getValue(String s){
}| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answers
- ajay.raj November 20, 2017 in United StatesInsert a number into an array of sorted intervals. For example, [1,4], [6,8], after insert 5, return [1,8]. class Interval{ int start; int end; public Interval(int start, int end){ this.start = start; this.end = end; } } class Solution{ public List<Interval> insert(List<Interval> list, int val){ } }
| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answersgive a bunch of job dependency, such as A-> B, A -> C, B-> D, and so on, implement two interfaces.
- ajay.raj November 17, 2017 in United States
The first one is get_next_stage, which returns jobs in parallel for the next phase. The second is job_done, which tells you which job completed.| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answersdetermine whether a number is the sum of two squares, such as 17 = 16 +1
- ajay.raj November 14, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answers
- ajay.raj November 14, 2017 in United StatesGive a matrix, for example 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 Find if there is a rectangle in the matrix, all four corners are 1 For the example, there is only one rectangle, that is 1 0 1 0 1 0 1 0 1
| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answersclass DirectedGraphNode {
- ajay.raj November 14, 2017 in United States
int label;
List<DirectedGraphNode> neighbors;
DirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<>();
}
}
check if there is a cycle in a directed graph, if there is a cycle, remove all the cycles| Report Duplicate | Flag | PURGE
Facebook SDE1 - 1of 1 vote
AnswersYou are given a binary tree and a function shouldBeErased(node to check whether a node should be erased. Erase all nodes that should be erased in the binary tree and return the resulting forest in the form of an array of every root node.
- ajay.raj November 13, 2017 in United States
Follow up:
What if this is a Binary Search Tree? (In this case you are given a list of nodes that should be erased instead of the function.) Does it make the problem simpler or more complicated or just the same?| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answersgiven a string and a segmentation length k
- ajay.raj November 12, 2017 in United States
For example:
"This is a good day" k = 10
Cut into:
"This (1/4)"
"is a (2/4)"
"good (3/4)"
"day (4/4)"
Each line followed by a suffix in the form of (i/n) has 10 chars including space (except for the last line), return the minimum cut required, for the example, just return 4.| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answerstrie search, Search Return all words that match the wildcard *
- ajay.raj November 12, 2017 in United States
such as
add ("car")
add ("caw")
add ("cauw")
search ("c*w") returns "caw" and "cauw".| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersThere are n bus lines, known bus stops by bus, the bus is bi-direction, ask from station A to station B at least a few transfers.
- ajay.raj November 10, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answers
- ajay.raj November 09, 2017 in United Statesgiven a binary array, you can flip 0 -> 1 or 1 -> 0 to make all the 1 are in the left part and all the 0 to the right part, return the minimun flip required example 1 1011000 -> 1111000 only need one flip 0 -> 1 example 2 00001 -> 10000 require 2 flips public int findMiniFlip(int[] nums) { } }
| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answersthe longest unique value path in a graph
- ajay.raj November 06, 2017 in United States
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public int findLongestUniqueValuePath(List<UndirectedGraphNode> node) {
}
}| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersGiven a 2d grid map of '1's (land) and '0's (water), find the perimeter of each island. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
- ajay.raj November 05, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersTo determine if two graphs have isomorphism or not
- ajay.raj November 05, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersGive an array A, find the (i, j) pairs that satisfy the condition.
- ajay.raj November 05, 2017 in United States
Condition 1: A [j] = A [i] + 1, Condition 2: j - i is as large as possible
Followup condition 1 is changed to A [j]> A [i]| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersGiven an array of length n + 1, containing elements 1 through n and a space,
- ajay.raj November 04, 2017 in United States
Requires the use of a given swap (index i, index j) function to sort the array,
You can only swap the gap and a number, in the end, put the gap at the end| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answersfind a shortest string to cover all of a list of string,
- ajay.raj November 04, 2017 in United States
For example, [aab, aabb, bc], should return aabbc,
because aab, aabb, bc are all the substring of aabbc| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answersgiven 2 list of interval representing users online offline timestamp e.g (already sorted), find all intervals that both of users are online.
- ajay.raj November 03, 2017 in United States
e.g A= [(3, 5), (7, 11)] B=[(2, 4), (9, 10)] --> [(3, 4), (9, 10)].| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswerDesign a SparseVector class that implements
- ajay.raj November 03, 2017 in United States
Vector interface, which contains 4 methods: get(int index),
increment(int index, int delta), numNonZeros(), and dotProduct(Vector other)| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
AnswersGiven an array of integers and k, find the difference between the number of the strictly increasing number of subarrays (of size more than one) and the number of the strictly decreasing subarray in the window of size k. your method should be time and space efficent
- ajay.raj November 03, 2017 in United States
example
int[] nums = {188930, 194123, 201345, 154243, 154243};
int k = 3;
Output
3, 0, -1
Explanation
For the first window of [188930, 194123, 201345], there are 3 increasing subranges ([188930, 194123, 201345], [188930, 194123], and [194123, 201345]) and 0 decreasing, so the answer is 3. For the second window of [194123, 201345, 154243], there is 1 increasing subrange and 1 decreasing, so the answer is 0. For the third window of [201345, 154243, 154243], there is 1 decreasing subrange and 0 increasing, so the answer is -1.
public int[] getdiff(int[] nums, int l){
}| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answers
- ajay.raj November 01, 2017 in United Statesgive an enum, where each element has a parent-children relationship, and children's expression is the value of parent append an index, such as enum vehicle { car = 1 toyota = 11 camry = 111 corolla = 112 honda = 12 truck = 2 GMC = 21 } Ask a value, return to his parent, such as GMC = 21, return to the truck
| Report Duplicate | Flag | PURGE
Google SDE1 - 1of 1 vote
AnswersGiven a list points on a 2d plane, find
- ajay.raj November 01, 2017 in United States
largest rectangular area that can be formed
for the rectangle only considers those parallel to x and y| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 0 votes
Answers
- ajay.raj October 31, 2017 in United StatesThere is an unordered interval stream, write a method, returns the total length that all intervals cover by now class Interval{ int start; int end; } public List<Integer> countCoverLength(Iterator<Interval> stream){ }
| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answers‘.’Matches any single character,' * 'Matches any sequence of characters (including the empty sequence).
- ajay.raj October 28, 2017 in United States
There are two input, one is string pattern, and the other is dictionary like dict = ["cat", "cats", "and", "sand", "dog"].
return a boolean: whether to find a dictionary in the pattern match the word
eg: dict = ["cat", "cats", "and", "sand", "dog"].
pattern = "* t", -> true (can match cat)
pattern = ".a *" -> true (can match cat, cats, can also match sand, because * can also express empty sequence)| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersHow would you store and retrieve values in Memcache if the values are larger than the individual value size allowed by Memcache?
- ajay.raj October 25, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersFind all words [A-Z] in a dictionary (about 1M words) that are made of a subset (in any order) of the chars in the input parameter [A-Z].
- ajay.raj October 19, 2017 in United States
ex: input "ACRAT" (10 to 20 chars, up to 30 worst case)
matching words: "A", "CAR", "ACA", "ART", "RAC".
non-matching words: "BAR", "AAA"
follow up : the input is a list of words. Return a list of words that each
list is formed by exactly the characters in the input list.
For example: two lists {“DEBIT”, “CARD”} and{“BAD”, “CREDIT”}
are formed by the same exact group of characters.| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersGiven a string separated by a space like "123456 abc+efg" determine
- ajay.raj October 18, 2017 in United States
the solution by mapping integers to letters like a:1, b:2, c:3, d:4, e:5, f:6.
The only operations allowed were + or -. So the calculated solution
that made the tests pass was 123+456 = 579.| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersHow many subsets of a given array sum to zero?
- ajay.raj October 18, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1