SDE1 Interview Questions
- 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 - 0of 0 votes
AnswersGiven numbers 1 through 52, take 5 unique numbers and determine
- ajay.raj October 18, 2017 in United States
if the number 42 can be made using any combination of addition (+),
subtraction (-), multiplication (*), and division (/) on those 5 numbers| Report Duplicate | Flag | PURGE
Facebook SDE1 - 1of 1 vote
Answers/* Intersection of two sorted interval lists, A=[(1,2), (5,7)..]
B=[(2,6)...] return [(5,6)..] */
- ajay.raj October 09, 2017 in United Statesimport java.util.*; class Interval{ int start; int end; public Interval(int start, int end){ this.start = start; this.end = end; } } class Solution { public List<Interval> Intersection(Interval[] i1, Interval[] i2) {}
| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answers* Given a string on length N. You can swap only the adjacent elements
- ajay.raj October 02, 2017 in United States
and each element can be swapped atmost once.
Find the no of permutations of the string that can be generated after
performing the swaps as mentioned.
Ex –
string – “12345”
Ans = 8
Explanations- (All the permutations)
12345
21345
13245
12435
12354
21435
13254
21354| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersGiven an array of n positive integers, find the number of subarrays
- ajay.raj October 02, 2017 in United States
such that product of the elements of those subarrays are less than k.
For eg. Arr= {2, 3, 6} k=10
No of such subarrays= 4| Report Duplicate | Flag | PURGE
Facebook SDE1 - 1of 1 vote
AnswersPrint the levels of a binary tree in reverse order using stack and recursion
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ]
public List<List<Integer>> levelOrderBottom(TreeNode root) {
- ajay.raj October 02, 2017 in United States
}| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answersgiven an array, find whether there exists 3 elements a,b,c in it such that a+b=c using efficient method.
- ajay.raj October 02, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersYou are provided a BST, which is corrupted. One of the nodes in it has 2 parents.
- ajay.raj October 02, 2017 in United States
Let’s say those are parent 1 and parent 2. It is ensured that none
of these parents will be the ancestor of the other. Identify the node,
and remove the link of the wrong parent.| Report Duplicate | Flag | PURGE
Facebook SDE1 - 1of 1 vote
AnswersGiven an adjacency matrix of a directed graph, find the number of cycles in the graph
- ajay.raj October 02, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answers
- ajay.raj September 19, 2017 in United StatesGiven an array of n * m matrix, and a moving matrix window (size k * k), move the window from top left to bottom right at each iteration, find the median number inside the window at each moving Can you do it better than brutal force method? void getMedian(int[][] matrix, int k){ print median } For matrix [ [1, 5, 3], [3, 2, 1], [4, 1, 9], ] The moving window size k = 2. At first the window is at the start of the array like this [ [|1, 5|, 3], [|3, 2|, 1], [4, 1, 9], ] ,get the median (2 + 3) / 2 = 2.5; then the window move one step forward. [ [1, |5, 3|], [3, |2, 1|], [4, 1, 9], ] ,get the median (2 + 3) / 2 = 2.5 then the window move one step forward again. [ [1, 5, 3], [|3, 2|, 1], [|4, 1|, 9], ] ,get the median (2 + 3) / 2 = 2.5 then the window move one step forward again. [ [1, 5, 3], [3, |2, 1|], [4, |1, 9|], ] ,get the median (1 + 2) / 2 = 1.5
| Report Duplicate | Flag | PURGE
Facebook SDE1 - 3of 3 votes
AnswersWe are planning an orienteering game.
- ajay.raj September 19, 2017 in United States
The aim of this game is to arrive at the goal (G) from the start (S) with the shortest distance.
However, the players have to pass all the checkpoints (@) on the map.
An orienteering map is to be given in the following format.
########
#@....G#
##.##@##
#..@..S#
#@.....#
########
In this problem, an orienteering map is to be given.
Calculate the minimum distance from the start to the goal with passing all the checkpoints.
Specification
* A map consists of 5 characters as following.
You can assume that the map does not contain any invalid characters and
the map has exactly one start symbol 'S' and exactly one goal symbol 'G'.
* 'S' means the orienteering start.
* 'G' means the orienteering goal.
* '@' means an orienteering checkpoint.
* '.' means an opened-block that players can pass.
* '#' means a closed-block that players cannot pass.
* It is allowed to move only by one step vertically or horizontally (up, down, left, or right) to the
next block.
Other types of movements, such as moving diagonally (left up, right up, left down and right down)
and skipping one or more blocks, are NOT permitted.
* You MUST NOT get out of the map.
* Distance is to be defined as the number of movements to the different blocks.
* You CAN pass opened-blocks, checkpoints, the start, and the goal more than once if necessary.
* You can assume that parameters satisfy following conditions.
* 1 <= width <= 100
* 1 <= height <= 100
* The maximum number of checkpoints is 18.| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answersconvert prefix to postfix expression
- ajay.raj September 16, 2017 in United States
public String convert2postfix(String prefix){
}| Report Duplicate | Flag | PURGE
Facebook SDE1 - 1of 1 vote
AnswersGiven an array of integers where each element points to the index of the next element how would you detect if there is a cycle in this array
- ajay.raj September 12, 2017 in United States
can you do it without extra space| Report Duplicate | Flag | PURGE
Facebook SDE1 - 2of 2 votes
AnswersThere is a maze of size m*n. You are sitting at (0,0). Another person is sitting in another cell. There are some cheeses placed in different cells with a cell value of 2. Some cells are blocked with a value of 1, thus you cannot pass it, while some cells are filled with 0, thus you can pass it.
- ajay.raj September 08, 2017 in United States
You can move to left, right, up, down at each step. You have to collect all the pieces of cheese and then reach to Another Person cell. You need to return the minimum no. of steps required to do so.
Public int getShortest(int[][] maze, int[] anotherPersonCell){
}| Report Duplicate | Flag | PURGE
Facebook SDE1 - 2of 2 votes
AnswersIn Docker, building an image has dependencies. An image can only be built once
- ajay.raj August 27, 2017 in United States
its dependency is built (If the dependency is from outside, then the image can
be built immediately).
Sometimes, engineers make mistakes by forming a cycle dependency of local images.
In this case, ignore the cycle and all the images depending on this cycle.
Input is vector of pair of images (image, its dependency).
Output the order of images to be built in order.
##Example:
```
Example 1:
{{"master", "ubuntu"}, {"numpy", "master"}, {"tensorflow", "numpy"}}
Output: master, numpy, tensorflow
Example 2:
{{"python", "numpy"}, {"numpy", "python"}, {"tensorflow", "ubuntu"}}
Output: tensorflow
Example 3:
{{"b", "c"}, {"c", "d"}, {"a", "b"}, {"d", "e"}, {"e","c"}, {"f", "g"}}
Ouput: f| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersThere are n servers, reboot time is S0, S1..Sn-1
- ajay.raj August 27, 2017 in United States
There are m tasks, the completion of the time required are T0, T1… Tm-1
How to assign tasks to each server makes the total time the shortest| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersGiven a binary tree, how do you serialize and deserialize. Remember it is not BST it is a general binary tree which can also have duplicate elements.
- agrawal.arpit35 August 22, 2017 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersFind the largest repeating sub-string in a string.
- Constantine August 22, 2017 in United States
ex: banana
ans is: ana| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersInput: expression_tree | sequence_of_operations
- ajay.raj August 20, 2017 in United States
The input is a single line of text with a expression tree and a sequence of operations separated by | character and ended by a \n newline character. Spaces are allowed in the input but should be ignored.
The expression tree is a sequence of 1-character variables A-Z and with sub expression trees formed by parenthesis (expression_tree). Examples: AB, A(B C D), (AB)C((DE)F)
The sequence of operations is a string of with characters R (reverse) or S (simplify)
Reverse means reverse the order of everything in expression tree. Applying reverse twice in a row cancels out. Example: (AB)C((DE)F) | R should print (F(ED))C(BA)
Simplify means remove the parentheses around the very first element in the expression tree and each of its subexpression trees. Applying S multiple times should have same result as applying S once. Example: (AB)C((DE)F) | S should print ABC(DEF)
String process(String input){
}| Report Duplicate | Flag | PURGE
Twitter SDE1 - 0of 0 votes
AnswersConvert Json string to Map
- ajay.raj August 02, 2017 in United States
public Map jsonToMap(String t) {
}| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersDesign Distributed Web Crawler.
- hprem991 August 01, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersWhat if server is slow, how to solve
- ajay.raj August 01, 2017 in United States
What if one server is down| Report Duplicate | Flag | PURGE
Facebook SDE1 - 1of 1 vote
AnswersArray has N integers,range[0...N-1]。Set S[k], 0 <= K < N as S[K] = {A[K], A[A[K]], A[A[A[K]]],....},
- ajay.raj July 29, 2017 in United States
write a function returns the size of the largest set S[K] for this array. return 0 if empty.
ex:
A = [5, 4, 0, 3, 1, 6, 2]
return 4 because S[2] equals {0, 5, 6, 2} 4 elements| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersGiven an array of integers and a target number, determine if an arithmetic expression using these integers can be evaluated to the target number, you are allowed to use '+', '-', '*', '/'. Follow-up: when evaluating the expression, take operand precedence into account,
- ajay.raj July 27, 2017 in United States
public boolean getTarget(int[] nums, int target){
}
exponentia is ok| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answersfind the Closest leaf to a given node in Binary Tree
- ajay.raj July 26, 2017 in United States
can you do it in o(n) time
public TreeNode findCloestLeafNode(TreeNode root, TreeNode target){}
no parent pointer| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answervalidate IP in string format and return the uint32 format
- ajay.raj July 26, 2017 in United States
‘1.2.3.4’ -> 0x01020304| Report Duplicate | Flag | PURGE
Facebook SDE1