Hot Topics
Navi Solution
Technical Round
Longest valid parentheses.
The longest valid parentheses is a problem in computer science that asks to find the length of the longest contiguous sub-string of a given string that consists of matching pairs of parentheses. The most common way to solve this problem is to use a stack to keep track of the positions of the last unmatched open parenthesis. When a closing parenthesis is encountered, the corresponding open parenthesis is popped from the stack and the length of the current valid substring is calculated by taking the difference between the current position and the position at the top of the stack. This process is repeated for each closing parenthesis, and the longest substring is returned at the end.
Design parking lot with various vehicle types, multiple floors, multiple entry & exists, admin, parking attendant, parking attendant on entry gate can create ticket and return payment receipt, admin can create parking lot, add floors, add spots, different pricing for each vehicle type.
A possible design for a parking lot with various vehicle types, multiple floors, multiple entry & exits, admin, parking attendants, and the ability for parking attendants on entry gates to create tickets and return payment receipts, as well as for admin to create parking lots, add floors, add spots, and set different pricing for each vehicle type, could include the following components:
Parking Lot Class: This class would contain information about the parking lot, such as the number of floors, the number of spots, and the pricing for each vehicle type. The admin would use this class to create a new parking lot and add floors and spots.
Floor Class: This class would contain information about each floor of the parking lot, such as the number of spots and the types of spots (e.g. handicapped, electric vehicle). The admin would use this class to add floors to the parking lot.
Spot Class: This class would contain information about each spot, such as its type (e.g. handicapped, electric vehicle), its availability, and its pricing. The admin would use this class to add spots to the parking lot.
Ticket Class: This class would contain information about each ticket, such as the vehicle type, the time of entry, the time of exit, and the cost. The parking attendants would use this class to create tickets and return payment receipts.
Entry/Exit Class: This class would manage the entry and exit of vehicles in the parking lot. It would be responsible for assigning spots to vehicles, keeping track of the number of available spots, and updating the availability of spots.
Admin Class: This class would be responsible for creating parking lots, adding floors, adding spots, and setting different pricing for each vehicle type.
Parking Attendant Class: This class would be responsible for creating tickets and returning payment receipts. The parking attendant at the entry gate would use this class to create a ticket when a vehicle enters the parking lot.
Payment Class: This class would be responsible for handling payment from the customer. It would be used by parking attendants to return payment receipts.
Report Class: This class would be used by the admin to generate reports about the parking lot, such as the number of vehicles parked, the revenue generated, and the occupancy rate.
It’s important to note that this is one possible design, and different requirements and constraints may lead to different designs.
What is hashing and indexing in DBMS?
Hashing and indexing are two techniques used in database management systems (DBMS) to improve the performance of data retrieval operations.
Hashing is a process of transforming a large, potentially variable-sized key into a smaller, fixed-size value, called a hash code, which represents the original key. The hash code is used as an index to access the data associated with the key in a data structure called a hash table. The goal of hashing is to distribute the keys uniformly across the hash table, so that the average number of keys that map to the same location, called a bucket, is small. This allows for fast retrieval of data, as the key can be transformed into the hash code, which is then used to directly access the data in the hash table.
Indexing is a technique used to create a separate data structure that stores a subset of the data in a table, along with a pointer to the location of the corresponding data in the table. The index is used to quickly locate the data in the table based on the indexed attributes, rather than having to scan the entire table. The index can be created on one or more columns of a table, and different types of indexes, such as B-tree or bitmap indexes, can be used depending on the specific use case.
In summary, Hashing is a technique used to map large keys to small fixed-size values and is used for quick data retrieval, where as Indexing is a technique used to create a separate data structure that stores a subset of the data in a table, along with a pointer to the location of the corresponding data in the table, for fast data retrieval.
How do b-trees work?
B-trees are a type of balanced tree data structure that are commonly used in database management systems (DBMS) and file systems to store and retrieve data efficiently. They are an extension of the more basic binary trees, and are designed to work with large amounts of data that do not fit in main memory.
A B-tree is a self-balancing tree that maintains a certain degree of balance by enforcing certain constraints on the number of keys that can be stored in each node. Each node in a B-tree can have multiple keys and multiple children. In a B-tree of order m, each node can have at most m-1 keys and m children. The root node must have at least 2 children, and all other nodes must have at least m/2 children.
The structure of a B-tree is such that all the keys in a node are sorted in ascending order, and the keys in the leftmost subtree of a node are less than the keys in the node, while the keys in the rightmost subtree of a node are greater than the keys in the node. This allows for fast searching, insertion, and deletion operations.
When a new key is inserted into a B-tree, it is inserted into the leaf node in the appropriate position, such that the keys in the node remain sorted in ascending order. If the number of keys in the node exceeds the maximum number allowed, the node is split into two, and the median key is promoted to the parent node. If the parent node also becomes full, it is also split and the process continues until a node with room for the new key is found.
When a key is deleted from a B-tree, it is first searched for in the leaf node where it should be located. If the key is found, it is removed from the node, and if the number of keys in the node falls below the minimum number allowed, the node is merged with one of its siblings. If a parent node loses too many keys, it is also merged with one of its siblings and the process continues until a node with the correct number of keys is found.
In summary, B-trees are a type of balanced tree data structure that are designed to work with large amounts of data that do not fit in main memory. They maintain a balance by enforcing certain constraints on the number of keys that can be stored in each node, and allow for fast searching, insertion, and deletion operations by maintaining a sorted order of keys in each node.
If I had to design a social media with likes and posts, what all classes/structures would I need?
If you were to design a social media platform with likes and posts, you would likely need several classes and structures to manage the different components of the system. Here is an example of some classes and structures that could be used:
User Class: This class would contain information about each user, such as their name, username, password, and list of friends or followers.
Profile Class: This class would contain information about a user’s profile, such as their bio, profile picture, and a list of posts.
Post Class: This class would contain information about each post, such as the text, image, video, or other content, the time it was posted, and a list of likes.
Like Class: This class would contain information about each like, such as the user who liked the post and the time the like was given.
Feed Class: This class would be responsible for managing the user’s feed, which is the collection of posts from the users they follow. It would be used to retrieve and display the most recent posts from the users a user follows.
Search Class: This class would be responsible for searching for users, posts, and other content on the platform. It would allow users to search by keyword, username, and other criteria.
Notification Class: This class would be responsible for managing notifications for a user, such as when someone likes or comments on their post, or when someone sends them a friend request.
Comment Class: This class would contain information about each comment, such as the text, the time it was posted, and the user who posted it.
Friend Class: This class would contain information about each friend, such as the user’s name, username, and profile picture.
It’s important to note that this is one possible design, and different requirements and constraints may lead to different designs.
How to build a Ledger system?
Building a ledger system involves several steps, and the exact implementation will depend on the specific requirements and constraints of the system. However, a general outline of the steps to build a ledger system could include:
Define the requirements: Identify the specific needs of the system, such as the type of transactions that will be recorded, the number of users that will access the system, and the level of security and privacy that is required.
Choose a consensus mechanism: Decide on the consensus mechanism that will be used to maintain the integrity of the ledger. Common consensus mechanisms include proof-of-work, proof-of-stake, and Byzantine fault tolerance.
Design the data structure: Determine the data structure that will be used to store the transactions on the ledger. This could include a linked list, a blockchain, or a directed acyclic graph.
Implement the ledger: Write the code to implement the ledger system, including the functions for adding, modifying, and deleting transactions, as well as the functions for maintaining the integrity of the ledger.
Implement security: Implement security features such as encryption, authentication, and access control to protect the ledger from unauthorized access and tampering.
Test the system: Test the ledger system thoroughly to ensure that it is functioning correctly and that all the requirements are met.
Deploy the system: Deploy the ledger system in a suitable environment, such as a cloud-based or on-premises infrastructure, and make it accessible to the users.
Monitor and maintain the system: Regularly monitor the system for any issues or errors and make updates and improvements as necessary.
It’s important to note that building a ledger system like a blockchain, requires a lot of knowledge and expertise, and it is highly recommended to consult with professionals in the field before attempting to build one. Also, it’s important to keep in mind that building a ledger system is not a trivial task, it involves a lot of planning and development, and it may take a significant amount of time and resources.
What is time complexity of searching in cache, and how?
The time complexity of searching in a cache refers to the amount of time it takes to find a specific item in the cache. The time complexity of searching in a cache is typically measured in terms of the number of operations required to find an item, such as the number of comparisons or the number of memory accesses.
There are different cache structures that have different time complexities for searching. The most commonly used cache structures are:
Direct-mapped cache: In this cache structure, each block of memory has a unique location in the cache. The time complexity of searching in a direct-mapped cache is O(1) or constant time, meaning that the time it takes to find an item is independent of the number of items in the cache.
Fully associative cache: In this cache structure, each block of memory can be stored in any location in the cache. The time complexity of searching in a fully associative cache is O(n), where n is the number of items in the cache. This is because the search algorithm has to compare the memory address of the item being searched for with the memory addresses of all the items in the cache.
Set-associative cache: In this cache structure, the cache is divided into a number of sets, and each set can store multiple blocks of memory. The time complexity of searching in a set-associative cache is typically O(m), where m is the number of blocks in each set. This is because the search algorithm has to compare the memory address of the item being searched for with the memory addresses of all the items in the set.
In general, the time complexity of searching in a cache can be improved by using a smaller cache size, increasing the associativity of the cache, or by using more sophisticated search algorithms.
It’s worth mentioning that, the time complexity is just a theoretical way to measure the performance of an algorithm. It’s a way of understanding how the performance of an algorithm will behave as the input size increases. In practice, the time complexity alone is not enough to determine the actual performance of an algorithm, as there are other factors that can affect it such as the specific hardware, the specific implementation, and the specific input dataset.
Implement an event based queue similar to SNS.
Here is an example of how you might implement an event-based queue similar to Amazon Simple Notification Service (SNS) using Python:
import threading
class EventQueue:
def __init__(self):
self.subscribers = []
self.queue = []
self.lock = threading.Lock()
def subscribe(self, subscriber):
with self.lock:
self.subscribers.append(subscriber)
def unsubscribe(self, subscriber):
with self.lock:
self.subscribers.remove(subscriber)
def enqueue(self, event):
with self.lock:
self.queue.append(event)
self._notify()
def _notify(self):
for subscriber in self.subscribers:
threading.Thread(target=subscriber.notify, args=(self.queue,)).start()
def dequeue(self):
with self.lock:
return self.queue.pop(0)
class Subscriber:
def __init__(self, name):
self.name = name
def notify(self, queue):
event = queue.dequeue()
print(f'{self.name} received event: {event}')In this example, the EventQueue class is the main component of the system. It maintains a list of subscribers, a queue of events, and a lock to control access to the shared data. The subscribe method is used to add a new subscriber to the list, the unsubscribe method is used to remove a subscriber from the list, and the enqueue method is used to add a new event to the queue. The _notify method is used to notify all the subscribers that there is a new event in the queue, it does this by starting a new thread for each subscriber, this way the subscribers will be notified concurrently.
The Subscriber class represents a consumer of events. It has a name attribute and a notify method that is called when there is a new event in the queue. The notify method removes the next event from the queue and prints the event.
In order to use this event-based queue, you would first create an instance of the EventQueue class, then create instances of the Subscriber class and subscribe them to the event queue, and then enqueue events to the queue.
queue = EventQueue()
subscriber1 = Subscriber("Subscriber 1")
subscriber2 = Subscriber("Subscriber 2")
queue.subscribe(subscriber1)
queueArray having 0s and 1s in sorted rows, find the row with min number of 1s.
You can find the row with the minimum number of 1s by iterating through the array and counting the number of 1s in each row. Keep track of the row with the current minimum number of 1s and update it if a new row with fewer 1s is found. Once you’ve gone through all the rows, the row with the minimum number of 1s will be the one you’ve been keeping track of.
Construct a framework for simple API.
Here is a basic framework for a simple API:
Define the endpoints: Decide on the URLs that the API will serve, and what type of HTTP requests (GET, POST, etc.) will be accepted at each endpoint.
Set up routing: Use a framework such as Express.js to handle routing and route incoming requests to the appropriate endpoint handlers.
Implement endpoint handlers: Write JavaScript functions that will handle requests made to each endpoint. These functions should process the incoming request data, interact with any necessary databases or external APIs, and return appropriate responses.
Validate requests: Implement request validation to ensure that incoming requests contain required data and that the data is in the correct format.
Handle errors: Write error-handling code to handle any unexpected errors that may occur during the processing of requests.
Document API: Create documentation for the API, including instructions on how to make requests, the structure of expected requests and responses, and any relevant error codes.
Test API: Test the API thoroughly to ensure that it is functioning as expected and that all endpoints return appropriate responses.
Deploy API: Deploy the API to a hosting service or server, making it accessible to external clients.
This is just a simple starting point, Depending on the complexity of the API, you might need to think about things like security, rate limiting, and scalability, among other things.
GitHub clone with search, filter dropdown, etc.
Here is a basic framework for building a GitHub clone with search, filter dropdown, and other features:
Set up a development environment: This might include installing necessary tools such as Git, Node.js, and a text editor.
Define project requirements: Determine what specific features are needed for the GitHub clone, such as search functionality, filter dropdown, etc.
Create the basic layout: Use a front-end framework such as React to build the basic layout of the application, including navigation and basic page structure.
Implement the search feature: Use the GitHub API to retrieve data for repositories and users. Create a search feature that allows users to search for repositories and users by keywords.
Add filter dropdown: Use a dropdown menu that allows users to filter search results by various criteria, such as language, number of stars, and date created.
Implement the repository and user pages: Create separate pages for repositories and users that display detailed information such as the repository’s description, number of stars, and contributors.
Implement user authentication: Allow users to sign up, log in, and log out of the application.
Test the application: Test the application thoroughly to ensure that all features are working as expected and that there are no bugs or errors.
Deploy the application: Deploy the application to a hosting service such as GitHub Pages or Heroku for others to access.
This is just a basic starting point and depending on the complexity of the application, you might need to think about more things like security, scalability, and performance.
Make structure of twitter like platform Stack questions.
Here is a basic structure for a Twitter-like platform for posting and answering stack questions:
User accounts: Allow users to create an account, login, and manage their profile, including the ability to edit their profile information and upload a profile picture.
Questions: Allow users to post questions, including a title, a detailed description, and tags.
Answers: Allow other users to answer questions posted by others, including the ability to add text, images, or code snippets to their answers.
Comments: Allow users to comment on both questions and answers, so they can ask for more information or give additional insights.
Voting: Allow users to upvote or downvote both questions and answers, in order to provide a way for the community to indicate which answers are most helpful.
Search and filter: Implement a search feature that allows users to search for questions by keywords or tags, as well as a filter feature that allows users to sort questions by relevance, date, or number of answers.
Notification: Implement a notification system that alerts users when their question or answer receives a new comment, upvote, or answer.
User reputation: Create a reputation system that rewards users for posting high-quality questions, answers, and comments.
Moderation: Implement a moderation system that allows administrators to review and remove inappropriate content.
Security: Implement various security features to protect the platform from various types of attacks, such as SQL injection or cross-site scripting(XSS).
This is just a basic starting point, depending on the complexity of the platform, you might need to think about more things like scalability, performance, and analytics.
Design a system to automate a CRM system for Navi sales agents. Array having 0s and 1s in sorted rows, find the row with min number of 1s.
Here is a basic design for a system to automate a CRM system for Navi sales agents:
Data storage: Use a database management system, such as MySQL or MongoDB, to store customer information, including contact details, purchase history, and any notes made by the sales agent.
Lead management: Create a system that allows sales agents to input and track leads, including assigning them to specific agents and tracking the status of each lead.
Contact management: Create a system that allows sales agents to view, add, and edit customer contacts, including contact information, purchase history, and notes.
Sales pipeline management: Create a system that allows sales agents to track the progress of each sale, including the ability to move a lead through different stages of the sales process, such as “contact made” or “proposal sent”.
Reporting: Create a reporting system that allows managers to view sales data and track the performance of individual sales agents.
Automated tasks: Implement automated tasks such as sending follow-up emails or scheduling calls, to help sales agents stay organized and on top of their leads.
Array handling: Create a function that takes in a 2D array of 0s and 1s and returns the row with the minimum number of 1s. This can be done by iterating through the array, counting the number of 1s in each row, and keeping track of the row with the lowest count.
Security: Implement various security features to protect the system from unauthorized access, such as user authentication and encryption of sensitive data.
Scalability: Design the system to be scalable, so it can handle an increasing number of sales agents and customers as the company grows.
This is just a basic starting point, depending on the complexity of the CRM system, you might need to think about more things like integrations, analytics, and user experience.
Coin Exchange Problem find all path in tree with sum k.
Here is a basic approach for solving the Coin Exchange Problem, which involves finding all paths in a tree with a specific sum (k):
Create a recursive function that takes in the current node and the current sum as arguments.
Check if the current sum is equal to k. If it is, add the current path to a list of paths with a sum of k.
If the current node has children, call the recursive function for each child, passing in the child node and the current sum plus the value of the child node.
If the current node is a leaf node (i.e. has no children), return to the parent node and backtrack to the previous path.
Repeat steps 2-4 for all nodes in the tree.
Return the list of paths with a sum of k.
Here is a simple example of a Python implementation:
def find_paths(root, sum, path, paths):
if not root:
return
path.append(root.val)
if root.val == sum and not root.left and not root.right:
paths.append(list(path))
else:
find_paths(root.left, sum-root.val, path, paths)
find_paths(root.right, sum-root.val, path, paths)
path.pop()
def find_paths_with_sum(root, sum):
paths = []
find_paths(root, sum, [], paths)
return pathsThis function will find all the path from root to leaf in the tree, that sum up to k.
Keep in mind that this approach has a time complexity of O(N^2) where N is the number of nodes in the tree, as it’s traversing all the nodes and for each node, it’s traversing the path and checking if the sum matches k.
Coin Exchange Problem find all path in tree with sum k.
Here is a basic approach for finding the largest substring with non-repeating characters using Ternary Search:
Create a function that takes in a string as an argument.
Initialize three pointers, left, middle, and right, to the start of the string.
Iterate over the string, starting from the middle pointer.
For each character, check if it has appeared before in the substring between the left and middle pointers.
If it has not appeared before, move the right pointer to the next character.
If it has appeared before, move the left pointer to the next character after the previous occurrence of the character.
Keep track of the maximum substring length and update it if a larger substring is found.
Repeat steps 4-7 for the middle and right pointers.
Return the maximum substring length.
Here is a simple example of a Python implementation:
def find_largest_substring(s):
left = 0
middle = 0
right = 0
max_length = 0
char_map = {}
while right < len(s):
if s[right] not in char_map:
char_map[s[right]] = right
right += 1
max_length = max(max_length, right - left)
elif middle <= char_map[s[right]]:
left = char_map[s[right]] + 1
middle = left
char_map[s[right]] = right
right += 1
else:
middle += 1
char_map[s[right]] = right
right += 1
return max_lengthThis approach uses a sliding window, and with the help of a hashmap to keep track of the last position of each character, it’s able to determine if a character is repeating or not. The time complexity of this approach is O(n) and the space complexity is O(n) as well.
Automata Fixing