Summary
I participated in the Citadel Online Assessment for a 2025 Internship and encountered a challenging algorithmic problem focused on modular arithmetic and combinations.
Full Experience
During my online assessment for the Citadel 2025 Internship, I was presented with a complex algorithmic problem. The task involved calculating the total sum of C(i,j) = i mod j + j mod i for all 1<=i<=n and 1<=j<=n, with the final sum needing to be returned modulo (10^9 + 7). Although the exact constraints were not provided, it was explicitly stated that an O(n^2) solution would not be efficient enough, indicating a need for a more optimized approach.
Interview Questions (1)
Given an integer n, calculate the total sum of all combinations C(i,j), where (1<=i<=n && 1<=j<=n) and where C(i,j) = i mod j + j mod i. Since the result can be very large, return the final sum modulo (10^9 + 7).
Function signature: int solve(int n)
Example:
int n = 3
C(3,3) = 3 mod 3 + 3 mod 3 = 0 + 0 = 0
C(3,2) = 3 mod 2 + 2 mod 3 = 1 + 1 = 2
C(3,1) = 3 mod 1 + 1 mod 3 = 2 + 2 = 4
C(2,3) = 2 mod 3 + 3 mod 2 = 1 + 1 = 2
C(2,2) = 2 mod 2 + 2 mod 2 = 0
C(2,1) = 2 mod 1 + 1 mod 2 = 1 + 1 = 2
C(1,3) = 1 mod 3 + 3 mod 1 = 4
C(1,2) = 1 mod 2 + 2 mod 1 = 2
C(1,1) = 1 mod 1 + 1 mod 1 = 0
TotalSum = 0+2+4+2+0+2+4+2+0 = 16
It was noted that an O(n^2) solution would not pass.
Summary
I had my first round interview with Citadel for their NXT program, where I was asked to design a data structure for finding the median from a data stream. Despite feeling the session went well and providing an optimized solution, I was rejected.
Full Experience
Just had my first round interview with Citadel for their NXT program. I’m a Senior Software Engineer with 3 years of experience in backend and infrastructure development, and this was my first step in their process.
Felt the session went well overall explained my thought process clearly, wrote working code, and optimized properly.
Result: Rejected the next morning.
Interview Questions (1)
Design a data structure that supports two APIs:
insert(num: int)
findMedian(): float
Essentially, this is the classic "Find Median from Data Stream" problem available on LeetCode here.
Summary
I had a phone screen with Citadel where I was asked to implement a Trie and its supporting functions, followed by an optimization question and a bonus question to find the longest prefix. I cleared the round.
Full Experience
Implement Trie and it's supporting functions -
* insert(word) - Insert a word in the trie,
- search(word) - search if the word exists in the trie, and
startsWith(prefix) - search if there exist any word which starts with <prefix>.
Clarified if we are only dealing with lowercase alphabets. Yes.
I implemented
TrieNodeclass TrieNode{
int val;
vector<TrieNode*> children;
};
Follow up question.
Currently, we are occupying 26 space for children. How can we optimize it ?
Suggested to use a Map instead of vector.
class TrieNode{ int val; unordered_map<int, TrieNode*> child; };
// int denotes 0 for 'a', 1 for 'b', or you can do char too in this case. // I chose int.
Looks good.
Bonus question.
Implement
longestPrefixWhichStartsWithPrefix(prefix) - find the longest prefix which starts with a given prefix.
prefix = abc
words = [abcdef, abcdeg] -> abcde
Cleared the round.
Interview Questions (2)
Implement Trie and it's supporting functions -
* insert(word) - Insert a word in the trie,
- search(word) - search if the word exists in the trie, and
startsWith(prefix) - search if there exist any word which starts with <prefix>.
Clarified if we are only dealing with lowercase alphabets. Yes.
Implement
longestPrefixWhichStartsWithPrefix(prefix) - find the longest prefix which starts with a given prefix.
prefix = abc
words = [abcdef, abcdeg] -> abcde