## Recent Interview Questions

- 0of 0 votes
We say that a character is unique in string S if it occurs exactly once in it. For example, in string S = "ACAX", the only unique characters are "C" and "X".

Let's define UNI(S) as the number of unique characters in string S. For example, UNI("ACAX") equals 2.

Given a string S, calculate the sum of UNI(S') over all non-empty substrings S'. If there are two or more equal substrings at different positions in S, we consider them different.

Since the answer can be very large, provide it modulo 1,000,000,007 (109 + 7).

Write a function:

class Solution { public int solution(String S); }

that, given a non-empty string S consisting of uppercase letters, returns the sum of UNI(S') over all non-empty substrings S' of S modulo 1,000,000,007.

For example, given "ACAX", your function should return 16, as explained visually as follows:

UNI("A") = 1

UNI("AC") = 2

UNI("ACA") = 1

UNI("ACAX") = 2

UNI("C") = 1

UNI("CA") = 2

UNI("CAX") = 3

UNI("A") = 1

UNI("AX") = 2

UNI("X") = 1

Total: 16

Given "CODILITY", your function should return 96.

Assume that:

the length of S is within the range [4..100,000];

string S consists only of uppercase letters (A−Z).

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

- 2of 2 votes
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,…

- 0of 0 votes
Given a pyramid of consecutive integers:

1

2 3

4 5 6

7 8 9 10

11 12 13 14 15

16 17 18 19 20 21

......

Find the sum of all the integers in the row number N.

For example:

The row #3: 4 + 5 + 6 = 15

The row #5: 11 + 12 + 13 + 14 + 15 = 65

- 0of 0 votes
find longest common suffix of two linked list.

- 0of 0 votes
Design a system to support a pool of servers. The pool Api should be able to add a server, get a server (can be random) and delete a server from the pool.

You need to design and implement an interface for such pool.

The pool implementation should operate with a high performance so all operations need to be done in O(1).

- 2of 2 votes
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)

- 0of 0 votes
Design bookshelf class model to perform checkout of book operation

- 0of 0 votes
Tell me how to test whether the high-order bit is set in a byte?

- 0of 0 votes
When would you use a linked list vs. arraylist?

- 0of 0 votes
Suppose under this directory /web there are 50,000 - html files

List all the files which has phone numbers with below pattern

(xxx)-xxx-xxxx

xxx-xxx-xxxx

- 0of 0 votes
Print out the grade-school multiplication table up to 12x12

multiplication output:`1 2 3 4 5 6 7 8 9 10 11 12 2 4 6 8 10 12 14 16 18 20 22 24 3 6 9 12 15 18 21 24 27 30 33 36 4 8 12 16 20 24 28 32 36 40 44 48 5 10 15 20 25 30 35 40 45 50 55 60 6 12 18 24 30 36 42 48 54 60 66 72 7 14 21 28 35 42 49 56 63 70 77 84 8 16 24 32 40 48 56 64 72 80 88 96 9 18 27 36 45 54 63 72 81 90 99 108 10 20 30 40 50 60 70 80 90 100 110 120 11 22 33 44 55 66 77 88 99 110 121 132 12 24 36 48 60 72 84 96 108 120 132 144`

*/

- 0of 0 votes
Write a program to read a string with first_name, last_name, age and sort it based on any of the input column name

sample string

john doe 33

smith black 9

diana yale 12

assume the string to be single giant string

- 0of 0 votes
How to design a system which allows millions of requests

- 0of 0 votes
Design an app which allows different types of jobs to be triggered at user specified delay

- 0of 0 votes
Implement below methods

//stores the number in some data structure

void store(n);

//tests whether the given number is present as sum of 2 numbers from the data structure store

boolean test(v);

e.g. store -> 1, 3, 5, 6

tests

4 = true (1 + 3)

5 = false (no sum will result into this)

6 = true (1 + 5)

- 0of 0 votes
write a program to list factors of a given number

e.g. for input as 12, factors are 1, 2, 3, 4, 6, 12

- 0of 0 votes
A group of friends are tracking the miles per gallon for each of their cars. Each time one of them fills up their gas tank, they record the following in a file:

His or her name

The type of car they drove

How many miles driven since they last filled up

How many gallons purchased at this fill up

Date of the fill

Their data is formatted as a comma separate value (csv) file with the following format for each row:(#person,carName,milesDriven,gallonsFilled,fillupDate)

Miles are recorded as floating-point numbers and gallons as integers.

Please create a program that allows members of this group to determine the miles per gallon (MPG) of each of their cars during a specific time range. Note: person may have more than one so a time range query might need to output data for one or more cars. A skeleton class will be provided; your job will be to complete the program.

The principal function for querying MPG is of the form (the exact name, data types, etc., can be learned by inspecting the "solution" class in the skeleton code):

GetRangeMPG(PersonName, StartDate, EndDate)

Returns list of objects containing (CarName, MPG)

MPG is calculated as (total miles traveled during time period)/ (total gallons filled during time period.

The dates you receive in the query should be treated inclusively.

- 0of 0 votes
Give a 0/1 matrix to find and remove the islands. Assume that the boundaries of the matrix are 1

The definition of islands is surrounded by 0

The simplest example is

enter:

111111

100001

100101

100001

111111

Output:

111111

100001

100001

100001

111111

- 0of 0 votes
Write a hash function so that a string and its reverse get the same return value

Hash(‘banana’) == hash(‘ananab’)

Hash(‘banana’) == hash(‘banana’)

Hash(‘banana’) != hash(‘banaaa’)

- 0of 0 votes
You need to design a new YouTube feature where userA is uploading a video and userB (friend of userA) gets notified for the video and wants to watch the same video in real time (i.e. even the video is not completely uploaded but we want to enable the other user to watch it).

How would you tackle the situation when userB wants to view the content starting from a position which is not yet uploaded.

Draw block diagram for this problem identifying the different components.

- -1of 1 vote
Design calculator and related class, which returns result of the given expression, e.g if input is (3* 3) + 2 it returns 11.

Identify different OOPS classes and how would you call them.

- 0of 0 votes
Given two positive integers represented as linked lists, provide the sum of the numbers as a linked list.

`1->2->3 4->5->6 ----------- 5->7->9 1->2->3 4->5 ----------- 1->6->8 4->5->6 7->8->9 ----------- 1->2->4->5`

- 0of 0 votes
Why facebook?

What was the biggest technical problem that you solved?

Do you have any apps on google play?

Give me a scenario where the requirements were ambiguous, what did you do?

- 0of 0 votes
Design Instagram like app end to end

- 0of 0 votes
Given a string "L*&EVe)))l", write a method which will determine if the input is a palindrome. Ignore all special characters. Uppercase/lowercase should be considered as same.

- 0of 0 votes
Imagine a room full of people, with only 1 celebrity in the room. Celebrity is defined as a person who does not know anyone, but everyone knows him/her. Write a method who will take array of people and a person as input and return boolean if the person is a celebrity or not.

- 1of 1 vote
A bus has to travel from A to B and the distance is d miles. There are many gas stations between A and B.

The bus has initially g gallon of gas in tank. 1 gallon of gas travels 1 mile.

Gas stations have inforamtion of remaining distance from station to destination b and max gas that can be filled from the station.

Find the minimum number of stops for bus without running out of gas ever.

eg: gas = 10 , distance = 20

gasStation[] = {{16,3}, {10, 7}, {14, 11},{11, 5}, {7, 6}}

o/p = 1

If bus stops at the stop{14,11} that is 14 miles away from destination and fills 11 gallon then it can reach destination with 1 gallon spare.

It can also stop as {16,3} and {10,7} but its 2 stops and at destination it runs out of gas.

Similarly {11, 5}, {7, 6} has 2 stops but has 1 gallon spare at destination.

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

- 3of 3 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
x={a,b,c}, y={p,q}, z={r,s}

Define a

Operation, x * y * z = {{a,p,r},{a,p,s},{a,q,r},{a,q,s}......{c,q s}}

Is to output all the results in the order of each subset, implementing a class iterator that has Next() and hasNext() methods