谷歌新加坡实习 OA

[ttz]

Singapore Summer 2020 Internship
面试用的是 CoCubes

Question #1:

GCD (Greatest Common Divisor) of two positive integers is the largest positive integer that divides both numbers without a remainder.
Siblings: Nodes with the same parent are called siblings.
Level of a tree: Level of a tree is the number of edges on the longest path from the root node to a leaf.
You are given nodes of a binary tree of leven n as input.
Caluclate the GCD of each pair of siblings and then find the max & min GCD among them. Print the difference of max & min GCD ( max GCD - min GCD)

Note:

• Print -1 if input tree is empty i.e level of tree is -1.
• Consider those nodes which have a sibling
• Print 0 if no such pair of siblings found

Input Format:

The input is in the following format:

• The first line takes an integer n as input which represents the level of tree (the root node is at 0 level). (if level is equal to -1, means empty tree)
• Next n+1 lines contain the nodes in the tree level order. Each i’th line represents the nodes present in the binary tree in i’th level.

1st line contains level 0 nodes. (i.e. root node).
2nd line contains nodes for level 1.
3rd line contains nodes for level 2 and so on.
Each node is represented by an integer value. Node value of -1 denotes an empty node(no node present at that place).

Output Format:

A single integer i.e., the difference of max & min GCD (max GCD - min GCD)

Constraints:

• -1 <= level of tree <= 20
• 0 < element at nodes of tree <= 500

[alp]

第二题方便告诉吗？

[ttz]

Question #2:

Relative sorting is defined as sorting two arrays (both in strictly ascending order) such that the only operation allowed is swapping i’th element of one array with the i’th elementh of the other array
An array is said to be in strictly ascending order if i’th element of the array is smaller than (i+1)'th element of the array.
You are given two arrays of size N. print the minimum number of swaps required to make both arrays relatively sorted.

Note:

• If the arrays are already relatively sorted, then print ‘0’
• If the arrays cannot be relatively sorted, then print ‘-1’.

Input Format:

The input consist of 3 lines:

• First line consist of the size of each array, i.e. N
• The next two lines contain N elements each seperated by a space

Output Format:

The output will be an integer i.e., the minimum number of swaps required to make both arrays relatively sorted.

Constraints:

• 0 < N < 11000
• 0 < Elements in array <= 10^9

Example:

Input:
4
1 4 4 9
2 3 5 10
Output:
1

[cloud]

[匿名1305]

[bm18369 (迷你宝马)]

Problem Statement :
There are several projects, and each is denoted by a one letter name. Each project may depend on one or more other projects (or none). For example, if project A depends on project B, then project A cannot complete before project B. Suppose you are given a list L, of K such dependencies, and also a list D, of J projects that have been delayed. Output a list of all projects that will be delayed, in lexicographical (alphabetical) order. You can assume that a project, A, will be delayed if any project A depends on is delayed. The input is guaranteed to contain no circular dependencies.

Input :

Test cases will be provided in the following multiline format. The first line contains one integer, C , which is the number of test cases that will follow. Each test case has the following format.

The first line of a test case contains two integers, K and J , separated by a space. K is the number of dependencies, and J is the number of delayed projects. K lines follow, each with the format:

XY

where X and Y are the names of projects and project X depends on project Y, project names are single uppercase English letters. Each pair gives a project dependency: Y must complete before X can complete. All K lines together form the list L of project dependencies.

Finally, the last line contains J space-delimited project names (single letters, uppercase). This gives the list D of length J of projects that have been delayed. Each project in D is listed in the dependency list at least once.

Limits :

• Test case count: 1 <= C <= 20
• Number of dependencies: 1 <= K <= 100
• Number of projects: 1 <= J <= 26
• Project name: Each name is a single uppercase letter from A to Z.

Outputs :
For each test case, output one line containing the test case index, starting from 1, followed by a space-delimited list of projects that will be delayed, do not add any space at the end of each line of output. The list must be in lexicographically sorted order. The resulting line should be in this format:

Case #i: X[1] X[2]…

where i is the index of the test case, starting from 1, and X[k] are the names of the projects that were delayed.

Sample Inputs :
3
2 1
B A
C B
B
5 2
P Q
P S
Q R
R T
S T
Q S
8 2
B A
C B
C E
D C
D F
E A
F E
G F
B F

Sample Output :
Case #1: B C
Case #2: P Q S
Case #3: B C D F G