Citadel Interview Questions

What is covariance?

Build a linked list in Java.

Implement a balanced binary search tree from scratch and explain its time complexity. Additionally, optimize the tree to efficiently handle duplicate values.

Given an array representing a sequence of user events (where each element is a user ID), find the length of the longest contiguous subarray where the most frequent user's frequency within the subarray equals the minimum frequency of any user in the entire event log. Implement an efficient function to return this maximum length.

Implement a linked list data structure in Java.

Design a financial instrument trading system. How would you ensure atomicity, consistency, and other key transactional properties in the system?

Given the head of a singly linked list, reverse the list and return the new head.

Given an array of points representing the elevations of a mountain (as a sequence of integers), and a specific position within this array, what is the highest point visible from that position?

Implement a queue using a stack.

Given a set of numbers [a, b, c, d, e] and a target value t, find the number of triplets in the set whose sum is at most t.

Given a CSV file as input, write a program to convert it to columnar data format.

Given a sentence containing three types of brackets (e.g., (), {}, []), determine if the brackets are properly balanced and in the correct order.

Given a sorted array of integers and a target integer, can you find two numbers in the array such that their sum equals the target?

Describe an algorithm for calculating the square root of x.

Given a binary tree, write a function to determine if it is a valid binary search tree.

Implement a hash table with collision handling using probing.

Design and implement a defaultdict class in Python using object-oriented design principles.

Given a matrix and the top-left and bottom-right coordinates of a submatrix, calculate the sum of the submatrix in (1) linear time and (2) constant time. You are allowed to preprocess the matrix.

Write code to implement a multi-reader/single-writer lock.

You have a worker and a gold bar. The worker will work for you for 15 days. He must have x/15 of the gold bar after the xth day of work. What is the minimum number of cuts you need to make to the gold bar to pay the worker accordingly?

Implement a function to compute the nth Fibonacci number using memoization.

Find the number of ways to get from one corner of a grid to the opposite corner, moving only down or right at each step.

How do you reverse a linked list?

Given an 8x8 chessboard, write code to calculate the number of ways to go from the top left corner to the bottom right corner, where you can move down, up, left, or right at each step.

Explain the difference between Lasso and Ridge regression.

Given three variables x, y, and z, where x is distributed as N(0,1), z is distributed as N(0, sigma^2), and y = x + z, with x independent of z: For a given observed value of y, what is the conditional distribution of x given y, i.e., p(x|y)?

What is an O(n log n) sorting algorithm? Give an example and briefly explain how it works.

Suppose you want to predict y and you have predictor vectors, each with known accuracy, variance, and sample length. How do you combine these predictors to minimize the residual standard error (RSE)?

There are three random variables, X, Y, Z. The correlations between each pair of variables are the same, i.e., ρ = Corr(X,Y) = Corr(Y,Z) = Corr(Z,X). What is the tightest bound you can give for ρ? How about the general case for n random variables?

What are the ways to construct a uniform distribution given only access to a fair coin?