majia168
 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
 majia168 in United States Report Duplicate  Flag
Google SDE1  0of 0 votes
Answerwrite 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  3of 3 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  3of 3 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  5of 5 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 Open Chat in New Window
how to delete a post here?
 majia168 April 05, 2017