Question:

Given an array of integers, return the indices of two numbers such that they add up to a specific target.

def two_sum(nums, target):

num_map = {}

for i, num in enumerate(nums):

diff = target - num

if diff in num_map:

return [num_map[diff], i]

num_map[num] = i

return []

Answer:
The solution uses a hash map to store numbers and their indices. As we iterate through the array, we
check if the complement (target - current number) exists in the map. This ensures we find the solution in
O(n) time.

Question:
How do you reverse a singly linked list?

Sample Answer (Python):

class ListNode:

def __init__(self, val=0, next=None):

self.val = val

self.next = next

def reverse_list(head):

prev = None

curr = head

while curr:

next_node = curr.next

curr.next = prev

prev = curr

curr = next_node
 return prev

This solution iterates through the linked list and reverses the pointers in a single pass, achieving an O(n)
time complexity.

Question:
Given a set of non-negative integers and a sum, find if there is a subset of the given set with sum equal
to the given sum. (Subset Sum Problem)

Answer:
This problem is solved using dynamic programming by constructing a 2D table that stores boolean
values indicating whether a sum can be achieved with a subset of the numbers.

def is_subset_sum(arr, n, target_sum):

dp = [[False for _ in range(target_sum + 1)] for _ in range(n + 1)]

for i in range(n + 1):

dp[i][0] = True

for i in range(1, n + 1):

for j in range(1, target_sum + 1):

if arr[i-1] > j:

dp[i][j] = dp[i-1][j]

else:

dp[i][j] = dp[i-1][j] or dp[i-1][j - arr[i-1]]

return dp[n][target_sum]

This is a classic dynamic programming solution with a time complexity of O(n*target_sum).

Question:
Design a URL shortening service like Bit.ly.

Answer:
You should consider the following aspects while answering:
  Unique short URL generation: Use Base62 (consisting of A-Z, a-z, and 0-9) to create
unique keys.
 Database schema: You need a table with columns for the short URL key and the original
URL. Index the short URL for fast lookups.
 API endpoints: Create APIs for generating short URLs and redirecting to the original
URL.
 Scalability: Use horizontal partitioning and load balancing to manage the high traffic
load.
 Caching: Use in-memory caching (like Redis) for frequently accessed URLs to reduce
database hits.

Sample Answer:

 Tech Stack: Use Django or Flask for the backend, MySQL or MongoDB for storage, and
Redis for caching.
 Algorithm: Generate a unique key for each long URL by hashing it, and store the key-
value pair in the database. Ensure that the keys are unique.

Question:
Write a SQL query to find the second highest salary from the employee table.

SELECT MAX(salary)

FROM employees

WHERE salary < (SELECT MAX(salary) FROM employees);

This query works by selecting the maximum salary that is less than the highest salary in the table.

Question:
What is a deadlock, and how can you avoid it?

Answer:
A deadlock occurs when two or more threads are blocked forever, each waiting for the other to
release a resource.

To avoid deadlock:

 Avoid circular wait: Ensure that all locks are acquired in a consistent order.
 Use timeouts: When acquiring a lock, use timeouts to avoid waiting indefinitely.
 Deadlock detection and recovery: Implement algorithms that detect deadlocks and take
corrective actions (e.g., rolling back transactions).

Question:
Explain the SOLID principles in Object-Oriented Programming.

Answer:
  Single Responsibility Principle (SRP): A class should have only one reason to change,
meaning it should have only one job.
 Open/Closed Principle (OCP): Software entities should be open for extension but
closed for modification.
 Liskov Substitution Principle (LSP): Objects of a superclass should be replaceable with
objects of a subclass without affecting the correctness of the program.
 Interface Segregation Principle (ISP): Clients should not be forced to depend on
interfaces they do not use.
 Dependency Inversion Principle (DIP): High-level modules should not depend on low-
level modules. Both should depend on abstractions.

Question:
How do you resolve a Git merge conflict?

Answer:

 First, use git status to identify the files that have conflicts.
 Open the conflicting files in a text editor and resolve the conflicts by manually editing the
sections with conflict markers.
 After resolving the conflicts, mark the files as resolved using:

git add <file_name>

 Finally, complete the merge by running

git commit

Question:
Explain the difference between quicksort and mergesort. Which one is better in practice?

Answer:

 QuickSort:
o Time Complexity: O(n log n) on average, but O(n²) in the worst case.
o Space Complexity: O(log n) (in-place sorting).
o Algorithm: QuickSort is a divide-and-conquer algorithm that picks a pivot
element and partitions the array such that elements smaller than the pivot go to its
left and larger elements go to its right, and then recursively applies the same to
subarrays.
o Best Use Case: Often used in practice due to its in-place sorting, faster average
performance, and cache efficiency.
 MergeSort:
o Time Complexity: O(n log n) in all cases.
o Space Complexity: O(n) (requires extra space for merging).
 o Algorithm: MergeSort is also a divide-and-conquer algorithm that divides the
array into halves, recursively sorts each half, and then merges the sorted halves.
o Best Use Case: Stable sorting (preserves order of equal elements) and guarantees
O(n log n) even in the worst case. Useful for linked lists or large datasets
requiring stable sorting.

Conclusion: QuickSort is generally faster and preferred in practice due to in-place sorting, but
MergeSort is more predictable in terms of performance.

Question:
Write a function for in-order traversal of a binary tree.

Answer: In-order traversal visits the nodes in the order: left subtree, root, right subtree.

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

def in_order_traversal(root):

result = []

def traverse(node):

if not node:

return

traverse(node.left) # Visit left subtree

result.append(node.val) # Visit root

traverse(node.right) # Visit right subtree

traverse(root)

return result

Question:
Write a function that performs binary search on a sorted array to find a target value.
Answer:

def binary_search(arr, target):

low, high = 0, len(arr) - 1

while low <= high:

mid = (low + high) // 2

if arr[mid] == target:

return mid

elif arr[mid] < target:

low = mid + 1

else:

high = mid - 1

return -1

Explanation:
Binary search works by repeatedly dividing the array in half and checking whether the target is greater
or smaller than the middle element. It has a time complexity of O(log n).

Question:
What are race conditions, and how can you prevent them?

Answer: A race condition occurs when the outcome of a program depends on the sequence or
timing of uncontrollable events, such as when multiple threads or processes access shared
resources concurrently.

How to prevent race conditions:

 Locks/Mutexes: Ensure that only one thread can access the critical section at a time.
 Atomic operations: Use atomic variables that can be modified in a single step, ensuring
thread safety without explicit locking.
 Synchronization mechanisms: Use mechanisms like semaphores or barriers to control
the sequence of execution.
 Volatile keyword (in some languages): Ensure that changes made by one thread are
visible to others immediately.

Question:
How would you design a hash table? What are the collision resolution strategies?

Answer: A hash table stores key-value pairs where each key is hashed to compute an index at
which the value is stored. The key challenges are:
 1. Hash Function: A good hash function distributes keys uniformly across the table.
2. Collision Handling: When two keys hash to the same index, collision handling strategies
are needed.

Collision resolution strategies:

 Chaining: Store multiple elements in the same bucket using a linked list.
 Open Addressing (Probing): When a collision occurs, find another open spot in the
array:
o Linear Probing: Check subsequent indices until an empty slot is found.
o Quadratic Probing: Use quadratic intervals to resolve collisions.
o Double Hashing: Use a second hash function to determine the step size for
resolving collisions.

Question:
What is the difference between a process and a thread?

Answer:

 Process:
o A process is an independent, self-contained unit that has its own memory space
(heap, stack, and data segments). Each process has its own address space and
resources.
o Processes are isolated from each other, and communication between processes
requires inter-process communication (IPC).
 Thread:
o A thread is a lightweight unit of execution that exists within a process. All threads
in a process share the same memory space (heap) but have separate stacks.
o Threads are easier to create and manage than processes, and they can directly
communicate with each other as they share the same address space.

Conclusion: Threads are faster and more efficient in terms of resource usage compared to
processes, but they also present challenges like synchronization to avoid race conditions.

Question:
What is the difference between TCP and UDP?

Answer:

 TCP (Transmission Control Protocol):

o Connection-oriented: Establishes a connection before transmitting data.
o Reliable: Ensures data is delivered in order and without loss, using error
checking, acknowledgments, and retransmission of lost packets.
o Use Case: Applications where reliability is crucial, such as HTTP, FTP, or email.
 UDP (User Datagram Protocol):
o Connectionless: Does not establish a connection before sending data.
 o Unreliable: Does not guarantee delivery, ordering, or error checking. Data
packets (datagrams) may arrive out of order or be lost.
o Use Case: Applications that require speed and can tolerate some data loss, like
video streaming, gaming, or VoIP.

Question:
How would you design a caching system? What eviction strategies would you use?

Answer: When designing a caching system, consider the following aspects:

 Cache Size: Define the maximum capacity of the cache to avoid consuming too much
memory.
 Key-Value Store: Use a hash table to store key-value pairs for fast lookups.

Eviction Strategies:

 LRU (Least Recently Used): Evict the least recently accessed item when the cache
reaches capacity.
 LFU (Least Frequently Used): Evict the item that is least frequently accessed.
 FIFO (First In, First Out): Evict the oldest item (the first item that was added) when the
cache is full.
 Random Eviction: Randomly evict items when the cache is full (simple but less
efficient).

Implementation (Example in Python):

python
from collections import OrderedDict

class LRUCache:

def __init__(self, capacity):

self.cache = OrderedDict()

self.capacity = capacity

def get(self, key):

if key not in self.cache:

return -1

self.cache.move_to_end(key)

return self.cache[key]
 def put(self, key, value):

if key in self.cache:

self.cache.move_to_end(key)

self.cache[key] = value

if len(self.cache) > self.capacity:

self.cache.popitem(last=False)

Question:
Write a query to find the employees who earn more than the average salary of the company.

Answer:

SELECT name, salary

FROM employees

WHERE salary > (SELECT AVG(salary) FROM employees);

This query calculates the average salary of all employees and then retrieves those whose salary is
greater than the average.

Question:
What is polymorphism in OOP, and how is it implemented in programming?

Answer: Polymorphism allows objects of different types to be treated as objects of a common

supertype. It is implemented in two forms:

1. Compile-time polymorphism (Method Overloading): The same method name is used

for different methods depending on the number or type of parameters.

class Math:

def add(self, a, b):

return a + b

def add(self, a, b, c):

return a + b + c

2. Run-time polymorphism (Method Overriding): A subclass provides a specific implementation of

a method that is already defined in its superclass.
3. class Animal:
4. def sound(self):
5. print("Some sound")
6. class Dog(Animal):
7. def sound(self):
8. print("Bark")
Polymorphism allows for flexibility and the ability to extend functionality without modifying
existing code.