BloomFilter

A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set. The price paid for this efficiency is that a Bloom filter is a probabilistic data structure: it tells us that the element either definitely is not in the set or may be in the set.

The BitArray is the backbone of the Bloom filter. It’s a compact array of bits used to represent a set of n elements (where n is the size of the array). Each bit represents whether an element is in the set.


public class BloomFilter<T>
{
    private readonly BitArray bitArray;
    private readonly int size;
    private readonly int hashFunctionCount;

    public BloomFilter(int size, int hashFunctionCount)
    {
        this.size = size;
        this.hashFunctionCount = hashFunctionCount;
        bitArray = new BitArray(size);
    }

    public void Add(T item)
    {
        for (int i = 0; i < hashFunctionCount; i++)
        {
            int hash = GetHash(item, i);
            bitArray[hash % size] = true;
        }
    }

    public bool Contains(T item)
    {
        for (int i = 0; i < hashFunctionCount; i++)
        {
            int hash = GetHash(item, i);
            if (!bitArray[hash % size])
            {
                return false;
            }
        }
        return true;
    }

    private int GetHash(T item, int index)
    {
        return item is not null ? item.GetHashCode() * index : 0;
    }
}

Call Center

There are three categories of workers at a call centre: supervisors, managers, and attendants. By default, the attendant will answer the call. If the attendant is unavailable or unable to assist the customer, the call will be forwarded to the appropriate management; if the manager is unable to assist the customer, the call will be forwarded to their supervisor.

public abstract class Employee
{
    public string Name { get; set; }
    public bool IsAvailable { get; set; }
    public Employee? Supervisor { get; set; }

    protected Employee(string name)
    {
        Name = name;
        IsAvailable = true;
    }

    public virtual bool HandleCall(Call call)
    {

        if (IsAvailable)
        {
            IsAvailable = false;
            var callHandled = CallHandled(call);
            IsAvailable = true;
            if (!callHandled)
            {
                return EscalateCall(call);
            }
            return callHandled;
        }
        return false;
    }

    private bool CallHandled(Call call) => call != null;
    private bool EscalateCall(Call call)
    {
        if (Supervisor != null)
        {
            return Supervisor.HandleCall(call);
        }
        return false;
    }
}

public class Attendant : Employee
{
    public Attendant(string name) : base(name) { }
}

public class Manager : Employee
{
    public Manager(string name) : base(name) { }
}

public class Supervisor : Employee
{
    public Supervisor(string name) : base(name) { }
}

public class Call
{
    public string CustomerName { get; set; }
    public string Query { get; set; }

    public Call(string customerName, string query)
    {
        CustomerName = customerName;
        Query = query;
    }
}

public class CallCenter
{
    private List<Employee> employees;

    public CallCenter()
    {
        employees = new List<Employee>();
    }

    public void AddEmployee(Employee employee)
    {
        employees.Add(employee);
    }

    public void RouteCall(Call call)
    {
        foreach (var employee in employees)
        {
            // check if employee available
            if (!employee.IsAvailable)
            {
                continue;
            }

            // check if call handled by the employee
            if (employee.HandleCall(call))
            {
                return;
            }
        }
    }
}

Deck Of Cards

public enum Suit
{
    Clubs,
    Diamonds,
    Hearts,
    Spades
}

public enum Rank
{
    Ace,
    Two,
    Three,
    Four,
    Five,
    Six,
    Seven,
    Eight,
    Nine,
    Ten,
    Jack,
    Queen,
    King
}

public class Card
{
    public Suit Suit { get; private set; }
    public Rank Rank { get; private set; }

    public Card(Suit suit, Rank rank)
    {
        Suit = suit;
        Rank = rank;
    }
}

public class Deck
{
    private List<Card> cards;

    public Deck()
    {
        cards = new List<Card>();

        foreach (Suit suit in Enum.GetValues(typeof(Suit)))
        {
            foreach (Rank rank in Enum.GetValues(typeof(Rank)))
            {
                cards.Add(new Card(suit, rank));
            }
        }
    }

    public void Shuffle()
    {
        Random rng = new Random();
        int n = cards.Count;
        while (n > 1)
        {
            n--;
            int k = rng.Next(n + 1);
            Card value = cards[k];
            cards[k] = cards[n];
            cards[n] = value;
        }
    }

    public Card DrawCard()
    {
        if (cards.Count == 0)
        {
            throw new InvalidOperationException("Deck is empty");
        }

        Card topCard = cards[cards.Count - 1];
        cards.RemoveAt(cards.Count - 1);
        return topCard;
    }
}

Chat System

using System;
using System.Collections.Generic;

public class User
{
    public string Name { get; private set; }

    public User(string name)
    {
        Name = name;
    }

    public void ReceiveMessage(Message message)
    {
        Console.WriteLine($"{Name} received: {message.Content} from {message.Sender.Name}");
    }
}

public class Message
{
    public User Sender { get; private set; }
    public string Content { get; private set; }

    public Message(User sender, string content)
    {
        Sender = sender;
        Content = content;
    }
}

public class ChatRoom
{
    private List<Message> _messages = new List<Message>();
    private List<User> _subscribers = new List<User>();

    public void Subscribe(User user)
    {
        _subscribers.Add(user);
    }

    public void PostMessage(User user, string content)
    {
        var message = new Message(user, content);
        _messages.Add(message);

        foreach (var subscriber in _subscribers)
        {
            if (subscriber != user)
            {
                subscriber.ReceiveMessage(message);
            }
        }
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        var alice = new User("Alice");
        var bob = new User("Bob");
        var charlie = new User("Charlie");

        var chatRoom = new ChatRoom();

        chatRoom.Subscribe(alice);
        chatRoom.Subscribe(bob);
        chatRoom.Subscribe(charlie);

        chatRoom.PostMessage(alice, "Hello, everyone!");
        chatRoom.PostMessage(bob, "Hi, Alice!");
    }
}

Distributed Search

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

public class Node
{
    private List<string> _data;

    public Node(List<string> data)
    {
        _data = data;
    }

    public List<string> Search(string query)
    {
        return _data.Where(item => item.Contains(query)).ToList();
    }
}

public class DistributedSearchSystem
{
    private List<Node> _nodes;

    public DistributedSearchSystem(List<List<string>> dataPartitions)
    {
        _nodes = dataPartitions.Select(partition => new Node(partition)).ToList();
    }

    public async Task<List<string>> SearchAsync(string query)
    {
        var tasks = _nodes.Select(node => Task.Run(() => node.Search(query))).ToList();
        var results = await Task.WhenAll(tasks);

        return results.SelectMany(result => result).ToList();
    }
}

public class Program
{
    public static async Task Main(string[] args)
    {
        var dataPartitions = new List<List<string>>
        {
            new List<string> { "apple", "banana", "cherry" },
            new List<string> { "dog", "elephant", "fox" },
            new List<string> { "grape", "honeydew", "ice cream" },
        };

        var searchSystem = new DistributedSearchSystem(dataPartitions);

        var results = await searchSystem.SearchAsync("a");

        foreach (var result in results)
        {
            Console.WriteLine(result);
        }
    }
}

Elevator


public class Elevator
{
    private int _currentFloor = 0;
    private Queue<int> _requests = new Queue<int>();

    public void RequestFloor(int floor)
    {
        _requests.Enqueue(floor);
    }

    public void ProcessRequests()
    {
        while (_requests.Count > 0)
        {
            var targetFloor = _requests.Dequeue();
            MoveToFloor(targetFloor);
        }
    }

    private void MoveToFloor(int floor)
    {
        Console.WriteLine($"Elevator moving from floor {_currentFloor} to floor {floor}");
        _currentFloor = floor;
        Console.WriteLine($"Elevator arrived at floor {_currentFloor}");
    }
}

Event Calendar

using System;
using System.Collections.Generic;
using System.Linq;

public class Event
{
    public string Title { get; private set; }
    public DateTime Start { get; private set; }
    public DateTime End { get; private set; }

    public Event(string title, DateTime start, DateTime end)
    {
        Title = title;
        Start = start;
        End = end;
    }
}

public class Calendar
{
    private List<Event> _events = new List<Event>();

    public bool HasOverlap(Event eventToAdd)
    {
        return _events.Any(e => (e.Start <= eventToAdd.End) && (e.End >= eventToAdd.Start));
    }

    public void AddEvent(Event eventToAdd)
    {
        if (HasOverlap(eventToAdd))
        {
            Console.WriteLine($"Cannot add event {eventToAdd.Title}. It overlaps with another event.");
            return;
        }

        _events.Add(eventToAdd);
    }

    public List<Event> GetEventsOnDate(DateTime date)
    {
        return _events.Where(e => e.Start.Date <= date.Date && e.End.Date >= date.Date).ToList();
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        var calendar = new Calendar();

        var event1 = new Event("Meeting with Bob", new DateTime(2024, 5, 1, 10, 0, 0), new DateTime(2024, 5, 1, 11, 0, 0));
        var event2 = new Event("Dentist appointment", new DateTime(2024, 5, 1, 10, 30, 0), new DateTime(2024, 5, 1, 11, 30, 0));
        var event3 = new Event("Lunch with Alice", new DateTime(2024, 5, 1, 12, 0, 0), new DateTime(2024, 5, 1, 13, 0, 0));

        calendar.AddEvent(event1);
        calendar.AddEvent(event2);  // This should fail because it overlaps with event1
        calendar.AddEvent(event3);

        var eventsOnMay1 = calendar.GetEventsOnDate(new DateTime(2024, 5, 1));

        foreach (var eventOnMay1 in eventsOnMay1)
        {
            Console.WriteLine($"{eventOnMay1.Start} to {eventOnMay1.End}: {eventOnMay1.Title}");
        }
    }
}

HashTable


public class HashTable<TKey, TValue>
{
    private const int InitialCapacity = 16;
    private const float LoadFactor = 0.75f;

    private Entry<TKey, TValue>[] entries;
    private int count;

    public HashTable()
    {
        entries = new Entry<TKey, TValue>[InitialCapacity];
        count = 0;
    }

    public void Add(TKey key, TValue value)
    {
        if ((float)count / entries.Length >= LoadFactor)
        {
            Resize();
        }

        int index = GetIndex(key);
        Entry<TKey, TValue> current = entries[index];

        if (current == null)
        {
            entries[index] = new Entry<TKey, TValue>(key, value);
            count++;
        }
        else
        {
            //traverse linked list to check if key is already exists.
            while (current.Next != null)
            {
                if (current.Key.Equals(key))
                {
                    throw new ArgumentException("An element with the same key already exists in the hashtable.");
                }
                current = current.Next;
            }

            current.Next = new Entry<TKey, TValue>(key, value);
            count++;
        }
    }

    public bool ContainsKey(TKey key)
    {
        int index = GetIndex(key);
        Entry<TKey, TValue> current = entries[index];

        while (current != null)
        {
            if (current.Key.Equals(key))
            {
                return true;
            }
            current = current.Next;
        }

        return false;
    }

    public TValue GetValue(TKey key)
    {
        int index = GetIndex(key);
        Entry<TKey, TValue> current = entries[index];

        while (current != null)
        {
            if (current.Key.Equals(key))
            {
                return current.Value;
            }
            current = current.Next;
        }

        throw new KeyNotFoundException("The specified key was not found in the hashtable.");
    }

    public bool Remove(TKey key)
    {
        int index = GetIndex(key);
        Entry<TKey, TValue> current = entries[index];
        Entry<TKey, TValue> previous = null;

        while (current != null)
        {
            if (current.Key.Equals(key))
            {
                if (previous == null)
                {
                    entries[index] = current.Next;
                }
                else
                {
                    previous.Next = current.Next;
                }
                count--;
                return true;
            }

            previous = current;
            current = current.Next;
        }

        return false;
    }

    public int Count => count;

    private void Resize()
    {
        Entry<TKey, TValue>[] oldEntries = entries;
        entries = new Entry<TKey, TValue>[oldEntries.Length * 2];
        count = 0;

        foreach (Entry<TKey, TValue> entry in oldEntries)
        {
            Entry<TKey, TValue> current = entry;
            while (current != null)
            {
                Add(current.Key, current.Value);
                current = current.Next;
            }
        }
    }

    private int GetIndex(TKey key)
    {
        int hashCode = key.GetHashCode();
        int index = hashCode % entries.Length;
        return index < 0 ? index + entries.Length : index;
    }

    private class Entry<TKey, TValue>
    {
        public TKey Key { get; }
        public TValue Value { get; }
        public Entry<TKey, TValue> Next { get; set; }

        public Entry(TKey key, TValue value)
        {
            Key = key;
            Value = value;
            Next = null;
        }
    }
}

The reason we use a linked list array (an array of linked lists) in a hashtable is to handle collisions. A collision occurs when two different keys produce the same hash value. By using a linked list at each index of the array, we can store multiple keys (and their associated values) that hash to the same index.

Heap Sort

Heap sort is a sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a heap. The heap itself has the property that every node in the heap is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) its two children. The heap sort algorithm then repeatedly removes the largest/smallest element from the heap, thus building the sorted list from back to front. Heap sort provides a good compromise of efficiency and simplicity. It has an average and worst-case time complexity of O(n log n).

First transforms the input array into a max heap. Then, it repeatedly swaps the first element (the maximum) with the last element of the heap, reduces the size of the heap by one, and heapifies the root element. This process continues until the heap is empty, resulting in a sorted array in ascending order.

public class HeapSort
{
    //Time complexity:It takes O(logn) for heapify and O(n) for constructing a heap. Hence, the overall time complexity of heap sort using min heap or max heap is O(n log n)
    //Space complexity: O(n) for call stack
    //Auxiliary Space complexity: O(1)  for swap two items

    public void Accending(int[] nums)
    {
        int N = nums.Length;
        for (int i = N / 2 - 1; i >= 0; i--)
        {
            MaxHeap(nums, N, i);
        }

        for (int j = N - 1; j >= 0; j--)
        {
            int temp = nums[0];
            nums[0] = nums[j];
            nums[j] = temp;
            MaxHeap(nums, j, 0);
        }
    }
    public void Decreasing(int[] nums)
    {
        int N = nums.Length;
        for (int i = N / 2 - 1; i >= 0; i--)
        {
            MinHeap(nums, N, i);
        }

        for (int j = N - 1; j >= 0; j--)
        {
            int temp = nums[0];
            nums[0] = nums[j];
            nums[j] = temp;
            MinHeap(nums, j, 0);
        }
    }

    private void MaxHeap(int[] nums, int N, int index)
    {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < N && nums[left] > nums[largest])
        {
            largest = left;
        }
        if (right < N && nums[right] > nums[largest])
        {
            largest = right;
        }

        if (largest != index)
        {
            int temp = nums[index];
            nums[index] = nums[largest];
            nums[largest] = temp;

            MaxHeap(nums, N, largest);
        }
    }

    private void MinHeap(int[] nums, int N, int index)
    {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < N && nums[left] < nums[smallest])
        {
            smallest = left;
        }
        if (right < N && nums[right] < nums[smallest])
        {
            smallest = right;
        }

        if (smallest != index)
        {
            int temp = nums[index];
            nums[index] = nums[smallest];
            nums[smallest] = temp;

            MinHeap(nums, N, smallest);
        }
    }
}

Hotel Booking

using System;
using System.Collections.Generic;
using System.Linq;

public enum RoomType
{
    DeluxeSingleBed,
    DeluxeDoubleBed
}

public class Room
{
    public int Number { get; private set; }
    public RoomType Type { get; private set; }

    public Room(int number, RoomType type)
    {
        Number = number;
        Type = type;
    }
}

public class Booking
{
    public Room Room { get; private set; }
    public DateTime StartDate { get; private set; }
    public DateTime EndDate { get; private set; }

    public Booking(Room room, DateTime startDate, DateTime endDate)
    {
        Room = room;
        StartDate = startDate;
        EndDate = endDate;
    }
}

public class Hotel
{
    private List<Room> _rooms = new List<Room>();
    private List<Booking> _bookings = new List<Booking>();

    public Hotel(List<Room> rooms)
    {
        _rooms = rooms;
    }

    public bool IsRoomAvailable(RoomType roomType, DateTime startDate, DateTime endDate)
    {
        return !_bookings.Any(b => b.Room.Type == roomType && b.StartDate < endDate && b.EndDate > startDate);
    }

    public void AddBooking(RoomType roomType, DateTime startDate, DateTime endDate)
    {
        if (!IsRoomAvailable(roomType, startDate, endDate))
        {
            Console.WriteLine($"Cannot add booking. No available {roomType} from {startDate} to {endDate}.");
            return;
        }

        var room = _rooms.First(r => r.Type == roomType && !_bookings.Any(b => b.Room.Number == r.Number && b.StartDate < endDate && b.EndDate > startDate));
        var booking = new Booking(room, startDate, endDate);
        _bookings.Add(booking);
    }

    public List<Booking> GetBookingsForRoomType(RoomType roomType)
    {
        return _bookings.Where(b => b.Room.Type == roomType).ToList();
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        var rooms = new List<Room>
        {
            new Room(1, RoomType.DeluxeSingleBed),
            new Room(2, RoomType.DeluxeSingleBed),
            new Room(3, RoomType.DeluxeDoubleBed),
            // Add more rooms as needed
        };

        var hotel = new Hotel(rooms);

        hotel.AddBooking(RoomType.DeluxeSingleBed, new DateTime(2024, 5, 1), new DateTime(2024, 5, 10));
        hotel.AddBooking(RoomType.DeluxeSingleBed, new DateTime(2024, 5, 5), new DateTime(2024, 5, 15));  // This should fail because it overlaps with the previous booking

        var bookingsForDeluxeSingleBed = hotel.GetBookingsForRoomType(RoomType.DeluxeSingleBed);

        foreach (var booking in bookingsForDeluxeSingleBed)
        {
            Console.WriteLine($"{booking.Room.Type} is booked from {booking.StartDate} to {booking.EndDate}");
        }
    }
}

LRU cache

public class LruCache<TKey, TValue> where TKey : notnull where TValue : class
{
    private readonly int capacity;
    private readonly Dictionary<TKey, TValue> cache;
    private readonly LinkedList<TKey> queue;

    public LruCache(int capacity)
    {
        this.capacity = capacity;
        this.cache = new Dictionary<TKey, TValue>(capacity);
        this.queue = new LinkedList<TKey>();
    }

    public void Add(TKey key, TValue value)
    {
        if (cache.TryGetValue(key, out _))
        {
            queue.Remove(key);
            queue.AddLast(key);
            cache[key] = value;
            return;
        }

        if (this.cache.Count >= capacity)
        {
            RemoveFirst();
        }

        cache.Add(key, value);
        this.queue.AddLast(key);

    }

    public TValue GetValue(TKey key)
    {
        if (cache.TryGetValue(key, out TValue node))
        {
            queue.Remove(key);
            queue.AddLast(key);
            return node;
        }
        return default;
    }

    private void RemoveFirst()
    {
        var node = this.queue.First;
        this.queue.RemoveFirst();
        this.cache.Remove(node!.Value!);
    }
}

ParkingLot

Parking lot system, each floor has parking slots and ramps to move on to the next floor, and each floor has two sensors, one for detech check-in and another for checkout. One more important point: there is an entry gate and one exit gate on the ground floor, and there is one direct movement of vichels, like within the same floor, moving from left to right, not right to left. one direct way to move, and the user needs to complete a cycle to move on next floor as well. This is one of the important points, and each floor has a number of slots. We also need to track available slots. Design an algorithm to get the available slots.

public class ParkingLot
{
    private int numberOfFloors;
    private List<Floor> floors;

    public ParkingLot(int numberOfFloors)
    {
        this.numberOfFloors = numberOfFloors;
        floors = new List<Floor>();

        for (int i = 0; i < numberOfFloors; i++)
        {
            floors.Add(new Floor(i));
        }
    }

    public void SensorDataReceived(int floorNumber, string sensorType)
    {
        if (sensorType == "A") // Sensor A indicates a vehicle has entered a slot
        {
            if (floors[floorNumber].GetAvailableSlots() > 0)
            {
                floors[floorNumber].DecreaseAvailableSlots();
            }
            else if (floorNumber < numberOfFloors - 1) // If the current floor is full, check the next floor
            {
                SensorDataReceived(floorNumber + 1, sensorType);
            }
            else
            {
                Console.WriteLine("Parking lot is full.");
            }
        }
        else if (sensorType == "B") // Sensor B indicates a vehicle has left a slot
        {
            floors[floorNumber].IncreaseAvailableSlots();
        }
    }

    public void DisplayAvailableSlots()
    {
        foreach (var floor in floors)
        {
            Console.WriteLine("Floor " + floor.GetFloorNumber() + ": " + floor.GetAvailableSlots() + " slots available.");
        }
    }
}

public class Floor
{
    private int floorNumber;
    private int availableSlots;

    public Floor(int floorNumber)
    {
        this.floorNumber = floorNumber;
        this.availableSlots = 10; // Assuming each floor has 10 slots
    }

    public void DecreaseAvailableSlots()
    {
        if (availableSlots > 0)
        {
            availableSlots--;
        }
    }

    public void IncreaseAvailableSlots()
    {
        if (availableSlots < 10) // Assuming each floor has 10 slots
        {
            availableSlots++;
        }
    }

    public int GetAvailableSlots()
    {
        return availableSlots;
    }

    public int GetFloorNumber()
    {
        return floorNumber;
    }
}

Parking Lot

Please design a parking lot system. There are three types of slots: small, compact, and large. A bike can park in any type of slot, and a car can park in a compact or large spot, but a bus can only park in a large spot.


public enum VehicleSize
{
    Small,
    Compact,
    Large
}

public abstract class Vehicle
{
    protected Vehicle(string number)
    {
        this.Number = number;
    }
    public string Number { get; }
    public abstract VehicleSize Size { get; }

}

public class Bike : Vehicle
{     
    public Bike(string number):base(number)
    {
    }
    public override VehicleSize Size => VehicleSize.Small;

}

public class Car : Vehicle
{
    public Car(string number) : base(number)
    {
    }
    public override VehicleSize Size => VehicleSize.Compact;
}

public class Bus : Vehicle
{
    public Bus(string number) : base(number)
    {
    }
    public override VehicleSize Size => VehicleSize.Large;
}

public class ParkingSpot
{
    public VehicleSize Size { get; private set; }
    public Vehicle CurrentVehicle { get; private set; }

    public ParkingSpot(VehicleSize size)
    {
        Size = size;
    }

    public bool IsAvailable=> CurrentVehicle == null;

    public bool CanFitVehicle(Vehicle vehicle)
    {
        return IsAvailable && (int)vehicle.Size <= (int)Size;
    }

    public bool ParkVehicle(Vehicle vehicle)
    {
        if (!CanFitVehicle(vehicle))
        {
            return false;
        }

        CurrentVehicle = vehicle;
        return true;
    }

    public void RemoveVehicle()
    {
        CurrentVehicle = null;
    }
}

public class ParkingFloor
{
    private List<ParkingSpot> spots;

    public ParkingFloor(int numSpots)
    {
        spots = new List<ParkingSpot>(numSpots);
    }

    public bool ParkVehicle(Vehicle vehicle)
    {
        foreach (var spot in spots)
        {
            if (spot.CanFitVehicle(vehicle))
            {
                return spot.ParkVehicle(vehicle);
            }
        }

        return false;
    }
}

public class ParkingLot
{
    private List<ParkingFloor> floors;

    public ParkingLot(int numFloors, int numSpotsPerFloor)
    {
        floors = new List<ParkingFloor>(numFloors);

        for (int i = 0; i < numFloors; i++)
        {
            floors.Add(new ParkingFloor(numSpotsPerFloor));
        }
    }

    public bool ParkVehicle(Vehicle vehicle)
    {
        foreach (var floor in floors)
        {
            if (floor.ParkVehicle(vehicle))
            {
                return true;
            }
        }

        return false;
    }
}

Print last `n` lines of a big file or big string.

public static void PrintLastLines(string fileName, int n)
{
    LinkedList<string> lines = new LinkedList<string>();
    using (FileStream fs = new FileStream(fileName, FileMode.Open, FileAccess.Read))
    {
        using (StreamReader sr = new StreamReader(fs))
        {
            string line;
            while ((line = sr.ReadLine()) != null)
            {
                lines.AddLast(line);
                if (lines.Count > n)
                    lines.RemoveFirst(); //remove first line.
            }
        }
    }
    foreach (string line in lines)
        Console.WriteLine(line);
}

Priority Queue

public class PriorityQueue<T>
{
    private readonly SortedDictionary<int, Queue<T>> queue = [];

    public void Enqueue(int priority, T item)
    {
        if (!queue.ContainsKey(priority))
        {
            queue.Add(priority, new Queue<T>());
        }
        queue[priority].Enqueue(item);
    }

    public T Dequeue()
    {
        if (queue.Count == 0)
        {
            return default!;
        }

        var topPriority = GetHightPriorty();

        var subqueue = queue[topPriority];

        var item = subqueue.Dequeue();

        if (subqueue.Count == 0)
        {
            queue.Remove(topPriority);
        }

        return item;
    }


    public int Count()
    {
        int count = 0;
        foreach (var item in queue)
        {
            count += item.Value.Count;

        }

        return count;
    }

    public bool IsEmpty => queue.Count == 0;

    private int GetHightPriorty()
    {
        var enurmator = queue.GetEnumerator();
        enurmator.MoveNext();
        return enurmator.Current.Key;
    }
}

Rate Limiter

Fixed Window RateLimiter

It will restrict the number of requests a client can make within a certain time window. It uses a dictionary to track the number of requests each client has made and when their window started. When a request comes in, it checks if the client’s window has expired. If it has, it starts a new window. If it hasn’t, it increments the client’s request count. If the count exceeds the limit, the request is denied. Otherwise, it’s allowed. This helps prevent any single client from overusing resources.


public class FixedWindowRateLimiter
{
    private readonly int requestLimit;
    private readonly TimeSpan windowDuration;
    private readonly ConcurrentDictionary<string, (int count, DateTime windowStart)> requestCounts = new ConcurrentDictionary<string, (int count, DateTime windowStart)>();

    public FixedWindowRateLimiter(int requestLimit, TimeSpan windowDuration)
    {
        this.requestLimit = requestLimit;
        this.windowDuration = windowDuration;
    }

    public bool IsAllowed(string clientId)
    {
        lock (requestCounts)
        {
            (int count, DateTime windowStart) = requestCounts.GetOrAdd(clientId, (0, DateTime.UtcNow));

            TimeSpan elapsed = DateTime.UtcNow - windowStart;
            if (elapsed > windowDuration)
            {
                requestCounts[clientId] = (0, DateTime.UtcNow); // Reset count for a new window
                return true;
            }

            if (count < requestLimit)
            {
                requestCounts[clientId] = (Interlocked.Increment(ref count), windowStart); // Incre-ment count
                return true;
            }

            return false; // Request limit reached
        }
    }
}

Leaky Bucket RateLimiter



public class LeakyBucketRateLimiter
{
    private readonly int capacity;
    private readonly TimeSpan interval;
    private int tokens = 0;
    private DateTime lastRefill = DateTime.UtcNow;
    private readonly object lockObject = new object(); // Dedicated locking object

    public LeakyBucketRateLimiter(int capacity, TimeSpan interval)
    {
        this.capacity = capacity;
        this.interval = interval;
    }

    public bool IsAllowed()
    {
        lock (lockObject) // Lock on the separate object
        {
            RefillTokens();

            if (tokens > 0)
            {
                tokens--;
                return true;
            }

            return false;
        }
    }

    private void RefillTokens()
    {
        TimeSpan elapsed = DateTime.UtcNow - lastRefill;
        int tokensToAdd = (int)Math.Floor(elapsed.TotalSeconds / interval.TotalSeconds);
        tokens = Math.Min(tokens + tokensToAdd, capacity); // Cap at capacity
        lastRefill = lastRefill.AddSeconds(tokensToAdd * interval.TotalSeconds);
    }
}

It calculates the time passed since the last refill, determines how many tokens to add based on this elapsed time and a set interval, and adds these tokens up to a maximum capacity. The time of the last refill is then updated. This ensures tokens are added at a fixed rate and the total number doesn’t exceed the capacity.

Sliding Window RateLimiter


public class SlidingWindowRateLimiter
{
    private readonly int requestLimit;
    private readonly TimeSpan windowDuration;
    private readonly ConcurrentQueue<DateTime> requestTimestamps = new ConcurrentQueue<DateTime>();

    public SlidingWindowRateLimiter(int requestLimit, TimeSpan windowDuration)
    {
        this.requestLimit = requestLimit;
        this.windowDuration = windowDuration;
    }

    public bool IsAllowed()
    {
        lock (requestTimestamps)
        {
            // Slide the window and remove expired timestamps
            DateTime threshold = DateTime.UtcNow - windowDuration;
            while (requestTimestamps.Count > 0 && requestTimestamps.TryPeek(out DateTime timeFrame) && timeFrame < threshold)
            {
                requestTimestamps.TryDequeue(out _);
            }

            // Check if the request count within the window is within limits
            return requestTimestamps.Count < requestLimit;
        }
    }

    public void AddRequest()
    {
        lock (requestTimestamps)
        {
            requestTimestamps.Enqueue(DateTime.UtcNow); // Add current timestamp to the window
        }
    }
}

Restaurant Finder


public class Restaurant
{
    public string Name { get; set; }
    public double Latitude { get; set; }
    public double Longitude { get; set; }
}


public class Location
{
    public double Latitude { get; set; }
    public double Longitude { get; set; }
}


public class RestaurantFinder
{
    private List<Restaurant> _restaurants;

    public RestaurantFinder(List<Restaurant> restaurants)
    {
        _restaurants = restaurants;
    }

    public Restaurant FindNearest(Location currentLocation)
    {
        return _restaurants.OrderBy(r => Distance(currentLocation, r)).First();
    }

    private double Distance(Location currentLocation, Restaurant restaurant)
    {
        var R = 6371e3; // Range (metres)
        var φ1 = currentLocation.Latitude * Math.PI / 180;
        var φ2 = restaurant.Latitude * Math.PI / 180;
        var Δφ = (restaurant.Latitude - currentLocation.Latitude) * Math.PI / 180;
        var Δλ = (restaurant.Longitude - currentLocation.Longitude) * Math.PI / 180;

        var a = Math.Sin(Δφ / 2) * Math.Sin(Δφ / 2) +
                Math.Cos(φ1) * Math.Cos(φ2) *
                Math.Sin(Δλ / 2) * Math.Sin(Δλ / 2);
        var c = 2 * Math.Atan2(Math.Sqrt(a), Math.Sqrt(1 - a));

        return R * c;
    }
}

Shopping Site

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

public class Product
{
    public string Name { get; private set; }
    public decimal Price { get; private set; }
    public int Quantity { get; set; }

    public Product(string name, decimal price, int quantity)
    {
        Name = name;
        Price = price;
        Quantity = quantity;
    }
}

public class Store
{
    private List<Product> _products = new List<Product>();

    public Store(List<Product> products)
    {
        _products = products;
    }

    public List<Product> GetProducts()
    {
        return _products;
    }
}

public class Cart
{
    private Dictionary<Product, DateTime> _products = new Dictionary<Product, DateTime>();

    public void AddProduct(Product product)
    {
        if (product.Quantity <= 0)
        {
            Console.WriteLine($"Cannot add product {product.Name}. It is not available.");
            return;
        }

        _products[product] = DateTime.Now.AddMinutes(15);
        product.Quantity--;
    }

    public decimal GetTotalPrice()
    {
        decimal total = 0;
        foreach (var product in _products.Keys)
        {
            total += product.Price;
        }
        return total;
    }

    public void CheckReservations()
    {
        var expiredReservations = _products.Where(p => p.Value < DateTime.Now).ToList();
        foreach (var reservation in expiredReservations)
        {
            reservation.Key.Quantity++;
            _products.Remove(reservation.Key);
        }
    }
}

public class Program
{
    public static async Task Main(string[] args)
    {
        var products = new List<Product>
        {
            new Product("Apple", 0.5m, 10),
            new Product("Banana", 0.3m, 20),
            new Product("Cherry", 0.2m, 30)
        };

        var store = new Store(products);
        var cart = new Cart();

        var apple = store.GetProducts().Find(p => p.Name == "Apple");
        cart.AddProduct(apple);

        Console.WriteLine($"Total price: {cart.GetTotalPrice()}");

        // Simulate waiting for 16 minutes
        await Task.Delay(TimeSpan.FromMinutes(16));

        cart.CheckReservations();

        Console.WriteLine($"Total price after checking reservations: {cart.GetTotalPrice()}");
    }
}

public class TextSharing
{
   
    /// <summary>
    /// Snippets collection.
    /// </summary>
    private static readonly ConcurrentDictionary<string, string> snippetMap = new ConcurrentDictionary<string, string>();


    public string GetSnippet(string Id)
    {
        snippetMap.TryGetValue(Id, out var snippet);

        return snippet;
    }

    public string Add(string textSnippet)
    {
        var snippetId = Guid.NewGuid().ToString();
        snippetMap.TryAdd(snippetId, textSnippet);

        return snippetId;
    }
}

Unique Number Generator

public class UniqueNumberGenerator
{
    private HashSet<int> generatedNumbers;
    private Random random;

    public UniqueNumberGenerator()
    {
        generatedNumbers = new HashSet<int>();
        random = new Random();
    }

    public int GenerateUniqueNumber()
    {
        int number;

        // Generate a new number until we get one that hasn't been generated before
        do
        {
            number = random.Next();
        }
        while (generatedNumbers.Contains(number));

        // Add the unique number to the set of generated numbers
        generatedNumbers.Add(number);

        return number;
    }
}

Url Shortener

public class UrlShortener
{
    private static readonly RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
    private static readonly ConcurrentDictionary<string, string> urlMap = new ConcurrentDictionary<string, string>();
    // A constant string of possible characters for the short url
    private const string UrlCharacters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

    public string Get(string shortUrl)
    {
        urlMap.TryGetValue(shortUrl, out var value);
        return value;
    }


    public string ShortUrl(string longUrl)
    {
        // Generate a new short url
        string shortUrl = GenerateRandomString(7);

        // Check if the short url is already in the dictionary
        while (urlMap.ContainsKey(shortUrl))
        {
            // Generate another short url
            shortUrl = GenerateRandomString(7);
        }

        // Add the mapping to the dictionary
        urlMap.TryAdd(shortUrl, longUrl);

        // Return the new short url
        return shortUrl;
    }


    private static string GenerateRandomString(int length)
    {
        // Create a byte array to store the random bytes
        byte[] bytes = new byte[length];

        rng.GetBytes(bytes);


        // Convert the byte array to a character array
        char[] chars = new char[length];
        for (int i = 0; i < length; i++)
        {
            // Use the byte value as an index to the UrlCharacters string
            chars[i] = UrlCharacters[bytes[i] % UrlCharacters.Length];
        }

        // Return the character array as a string
        return new string(chars);
    }

}

Web Crawler

public class WebCrawler
{
    private readonly HashSet<string> _visitedUrls = new HashSet<string>();
    private readonly HttpClient _httpClient = new HttpClient();

    public async Task CrawlAsync(string url)
    {
        if (!_visitedUrls.Add(url))
        {
            // URL has already been visited.
            return;
        }

        Console.WriteLine($"Crawling {url}");

        var content = await _httpClient.GetStringAsync(url);
        var htmlDocument = new HtmlDocument();
        htmlDocument.LoadHtml(content);

        var links = htmlDocument.DocumentNode.SelectNodes("//a[@href]");
        if (links == null)
        {
            return;
        }

        foreach (var link in links)
        {
            var hrefValue = link.GetAttributeValue("href", string.Empty);
            if (Uri.IsWellFormedUriString(hrefValue, UriKind.Absolute))
            {
                await CrawlAsync(hrefValue);
            }
        }
    }
}

Low-Level System Design Problems

BloomFilter

Call Center

Deck Of Cards

Chat System

Distributed Search

Elevator

Event Calendar

HashTable

Heap Sort

Hotel Booking

LRU cache

ParkingLot

Parking Lot

Print last `n` lines of a big file or big string.

Priority Queue

Rate Limiter

Fixed Window RateLimiter

Leaky Bucket RateLimiter

Sliding Window RateLimiter

Restaurant Finder

Shopping Site

Unique Number Generator

Url Shortener

Web Crawler

Post a Comment

Fundamentals of oops with C#

Benefits and trade-offs of minimal APIs in .NET Core

Contact Form

Low-Level System Design Problems

BloomFilter

Call Center

Deck Of Cards

Chat System

Distributed Search

Elevator

Event Calendar

HashTable

Heap Sort

Hotel Booking

LRU cache

ParkingLot

Parking Lot

Print last n lines of a big file or big string.

Priority Queue

Rate Limiter

Fixed Window RateLimiter

Leaky Bucket RateLimiter

Sliding Window RateLimiter

Restaurant Finder

Shopping Site

Text Sharing

Unique Number Generator

Url Shortener

Web Crawler

Post a Comment

Contact Form

Print last `n` lines of a big file or big string.