Google Sde1 Interview Questions and Answers

N queen problem is to place N queens on an NxN chessboard without any two queens threatening each other.

• The problem can be solved using backtracking algorithm

• Start with placing a queen in the first row and move to the next row

• If no safe position is found, backtrack to the previous row and try a different position

• Repeat until all queens are placed or no safe position is found

• Code can be written in any programming langua...read more

Check if there exists any sub array with given sum in the array with O(1K) space complexity.

• Use two pointers to traverse the array and maintain a current sum.

• If the current sum is greater than the given sum, move the left pointer.

• If the current sum is less than the given sum, move the right pointer.

• If the current sum is equal to the given sum, return true.

NP hardness refers to the difficulty of solving a problem in non-deterministic polynomial time.

• NP-hard problems are some of the most difficult problems in computer science.

• They cannot be solved in polynomial time by any known algorithm.

• Examples include the traveling salesman problem and the knapsack problem.

References and pointers are both used to access memory locations, but references cannot be null and cannot be reassigned.

• Pointers can be null and can be reassigned to point to different memory locations.

• References are automatically dereferenced, while pointers need to be explicitly dereferenced.

• Pointers can perform arithmetic operations, while references cannot.

• Example: int x = 5; int *ptr = &x; int &ref = x;

• Example: i

A reference variable is a variable that holds the memory address of an object, while an actual reference is the object itself.

• A reference variable is declared with a specific type and can only refer to objects of that type.

• An actual reference is the object itself, which can be accessed and manipulated using the reference variable.

• Changing the value of a reference variable does not affect the original object, but changi...read more

When we type an URL, the browser sends a request to the server hosting the website and retrieves the corresponding webpage.

• The browser parses the URL to extract the protocol, domain, and path.

• It resolves the domain name to an IP address using DNS.

• The browser establishes a TCP connection with the server.

• It sends an HTTP request to the server.

• The server processes the request and sends back an HTTP response.

• The browser re

Implementation of LRU cache using a doubly linked list and a hash map.

• LRU (Least Recently Used) cache is a data structure that stores a fixed number of items and evicts the least recently used item when the cache is full.

• To implement LRU cache, we can use a doubly linked list to maintain the order of items based on their usage frequency.

• We can also use a hash map to store the key-value pairs for quick access and retrie...read more

Indexing in DBMS is a technique to improve query performance by creating a data structure that allows faster data retrieval.

• Indexing is used to speed up data retrieval operations in a database.

• It involves creating a separate data structure that maps the values of a specific column to their corresponding records.

• This data structure is called an index.

• Indexes are typically created on columns that are frequently used in s...read more

B trees and B+ trees are data structures used for efficient storage and retrieval of data in databases.

• B trees are balanced trees with a variable number of child nodes per parent node. They are commonly used in databases to store large amounts of data.

• B+ trees are a variant of B trees where all data is stored in the leaf nodes, and the internal nodes only contain keys. They are commonly used in databases for indexing.

• B...read more

AVL trees are self-balancing binary search trees. They maintain a balance factor to ensure height balance.

• AVL trees are named after their inventors, Adelson-Velsky and Landis.

• They are height-balanced, meaning the difference in height between left and right subtrees is at most 1.

• Insertion and deletion operations may cause imbalance, which is corrected by rotations.

• AVL trees have a worst-case time complexity of O(log n) ...read more

Given a list of process IDs and their corresponding parent process IDs, print the IDs of all processes that are children of a specific process ID, and recursively kill all their children.

• Iterate through the list of process IDs and parent process IDs

• Check if the current process ID is the one to be killed

• If yes, recursively find and print all its children

• If a child has further children, recursively kill them as well