Airtel X- Labs Interview Questions and Answers

Design a URL shortener

• Generate a unique short code for each URL

• Store the mapping of short code to original URL in a database

• Redirect users to the original URL when they access the short code

Find two elements in an array that sum up to a specified target value.

• Use a hash set to store elements as you iterate through the array.

• For each element, check if (target - element) exists in the set.

• If it exists, you've found a pair; if not, add the element to the set.

• Example: For array [1, 2, 3, 4] and sum 5, the pair is (1, 4) or (2, 3).

• Time complexity is O(n) due to single pass through the array.

LRU cache implementation using doubly linked list and hash map.

• Use a doubly linked list to keep track of the order of elements in the cache.

• Use a hash map to store the key-value pairs for fast access.

• When a new element is added, check if the cache is full and remove the least recently used element.

• When an element is accessed, move it to the front of the linked list.

Program to find the Next Smaller Element

• Create an empty stack

• Traverse the array from right to left

• Pop elements from stack until a smaller element is found

• If no smaller element is found, output -1

• Push the current element onto the stack

Return odd and even numbers from two stacks, one full and one empty, without using any other memory.

• Pop elements from full stack and check if it's odd or even

• Push odd elements to one stack and even elements to another

• Push elements back to full stack in alternating order

• Time complexity: O(n), Space complexity: O(1)

CAP theorem states that a distributed system cannot guarantee consistency, availability, and partition tolerance at the same time.

• Consistency: all nodes see the same data at the same time

• Availability: every request receives a response, without guarantee that it contains the most recent version of the information

• Partition tolerance: the system continues to function even when network partitions occur

• Examples: Cassandra p...read more

Deadlock occurs when two or more processes are unable to proceed because each is waiting for the other to release resources.

• Deadlock can happen in multi-threaded applications when resources are locked.

• Example: Thread A locks Resource 1 and waits for Resource 2, while Thread B locks Resource 2 and waits for Resource 1.

• Deadlock detection algorithms can help identify deadlocks in systems.

• Avoiding deadlock can be achieved ...read more