Twitter OA

Posted by James

Twitter Online Assessment

K-Difference OJ
Reaching Point OJ
Activate Fountain OJ
Twitter Social Network
Sub-palindrome
Coloring The Blocks

Twitter OA : K-Difference

.

Given an array of distinct integers and a target value, determine the number of distinct pairs of integers in the array with an absolute difference equal to the target amount. Two pairs are distinct if they differ in at least one value. To illustrate, the pairs (1, 3) and (3, 2) are distinct. The pairs (1, 3) and (3, 1) are not.
For example, given the array a = [1,3,5] and a target difference k = 2. There are two pairs: [1,3] and [3,5], that have the target difference.

Function Description
Complete the function kDifference in the editor below. The function must return an integer that represents the number of distinct pairs in a having a difference of k.
kDifference has the following parameter(s);
a[a[0]....a[n-1]]: array of integers
k: the target difference
Constraints
• 5 <= n <= 10^5
• 0 < a[i] <= 2 * 10^9
• Each a[i] is distinct, i.e. unique within a.
• 1 <= k <= 10^9

Sample Input :
[1, 5, 3, 4, 2, 2]

Sample Output :
3

Explanation
Count the number of pairs in a = [1,5, 3, 4, 2] whose difference is k = 2. The following three pairs meet the criterion: (1,3), (5, 3), and (4,2).

Sample Input :
[363374326,364147530,61825163,107306571,128124602,139946991,428047635,491595254,879792181,106926279]

Sample Output:
0

Explanation:
Count the number of pairs in a = [363374326, 364147530, 61825163, 107306571, 1281246024, 139946991, 428047635, 491595254, 879792181, 106926279] whose difference is k = 1. Because no such pair of integers exists in a, return 0.

Sample Input :
[6,2,4,6,8,10,12,2]

Sample Output :
5

Explanation:
Count the number of pairs in a = [2, 4, 6, 8, 10, 12] whose difference is k = 2. The following five pairs meet the criterion: (2,4),(4, 6), (6,8), (8, 10), and (10, 12).


Solve the problem:








Reaching Point

.

There is a bot that located at a pair of integer coordinates, (x,y). It must be moved to a location with another set of coordinates. Though the bot can move any number of times, it can only make the following two types of moves:

1. From location (x, y) to location (x + y, y).

2. From location (x, y) to location (x, x + y).

For example, if the bot starts at (1, 1), it might make the following sequence of moves: (1, 1) -> (1, 2) -> (3, 2) -> (5,2). Note that movement will always be either up or to the right.

Given starting and target ending coordinates, determine whether the bot can reach the ending coordinates given the rules of movement.

Function Description

Complete the function canReach in the editor below. The function must return True if the bot can reach its goal, otherwise return False.

canReach has the following parameter(s):

x1: integer value, starting x coordinate

y1: integer value, starting y coordinate 

x2: integer value, target x coordinate

y2: integer value, target y coordinate

Constraints

• 1 <= x1, y1, x2, y2 <= 1000

Input: 

1, 4, 5, 9

Output:

False


Solve the problem:








Twitter Social Network

.

Twitter follower relationships graph may be represented in a matrix as a series of binary digits. For example, the direct relationships for person with persons 0 through 5 might be shown as 101100. This means that person O follows persons 0, 2 and 3, the indices of each of the 1 values. A follower relationship is transitive for the context of this problem. In other words, if person O follows person 2 and person 2 follows person 3, then person 0 indirectly follows person 3 through person 2. Person 0 and person 3 are said to be in an indirect relationship. A group is composed of all of the people who are in a relationship, either directly or transitively,

For example, consider the following relationships matrix:
110
110
001

Persons 0 and 1 are connected, while person 2 is not. There are 2 groups.
Determine the number of groups represented in a matrix.

Note: The method signatures may vary a little depending on the requirements of your chosen language. For example, C language will have an argument that represents the number of rows and columns in the matrix.

Function Description
Complete the function countGroups in the editor below. The function must return an integer representing the number of groups of people.

countGroups has the following parameter(s):
related[related[0],...related[n-1]]: an array of strings of binary digits related[i] that represent direct connections of people

Constraints
• 1 <= n <= 300
• 0 <= i < n
• |related| = n
• Each related[i] contains a binary string of n zeroes and ones. related is a square matrix.

Sample Input :
4
1100
1110
0110
0001
Sample Output :
2
Explanation
There are n = 4 people numbered related[0] through related[3]. There are 2 pairs who directly know each another: (related[0], related[1]) and (related[1], related[2]). Because a relation is transitive, the set of people related[0], related[1], related[2]} is considered a single group. The remaining person, related[3], doesn't know any other people and is a separate group: {related[3]]. There are a total of 2 groups.

Sample Input :
5
10000
01000
00100
00010
00001
Sample Output :
5
Explanation
No direct relationships are shown so there are 5 groups: {related[0]}, {related[1]}, {related[2]}, {related[3]}, and {related[4]}.

Activate Fountain

.

There is a one-dimensional garden of length n. In each position of the n length garden, a fountain has been installed. The fountain at the ith position has a value a[i] (where 1 <= i <= n) that describes the coverage limit of fountain i. A fountain can cover the range from the position max( (i - a[i]), 1) to min ((i + a[i]), n).

For example, if garden length n = 3 and a = {1, 2, 1}, then:

For position 1: a[1] = 1, range = 1 to 2.

For position 2: a[2] = 2, range = 1 to 3.

For position 3: a[3] = 1, range = 2 to 3.

In the beginning, all the fountains are switched off. Determine the minimum number of fountains you need to activate so that whole n length garden will be covered by water. In the example, the 1 fountain at position a[2] covers the whole garden.

Function Description

Complete the function fountainActivation in the editor below. The function must return an integer that denotes the minimum number of fountains that must be activated to cover the entire garden by water.

fountainActivation has the following parameter:

a[a[O)... a[n-1]]: an array of integers

Constraints

• 1 <= n <= 10^5

• 0 <= a[i] <= min( n, 100) (where 1 <= i <= 10^5)

Sample Input

3,1,1,1

Sample Output

1

Explanation

Here, a = {1, 1, 1)

If the 2nd fountain is active, the range from position 1 to 3 will be covered. The total number of fountains needed is 1.


Solve the problem:








Twitter OA : Sub-palindrome

.

Twitter users love word play. Imagine a Twitter feature that finds palindromes in tweets!
A palindrome is a string that reads the same forward and backward, e.g. 121 or tacocat. A substring is a contiguous subset of characters in a string. Given a strings, how many distinct substrings of s are palindromes?

For example, s = mokkori. Some of its substrings are [m,o,k,r,i,mo,ok, mok,okk,kk,okko]. Each of the red elements is a palindromic substring of s. In total, there are 7 distinct palindromes.

Function Description
Complete the function palindrome in the editor below. The function must return the number of distinct palindromes as an integer.

palindrome has the following parameter(s):
s: a string

Constraints
• 1 <= |s| <= 5000
• Each character s[i] is in ascii[a-z]

Sample Input :
s=aabaa
Sample Output :
5
Explanation
Palindromic substrings are [a, aa, aabaa, aba, b]
The substring 'a' occurs 4 times, but is counted only once. Similarly, the substring 'aa' occurs twice but counts as one distinct palindrome.

Twitter OA : Coloring the blocks

.

There are n blocks placed in a row. Each block must be covered with one of the three colors available, but no two adjacent blocks can be the same color. The cost of coloring each block varies and is given in an array. Given the cost of using each color on each block, determine the minimum cost to color all of the blocks.

For example, there are three blocks to color and the cost to use each color for each block is given as cost = [[1,2,3], [1,2,3], [3,3,1]]. For the first block, the cheapest color is the first color which costs 1. For the second block, colors cost the same but color 1 cannot be used because it matches the first block. Instead, choose color 2. For the third block, it can be color 1 or color 3. The cheaper is color 3 at 1 unit. The total cost to color the blocks is 1 + 2 + 1 = 4.


Function Description
Complete the function minPrice in the editor below. The function must return an integer that denotes the minimum cost to color all of the blocks.
minPrice has the following parameter:
cost[cost[0]...cost[n-1]]: an array of integers where cost[i][j] denotes the cost of using the jth color on the ith block.

Constraints
• 1 <= n <= 100
• 0 <= cost[i][j] <= 100

Sample Input :
3
3
1 2 2
2 2 1
2 1 2
Sample Output :
3

Explanation
Choose the cheapest color for each block: color 1 for block 0, color 3 for block 1 and color 2 for block 2.

Sample Input :
3
3
1 2 2
2 3 3
3 3 1
Sample Output :
5

Explanation
Choose color 1 for block 0, color 2 for block 1 and color 3 for block 2. Even though color 1 is cheaper to use for block, 1, the same color cannot be used on adjacent blocks.

 

More Twitter OA updates are on the way. Follow us....

.


Get one-to-one training from Google Facebook engineers

One-on-One Algorithm and Coding Training

One-on-One System Design Training

One-on-One Mock Interview


Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.aonecode.com
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.


Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.


Free Consultation

aonecoding@gmail.com