CareerCup

Find all triplet that sum to a given value in an array of integers, given that the array is too big to fit into memory

Give an array A of n integers where 1 <= a[i] <= K.
Find out the length of the shortest sequence that can be constructed out of numbers 1, 2, .. k that is NOT a subsequence of A.
eg. A = [4, 2, 1, 2, 3, 3, 2, 4, 1], K = 4
All single digits appears. Each of the 16 double digit sequences, (1,1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2) ... appears. Because (1, 1, 2) doesn't appear, return 3.

Write a function that takes a magic number and a list of numbers. It returns true if it can insert add or subtract operations in the list of numbers to get the magic number. Otherwise, it returns false.

For example:

f(10, [1,2]) = false. There's no way to add or subtract 1 and 2 to get 10.
f(2, [1,2,3,4]) = true. 1 + 2 + 3 - 4 = 2.
f(0, []) = true
f(1, []) = false
f(1, [1]) = true
f(0, [1]) = false

Implement a rate-limiter-like iterator and how to improve the space complexity

Given a <Word, TimeStamp> pair data type iterator as input. Implement an iterator based on it which can ignore the item if the same word has occurred in the past 10 seconds.

My implementation is to use a HashMap to memorize the word and its latest timestamp + 10s. For each new item, it will be checked against the HashMap to see if it has duplicated word occurred in the past 10s.

The interviewer asked me how to improve the space complexity if the string value varieties are infinite. He mentioned some boundary stuff.

Could anyone share some thoughts?

Multi -level cache system design with different storage in each level.
Read Operation : – Minimum time to read a particular key from cache system. This should be followed by writing the key in all levels above it. Eg. if “key” is found at level ‘i’, add this key to cache present at 1 to i-1 level.

b. Write Operation: – Any write Operation should write in cache of all levels.

You can choose any algorithm for cache management like LRU, MRU.

Reverse a linked list

there is a 2d array and gbikes are located in that location. there is a person and he wants to know the nearest location of the bike which is available for him(there can be more than 1 nearest bike). person can only move left , right , up or down. output should be the distance in int.

Design a system like github.

A city represented by a rectangular matrix is divided into plot of lands, and the cost of each plot is known. Find the largest rectangular area of land we can buy, within a budget B.

4 6 7
3 5 2
2 4 5

B = 16

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

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.

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.

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