CareerCup

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.

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?

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

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?

find max path sum in DAG, weight can be negative

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]

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 = []

Evaluate infix expression: 2 + 3 * 5

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.

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,…

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)

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.

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.

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

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.

given start and end of a given set of meetings, asking how to schedule
as many meetings as possible。

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

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

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

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

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.

Google Fucked up question.

Given a random list of appointments (Start Date , End Date). Find all the appointments that are colliding.

This pretty easy looking question screwed me up today.There are tons of edge cases, I couldn't complete em all and 45 minutes pass like 15 minutes while explaining and coding same time.

You have two arrays of strings, words and parts. Return an array that contains the strings from words, modified so that any occurrences of the substrings from parts are surrounded by square brackets [], following these guidelines:

If several parts substrings occur in one string in words, choose the longest one. If there is still more than one such part, then choose the one that appears first in the string.

Example

For words = ["Apple", "Melon", "Orange", "Watermelon"] and parts = ["a", "mel", "lon", "el", "An"], the output should be
findSubstrings(words, parts) = ["Apple", "Me[lon]", "Or[a]nge", "Water[mel]on"].

While "Watermelon" contains three substrings from the parts array, "a", "mel", and "lon", "mel" is the longest substring that appears first in the string.

Given an integer n, replace its bits starting from the bit at position a to the bit at position b, inclusive, with the bits of integer k. Count from the least significant bit to the most significant bit, starting from 0.

Example:

For n = 1024, a = 1, b = 6 and k = 17, the output should be
insertBits(n, a, b, k) = 1058.
n = 100 0000 00002, k = 1 00012, 1058 = 100 0010 00102.

For n = 11, a = 1, b = 2 and k = 2, the output should be
insertBits(n, a, b, k) = 13.
n = 10112, k = 102, 13 = 11012.

Implement a function that takes two strings, s and x, as arguments and finds the first occurrence of the string x in s. The function should return an integer indicating the index in s of the first occurrence of x. If there are no occurrences of x in s, return -1.

Example:

For s = "AGoogleInterviewIsAwesome" and x = "IA", the output should be
strstr(s, x) = -1;
For s = "AGoogleIsAwesome" and x = "IsA", the output should be
strstr(s, x) = 10.

Apparently, my solution was not efficient enough with string lengths that are 2000+:

int findFirstSubstringOccurrence(String s, String x) {
    int sLen = s.length();
    int xLen = x.length();
    int tracker = 0;
    
    if (sLen == xLen) {
        if (s.equals(x)) {
            return 0;
        } else {
            return -1;
        }
    } else {
        if (xLen >= 1) {
            for (int index = 0; index < sLen; index++) {
                if (s.charAt(index) == x.charAt(tracker)) {
                    tracker++;
                    if (tracker == xLen) {
                        return index - (xLen - 1);
                    }
                } else {
                    index -= tracker;
                    tracker = 0;
                }
            }
        }
    }
    return -1;
}

Convert a string with digits into a literal representation of the number like: 1001 to one thousand one

Imagine a computer where you have no "/" (divide) operation. All other operations are implemented including addition, multiplication, binary shift etc. Implement function div(int a, int b) using available operators only.

Given the list of the numbers. In this list, there are the numbers from the Fibonacci sequence.
Write the algorithm that retrieves all the numbers which belong to the Fibonacci sequence of numbers.

Write a function that takes two numbers as strings and returns the result as a string:
mul(l string, r string) : string
Assume the numbers might be too large to be parsed into a variable of any numeric type the language has.

Give a decimal number, such as 123. Asking a total of smaller num than 123 made up by 1 and 0 composed of decimal numbers.
111, 110, 101, 100, 11, 10, 1, 0.