200+ SDE Interview Questions and Answers

LRU cache is a data structure that stores most recently used items and discards least recently used items.

• LRU stands for Least Recently Used

• It is implemented using a doubly linked list and a hash map

• When an item is accessed, it is moved to the front of the list

• When the cache is full, the least recently used item is removed from the end of the list

• Example: A web browser cache that stores recently visited web pages

Out of 9 identical marbles, find the one that is heavy.

• Divide the marbles into groups of three

• Weigh two groups against each other

• If one group is heavier, weigh two marbles from that group

• If they are equal, the heavy marble is in the third group

• If the weighed marbles are unequal, the heavy marble is in that group

Facebook implements graph search by indexing user data and using natural language processing.

• Facebook indexes user data to create a graph of connections and relationships.

• Natural language processing is used to interpret user queries and return relevant results.

• Graph search allows users to search for specific information within their network, such as 'friends who like hiking'.

Find k closest points to origin from a set of 2D points.

• Calculate distance of each point from origin using distance formula

• Sort the points based on distance in ascending order

• Return first k points from the sorted list

Find total possible valid unique combinations of given number of pairs of parenthesis without duplicity.

• Use recursion to generate all possible combinations

• Check for validity of each combination using a stack

• Use a set to avoid duplicity

A tree is a data structure consisting of nodes connected by edges, with a single root node and no cycles.

• Nodes represent elements of the tree, and edges represent the relationships between them.

• Each node can have zero or more child nodes, and each child node can have its own children.

• Trees are commonly used in computer science for organizing and searching data, such as in binary search trees.

• Examples of trees include file systems, family trees, and HTML document object models...read more

A graph can be called a tree if it is connected and has no cycles.

• A tree is a type of graph with no cycles.

• It must be connected, meaning there is a path between any two vertices.

• It has n-1 edges, where n is the number of vertices.

• Examples include family trees, file directory structures, and decision trees.

Reversing two halves of a linked list problem

• Identify input and output linked lists

• Reverse the two halves of the input linked list

• Compare the reversed input linked list with the output linked list

• If they match, return true else false

Convert Roman numerals to integer in O(n) time

• Create a dictionary to map Roman numerals to integers

• Iterate through the string from right to left

• If the current numeral is less than the previous, subtract it from the total

• Else, add it to the total

• Return the total

Sum all numbers formed from root to leaf paths in a binary tree

• Traverse the tree from root to leaf nodes, keeping track of the current number formed

• Add the current number to the sum when reaching a leaf node

• Recursively explore left and right subtrees

An algorithm to find top 10 trending words inserted by users in sites like Twitter.

• Collect a large dataset of tweets

• Tokenize the tweets into individual words

• Remove stop words and punctuation

• Count the frequency of each word

• Sort the words by frequency in descending order

• Select the top 10 words

Add mathematical operators to make given expressions true.

• Use addition, subtraction, multiplication, division, exponentiation, and parentheses to modify the expressions.

• For example, 5 - 3 + 2 = 4 can be made true by adding parentheses: 5 - (3 + 2) = 0.

• Another example is 6 6 6 6 = 4 can be made true by using square root: √6 ÷ √6 + √6 - √6 = 4.

Typing amazon.com in the browser's address bar takes you to Amazon's website.

• The browser sends a request to the DNS server to resolve the domain name 'amazon.com' to an IP address.

• The browser establishes a TCP connection with the server at the resolved IP address.

• The browser sends an HTTP request to the server for the homepage of Amazon's website.

• The server responds with the HTML code for the homepage, which the browser renders and displays to the user.

Find the first occurrence of 1 in a sorted binary array.

• Use binary search to find the first occurrence of 1.

• If the mid element is 1, check if it's the first occurrence or if the element before it is 0.

• If the mid element is 0, search in the right half of the array.

• If the mid element is 1 and the element before it is also 1, search in the left half of the array.

Sliding window problem to minimize partial sum of array.

• Use two pointers to maintain the window.

• Move the right pointer to expand the window and left pointer to shrink it.

• Keep track of the minimum partial sum seen so far.

• Example: Given array [2, 3, 1, 2, 4, 3] and window size 3, the minimum partial sum is 6.

Memory leakage is a situation where a program fails to release memory it no longer needs.

• Memory leakage can cause a program to slow down or crash due to insufficient memory.

• It is caused by programming errors such as not freeing allocated memory or losing references to it.

• Examples include forgetting to close a file or database connection, or not releasing memory allocated for a variable.

• Memory leakage can be detected using memory profiling tools.

• Preventing memory leakage invol...read more

Use sliding window technique to find starting indices of substring formed by concatenating words from list in string S.

• Create a hashmap to store the frequency of words in the list.

• Use sliding window of size equal to total length of all words combined.

• Slide the window through the string and check if the substring formed matches the hashmap.

• If match found, store the starting index of the substring.

Find 2 maximum elements in array in O(n+log(n)) comparison

• Use divide and conquer approach

• Divide array into two halves

• Recursively find max elements in each half

• Compare the two max elements to find the overall max elements

Populate sibling of a tree node with next node in same level with O(1) space complexity.

• Traverse the tree level by level using BFS.

• For each node, check if it has a sibling to its right.

• If yes, populate the sibling pointer of the current node with the right sibling.

• If no, move to the next level.

• Repeat until all levels are traversed.

A dynamic data structure for storing images as arrays of strings.

• Use a 2D array of strings to represent the image pixels.

• Implement resizing methods to adjust the size of the image.

• Include methods for adding, removing, and modifying pixels.

• Consider using compression techniques to reduce memory usage.

• Support various image formats such as JPEG, PNG, and BMP.

Babel is a JavaScript compiler that converts modern JavaScript code into backward-compatible versions for different environments.

• Babel allows developers to write code using the latest ECMAScript features without worrying about browser compatibility.

• It transforms code written in ES6/ES7 into ES5, which is supported by older browsers.

• Babel plugins can be used to add additional features or transform code in specific ways.

• It can also be configured to target specific environments ...read more

Stack data structure is used in function call stack, undo mechanisms, and expression evaluation.

• Function call stack in programming languages like C, Java, etc.

• Undo mechanisms in text editors and software applications.

• Expression evaluation in compilers and calculators.

Use a hash table to store phone numbers alongside names for quick lookups.

• Use a hash table where the keys are the phone numbers and the values are the corresponding names.

• This allows for constant time lookups of names based on phone numbers.

• Example: {"555-1234": "John Doe", "555-5678": "Jane Smith"}

Find the first occurrence of 1 in a sorted infinite binary tree.

• Use binary search to traverse the tree.

• If the current node is 1, check if its left child is also 1. If yes, move to the left subtree, else return the current node.

• If the current node is 0, move to the right subtree.

• Repeat until the first occurrence of 1 is found or the tree is exhausted.

Design a valet parking lot with ticket assignment and car retrieval using best fit and nearest distance.

• Create a parking lot with designated spots for each size of car

• Assign a ticket to the customer upon entry and record the spot number

• Retrieve the car by searching for the nearest available spot of the appropriate size

• Use best fit algorithm to minimize empty spots

• Implement a system for payment upon exit

Status updates can be implemented through various methods such as push notifications, real-time updates, and periodic polling.

• Use push notifications to instantly update users on important changes.

• Implement real-time updates using websockets or server-sent events for a seamless user experience.

• Periodically poll the server for updates using AJAX or other similar technologies.

• Provide a clear and concise interface for users to view and interact with status updates.

• Consider implem...read more

Counting the number of islands in a grid involves identifying connected groups of '1's in a 2D matrix.

• Iterate through each cell in the grid.

• If the cell is a '1', perform a depth-first search to mark all connected '1's as visited.

• Increment the island count for each new island found.

• Continue until all cells have been visited.

Facebook stores likes/dislikes as data points in their database.

• Likes and dislikes are stored as separate data points.

• Each like/dislike is associated with a unique ID for the post or comment.

• The data is stored in Facebook's database and can be accessed through their API.

• Likes/dislikes can also be used to personalize a user's newsfeed.

• Facebook also uses likes/dislikes to gather data for targeted advertising.

Construct a mirror tree from a given tree and return the root of the mirror tree.

• Traverse the given tree in a recursive manner.

• Swap the left and right child of each node.

• Return the root of the mirror tree.

Macros are preprocessor directives that replace code at compile time. They offer faster execution but can be error-prone.

• Macros are faster than functions as they are replaced at compile time

• Macros can be used for conditional compilation

• Macros can be used to define constants

• Macros can be error-prone as they do not undergo type-checking

• Macros can make code harder to read and debug

Foreign key is a key used to link two tables in a database, enforcing referential integrity.

• Foreign key is a column or a set of columns in one table that references the primary key in another table.

• It ensures that the values in the foreign key column(s) match the values in the primary key column of the referenced table.

• Foreign key constraints help maintain data integrity by preventing actions that would destroy links between tables.

• For example, in a database with tables 'Orde...read more

Remove duplicates from a string in O(n) without using hash

• Use an array of boolean values to keep track of characters already seen

• Iterate through the string and mark characters as seen in the array

• If a character has already been seen, remove it from the string

When you type amazon.com in a browser, it sends a request to the Amazon servers, which then respond by sending back the website's content to be displayed on your screen.

• Browser sends a DNS request to resolve the domain name 'amazon.com' to an IP address

• Browser establishes a TCP connection with the Amazon servers

• Browser sends an HTTP request to the Amazon servers for the website content

• Amazon servers process the request and send back the website content

• Browser renders the webs...read more

DSA stands for Data Structures and Algorithms. One commonly used data structure is an array.

• DSA is essential for solving complex problems efficiently.

• Data structures like arrays, linked lists, trees, graphs, etc., are used to store and manipulate data.

• Algorithms are used to perform operations on these data structures.

• Implementing an array involves creating a fixed-size collection of elements of the same type.

• Example: Implementing an array in C++ - int arr[5];

Developing frontend and backend for seamless data flow involves designing APIs, using frameworks like React and Node.js, and ensuring proper data validation and error handling.

• Design APIs to establish communication between frontend and backend

• Utilize frameworks like React for frontend and Node.js for backend development

• Implement proper data validation to ensure data integrity

• Handle errors effectively to maintain seamless data flow

I would invest in real estate, start a charitable foundation, and travel the world.

• Invest in real estate to generate passive income

• Start a charitable foundation to give back to the community

• Travel the world to experience different cultures and broaden my horizons

Virtual functions can cause problems due to their dynamic nature, but can be solved using various techniques.

• Use pure virtual functions to ensure all derived classes implement the function

• Use interface classes to define a common interface for all derived classes

• Use smart pointers to manage memory and avoid memory leaks

• Use virtual destructors to ensure proper destruction of objects

• Avoid excessive use of virtual functions to improve performance

The shortest distance between two farthest vertices in a cubical room is the length of the diagonal of the cube.

• The diagonal of a cube can be calculated using the formula: sqrt(3) * side length

• In a cube with side length 1 unit, the diagonal length is sqrt(3) units

• Therefore, the shortest distance between two farthest vertices in a cubical room is sqrt(3) times the side length of the cube

To fix code that is working properly, first identify the problem, analyze the code, make necessary changes, and test thoroughly.

• Identify the problem by reproducing the issue and understanding the expected behavior.

• Analyze the code to find any logical errors, syntax issues, or performance bottlenecks.

• Make necessary changes by modifying the code, fixing bugs, optimizing algorithms, or enhancing functionality.

• Thoroughly test the modified code to ensure it works as expected and d...read more

Tournament tree is a binary tree where each node represents a match between two players/teams.

• Tournament tree is used in sports tournaments to determine the winner.

• The leaf nodes represent the players/teams and the internal nodes represent the matches.

• The winner of each match is the node with the higher score.

• Code can be written using a recursive function to traverse the tree and determine the winner.

The seating arrangement in a movie theater typically consists of rows of seats facing a large screen.

• Seats are usually arranged in rows, with each row positioned higher than the one in front to ensure clear visibility of the screen.

• Seats may be numbered for easy identification and to help with ticket allocation.

• There are different types of seating arrangements such as standard seating, VIP seating, recliner seats, etc.

Array is a collection of elements stored in contiguous memory locations while linked list is a collection of nodes linked by pointers.

• Arrays have fixed size while linked lists can grow or shrink dynamically

• Insertion and deletion is faster in linked lists than arrays

• Accessing elements in arrays is faster than linked lists

• Arrays are better for random access while linked lists are better for sequential access

To find the top 10 selling products, sort the products by their sales count in descending order and select the first 10.

• Sort the products by their sales count in descending order

• Select the first 10 products from the sorted list

FB messages work by allowing users to send and receive text, images, videos, and other media through the Facebook platform.

• Messages can be sent to individuals or groups of people.

• Users can also send voice messages and make voice and video calls through the messaging feature.

• Messages can be archived or deleted, and users can also choose to ignore or block certain senders.

• Facebook uses end-to-end encryption to protect the privacy and security of messages.

• Messages can be accesse...read more

FB Mail is a messaging service that allows Facebook users to send and receive messages from other users.

• FB Mail is integrated into the Facebook platform and can be accessed through the Messenger app or website.

• Users can send messages to individuals or groups, and can also attach files, photos, and videos.

• FB Mail also includes features such as message requests, message filtering, and message archiving.

• Messages can be sent and received in real-time, and users can also receive n...read more

Sort a stack using recursion.

• Pop the top element from the stack and recursively sort the remaining stack.

• Insert the popped element in the correct position in the sorted stack.

• Repeat until the entire stack is sorted.

• Use a helper function to insert the element in the correct position.

• Time complexity: O(n^2), space complexity: O(n) due to recursion.

• Example: Input stack - [5, 2, 7, 1], Output stack - [1, 2, 5, 7]

A function to delete nodes from a Dequeue.

• Create a function that takes the Dequeue and the value of the node to be deleted as parameters.

• Traverse the Dequeue to find the node with the given value.

• If the node is found, update the pointers of the previous and next nodes to bypass the node to be deleted.

• If the node is the first or last node, update the head or tail pointers accordingly.

• Free the memory allocated to the node.

• Handle cases where the Dequeue is empty or the node is n...read more