## Software Engineer Interview Questions

- 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 States`private 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 - 1of 1 vote

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 States`memcache.set(key, value) memcache.get(key)`

| Report Duplicate | Flag | PURGE

Triplebyte Software Engineer System Design - 0of 0 votes

AnswersWrite a program that reads a maze from a file and outputs from 'X' to 'O'. Example,

- mrsurajpoudel.wordpress.com September 30, 2016 in United States`Input: ########## X # # # # # # # # O ########## Output: ########## +++#+++++# # +#+ # +# # +++ # ++ ##########`

| Report Duplicate | Flag | PURGE

Software Engineer Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window