SDE1 Interview Questions
- 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.
- ajay.raj May 26, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1 - 1of 1 vote
AnswersThere are N gas stations along a circular route, where the amount of gas at station i is gas[i].
- majia168 May 23, 2017 in United States
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You can begin the journey with an empty tank at one of the gas stations.
Return ALL the starting gas station's index where you can travel around the circuit once
public List<Integer> canCompleteCircuit(int[] gas, int[] cost) {
}| Report Duplicate | Flag | PURGE
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.
- ajay.raj May 22, 2017 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 | PURGE
Facebook SDE1 - -1of 1 vote
AnswersDesign copy-on-write string class
- ajay.raj May 22, 2017 in United States
e.g. stringclass s("abc");
stringclass s1 = s; // no copy
s = "bcd"; // copy| Report Duplicate | Flag | PURGE
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){
- ajay.raj May 20, 2017 in United States
}| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
Answers/From the input array, output a subset array with numbers part of a Fibonacci series.
- ajay.raj May 20, 2017 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 | PURGE
Facebook SDE1 - 0of 0 votes
AnswersCan multiple threads improve the time complexity to merge k sorted arrays? If so, how?
- ajay.raj May 18, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1 Arrays - 0of 0 votes
AnswersGives an array of unsorted int (may have negative number),
- ajay.raj May 15, 2017 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 | PURGE
Facebook SDE1 - 0of 0 votes
Answers
- ajay.raj May 15, 2017 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 | PURGE
Facebook SDE1 - 0of 0 votes
AnswersFor a given array, find the subarray (containing at least k number) which has the largest sum.
- ajay.raj May 13, 2017 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 | PURGE
Facebook SDE1 - 0of 0 votes
Answersfind maximum contiguous subarray sum with size (the number of the element in the subarray) <= k
- ajay.raj May 12, 2017 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 | PURGE
Facebook SDE1 - 0of 0 votes
Answers// Read4K - Given a function which reads from a file or
- ajay.raj May 11, 2017 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 | PURGE
Facebook SDE1 - 1of 1 vote
Answerhow to keep track of the sum in a sliding window for the data that are on disk
- ajay.raj May 11, 2017 in United States
rather than memory| Report Duplicate | Flag | PURGE
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?
- ajay.raj May 11, 2017 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 | PURGE
Google SDE1 - 0of 0 votes
AnswersA table has some number of balls at various positions on a line segment.
- ajay.raj May 11, 2017 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 | PURGE
Google SDE1 - 0of 0 votes
Answersgiven a graph: example -> A company holds 10% of B company’s share,
- ajay.raj May 11, 2017 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 | PURGE
Facebook SDE1 - 0of 0 votes
Answers
- ajay.raj May 11, 2017 in United States// Design and implement key value system // // string -> string // Insert a key-value pair or modify a value void put(string key, string value); // Delete a key-value 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 | PURGE
Facebook SDE1 - 0of 0 votes
AnswersWhat is the cost / complexity of a String.indexof() function call in java?
- ajay.raj May 08, 2017 in United States| Report Duplicate | Flag | PURGE
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.
- ajay.raj May 08, 2017 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 | PURGE
Facebook SDE1 - 0of 0 votes
AnswersGiven an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.
- ajay.raj May 08, 2017 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 | PURGE
Facebook SDE1 - 0of 0 votes
AnswersHow to check the validity of a 4 digit credit card expiration date (mm/yy)
- ajay.raj May 06, 2017 in United States
that still works 100 years from now.
public boolean isValid(String s){
}| Report Duplicate | Flag | PURGE
Amazon SDE1 - 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
- ajay.raj May 04, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1 - 1of 1 vote
AnswersSuppose you have a 2-D 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) {
- ajay.raj May 04, 2017 in United States| Report Duplicate | Flag | PURGE
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,
- ajay.raj May 04, 2017 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 | PURGE
Facebook SDE1 - 1of 1 vote
AnswersWrite a function that returns true if the binary representation of an integer is a palindrome.
- maxxwizard May 03, 2017 in United States for Marketplace
9 = 1001 = palindrome
8 = 1000 = not palindrome| Report Duplicate | Flag | PURGE
Amazon SDE1 Java - 0of 0 votes
AnswersEnter a two digit number, find the year closest to this year.
- ajay.raj May 03, 2017 in United States
Example input 99, return 1999;
Input 15, return 2015.
public int getClosestYear(int input){
}| Report Duplicate | Flag | PURGE
Facebook SDE1 - -2of 4 votes
Answersgenerate random number which differs from the number generated last time in the range of [min, max)
- ajay.raj May 01, 2017 in United States
what is the best way to do it?
public int getNumber(int min, int max){
}| Report Duplicate | Flag | PURGE
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:
a--d--o--g--a--c--t
word : dog, return true;
word: cat, return false;
The same letter may not be used more than once.
- ajay.raj May 01, 2017 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 | PURGE
Facebook SDE1 - 0of 0 votes
AnswersGiven a Binary tree (Not binary Search Tree ), find the inorder successor of a node.
- ajay.raj April 30, 2017 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 | PURGE
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.
- ajay.raj April 30, 2017 in United States
eg:
I/P : 4
O/P: 4 (0,1,2,4 Valid)
public int count(int n){
}| Report Duplicate | Flag | PURGE
Facebook SDE1