1. Reverse linked list.
2. Implement LRU cache
3. Implement reader writer lock

Question

1. Reverse linked list. 
2. Implement LRU cache
3. Implement reader writer lock

Anonymous · Accepted Answer

1.in C# if you use the  System.Collections.Generic.LinkedLIst you have the built in Reverse() method but obviously that's not what the interviewer asked for;). the below is a implementation of a method which reverse your generic LinkedList (can take any type)
**by give it few tweaks it can also get a custom Linked List:
public static LinkedList ReverseLinkedList(LinkedList linkedList)
    {
      // ------------------------------------------------------------
      // Create a new linked list and add all items of given 
      // linked list to the copy linked list in reverse order
      // ------------------------------------------------------------
      LinkedList copyList = new LinkedList();

      // ------------------------------------------------------------
      // Start from the latest node
      // ------------------------------------------------------------
      LinkedListNode start = linkedList.Last;

      // ------------------------------------------------------------
      // Traverse until the first node is found
      // ------------------------------------------------------------
      while (start != null)
      {
        // ------------------------------------------------------------
        // Add item to the new link list
        // ------------------------------------------------------------
        copyList.AddLast(start.Value);

        start = start.Previous;
      }

      return copyList;
    } 

2.
public class LeastRecentlyUsedCache
{
    private readonly Dictionary entries;
    private readonly int capacity;
    private Node head;
    private Node tail;       
 
    private class Node
    {
        public Node Next { get; set; }
        public Node Previous { get; set; }
        public TKey Key { get; set; }
        public TValue Value { get; set; }
    }
 
    public LeastRecentlyUsedCache(int capacity = 16)
    {
        if (capacity ();
        head = null;
    }
 
    public void Set(TKey key, TValue value)
    {
        Node entry;
        if (!entries.TryGetValue(key, out entry))
        {
            entry = new Node { Key = key, Value = value };
            if (entries.Count == capacity)
            {
                entries.Remove(tail.Key);
                tail = tail.Previous;
                if (tail != null) tail.Next = null;
            }
            entries.Add(key, entry);
        }
 
        entry.Value = value;
        MoveToHead(entry);
        if (tail == null) tail = head;
    }
 
    public bool TryGetValue(TKey key, out TValue value)
    {
        value = default(TValue);
        Node entry;
        if (!entries.TryGetValue(key, out entry)) return false;
        MoveToHead(entry);
        value = entry.Value;
        return true;
    }
 
    private void MoveToHead(Node entry)
    {
        if (entry == head || entry == null) return;
 
        var next = entry.Next;
        var previous = entry.Previous;
 
        if (next != null) next.Previous = entry.Previous;
        if (previous != null) previous.Next = entry.Next;
 
        entry.Previous = null;
        entry.Next = head;
 
        if (head != null) head.Previous = entry;
        head = entry;
 
        if (tail == entry) tail = previous;
    }
}

Anonymous · Answer

3. using monitor
public class ReaderWriterLock
{
    private int m_activeReaderCount;
    private bool m_activeWriter;
    private object m_countLock;

public ReaderWriterLock()
    {
        m_activeReaderCount = 0;
        m_activeWriter = false;
        
        m_countLock = new object();
    }

    public void BeginRead()
    {
        Monitor.Enter(m_countLock);

        while (m_activeWriter)
        {
            Monitor.Wait(m_countLock);
        }

        m_activeReaderCount++;

        Monitor.Exit(m_countLock);
    }

    public void EndRead()
    {
        Monitor.Enter(m_countLock);

        m_activeReaderCount--;
        if (m_activeReaderCount == 0)
        {
            // At this point we are sure that only writers can be in the
            // wait queue, so it is sufficient to wake up just one of them.
            Monitor.Pulse(m_countLock);
        }

        Monitor.Exit(m_countLock);
    }

    public void BeginWrite()
    {
        Monitor.Enter(m_countLock);

        while ((m_activeReaderCount != 0) || (m_activeWriter))
        {
            Monitor.Wait(m_countLock);
        }

        m_activeWriter = true;

        Monitor.Exit(m_countLock);
    }

    public void EndWrite()
    {
        Monitor.Enter(m_countLock);

        m_activeWriter = false;
        
        // Both readers and writers can be in the wait queue.
        // We will wake them up all and let them compete for
        // the right to read / write.
        Monitor.PulseAll(m_countLock);

        Monitor.Exit(m_countLock);
    }
}

Varonis Systems

Varonis Systems interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?