Coral Associates Interview Questions and Answers

In a group of people with a symmetric relation of knowing each other, there will always be at least two people who know the same number of people.

• Consider the person who knows the maximum number of people in the group.

• If there is no one who knows the same number of people, then everyone else must know a different number of people.

• But this would mean that the total number of people known by everyone else is different from the total number of people known by the person who know...read more

For any subset of size n+1 of the set S of the first 2n numbers, there exists 2 numbers u and v such that u divides v.

• Divide the set S into two subsets of n numbers each.

• By the pigeonhole principle, at least one of the subsets contains two numbers whose ratio is an integer.

• If the subset contains n+1 numbers, then one of the numbers must be in the subset with the two numbers whose ratio is an integer.

• Therefore, there exists 2 numbers u and v such that u divides v.

Algorithm to determine visible buildings in a 2D plane with given positions and heights

• Sort the buildings by their x-coordinates

• Traverse the sorted buildings from left to right

• For each building, check if it is visible by comparing its height with the maximum height of previously visited buildings

• If visible, add it to the list of visible buildings

• Return the list of visible buildings

If dist(u,v)>n/2 in an undirected graph, there exists a vertex x such that removing x makes u and v go to different connected components.

• Find the shortest path between u and v

• If the path length is greater than n/2, then there must be a vertex x on the path

• Removing x will separate u and v into different connected components

Find the largest substring formed from repetition of a smaller string.

• Identify all possible substrings of the given string.

• Check if each substring can be formed by repeating a smaller string.

• Return the largest substring that can be formed from repetition of a smaller string.

For an odd-sized grid, there cannot be a Hamiltonian cycle in the graph.

• A Hamiltonian cycle is a path that visits every vertex exactly once and ends at the starting vertex.

• In an n*n grid, there are n^2 vertices and each vertex has degree 4.

• For an odd n, the total degree of all vertices is odd, which means there cannot be a Hamiltonian cycle.

Prove that F_nk is divisible by F_n where F_i is the ith Fibonacci number. with f_0 = 0

• Use mathematical induction to prove the statement

• Base case: F_n0 = 0, F_n is also 0, so 0 is divisible by 0

• Inductive step: Assume F_nk is divisible by F_n, prove F_n(k+1) is divisible by F_n

• F_n(k+1) = F_nk + F_n(k-1), use the assumption to show that F_nk is divisible by F_n

• Therefore, F_n(k+1) is also divisible by F_n

• Hence, the statement is true for all k

Prove that there exists a rectangle with all corners of the same color in a 2D plane with blue and red points.

• Divide the plane into a grid of squares.

• By the pigeonhole principle, there must be at least one row or column with four points of the same color.

• Consider the pairs of points in that row or column and check if any of them form a rectangle.