SDE - Intern

Design and implement a Least Frequently Used(LFU) Cache, to implement the following functions:

1. put(U__ID, value): Insert the value in the cache if the key(‘U__ID’) is not already present or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting the new item.

2. get(U__ID): Return the value of the key(‘U__ID’),  present in the cache, if it’s present otherwise return -1.

Note:

  1) The frequency of use of an element is calculated by a number of operations with its ‘U_ID’ performed after it is inserted in the cache.

  2) If multiple elements have the least frequency then we remove the element which was least recently used. 

You have been given ‘M’ operations which you need to perform in the cache. Your task is to implement all the functions of the LFU cache.

Type 1: for put(key, value) operation.
Type 2: for get(key) operation.

Example:

We perform the following operations on an empty cache which has capacity 2:

When operation 1 2 3 is performed, the element with 'U_ID' 2 and value 3 is inserted in the cache.

When operation 1 2 1 is performed, the element with 'U_ID' 2’s value is updated to 1.  

When operation 2 2 is performed then the value of 'U_ID' 2 is returned i.e. 1.

When operation 2 1 is performed then the value of 'U_ID' 1 is to be returned but it is not present in cache therefore -1 is returned.

When operation 1 1 5 is performed, the element with 'U_ID' 1 and value 5 is inserted in the cache. 

When operation 1 6 4 is performed, the cache is full so we need to delete an element. First, we check the number of times each element is used. Element with 'U_ID' 2 is used 3 times (2 times operation of type 1 and 1-time operation of type 1). Element with 'U_ID' 1 is used 1 time (1-time operation of type 1). So element with 'U_ID' 1 is deleted. The element with 'U_ID' 6 and value 4 is inserted in the cache. 

Given a ‘N’ * ’M’ maze with obstacles, count and return the number of unique paths to reach the right-bottom cell from the top-left cell. A cell in the given maze has a value '-1' if it is a blockage or dead-end, else 0. From a given cell, we are allowed to move to cells (i+1, j) and (i, j+1) only. Since the answer can be large, print it modulo 10^9 + 7.

For Example :

Consider the maze below :
0 0 0 
0 -1 0 
0 0 0

There are two ways to reach the bottom left corner - 

(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)
(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)

Hence the answer for the above test case is 2.

Given a table of employees(id, name, salary), write an SQL query to find the second-highest salary.

Given two tables — customers(id, name) and orders(id, customer_id, order_date) — write an SQL query to find all customers who have never placed an order.

You are given the head of a doubly linked list. Your task is to convert this list into a singly linked list in-place.

A doubly linked list node has pointers to both the next and the previous node in the sequence. A singly linked list node only has a pointer to the next node.

To perform the conversion, you must iterate through the list and remove the prev pointer from every node by setting it to null. The sequence of nodes and their data, determined by the next pointers, must remain unchanged.

Your function should return the head of the modified list.

Build a notification service with retry mechanisms and an asynchronous architecture.

Write a mock code to calculate the factorial of a number, similar to the functionality in a phone calculator.

I was mainly asked about Java, including OOPs paradigms, runtime and compile-time polymorphism (Learn), the string pool, and comparisons between Java 8 and previous versions — primarily focusing on the Collection Framework.

Apart from that, I had a discussion on designing an Amazon cart system — covering what APIs would be needed, how to optimize the database, and how to scale the system.

That’s all!

• How are you going to manage here?
• What do you consider your weaknesses?
• What other programming languages do you know?