majia168
 0of 0 votes
Answer
 majia168 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
Facebook SDE1  1of 1 vote
AnswerWe are planning an orienteering game.
 majia168 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 openedblock that players can pass.
* '#' means a closedblock 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 openedblocks, 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
Facebook SDE1  0of 0 votes
Answersconvert prefix to postfix expression
 majia168 in United States
public String convert2postfix(String prefix){
} Report Duplicate  Flag
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
 majia168 in United States
can you do it without extra space Report Duplicate  Flag
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.
 majia168 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
Facebook SDE1  1of 1 vote
AnswersWe start with a list of Integers. We can remove a group of integers from the list if the all but one equals the remaining number. This removal operation can be performed in the remaining number of list until no more operations can be performed.
 majia168 in United States
Write a function which can accept an array of integers, and return the minimal number of remaining integers from performing this operation.
Example [1, 3, 5, 6] > remove 1, 5, 6 , because 1 + 5 = 6, thus only [3] left, so return 1
[48, 20, 1, 3, 4, 6, 9, 24] > remove 3, 6, 9 , because 3 + 6 = 9, and remove 4, 20, 24, 48, because 4 + 20 + 24 + 48, thus only [1] left, so return 1
int left(int[] nums){
} Report Duplicate  Flag
Facebook Software Developer  0of 0 votes
AnswersThe numbers on a telephone keypad are arranged thus:
1 2 3 4 5 6 7 8 9 0
Starting from any digit, and choosing successive digits as a knight moves in chess, determine how many different paths can be formed of length n. There is no need to make a list of the paths, only to count them.
 majia168 in United States
A knight moves two steps either horizontally or vertically followed by one step in the perpendicular direction; thus, from the digit 1 on the keypad a knight can move to digits 6 or 8, and from the digit 4 on the keypad a knight can move to digits 3, 9 or 0. A path may visit the same digit more than once.
Your task is to write a function that determines the number of paths of length n that a knight can trace on a keyboard starting from any digit .
public int findNumberOfPaths(int digit, int step){ Report Duplicate  Flag
Facebook Software Engineer  1of 1 vote
AnswersIn Docker, building an image has dependencies. An image can only be built once
 majia168 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
Facebook SDE1  0of 0 votes
AnswersThere are n servers, reboot time is S0, S1..Sn1
 majia168 in United States
There are m tasks, the completion of the time required are T0, T1… Tm1
How to assign tasks to each server makes the total time the shortest Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersInput: expression_tree  sequence_of_operations
 majia168 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 1character variables AZ 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
Twitter SDE1  0of 0 votes
AnswersConvert Json string to Map
 majia168 in United States
public Map jsonToMap(String t) {
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersWhat if server is slow, how to solve
 majia168 in United States
What if one server is down Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersGiven a 2D matrix of 0's and 1's, where the 1's make up a rectangle, find the coordinates of the topleft corner of the rectangle and the rectangle's width and height.
 majia168 in United States Report Duplicate  Flag
Facebook Jr. Software Engineer  1of 1 vote
AnswersArray has N integers，range[0...N1]。Set S[k], 0 <= K < N as S[K] = {A[K], A[A[K]], A[A[A[K]]],....},
 majia168 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
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 '+', '', '*', '/'. Followup: when evaluating the expression, take operand precedence into account,
 majia168 in United States
public boolean getTarget(int[] nums, int target){
}
exponentia is ok Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answersfind the Closest leaf to a given node in Binary Tree
 majia168 in United States
can you do it in o(n) time
public TreeNode findCloestLeafNode(TreeNode root, TreeNode target){}
no parent pointer Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answervalidate IP in string format and return the uint32 format
 majia168 in United States
‘1.2.3.4’ > 0x01020304 Report Duplicate  Flag
Facebook SDE1  1of 1 vote
AnswersGiven a nnery tree and its deep copy, a node in the original tree, return the corresponding node in the copy
 majia168 in United States
public TreeNode getCopyNode(TreeNode root, TreeNode copy, TreeNode node) Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answerwrite bash code to determine if the first number in the string is greater than 1000
 majia168 in United States
STR="count  43952 (1 rows)" Report Duplicate  Flag
Amazon Backend Developer  0of 0 votes
AnswersWrite the code to find the median of an unsorted array in average linear time.
 majia168 in United States
followup the array is distributed across many machines. Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswerWrite a function to split a SQL query into individual statements.
 majia168 in United States
give you a String which contains a separate Query with a semicolon ";" return all valid queries
Such as
"select name from courseinfo ;; select * from db1 where home = 'usa' ;"
The main thing to consider is that some special cases such as the escape symbol and the quotation marks inside the semicolon
public List<String> getQuery(String queries){
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answersgiven a list of numbers, put with +  * / any two number, find the maximum value you can get.
 majia168 in United States
int getMaxNumber(int[] nums){
} Report Duplicate  Flag
Facebook Software Engineer  0of 0 votes
AnswersGiven a group of movies and their start time, assuming that are 1 hour long,
 majia168 in United States
Returns a movie schedule (no time conflict).
enter:
Movie ("Shining", [14, 15, 16])
Movie ("kill bill", [14, 15])
Movie ("Pulp fiction", [14, 15])
One possible result is shining 16, kill bill 15, pulp fiction 14
public void schedule (HashMap <String, List <Integer >> map) {
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answersfriend circle. Given a streaming pairs representing friend relationship
 majia168 in United States
(1, 2) means 1 and 2 are friends, (1, 3) means 1 and 3 are friends
Return all its friends.
List<Integer> getFriends (Iterator<List<Integer>> relations, int id){
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answersgiven a matrix and a target, return if there is a path who’s sum is == target
 majia168 in United States
Input: matrix, integer output: true or false; Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answerspermute the String including case change
 majia168 in United States
"abc".
For example:
abc
ABC
Abc
aBc
abC
ABc
abC
AbC Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answersimplemnt JSON.stringify()
 majia168 in United States Report Duplicate  Flag
Facebook SDE1  1of 1 vote
Answersgiven a string of number, you can add a + or * sign between any two numbers, find the maximum value you can get
 majia168 in United States
ex. s = "89" > 8 * 9 = 72
int maxNumber(String s){} Report Duplicate  Flag
Facebook Software Engineer  0of 0 votes
AnswersGive you an unsorted integer iterator
 majia168 in United States
and a percentage that is expressed in double (for example, 0.4 for 40%),
and find the number of the sorted array at the percentage position.
Example: Enter [1 3 2 5 4 6 7 9 8 10], and 0.6, you will return 6
public int findNumber(Iterator<Integer> nums, double percent){
} Report Duplicate  Flag
Facebook Software Engineer  0of 0 votes
Answerscan you use union find to Detect Cycle in a Directed Graph? why or why not
 majia168 in United States Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersShell command, there is a log file, you want all the "error" inside the line to find out into another file inside,
 majia168 in United States
What instruction, Report Duplicate  Flag
Amazon SDE1  0of 0 votes
Answerhow to design github
 majia168 in United States Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersReturn the most popular 10 words in the past 24 hours for twitter
 majia168 in United States
Follow up in order to reduce the size of each log, do not write timestamp, how to get the same answer, Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersGiven a Calendar class (there are three fields, year, month, day) and a number of N,
 majia168 in United States
Implement a function that returns the calendar after N days,
For example, if the input is {2017, 3,20} and 12, then the return is {2017,4, 1} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answersimplement a Fibonacci iterator
 majia168 in United States Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersNow we have one server, one database, what if response time is slow?
 majia168 in United States
How to optimize? Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersGiven an integer n, count the total number of digit 3 appearing in all nonnegative integers less than or equal to n.
 majia168 in United States
(E.x: given 30, return 4 {3,13, 23, 30}) Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answersprime factors. given a number return the prime factor multiplication.
 majia168 in United States
eg. 90 = 2 * 3 * 3 * 5. Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersRemove any number containing 9 like 9, 19, 29, ... 91, 92, ... 99, 109...
 majia168 in United States
Write a function that returns the nth number. E.g. newNumber(1) = 1
newNumber(8) = 8, newNumber(9) = 10 Report Duplicate  Flag
Facebook SDE1  2of 2 votes
AnswersGiven a n*m size 2D array with integers from 1 to n*m  1 in it.
 majia168 in United States
Integers are not sorted. The last position of the matrix stays a movable block.
For each time, you can swap the movable block with any adjacent number.
And eventually you will have the integers sorted and the movable block returned
to its starting position. Think about an approach to print the path.
(You can assume it always have at least a solution) Report Duplicate  Flag
Facebook Software Engineer  0of 0 votes
AnswersHow to get the repeating decimal pattern of a division? (e.g 1/3, 1/6)
 majia168 in United States Report Duplicate  Flag
Facebook Software Engineer  1of 1 vote
AnswersGiven a preorder traversal of a BST, print out the inorder transversal of the BST
 majia168 in United States
public void printInorder(int[] nums){} Report Duplicate  Flag
Facebook Software Engineer  0of 0 votes
Answers/* Find all subsets of size k in an array that sum up to target
 majia168 in United States
the array may contains negative number */
class Solution {
public List<List<Integer>> combinationSum(int[] nums, int target, int k) {
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersA bot is an id that visit the site m times in the last n seconds,
given a list of logs with id and time sorted by time, return all the bots's id
 majia168 in United Statesclass Log{ String id; int time; } public HashSet<String> getBots(Log[] logs, int m, int n){ }
 Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answershow to implement a Wish List like this one
 majia168 in United States
https://www.amazon.com/hz/wishlist/intro Report Duplicate  Flag
Amazon SDE1  0of 0 votes
Answersdownload all urls from 1000 hosts. Imagine all the urls are graph.
 majia168 in United States
Requirement: Each host has bad internet connection among each other, Has to download url exacly once. Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswerGive you a robot and a room where you do not know where the robot is in the room and you do not know the size of the room, you have a remote control that allows the robot to walk around four directions. Here you give a move method: boolean move (int direction), direction: 0,1,2,3 that four directions. If it can move in that direction, return true, and if it cannot move in that direction, return false. Ask you determine how big this room is. the shape of the room can be any shape, so you cannot assume it is rectangle or square.
 majia168 in United States Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersGiven n1, n2 is the number after removing one digit from n1. Example, n1 = 123, then n2 can be 12, 13 or 23.
 majia168 in United States
If we know the sum of n1 + n2, and find the possible values of n1 and n2.
public List<List<Integer>> getNumber(int sum){
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersDesign copyonwrite string class
 majia168 in United States
e.g. stringclass s("abc");
stringclass s1 = s; // no copy
s = "bcd"; // copy Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersGiven an ODD number, print diamond pattern of stars recursively.
n = 5, Diamond shape is as follows: * *** ***** *** *
void print(int n){
 majia168 in United States
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answers/From the input array, output a subset array with numbers part of a Fibonacci series.
 majia168 in United States
// input: [4,2,8,5,20,1,40,13,23]
// output: [2,5,1,8,13]
public static List<Integer> getFibNumbers(int[] nums){} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersCan multiple threads improve the time complexity to merge k sorted arrays? If so, how?
 majia168 in United States Report Duplicate  Flag
Facebook SDE1 Arrays  0of 0 votes
AnswersGives an array of unsorted int (may have negative number),
 majia168 in United States
rearrange the array such that the
num at the odd index is greater than the num at the even index.
example
giving 5, 2, 3, 4, 1, one of the expected result is 1,4,2,5,3,
please solve it in o(n) time, where n is the length of the array
public void rearrange(int[] nums){
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answers
 majia168 in United StatesGiven a string, find all possible combinations of the upper and lower case of each Alphabet char, keep the none Alphabet char as it is. example1 s = "ab", return: "Ab", "ab", "aB", "AB" example2 s = "a1b", return: "A1b", "a1b", "a1B", "A1B" public List<String> getPermutation(String s){ }
 Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersFor a given array, find the subarray (containing at least k number) which has the largest sum.
 majia168 in United States
Example:
// [4, 2, 1, 3], k = 2, return 1, and the subarray is [2, 1]
// [1, 1, 1, 1, 1, 1], k = 3, return 6, and the subarray is [1, 1, 1, 1, 1, 1]
try to do it in O(n) time
Followup, if input is stream, how to solve it
public int maxSubArray(int[] nums, int k) {} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answersfind maximum contiguous subarray sum with size (the number of the element in the subarray) <= k
 majia168 in United States
a brute force method is very simple, can you do it better?
public int maxSum(int[] nums, int k){
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answers// Read4K  Given a function which reads from a file or
 majia168 in United States
// network stream up to 4k at a time, give a function which
// which can satisfy requests for arbitrary amounts of data
private int read4K(char[] buf) {
// GIVEN
}
// IMPLEMENT:
public int read(char[] buf, int toRead) { }
Due to network latency, if the read4K method return a value < 4k, it does not necessarily mean that we reach the End of File (EOF), in this case, you should continue to read the file until you reach toRead or EOF. Report Duplicate  Flag
Facebook SDE1  1of 1 vote
Answerhow to keep track of the sum in a sliding window for the data that are on disk
 majia168 in United States
rather than memory Report Duplicate  Flag
Google SDE1  0of 0 votes
AnswersInsert a node in a complete binary tree efficiently.
it is not BST, it is just a regular binary tree
public TreeNode insert(TreeNode root, int val){
}
this my solution using bfs (O(n) time), is there any more efficient method?
 majia168 in United Statesimport java.util.*; class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode(int val){ this.val = val; } } class Solution{ public TreeNode insertCompleteTree(TreeNode root, int val){ if(root == null){ return new TreeNode(val); } Queue<TreeNode> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ int size = q.size(); for(int i = 0; i < size; i++){ TreeNode cur = q.remove(); if(cur.left == null){ cur.left = new TreeNode(val); return root; }else{ q.add(cur.left); } if(cur.right == null){ cur.right = new TreeNode(val); return root; }else{ q.add(cur.right); } } } return null; } public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null){ return res; } Queue<TreeNode> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ int size = q.size(); List<Integer> list = new ArrayList<>(); for(int i = 0; i < size; i++){ TreeNode cur = q.remove(); list.add(cur.val); if(cur.left != null){ q.add(cur.left); } if(cur.right != null){ q.add(cur.right); } } res.add(list); } return res; } public static void main(String[] args){ Solution s = new Solution(); TreeNode root = null; int[] nums = {1, 2, 3, 4, 5, 6, 7}; for(int num : nums){ root = s.insertCompleteTree(root, num); System.out.println(s.levelOrder(root)); } } }
 Report Duplicate  Flag
Google SDE1  0of 0 votes
AnswersA table has some number of balls at various positions on a line segment.
 majia168 in United States
All are moving with same speed in one or the other direction.
Wherever a collision occurs they change direction.
A ball falls from the edges of the table.
Find the time when all balls fall of the table
given initial position of each ball and speeds Report Duplicate  Flag
Google SDE1  0of 0 votes
Answersgiven a graph: example > A company holds 10% of B company’s share,
 majia168 in United States
B company holds 5% of C company’s share, A company holds 2% of C company’s share,
what percent of C company’s share does A company hold? Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answers
 majia168 in United States// Design and implement key value system // // string > string // Insert a keyvalue pair or modify a value void put(string key, string value); // Delete a keyvalue pair void delete(string key); // Gets a value given a snapshot string get(string key, Snapshot snap); // Take a snapshot Snapshot takeSnapshot(); // Delete a snapshot void deleteSnapshot(Snapshot snap); // put(k1,v1) // put(k2,v2) // put(k3,v3) // takeSnapshot > snap1 { k1 > v1, k2 > v2, k3 > v3 } // get(k1,snap1) > v1 // put(k1,v4) // delete(k3) // takeSnapshot > snap2 { k1 > v4, k2 > v2 } // get(k1,snap2) > v4 // get(k1,snap1) > v1 // get(k3,snap2) > XX // deleteSnapshot(snap1) // get(k1,snap1) > XX // Space efficient is more important than time efficient, thus please use as small space as possible.
 Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersWhat is the cost / complexity of a String.indexof() function call in java?
 majia168 in United States Report Duplicate  Flag
Amazon SDE1  0of 0 votes
AnswersGiven a task sequence tasks such as ABBABBC, and an integer k, which is the cool down time between two same tasks. Assume the execution for each individual task is 1 unit.
 majia168 in United States
rearrange the task sequence such that the execution time is minimal.
Example:
S = AAABBBCCC, K = 3
Result: ABCABCABC (all 'A's are 3 distance apart, similarly with B's and C's), thus return 9
S = AAABC, K=2
Result: ABCA_ _A, thus return 7
S = AAADBBCC, K = 2:
Result: ABCABCDA, thus return 8
public int rearrangeTasks(String tasks, int cooldown){
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersGiven an array of n elements which contains elements from 0 to n1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.
 majia168 in United States
Try to do it in one pass
example
[4, 2, 0, 5, 2, 0, 1] return: 0, 2
[1, 2, 3, 0, 0, 1, 3, 6, 6,6] return 0, 1, 3, 6
public List<Integer> findRepeat(int nums[]){
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersHow to check the validity of a 4 digit credit card expiration date (mm/yy)
 majia168 in United States
that still works 100 years from now.
public boolean isValid(String s){
} Report Duplicate  Flag
Amazon SDE1  0of 0 votes
Answerswhat is the time complexity for java.util.Random.nextInt()
 majia168 in United States Report Duplicate  Flag
Amazon Java Developer  0of 0 votes
Answersconvert a ternary expression into a Binary tree structure. a?b:c a / \ b c a?b?c:d:e a / \ b e / \ c d class TreeNode{ char val; TreeNode left; TreeNode right; public TreeNode(char val){ this.val = val; } } public TreeNode build(String s){}
try to do it in o(n) time complexity, n is the size of the string
 majia168 in United States Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswerSuppose you have a 2D grid. Each point is either land or water. There is also a start point and a goal. There are also keys that open up doors. Each key corresponds to one door. Implement a function that returns the shortest path from the start to the goal using land tiles, keys and open doors. Data Representation The board will be passed as an array of chars. A board can have the following tiles. 0 = Water 1 = Land 2 = Start 3 = Goal uppercase = door lowercase = key Example Maps (keys at each step are not required) `No doors` char[][] board1 = {{'0', '2', '1', '1', '1'}, {'0', '1', '0', '0', '1'}, {'0', '1', '0', '0', '3'}, {'0', '1', '0', '0', '1'}, {'0', '1', '1', '1', '1'}}; path : [0,1]>[0,2]>[0,3]>[0,4]>[1,4]>[2,4] `One door` char[][] board2 = {{'0', '2', '1', '1', '1'}, {'0', '1', 'a', '0', 'A'}, {'0', '1', '0', '0', '3'}, {'0', '1', '0', '0', '1'}, {'0', '1', '1', '1', '1'}}; path : [0,1]>[0,2]>[1,2]>[0,2]>[0,3]>[0,4]>[1,4]>[2,4]
public List<int[]> solve(char[][] board) {
 majia168 in United States Report Duplicate  Flag
Google SDE1  0of 0 votes
AnswersGroup a list of words so that the same group of words have a common substring, and this common substring is also in the word lists,
 majia168 in United States
example
[cow "," cold "," an "," co "], return [[" can "," an "], [" cow "," cold "," co "]]
["can", "cow", "cold"], return [["can"], ["cow"], ["cold"]]
["c", "ca", "can"], return [["c", "ca", "can"]]
public List<List<String>> groupWords(String[] s) Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersEnter a two digit number, find the year closest to this year.
 majia168 in United States
Example input 99, return 1999;
Input 15, return 2015.
public int getClosestYear(int input){
} Report Duplicate  Flag
Facebook SDE1  2of 4 votes
Answersgenerate random number which differs from the number generated last time in the range of [min, max)
 majia168 in United States
what is the best way to do it?
public int getNumber(int min, int max){
} Report Duplicate  Flag
Facebook SDE1  1of 1 vote
AnswersGiven a undirected graph with each node representing a char and a word,
check if the word can be formed by any path of the graph
example
graph:
adogact
word : dog, return true;
word: cat, return false;
The same letter may not be used more than once.
 majia168 in United Statesclass Node { char label; List<Node> neighbors; Node(char x) { label = x; neighbors = new ArrayList<>(); } } class Solution { public boolean exist(List<Node> nodes, String word) { } }
 Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersGiven a Binary tree (Not binary Search Tree ), find the inorder successor of a node.
 majia168 in United Statesclass TreeNode{ TreeNode left; TreeNode right; int val; public TreeNode(int val){ this.val = val; } } public TreeNode inOrderSuccessor(TreeNode root, TreeNode n) {
 Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersGiven a positive integer n, find the no of integers less than equal to n, whose binary representation doesn't contain consecutive 1s.
 majia168 in United States
eg:
I/P : 4
O/P: 4 (0,1,2,4 Valid)
public int count(int n){
} Report Duplicate  Flag
Facebook SDE1  1of 1 vote
AnswersGiven m 0 and n 1, count the total number of permutations where two 1 cannot be adjacent
 majia168 in United States
public int count(int m, int n){
} Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersGiven a binary tree, return all the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
Given a binary tree
 majia168 in United States/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ 1 / \ 2 3 / \ 4 5 Return [4,2,1,3] and [5,2,1,3]. Public List<List<Integer>> getLongestPath(TreeNode root) { }
 Report Duplicate  Flag
Google SDE1  1of 1 vote
AnswersGenerate a random 4digit even number : the adjacent 2 digits must be different.
 majia168 in United States
public int getNumber(){
} Report Duplicate  Flag
Google Software Engineer  1of 1 vote
Answerswrite a function that randomly return a random Fibonacci number in range [min, max)
 majia168 in United States
public int getRandom (int min, int max){} Report Duplicate  Flag
Google SDE1  0of 0 votes
Answerswrite a function that randomly return a random prime number in range [min, max)
 majia168 in United States
public int getRandom (int min, int max){} Report Duplicate  Flag
Google SDE1  0of 0 votes
Answershow does java implement priority queue?
 majia168 in United States
i answered min heap, the interviewer seemed it was not right Report Duplicate  Flag
Amazon SDE1  0of 0 votes
Answer
 majia168 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 = 41 = 3, exclusive time = 31 = 2 F2: inclusive time = 32 = 1, exclusive time = 1
 Report Duplicate  Flag
Facebook SDE1  0of 0 votes
AnswersFind the subarray within an array (containing at least TWO number) which has the largest sum.
 majia168 in United States
For example, given the array [2,1,3,4,1],
the contiguous subarray [2,1] has the largest sum = 3.
try to do it in O(n) time
Followup, if input is stream, how to solve it
public int maxSubArray(int[] nums) {} Report Duplicate  Flag
Facebook Software Engineer  0of 0 votes
Answerstokenize string, "" and [] are token flags, such as
 majia168 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
Google SDE1  0of 0 votes
AnswersWhat design pattern is used to implement a SynchronizedHashMap?
 majia168 in United States Report Duplicate  Flag
Amazon Java Developer  0of 0 votes
AnswersF (n) = 3n + 1 (if n is odd) or n / 2 (if n is even)
 majia168 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
Google SDE1  0of 0 votes
AnswersFind the Lexicographic next word of the input word from a list of words
 majia168 in United States
Example
Words list
[Cat, dog, cow, donkey, zebra, monkey],
input
duck
output
monkey
Input
dog
output
donkey
Can you use trie to solve it?
public String findNextWord(List<String> words, String input){
} Report Duplicate  Flag
Google Software Engineer  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
 majia168 in United States Report Duplicate  Flag
Google SDE1  1of 1 vote
Answerswrite a function that randomly return only odd number in range [min, max)
 majia168 in United States
public int getRandomOdd(int min, int max){} Report Duplicate  Flag
Google Software Developer  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.
 majia168 in United States
element can have two chars, for example Fe2(SO4)3
public HashMap<Character, Integer> getCount(String chemicals){
} Report Duplicate  Flag
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
 majia168 in United States
public List<char[]> getDerangement(char[]){} Report Duplicate  Flag
Facebook SDE1  2of 2 votes
Answersthree sum with duplicate, pirnt all indexes, for example:
 majia168 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
Facebook SDE1  0of 2 votes
AnswersGiven an array of task and k wait time for which a repeated task
 majia168 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
Facebook SDE1  0of 0 votes
AnswersGiven an unsorted array, sort it in such a way that the first
 majia168 in United States
element is the largest value, the second element is the smallest,
the third element is the second largest element and so on.
[2, 4, 3, 5, 1] > [5, 1, 4, 2, 3]
can you do it without using extra space
public void sortAlternate(int[] nums){} Report Duplicate  Flag
Facebook SDET  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.
 majia168 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
Facebook SDE1  1of 1 vote
Answerdeleted
 majia168 in United States Report Duplicate  Flag
Google 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 bipartiteness of a graph
 majia168 in United States Report Duplicate  Flag
Facebook SDE1  0of 0 votes
Answers* Definition for a binary tree node.
 majia168 in United States
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
Given an array of Binary Tree Node, check if all of these nodes can form a binary tree?
Public boolean canForm(TreeNode[] nodes){
} Report Duplicate  Flag
Google Software Engineer / Developer  0of 0 votes
AnswersGive a Runable interface, and then give a scheduler post method. This post is parallel, for example:
 majia168 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
Google SDE1  4of 4 votes
Answersthere is a bunch of tasks, each have different time to complete, task is independent, and then there are some workers,
 majia168 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
Facebook SDE1  4of 4 votes
AnswersGiven an nonnegative int array and target number, check if the target can be equal to the sum of nonnegative multiples of the numbers in the array.
 majia168 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
Google SDE1  2of 2 votes
AnswersFind three nonoverlap windows of size k in an int array, that together has a maximum sum
 majia168 in United States
of the 3k entries.
example
int[] nums = [1,2,1,2,6,7,5,1]
k = 2
output
[1,2],[2,6],[7,5] Report Duplicate  Flag
Google Software Engineer  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
 majia168 in United States
public int countSubSet(int[] nums, int target){
} Report Duplicate  Flag
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.
 majia168 in United States Report Duplicate  Flag
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”
 majia168 in United States Report Duplicate  Flag
Google SDE1  0of 0 votes
AnswersGiven an array that contains both positive and negative integers, find the start and end index of the subarray that achieves the maximum subarray product using one pass
 majia168 in United States Report Duplicate  Flag
Google  0of 0 votes
Answershow to find leaf node value from preorder sequence of BST without rebuilding the tree
 majia168 in United States Report Duplicate  Flag
Google Software Engineer  0of 0 votes
Answersdeleted
 majia168 in United States Report Duplicate  Flag
Google Software Engineer  2of 2 votes
AnswersSay you have an array for which the ith element is the price of a given stock on day i.
 majia168 in United States
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
, but each time you sell you need to pay transaction fee, please calculate the maximum profit you can take.
public int maxProfit(int[] prices, int fee) {
} Report Duplicate  Flag
Google  0of 0 votes
Answersfor a binary tree, print the root to the leaf path, but add "_" to indicate the relative position.
example:
 majia168 in United StatesA / \ B C / \ / \ D E F G output _ _ A _ B D _A B _E A _C F A _ C _ _ G
 Report Duplicate  Flag
Google Software Engineer  0of 0 votes
Answers/**
 majia168 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
Google SDE1  4of 4 votes
Answers/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
Find if a given binary tree has duplicate sub trees.
followup:
Find all duplicate subtrees in a binary tree
 majia168 in United StatesFor example, 1 / \ 2 3 / / \ 4 2 4 / 4 The following are two duplicate subtrees: 2 / 4 and 4 Therefore, return [ [2,4], [4] ].
 Report Duplicate  Flag
Google Software Engineer / Developer  0of 0 votes
Answercount Number of balanced Binary Tree given Preorder Sequence length
 majia168 in United States Report Duplicate  Flag
Amazon SDE1  6of 6 votes
AnswersPaper Cut into Minimum Number of Squares
 majia168 in United States
Given a paper of size A x B. Task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.
Examples:
Input : 13 x 29
Output : 9
Explanation :
2 (squares of size 13x13) +
4 (squares of size 3x3) +
3 (squares of size 1x1)=9
Input : 4 x 5
Output : 5
Explanation :
1 (squares of size 4x4) +
4 (squares of size 1x1)
geeksforgeeks provides a solution, but it is not right
http://www.geeksforgeeks.org/papercutminimumnumbersquares/ Report Duplicate  Flag
Google  0of 0 votes
AnswersGiven a diamond shape matrix, find the minimum path sum from top to bottom.
Each step you may move to adjacent numbers on the row below.
 majia168 in United States[ [2], [3,4], [6,5,7], [4,1,8,3], [2,5,4], [6,4], [1] ]
 Report Duplicate  Flag
Amazon Software Engineer / Developer  0of 0 votes
AnswersDesign a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)
 majia168 in United States Report Duplicate  Flag
Facebook Software Engineer / Developer  0of 0 votes
AnswersIf a string is matched to any filter, it is in the black list, otherwise not.
 majia168 in United States
Design a data structure and implement following two functions.
addFilter(filter)
isInBlackList(string)
filters are in the form of
“a*b”
“abc”
“aa*b”
having at most one star, which matches 0 or more chars. Report Duplicate  Flag
Amazon Software Engineer
how about this one?
#include <iostream>
#include <vector>
using namespace std;
int minsum(vector<vector<int>> &nums){
int n=nums.size();
if(n==0) return 1;
for(int i=1;i<n;i++){
for(int j=0;j<nums[i].size();j++){
// fom top to middle
if(nums[i].size()>nums[i1].size()){
if(j1>=0&&j<nums[i1].size()){
nums[i][j]+= min(nums[i1][j1],nums[i1][j]);
}else if(j==0){
nums[i][j]+=nums[i1][j];
}else{
nums[i][j]+=nums[i1][j1];
}// from mid to bottom
}else{
nums[i][j]+=min(nums[i1][j],nums[i1][j+1]);
}
}
}
return nums[n1][0];
}
/*
[
[2],
[3,4],
[6,5,7],
[4,1,8,3],
[2,5,4],
[6,4],
[1]
]
*/
int main() {
vector<vector<int>> nums={{2},{3,4},{6,5,7},{4,1,8,3},{2,5,4},{6,4},{1}};
cout<<minsum(nums);
/*for(auto num:minsum(nums)){
for(auto n:num)
cout<<n<<" ";
cout<<endl;
}*/
//cout<<"Hello";
return 0;
}

majia168
March 02, 2017
RepEdwards IVF Surrogate is one of the best & most successful provider of surrogate services.We provide moral, emotional, ethical and ...
RepWant to know how to protect from black magic? Guru Ji is the world’s famous astrologer and he has ...
RepSpent 20012006 getting my feet wet with Slinkies in Fort Walton Beach, FL. mantra to control girl Spent 20012006 working ...
RepPrestige Luxury Rentals, Tech Lead at Prestige Luxury Rentals
Prestige Luxury Rentals is highly recommended company for exotic car rental Miami. With our top brand vehicles like; exotic, luxury ...
RepAmber Van is the top rated company that offers friendly and professional removals services.Our featured services includes domestic moves ...
RepAre you searching for the most powerful and very strong mantra for your husband? If you want to do Jadoo ...
RepJonathan Galgano, Data Engineer at Blue Jeans
Drive with the most affordable Exotic Car Rental South Beach. Prestige luxury Rentals is offering you with the finest car ...
RepJohn Colcomb, Analyst at A9
With more than 20 years of car rental and dealership experience, responsible for developing growth strategies to maximize operational effectiveness ...
RepLarry Alvarez, Analyst at ASU
Prestige Luxury Rentals is one of the most renowned car rental companies in USA. We are locally owned and operated ...
RepSCREENish employee time tracking software can be used as desktop or mobile app. Once the employee has tracked his working ...
RepBlack magic mantra is simple and easy mantra. Call our specialist today for advice on black magic mantra to kill ...
RepGerard Swearingen, Consultant at ADP
Want to book exotic and luxury car rental in Atlanta, GA ? We, Prestige Luxury Rentals are the best car rentals ...
Open Chat in New Window
rsrs3
 majia168 May 04, 2017for {"an","dan", "c"}, your codes return [[an], [c], [dan]]
but it should be [[c], [an, dan]]