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

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 4/4
Build HTML Reverser
Given
<A>(hello)(<P>ab</P>)(<S>hi</S>)</A>
Return
<A>(<S>ih</S>)(<P>ba</P>)(olleh)</A>

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.

April Google Interview 2/4
Count Number Given Array
Level1 Unsorted Array [1, 3, 2, 1, 2 ,3 , 4, 10]
Find occurrence of 1
Level 2 Sorted Array
Find occurrence of 1

Table: Customers
id | name

1|alice
2|bob
3|carol

Table: Orders
id | customer_id | content

1|1|House
2|2|car
3|2|dog
4|10|cow

please write a query which returns all of the invalid orders (where invalid means their customer_id does not have an associated customer)

4|10|cow

Suppose you have a list of tasks which need to be executed. Some of these tasks have dependencies which must be executed before they are. Please provide a method which, when given a list of tasks, will provide a valid ordering in return.

Example:
Input: [ A, B, C, D ]
A <- B, C
B <- C, D
D <- C
Return: [ C, D, B, A ]

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

You are given an array of strings. For example, ["AB", "BC", "FOO", "ZA", "BAZ"]
- Output strings where you can get from one to the other using any ROT transformation.

ROT_1(AB) = BC
ROT_1(BC) = CD
ROT_25(AB) = ZA
AB,BC you can go from one to the other using ROT_1
Input: list of strings
Output: strings where you can get from one to the other using any ROT transformation.
Example:
Input : ["AB", "BC", "FOO", "ZA", "BAZ"]
Output: [ [ab, bc] , [ab, za] ]
AB,BC because you can go from one to the other using ROT_1
AB,ZA because you can go from one to the other using ROT_25
Do not return FOO, BAZ you can’t get from one to the other.

How do you go about the phone interview for troubleshooting a problem, say "my computer has become slow 3 times from the last week.". Can someone please give the detailed explanation of how to go about this question. Also, "my internet is not working". How to go about these 2 troubleshooting problems in the phone interview?

Given list of schedules for different flights in a month, determine maximum number of flights that can be in the air anytime in that month.
Input : list of schedules for flights.- spread over a month.

output: a number - maximum flights that can be in the air
Assumptions: 1. All the given times are in a specific timezone( like GMT).
2. Given Schedules can be any time in the month

Given a list of N threads detect a deadlock in the system.

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".

Using Google BigQuery documentation, provide at least three (3) possible failure modes that could cause following customer problem:

""" I am ingesting data regularly in streaming mode into my mobile-events table, querying the data back however shows timestamps six hours behind. Please help. """
You can use public BigQuery documentation for the client side and make assumptions about the serving side based on your experience with other similar products, provided the serving stack spreads across multiple machines and microservices.

BIG DAT AND MACHINE LEARNING
Hi Cloud Support,
I have records like this in BigQuery:
logs.datetime: ''2017-07-01T13:51:03"
logs.type: "worker"
logs.message: "Starting pipeline"
apps.name: "reader_af45c9"
apps.log_type: "worker"
And I'm trying to run this query:
select logs.datetime, logs.type, logs.message, apps.name
from logs inner join apps on logs.type = apps.log_type
where logs.datetime > "2017-07-01T00:00:00" and logs.datetime < "2017-07-02T00:00:00"
group by apps.name;
But it's not working. Can you help me?

A sample state of ‘a’:
[[2, NULL, 2, NULL],
[2, NULL, 2, NULL],
[NULL, NULL, NULL, NULL],
[NULL, NULL, NULL, NULL]]
FUNCTION foo()
FOR y = 0 to 3
FOR x = 0 to 3
IF a[x+1][y] != NULL
IF a[x+1][y] = a[x][y]:
a[x][y] := a[x][y]*2
a[x+1][y] := NULL
END IF
IF a[x][y] = NULL
a[x][y] := a[x+1][y]
a[x+1][y] := NULL
END IF
END IF
END FOR
END FOR
END FUNCTION

Design a turn-by-turn application. Prioritize v1 features and tell why

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.

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).

check if there are two subarrays in an array are identical

comparison of two strings if they are the same, use o(1) space
abc \ b is equal to ab
abc \ ca equals abcA

\ b = backspace
\ c = CapsLock

convert Prefix to Postfix using recursion
+ * A B / C D -> A B * C D / +

Design a dictionary with historical records
t0: hdict = HistoricalDict ()
t2: hdict.set ('foo', 1)
t4: hdict.set ('foo', 2)
t5: hdict.get ('foo', t5) -> 2
t6: hdict.get ('foo', t3) -> 1
t7: hdict.get ('foo', t0) -> None

CSS colors can be defined in the hexadecimal notation "#rgb", a shorthand for "#rrggbb". For example, "#03f" is equivalent to "#0033ff". Suppose the similarity between two colors "#abcdef" and "#ghijkl" is defined as (-(ab-gh)^2 - (cd-ij)^2 - (ef-kl)^2), write a function that accepts a color in the "#abcdef" format and returns a "#rgb" color that is most similar to the input. For example, given "#09f166", "#1e6" should be returned.

Given a binary tree, output the maximum EVEN sum along any path
      10
     /    \
    2      5
   /  \      \
  1   101    13
Maximum even sum = 101 +2 +10 + 5 = 118

convert a Sorted linkedList to complete BST

Give N socks, there is no guarantee that each can be paired, socks two colors, black and white, you need to pair them

css color format # abcdef, another abbreviated color format # rgb
(Converted to the previous format, ie, #rrggbb.) Now give your #abcdef, the first color format, to find the two least different colors, #rgb.

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.

Given list of edge in the graph, find the number of reversed pairs,(1,2)
and (2,1) are such pair. Follow up: How to implement the distributed version.