Katkat
Back

Answer conceptual true/false and caching questions

ImcSoftware Engineer · HR Screen
MediumSoftware EngineerHR ScreenSoftware Engineering Fundamentals

Last updated

This problem tests foundational knowledge of computer architecture (integer representation), memory management strategies (caching), and graph theory essentials.

Part 1: Bit Manipulation and Signedness

Explain the difference between a signed and unsigned 32-bit integer representation in terms of how the most significant bit (MSB) is interpreted. If you perform a right-shift operation on a signed integer versus an unsigned integer, how does the behavior differ at the hardware/compiler level?

Part 2: Cache Eviction Policies

You are tasked with implementing a cache for a high-frequency trading system. Compare Least Recently Used (LRU) and Least Frequently Used (LFU) eviction policies.

  1. Define the criteria for eviction for each.
  2. Provide an example scenario where LRU would perform significantly better than LFU.
  3. Discuss the space and time complexity trade-offs for tracking metadata for these two policies.

Part 3: Graph Fundamentals

Consider a directed graph G = (V, E).

  1. Define the concept of the "in-degree" and "out-degree" of a vertex.
  2. If a graph is represented as an adjacency matrix, what is the time complexity to find the in-degree of a specific vertex v?
  3. How does this complexity change if you transition the storage format to an adjacency list? State your assumptions regarding the structure of the list.

Hints

Hint 1

Recall that signed integers typically use two's complement representation, meaning the MSB acts as a sign bit.

Hint 2

Think about the 'recency' bias of LRU versus the 'frequency' bias of LFU and how they handle stale data that was once popular.

Hint 3

For the adjacency matrix, consider whether you need to iterate over rows or columns to count incoming edges.

Follow-up questions

  • How would you modify an LRU cache to be thread-safe in a multi-threaded environment without introducing significant lock contention?
  • If your graph is extremely sparse (number of edges E << V^2), which representation is more memory-efficient and why?
  • Can you implement an O(1) time complexity mechanism to update the frequency count in an LFU cache?