Software Engineer Interview Questions
- 0of 0 votes
AnswersFind longest consecutive path in a binary tree.
- wtcupup2017 December 10, 2016 in United States
1. the path can be decreasing or increasing, i.e [1,2,3,4] and [4,3,2,1] are both valid
2. the path can be child-parent-child, not necessarily a parent-to-child path
similar to this question: http://www.geeksforgeeks.org/longest-consecutive-sequence-binary-tree/| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersGiven a singly linked list: 1->2->3->4->5
- rainnyforeverluv December 09, 2016 in United States
Change it to 1->5->2->4->3 using O(1) space| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersImplement delete operation for N-ary tree. Your function should return a list of roots after deletion operation. Notice that your delete function only delete one node instead of a subtree. The delete function takes a list of nodes to be deleted.
- wtcupup2017 December 09, 2016 in United Statesprivate class TreeNode { int val; TreeNode[ ] child; } List<TreeNode> delete(TreeNode root, HashSet<TreeNode> set) { }
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven a list of manager and employee information represented in hashMap entries {AAA->BBB,CCC,EEE},{CCC->DDD}.
Print company structure tree with proper indentations. BBB, CCC and EEE directly reports to AAA, so they have one white space before "-", DDD reports to CCC, it has two whitespace before "-". The input is map<String,List<String>>
- wtcupup2017 December 08, 2016 in United States-AAA -BBB -CCC -DDD -EEE
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersA producer continuously produces a stream of characters. There are multiple consumer threads which read the chars and match to one of known strings and increment the counter for that pattern. Write the consumer function. Show how you will synchronize and maintain parallelism.
- kgok December 06, 2016 in United States
Ex: Producer: abcdegabccaabbaacv ......
Known strings[] = {"ab", "aa", "fff" ... }
patternMatchCount[] = {3, 2, 0 ... }| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer Algorithm - 2of 2 votes
AnswersGiven N stacks, each stack contains Si elements, find the maximum sum of the M numbers in the N stacks. To get the number of the stack, only supporting get the top number. For example, S=[1,200,1,2,3], if you want to get the number 200, you need choose 3,2,1 first.
- jeffrey November 28, 2016 in United States
EX:
S1=[1,1,100,3]
S2=[2000,2,3,1]
S3=[10,1,4]
the maximum sum of the 3 numbers in the above stacks is 3+100+3=107.
Any better solution for this problem?| Report Duplicate | Flag | PURGE
Google Software Engineer Dynamic Programming - 0of 4 votes
AnswersGiven two pre-order traversal arrays of two binary search tree respectively, find first pair of non-matching leaves.
- wtcupup2017 November 27, 2016 in United States
Follow Up: If they are general binary trees instead of BSTs, could you solve it? give out your reason.
For the first question, I was thinking to construct two BSTs from pre-order traversal then do a leaf-level comparison. Any better solutions are welcome.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersGiven a binary tree and a target number, return whether or not there exist a path that can create target number. All inputs are integers. Target is not a string.
- cool November 22, 2016 in United States
NOTE:: this is not path sums to target number
ex:
3
4 5
6 7 8 9
359 = return true
38 = return false
47 = return true
6 = return true| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 2of 2 votes
AnswersYou are the main character in a game where you have to defeat a number of enemies in order. The player has a strength value and an initial amount of money. Each enemy also has a strength value, plus a price.
- camiloni42 November 19, 2016 in United States
When facing each enemy you can either:
1) Fight him (if your strength is enough). You keep your money.
2) Bribe him (if you have the necessary money). You subtract the enemy's price from your money, and it joins you and adds its strength to yours.
Given a starting strength and amount of money, calculate the optimal strategy and the amount of money you end with (-1 if impossible).
This can be easily solved recursively in O(2^n) basically trying out each option at every enemy. But is there a polynomial solution, maybe involving DP?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersFinding biggest plus sign "+" in a sparse matrix(matrix with elements 0 and 1)
- wtcupup2017 November 19, 2016 in United States
For example, the biggest plus sign for following matrix is located at (2,2), with length 1 for each edge(Yes, each edge should have same length)
0 0 1 0 0 1 0
1 0 1 0 1 0 1
1 1 1 1 1 1 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0
Hint: use DFS/BFS| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersGiven a list of coin values, and quantity of each type of coin. Write a
- snakeonbasket November 18, 2016 in United States
program to return the set of all possible sums which can be made using those
coins.
ex. coins = [10, 50, 100, 500]
quantity = [5, 3, 2, 2]
sum could be 400 , 300 ,200 , 100| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswerWrite a function that compares Spanish strings, how would you handle special cases like 'ch' ?
- Gear November 17, 2016 in United States
c < ch < d, ch will be represented as 2 ASCII characters| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersDefine amazing number as: its value is less than or equal to its index. Given a circular array, find the starting position, such that the total number of amazing numbers in the array is maximized.
- wtcupup2017 November 13, 2016 in United States
Example 1: 0, 1, 2, 3
Ouptut: 0. When starting point at position 0, all the elements in the array are equal to its index. So all the numbers are amazing number.
Example 2: 1, 0 , 0
Output: 1. When starting point at position 1, the array becomes 0, 0, 1. All the elements are amazing number.
If there are multiple positions, return the smallest one.
should get a solution with time complexity less than O(N^2)| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersGiven 'n' circles (each defined by center and radius)
- sheva November 12, 2016 in United States
Write an algorithm to detect if circles intersect with any other circle in the same plane
Better than O(n^2) complexity| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersReturn the pivot index of the given array of numbers. The pivot index is the index where the sum of the numbers on the left is equal to the sum of the numbers on the right. Input Array {1,2,3,4,0,6}
- umesh.shaw November 11, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Arrays - 1of 1 vote
AnswersGiven the village of a map represented as a 2D grid containing houses,bushes and open-spaces, write a program to find a point for conducting a meeting in the map. Such point should be minimum from all the houses in the village.
Eg.# # # # # # # A # # B # # # # # # # C # # # # # #
# -> represents the bushes
- angry_scorpion November 10, 2016 in United States
A, B, C -> position of houses
I provided a O(n*a*b) approach, where n-> no. of houses , a,b->dimensions of the grid.
The interviewer asked me for some special cases. Can it be done more efficiently?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersUsing that data structure, devise an algorithm to compute the dot product between two sparse matrices.
- Brookekelseyryan November 05, 2016 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersWhat data structure would you use to store the entries of a sparse matrix?
- Brookekelseyryan November 05, 2016 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 1of 3 votes
AnswersCreate a function to calculate the height of an n-ary tree.
- theNightsKing16 November 03, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Trees and Graphs - 1of 1 vote
AnswersMagical binary strings are non-empty binary strings if the following two conditions are true:
- zandu November 01, 2016 in India
The number of 0's is equal to the number of 1's.
For every prefix of the binary string, the number of 1's should not be less than the number of 0's.
A magical string can contain multiple magical substrings. If two consecutive substrings are magical, then we can swap the substrings as long as the resulting string is still a magical string. Given a magical binary string, str, perform zero or more swap operations on its consecutive magical substrings such that the resulting string is aslexicographically large as possible. Two substrings are considered to be consecutive if the last character of the first substring occurs exactly one index before the first character of the second substring.
-----
Input Format
a single binary string, str.
Constraints
It is guaranteed that str is a binary string of 1's and 0's only.
1 ≤ length(str) ≤ 50
It is guaranteed that str is a magical string.
Output Format
Find a string denoting the lexicographically largest magical string that can be formed from str.
Sample Input 0
11011000
Sample output
11100100
Explanation of sample
Given the magical string str = 11011000, we can choose two consecutive magical substrings, 1100 and 10, to swap such that the resultant string, str' = 11100100, is the lexicographically largest possible magical string possible. Thus, we return the value of str', which is 11100100, as our answer.
.| Report Duplicate | Flag | PURGE
N/A Software Engineer Algorithm - 0of 0 votes
AnswersGiven a binary tree & the following TreeNode definition, return all root-to-leaf paths.
Definition of TreeNode:public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val) { this.val = val; this.left = this.right = null; } }
EXAMPLE
Given the following binary tree: 1 / \ 2 3 \ 5 All root-to-leaf paths are: [ "1->2->5", "1->3" ]
From Lint Code - http://www.lintcode.com/en/problem/binary-tree-paths/
- johndifini October 29, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a string, parse it and return a string array. It's like a tokenizer, but the rules are too...
- OctA October 29, 2016 in United States
For exmple, string="abc(edf)hij{klmn}opq[rst]uvw"
The delimiter are (), {}, []. They are in pair. So output array:
["abc", "edf", "hij", "klmn", "opq", "rst", "uvw"]
That's the rule 1. The rule 2 is, if any two consecutive "(" means escaping, that is "((" is actually output char "(". It's not part of the delimitor. Similar to ")", "{", "}", "[", "]".
abc(e))df) => ["abc", "e)df"], since the "))" outpus ")".
Rule 3: if "{" is inside a delimiter pair (), then "{" isn't part of the delimitor. Output it as is.
abc(e{df}}g) => ["abc", "e{df}}g"]| Report Duplicate | Flag | PURGE
HULU Software Engineer Algorithm - 1of 1 vote
Answers/*
- cheeyim October 28, 2016 in Singapore
# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.
# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:
# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
# For example:
# input = [(1,4), (2,3)]
# > 3
# input = [(4,6), (1,2)]
# > 3
# input = [(1,4), (6,8), (2,4), (7,9), (10, 15)]
# > 11
*/| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 2 votes
Answerswrite a SQL query to retrieve the number of students that received a GPA of 3 or 4. the query should return Total number of students that receive a GPA of 3 separate from Total number of students that receive GPA 4.
- aryan October 19, 2016 in United States
Schema:-
Student:- Student_ID, name, phoneno, email, gpa, gradyear
Classes: Class_ID, name, description
student_classes:- Class_ID, Student_ID, Grade| Report Duplicate | Flag | PURGE
Amazon Software Engineer Database - -1of 1 vote
AnswersGiven an un-directed weighted graph G(V,E), find the minimum weight between two given nodes X & Y
- gsharma34065 October 14, 2016 in India
(i.e. sum of weights of edges between X & Y).
You can add an extra egde with weight W between any two nodes in the graph exactly one time (if required).| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven infinite supply of coins of denominations 25, 10, 5 and 1, find the distinct number of ways to use the coins to sum up to the given value
- rajansthapit October 10, 2016 in United States| Report Duplicate | Flag | PURGE
Adobe Software Engineer Algorithm - 0of 0 votes
AnswersGiven a string s, return all the palindromic permutations ( without duplicates), of it. Return an empty array if no palindromic combinations can be formed.
- NS October 04, 2016 in United States| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 0of 0 votes
AnswersGiven a string, determine if a permutation of a string can form a palindrome.
- NS October 04, 2016 in United States| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 0of 0 votes
AnswerYou have a web scraper that pulls car listing from Craiglist and other web sites. Design the system and API for the users to read the data.
- mrsurajpoudel.wordpress.com September 30, 2016 in United States
Follow-up : How will you scale your system?| Report Duplicate | Flag | PURGE
Triplebyte Software Engineer System Design - 0of 0 votes
AnswersDesign a cache for larger objects(>1MB) using memcached. You need to use API provided by memcached(which has constraint of not using more than 1MB of data per key). API are
- mrsurajpoudel.wordpress.com September 30, 2016 in United Statesmemcache.set(key, value) memcache.get(key)
| Report Duplicate | Flag | PURGE
Triplebyte Software Engineer System Design