Citadel Interview Questions

Implement a class for the game Connect 4.

Given an array v, find the number of pairs of indices (i, j) such that v[i] = v[j] = v[i+1] + v[i+2] + ... + v[j-1]. Your solution should have time complexity O(n log n).

How would you solve a scheduling issue given a directed acyclic graph (DAG) of tasks and k computers? What if k is one or infinity?

Design an algorithm to randomly select people in a city such that the probability of selecting someone from a given district is proportional to the district's population size. Additionally, discuss how you would test your implementation and optimize its runtime, considering repeated calls to the selection function with an acceptable error margin.

If a Binary Search Tree was implemented incorrectly such that a node has a left child that is not smaller than itself, how would you detect this violation? What is the most efficient method to identify this issue?

Given an n x n chessboard, return the minimum number of knight moves required to get from point (a, b) to point (c, d).

Return a minimum-length list of perfect squares whose sum equals a given value k.

Reverse a linked list in place.

Implement a class for the game Connect Four.

Find the number of pairs of indices (i, j) in an array v such that v[i] = v[j] = v[i+1] + v[i+2] + ... + v[j-1]. Design an algorithm with time complexity O(n log n).

If a Binary Search Tree was implemented incorrectly, such that a number to the left of a node is not smaller as it should be, how would you detect this mistake? What is the most efficient way to identify such an error?