## Twitter Online Assessment

K-Difference OJReaching 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

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