## Software Engineer Interview Questions

- 0of 0 votes
Given a bar chart which the heights of bars are notated as an array of positive integers. Rectangles can be formed in areas covered by one or more bars. Find the largest rectangle.

- 1of 1 vote
FB On-site March

Q: Find number of Islands.

XXXOO

OOOXX

XXOOX

Return 3 islands.

1 1 1OO

OOO2 2

3 3OO 2

Followup: If the board is too big to fit in memory, how to get the number?

- 0of 0 votes
.

- 0of 0 votes
Given two sets of intervals such as {[1, 2], [4, 8]} and {[2, 5]}. Find their union {[1, 8]} for the two intervals.

- 0of 0 votes
Design a dictionary which words are grouped by the same characters. For example, dog and god are in the same group. And how to make it scalable to handle a huge number of words?

- 2of 2 votes
Find the median of a very big array of integer. Only iterator of array is given

- 1of 1 vote
Google

Given two lowercase strings, S1 and S2, sort S1 in same order as S2.

If a character in S1 doesn't exist in S2, put them at the end. If S1 is "program" and S2 is "grapo", then return "grrapom".

- 2of 2 votes
Twitter

Count number of each character in a string and print out the counts from highest to lowest.

- 0of 0 votes
find max path sum in DAG, weight can be negative

- 2of 2 votes
Search for a target value from a sorted array with unknown size.

- 1of 1 vote
Adobe (phone)

Return the value of the item k away from the end of a linked list

- 2of 2 votes
Find a byte array in a byte file.

For e.g.

finding arr = bytearray([3,4,5,3]) in byte file ([24,3,4,5,3,4,5,3,9, 255,...])

output: 1, 4, ...

since arr is found at idx 1, 4, ...

- 0of 0 votes
Given a string as input, return the list of all the patterns possible:

`'1' : ['A', 'B', 'C'], '2' : ['D', 'E'], '12' : ['X'] '3' : ['P', 'Q']`

Example if input is '123', then output should be [ADP, ADQ, AEP, AEQ, BDP, BDQ, BEP, BEQ, CDP, CDQ, CEP, CEQ, XP, XQ]

- 0of 0 votes
Given an Input file of IPv4 addresses, filter and write them into Valid and Invalid IPs.

Input file = ["192.100.0.1, "10.0.0.1", "aa.bb.cc.dd", "10.0", "999.10.10.1"]

Valid = []

Invalid = []

- 2of 2 votes
Jet.com

Print a matrix in zigzag traversal (diagonally).

For matrix

1 2 3 4 5 6

7 8 9 10 11 12

13 14 15 16 17 18

19 20 21 22 23 24

Print

1 2 7 13 8 3 4 9 14 19 20 15 10 5 6 11 16 21 22 17 12 18 23 24

- 0of 0 votes
Evaluate infix expression: 2 + 3 * 5

- 0of 0 votes
Interleave two singly linked lists into one.

LL1: 1 -> 2 -> 3 -> 4

LL2: 10 -> 20 -> 30 -> 40 ->50

Output LL1: 1-> 10 -> 2 -> 20 -> 3 -> 30 -> 4.

Note: Stop when we hit null for LL1.

- 1of 1 vote
Dropbox

Grid Illumination: Given an NxN grid with an array of lamp coordinates.

Each lamp provides illumination to every square on their x axis,

every square on their y axis, and every square that lies in their diagonal

(think of a Queen in chess).

Given an array of query coordinates,

determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on,…

- 1of 1 vote
March 2018 Phone Interview FB

Calculate a moving average that considers the last N values.

Circular Queue (Interviewer didn't agree with the linked list queue that I suggested at first. Said the pointers took space)

- 2of 2 votes
Feb On-site Google

DP Problem. Given the length and width of a matrix, get the number of paths from bottom-left to bottom right.

You may only walk into those 3 directions ➡ (right) ↗ (upper-right) ↘ (lower-right) at each point.

Follow-up: optimize 2d DP to 1d DP of linear extra space.

Follow-up: what if some cells are blocked

System Design

Availability test/debug on distributed system. Discussed and drafted about failover, replication, NoSQL etc.

Interviewer seemed to be expecting more but time ran out.

- 2of 2 votes
Feb On-site Google

Print all numbers satisfying the expression 2^i * 5^i (where i, j are integers i >= 0 and j >= 0) in increasing order up to a given bound N.

2^i stands for power(2, i).

- 0of 0 votes
Given the description of the ancient castle that contains years (e.g 910, 1111, 1560, 1809), centuries (X, XII, IX or 11th c, 15th c). The years and centuries might repeat many times.

Assume that the centuries are equals(e.g XI = 1000, XV = 1400, 16th c = 1500)

Find the first historical mention about the castle in the text if you know that the very first mention could not be under 601 year.

- 0of 0 votes
Write a simple RegEx parser function that handles only the

operators * (0 or more) and + (1 or more), and returns true if

the provided string is a match. Signature:

boolean isMatch(String regex, String input).

Example: regex = a*b+ce, input = bce, return true

Example: regex = a*b+ce, input = ace, return false

Example: regex = a*b+ce, input = abcee, return false

- 0of 0 votes
Given a tree and a number N,

construct another tree such that each node of the tree has either 0 or

N elements,except for one node which has between 0 to N elements.

Only other constraint is

that ancestry is preserved in the new tree.

- 0of 0 votes
given start and end of a given set of meetings, asking how to schedule

as many meetings as possible。

- 0of 0 votes
Given two input arrays, return true if the words array is sorted according to the ordering array

Input:

words = ['cc', 'cb', 'bb', 'ac']

ordering = ['c', 'b', 'a']

Output: True

Input:

words = ['cc', 'cb', 'bb', 'ac']

ordering = ['b', 'c', 'a']

Output: False

- 2of 2 votes
Give the following input, output if the array is sorted according to the ordering array given. Return true or false.

Input:

words = ['cc', 'cb', 'bb', 'ac']

ordering = ['c', 'b', 'a']

Output: True

Input:

words = ['cc', 'cb', 'bb', 'ac']

[bb cb cc ac]

ordering = ['b', 'c', 'a']

Output: False

- -1of 1 vote
Define a class 'Space' which has a member string variable that indicates if the space is a "tree", a "house" or an empty space and another member variable that will store the 'space neighbors' (left, right, up and down only)

Given a 'Grid' (list) of Spaces write the code for the findAll(start) method to find all the trees and houses given a 'Space' as start point

Example, Grid of 'Spaces':

T 0 0 H 0

0 0 0 0 0

H H T H 0

Where Ts are trees and Hs are houses

- 0of 0 votes
Given a binary tree (not only BST) return the length of the longest consecutive sequence. The sequence can be between ANY TWO nodes and not only from root to leaves.

For example:`- 2 / \ 1 3 / / \ 0 4 7 / 10`

Should return 5: 0->1->2->3->4

- -1of 1 vote
I am surprised by this GS question.I thought this is one of the classic number theory partition problem which is so hard that the best algorithm is approximation one.

Given value, find all possible combination of ways which equals to that sum.