-
Notifications
You must be signed in to change notification settings - Fork 0
Data Structures and Algorithms Technical Interview Assessment
-
Explain the difference between an array and a linked list. When would you choose one over the other?
-
Compare and contrast the time complexities for common operations (access, insert, delete) on the following data structures:
- Array
- LinkedList
- Dictionary/HashMap
- Queue
- Stack
- Binary Search Tree
- Heap
-
Describe the concept of time complexity and space complexity. How do you determine the Big O notation for an algorithm?
-
What is the difference between a stable and unstable sorting algorithm? Provide examples of each.
-
Explain the concept of a hash collision and describe at least two strategies to handle collisions.
-
What is recursion? When is it appropriate to use recursion versus iteration? Provide an example of a problem that is well-suited for a recursive solution.
-
Describe the divide and conquer algorithm paradigm. Give an example of a sorting algorithm that uses this approach.
-
Explain the concept of dynamic programming. How does it differ from simple recursion?
-
What is a graph? Explain the difference between depth-first search (DFS) and breadth-first search (BFS).
-
Describe the difference between a greedy algorithm and dynamic programming. When would you use each?
Implement a function to find the maximum subarray sum in an array of integers.
public static int MaxSubarraySum(int[] nums)
{
// Implement Kadane's algorithm
int maxSoFar = nums[0];
int maxEndingHere = nums[0];
for (int i = 1; i < nums.Length; i++)
{
maxEndingHere = Math.Max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.Max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}Time Complexity: O(n) where n is the length of the array Space Complexity: O(1)
Implement a function to detect a cycle in a linked list.
public class ListNode
{
public int Value { get; set; }
public ListNode Next { get; set; }
public ListNode(int value)
{
Value = value;
Next = null;
}
}
public static bool HasCycle(ListNode head)
{
// Implement Floyd's Cycle-Finding Algorithm (Tortoise and Hare)
if (head == null || head.Next == null)
return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.Next != null)
{
slow = slow.Next; // Move one step
fast = fast.Next.Next; // Move two steps
if (slow == fast) // If they meet, there's a cycle
return true;
}
return false;
}Time Complexity: O(n) where n is the number of nodes in the linked list Space Complexity: O(1)
Implement in-order, pre-order, and post-order traversal for a binary tree.
public class TreeNode
{
public int Value { get; set; }
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
public TreeNode(int value)
{
Value = value;
Left = null;
Right = null;
}
}
public static List<int> InOrderTraversal(TreeNode root)
{
List<int> result = new List<int>();
InOrderHelper(root, result);
return result;
}
private static void InOrderHelper(TreeNode node, List<int> result)
{
if (node == null)
return;
InOrderHelper(node.Left, result);
result.Add(node.Value);
InOrderHelper(node.Right, result);
}
public static List<int> PreOrderTraversal(TreeNode root)
{
List<int> result = new List<int>();
PreOrderHelper(root, result);
return result;
}
private static void PreOrderHelper(TreeNode node, List<int> result)
{
if (node == null)
return;
result.Add(node.Value);
PreOrderHelper(node.Left, result);
PreOrderHelper(node.Right, result);
}
public static List<int> PostOrderTraversal(TreeNode root)
{
List<int> result = new List<int>();
PostOrderHelper(root, result);
return result;
}
private static void PostOrderHelper(TreeNode node, List<int> result)
{
if (node == null)
return;
PostOrderHelper(node.Left, result);
PostOrderHelper(node.Right, result);
result.Add(node.Value);
}Time Complexity: O(n) for all traversals, where n is the number of nodes in the tree Space Complexity: O(h) where h is the height of the tree (due to recursion stack)
Implement BFS and DFS for a graph represented as an adjacency list.
public class Graph
{
private Dictionary<int, List<int>> adjacencyList;
public Graph()
{
adjacencyList = new Dictionary<int, List<int>>();
}
public void AddVertex(int vertex)
{
if (!adjacencyList.ContainsKey(vertex))
adjacencyList[vertex] = new List<int>();
}
public void AddEdge(int source, int destination)
{
if (!adjacencyList.ContainsKey(source))
AddVertex(source);
if (!adjacencyList.ContainsKey(destination))
AddVertex(destination);
adjacencyList[source].Add(destination);
}
public List<int> BFS(int startVertex)
{
List<int> result = new List<int>();
HashSet<int> visited = new HashSet<int>();
Queue<int> queue = new Queue<int>();
if (!adjacencyList.ContainsKey(startVertex))
return result;
queue.Enqueue(startVertex);
visited.Add(startVertex);
while (queue.Count > 0)
{
int currentVertex = queue.Dequeue();
result.Add(currentVertex);
foreach (int neighbor in adjacencyList[currentVertex])
{
if (!visited.Contains(neighbor))
{
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
}
}
return result;
}
public List<int> DFS(int startVertex)
{
List<int> result = new List<int>();
HashSet<int> visited = new HashSet<int>();
if (!adjacencyList.ContainsKey(startVertex))
return result;
DFSHelper(startVertex, visited, result);
return result;
}
private void DFSHelper(int vertex, HashSet<int> visited, List<int> result)
{
visited.Add(vertex);
result.Add(vertex);
foreach (int neighbor in adjacencyList[vertex])
{
if (!visited.Contains(neighbor))
DFSHelper(neighbor, visited, result);
}
}
}Time Complexity:
- BFS: O(V + E) where V is the number of vertices and E is the number of edges
- DFS: O(V + E) Space Complexity: O(V) for both BFS and DFS
Implement a quick sort algorithm for an array of integers.
public static void QuickSort(int[] arr, int left, int right)
{
if (left < right)
{
int pivotIndex = Partition(arr, left, right);
QuickSort(arr, left, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, right);
}
}
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++)
{
if (arr[j] <= pivot)
{
i++;
Swap(arr, i, j);
}
}
Swap(arr, i + 1, right);
return i + 1;
}
private static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}Time Complexity:
- Average case: O(n log n)
- Worst case: O(n²) (when the array is already sorted or nearly sorted) Space Complexity: O(log n) due to the recursion stack
Implement a function to find the longest common subsequence of two strings.
public static string LongestCommonSubsequence(string text1, string text2)
{
int m = text1.Length;
int n = text2.Length;
// dp[i,j] represents the length of LCS of text1[0...i-1] and text2[0...j-1]
int[,] dp = new int[m + 1, n + 1];
// Fill the dp table
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (text1[i - 1] == text2[j - 1])
dp[i, j] = dp[i - 1, j - 1] + 1;
else
dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
}
}
// Backtrack to find the actual LCS
StringBuilder sb = new StringBuilder();
int x = m, y = n;
while (x > 0 && y > 0)
{
if (text1[x - 1] == text2[y - 1])
{
sb.Insert(0, text1[x - 1]);
x--;
y--;
}
else if (dp[x - 1, y] > dp[x, y - 1])
x--;
else
y--;
}
return sb.ToString();
}Time Complexity: O(m * n) where m and n are the lengths of the two strings Space Complexity: O(m * n) for the dp table
Design an algorithm for processing a large number of financial transactions. The system needs to:
- Process transactions in the order they are received
- Detect and handle duplicate transactions
- Calculate running balances for accounts
- Support efficient querying of transaction history
Explain your choice of data structures, algorithms, and their time/space complexity.
Design an algorithm for a real-time fraud detection system that:
- Monitors transaction patterns
- Identifies suspicious activities based on predefined rules
- Learns from historical data to improve detection
- Minimizes false positives
Explain your approach, including data structures, algorithms, and time/space complexity analysis.
Design a matching engine for a trading system that:
- Maintains order books for different securities
- Matches buy and sell orders efficiently
- Implements price-time priority
- Handles market orders and limit orders
- Supports cancellation of orders
Explain your choice of data structures, algorithms, and their time/space complexity.
Review the following C# code and optimize it for better performance:
public class PerformanceChallenge
{
public static List<int> FindCommonElements(List<int> list1, List<int> list2)
{
List<int> result = new List<int>();
for (int i = 0; i < list1.Count; i++)
{
for (int j = 0; j < list2.Count; j++)
{
if (list1[i] == list2[j])
{
result.Add(list1[i]);
break;
}
}
}
return result;
}
public static bool IsPrime(int n)
{
if (n <= 1) return false;
if (n <= 3) return true;
for (int i = 2; i < n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
public static List<int> GetPrimesUpTo(int n)
{
List<int> primes = new List<int>();
for (int i = 2; i <= n; i++)
{
if (IsPrime(i))
primes.Add(i);
}
return primes;
}
public static int Fibonacci(int n)
{
if (n <= 1) return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
public static int[] MergeArrays(int[] arr1, int[] arr2)
{
List<int> result = new List<int>();
foreach (int num in arr1)
result.Add(num);
foreach (int num in arr2)
result.Add(num);
result.Sort();
return result.ToArray();
}
}For each method:
- Identify performance issues
- Explain the current time and space complexity
- Optimize the code to improve performance
- Explain the optimized time and space complexity
Candidates will be evaluated on:
- Understanding of core data structures and algorithms
- Ability to analyze time and space complexity
- Problem-solving approach and logical thinking
- Code quality, including readability and optimization
- Knowledge of algorithm design paradigms (divide and conquer, dynamic programming, etc.)
- Ability to optimize code for performance
- Understanding of trade-offs between different approaches
- Application of algorithms to real-world scenarios
- Communication skills when explaining technical concepts
- Knowledge of C# language features relevant to algorithm implementation