CareerCup

The wildcard regex can include the characters * and + .

‘+’ – matches any single character or empty character!

‘*’ – Matches any sequence of characters (including the empty sequence) For example,

Text = "baaabab":

regex = "ba*a++", output : true

regex = "ba*a+", output : true

regex = "a*ab", output : false

//empty string

Text=""

Regex= "+" , output : true

I was asked this question in a recent interview for a startup.

We have coffee vending machine with 3 buttons which can dispense 4oz, 7oz and 13oz of coffee.

Given a cup and the min and max amount(oz) of coffee it should fill. determine if the coffee vending machine can satisfy the condition.

The buttons can be pressed as many times as possible to fill the cup. Coffee shouldn't overflow..

AWS phone interview
Find the left view of binary tree
1
/ \
2 3
/\ \
4 5 6
/ /
7 8
/
9
return [1, 2, 4, 7, 9]

If b == “1”:
quit()

Write a method that can take in an unordered list of airport pairs visited during a trip, and return the list in order:

Unordered: ("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"), ("PDX", "ITO"), ("SEA", "PDX")
Ordered: ("ANC", "SEA"), ("SEA", "PDX"), ("PDX", "ITO"), ("ITO", "KOA"), ("KOA", "LGA"), ("LGA", "CDG")

April Google Interview 1/4
A = a+b-c-a-b-c-a-b (Tree)
B = b+a+c+a+b-c+b (Tree)
is A equal to B

April Google Interview 3/4
Maze
N,M array
Level 1 0,0 to N-1,M-1 => Path exsits?
Level 2 if path exists then print path
Level 3 if path exists then print min cost path
Level 4 O(nm log mn) using Priority Queue.

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

Find the largest duplicate subtree in a binary tree


For example,

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4
The following are two duplicate subtrees:

      2
     /
    4
and

    4

but the former is the largest, thus return the root of the first subtree

Given a target string, an input request replaces the word after the given index a->b such as:
Target string: "Hello world!"
Input:{s:0, a:Hello b: Goodbye}
Output:"Goodbye world!".
The requirement is that input be given to several words that need to be changed at one time: {{s:0,a:Hello,b:Goodbye},{s:11,a:!,b:?},{s:6 a: World,b:friend}}
And each modified index is based on the original unmodified target string so the end result is
"Goodbye friend?"

given a n-ary tree, find the total distance from this node to any other nodes

class TreeNode {
int val;
List<TreeNode> children;
TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}


public int findDistance(TreeNode root, TreeNode node) {

}

Assume courses labeled by their index in an array. Given a list of pairs where the first element represents a prerequisite course required for the second course, derive an ordered list of courses.

For a given set of non-negative integers get the number of subsets that add up to a target value k.

For a given array of integers compute the maximum sum of any range in the array. Then modify the function to find maximum product (note the effect of negatives on max product).

Write a function to compute n^k. (don't forget negative exponents)

Print (or return) the longest movie title found by successively matching the last and first words in each title, joining to form new titles, given a file containing a list of movie titles.
For example: 'OF MICE AND MEN' and 'MEN IN BLACK' join to form 'OF MICE AND MEN IN BLACK'.
You could further join 'OF MICE AND MEN IN BLACK' wth 'BLACK MASS' to form 'OF MICE AND MEN IN BLACK MASS'.

The longest title I found (at 143 characters is): WENT TO CONEY ISLAND ON A MISSION FROM GOD BE BACK BY FIVE WIVES THREE SECRETARIES AND ME WITHOUT YOU CANT TAKE IT WITH YOU WERE NEVER LOVELIER

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?

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