## Software Engineer Interview Questions

- 3of 5 votes

AnswersPhone screen Q: String encoding and decoding: Design a method that converts a list of strings into a single string which can be later converted back to the list.

- aonecoding January 15, 2017 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Programming Skills - 3of 5 votes

AnswersQ: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.

- aonecoding January 15, 2017 in United States`/usr /local profile.jpg /bin config.txt dest.png /rbin image.gif /sys /re /tmp pic.jpg ..... ……`

| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersYou are given an array of integers(with all valid input) You have to write a function which will produce another array, where the value in each index of the array will be the product of all values in the given array accept that index.

- Azarbaizan January 10, 2017 in United States for Market Place

Example

Array 1: 1 2 3 4 5

Array 2: 120 60 40 30 24.

Come up with a solution of O(n^2) can you improve it?| Report Duplicate | Flag | PURGE

Amazon Software Engineer Arrays - 0of 0 votes

AnswersRandom generate a NxN matrix with only four types of element: 1,2,3,4.

- wtcupup2017 December 30, 2016 in United States

However, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)

ex:

valid:

1 2 1 1

3 1 4 2

1 2 4 2

3 1 2 3

invalid because the first column has element 1 appears three times and all 1s are connected to each other :

1 2 1 3

1 3 4 2

1 2 4 4

2 3 2 2| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersAn interesting question asked in Google’s phone interview : suppose a row of parking lot with n spots, one of them is empty and n-1 spots are occupied with cars. Only one operation is allowed: move one car from its position to the empty spot. Given a initial order of cars and a final order, output steps needed to convert initial order to final oder with that operation.

- wtcupup2017 December 28, 2016 in United States

Follow up: Minimize steps needed.

ex:

{1 2 3 -1 4 5}

move car 1 to empty spot(denoted as -1) will make it {-1,2,3,1,4,5}

push 1 to the output list because you move car 1 to the empty spot

suppose you have a initial order {1 2 3 -1 4 5} and a final order {5,1,-1,3,2,4}, you need to transfer {1 2 3 -1 4 5} to {5,1,-1,3,2,4}, push each car moved into a output list.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersGiven two big files merge the files on to a third file such that the lines interleave.

- santakdalai90 December 20, 2016 in India| Report Duplicate | Flag | PURGE

EFI Software Engineer design - 0of 0 votes

AnswersGiven an array of random numbers, shuffle the numbers once again with the least possibility of it being same as previous configuration.

- santakdalai90 December 20, 2016 in India| Report Duplicate | Flag | PURGE

EFI Software Engineer Arrays - 0of 0 votes

AnswersGiven two linked lists find if they are making a shape of 'Y' or a shape of 'V'.

- santakdalai90 December 20, 2016 in India| Report Duplicate | Flag | PURGE

EFI Software Engineer Linked Lists - 0of 0 votes

AnswersIf you can hop 1, 2, or 3 steps at a time, calculate the total number of possible combinations for `n` steps.

- noitidart December 10, 2016 in United States| Report Duplicate | Flag | PURGE

Linkedin Software Engineer Algorithm - 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 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

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

Open Chat in New Window