Tamoban Javnoi COMPUTER SCIENCE & IT   -   Data Structures & Algorithms

Which data structure is most suitable for implementing an LRU (Least Recently Used) cache?

An LRU (Least Recently Used) cache is most efficiently implemented using a combination of a HashMap and a Doubly Linked List. The HashMap provides O(1) access to cache entries, while the Doubly Linked List maintains the order of usage, allowing for quick updates to the most recently and least recently used elements.
Tamoban Javnoi COMPUTER SCIENCE & IT   -   Data Structures & Algorithms

Why is the space complexity of a recursive algorithm often higher than its iterative counterpart?

The space complexity of a recursive algorithm is often higher than its iterative counterpart because recursion requires additional stack space to store the state of each function call. Each recursive call adds a new frame to the call stack, which increases the overall space complexity.
Tamoban Javnoi COMPUTER SCIENCE & IT   -   Data Structures & Algorithms

Where is a heap data structure typically used?

A heap data structure is typically used to implement a priority queue. Heaps allow for efficient retrieval of the highest (or lowest) priority element and support operations like insertion and deletion in logarithmic time, making them ideal for priority queues.
Tamoban Javnoi COMPUTER SCIENCE & IT   -   Data Structures & Algorithms

When does the Dijkstra's algorithm fail to find the shortest path in a graph?

Dijkstra's algorithm fails to find the shortest path if the graph contains negative weight edges. The algorithm assumes that all edge weights are non-negative, and the presence of negative weights can lead to incorrect results and infinite loops.
Tamoban Javnoi COMPUTER SCIENCE & IT   -   Data Structures & Algorithms

What is the time complexity of inserting an element into a Binary Search Tree (BST) in the worst case?

In the worst case, a Binary Search Tree (BST) can become a skewed tree (like a linked list), where each node has only one child. In such a scenario, the time complexity of inserting an element becomes O(n), where n is the number of nodes in the tree.
Tamoban Javnoi COMPUTER SCIENCE & IT   -   Operating Systems

When is the "thrashing" condition likely to occur in a system using virtual memory?

Thrashing occurs when a system has insufficient physical memory, causing excessive paging as the operating system continuously swaps data between RAM and disk. This leads to high overhead and severely degrades system performance, as more time is spent on paging rather than executing processes.
Tamoban Javnoi COMPUTER SCIENCE & IT   -   Operating Systems

Why do modern operating systems use preemptive multitasking?

Modern operating systems use preemptive multitasking to enhance user interactivity and system responsiveness. It allows the operating system to interrupt a running process and switch the CPU to another process, ensuring that all processes receive appropriate attention and that the system remains responsive to user inputs.
Tamoban Javnoi COMPUTER SCIENCE & IT   -   Operating Systems

Which memory management scheme allows the physical address space of a process to be non-contiguous?

Paging is a memory management scheme that allows the physical address space of a process to be non-contiguous. It eliminates the need for contiguous allocation of physical memory and thus reduces fragmentation by dividing memory into fixed-sized pages.
Tamoban Javnoi COMPUTER SCIENCE & IT   -   Operating Systems

How to resolve the critical section problem in concurrent programming?

The critical section problem can be resolved using synchronization mechanisms such as semaphores. Semaphores are variables used to control access to common resources by multiple processes in a concurrent system, ensuring that only one process can enter the critical section at a time.
Tamoban Javnoi COMPUTER SCIENCE & IT   -   Operating Systems

What mechanism does an operating system use to handle the execution of multiple processes that require frequent access to the CPU?

Round-robin scheduling is a time-sharing scheduling algorithm used by the operating system to handle the execution of multiple processes. Each process is assigned a fixed time slot (quantum), and processes are cycled through in a circular order, ensuring that all processes get a fair share of CPU time.

COMPUTER SCIENCE & IT