Citadel Interview Questions

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.

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

Given an array representing user events, find the length of the longest contiguous subarray where the most frequent user in that subarray has the same number of events as the least frequent user in the entire event log. Write an efficient function to solve this problem.

How can a deadlock occur?

Given an array representing heights of points on a mountain and a starting position, what is the highest point that is visible from that position?

Given a set of numbers [a, b, c, d, e] and a target t, find the number of triplets from the set whose sum is less than or equal to t.

Given a sentence containing three types of brackets—parentheses (), square brackets [], and curly braces {}—determine if the brackets are properly matched and ordered.

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