100+ Sde1 Interview Questions and Answers

A list of technical questions related to data structures and algorithms in Java.

• Arrays are fixed in size while ArrayLists can dynamically grow and shrink.

• Queue can be implemented using a linked list by adding elements to the end and removing from the front.

• To fill a BST with a sorted array, we can recursively divide the array in half and add the middle element as the root.

• Random pointer linked-list clone can be done by creating a new node for each node in the original list an...read more

A doubly-linked list is a data structure where each node contains a reference to both the previous and next nodes.

• Allows traversal in both directions

• Used in implementing LRU cache

• Used in browser history

• Used in undo-redo functionality

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

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.

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 language

• Example: https://www.geeksforgeeks.org/n-queen-problem-b...read more

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: int *ptr = nullptr; int &ref = x; // not allowed

Typing a URL initiates a series of steps to retrieve and display the requested web page in the browser.

• 1. DNS Resolution: The browser checks the URL and queries a DNS server to translate the domain name into an IP address.

• 2. TCP Connection: A TCP connection is established with the server using the IP address, typically on port 80 (HTTP) or 443 (HTTPS).

• 3. Sending HTTP Request: The browser sends an HTTP request to the server, asking for the specific resource (e.g., HTML page).

• 4...read more

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 changing the value of an actual reference does.

• Reference variabl...read more

Discussing time complexities of data structures and algorithms is crucial for understanding performance in software development.

• Time complexity measures the amount of time an algorithm takes to complete as a function of the input size.

• Common complexities include O(1) for constant time, O(n) for linear time, and O(n^2) for quadratic time.

• For example, accessing an element in an array is O(1), while searching for an element in an unsorted array is O(n).

• Understanding these comple...read more

Burn one wire at both ends and the other wire at one end. When the first wire burns out, light the other end of the second wire.

• Burn one wire at both ends and the other wire at one end

• When the first wire burns out, light the other end of the second wire

• The second wire will burn for 15 minutes, totaling 45 minutes

In-memory DB stores data in RAM for faster access while MySQL stores data on disk.

• In-memory DB is faster than MySQL as it eliminates disk I/O operations.

• In-memory DB is suitable for real-time applications that require low latency.

• MySQL is suitable for applications that require data persistence and durability.

• In-memory DB may not be suitable for large datasets as it requires a lot of RAM.

• MySQL supports complex queries and transactions while In-memory DB may not.

• Examples of In-...read more

Name mangling is used by compilers to differentiate between different functions with the same signature.

• Name mangling is a process of encoding/decoding function names to include additional information such as parameter types and namespaces.

• This allows the compiler to differentiate between functions with the same name and signature.

• For example, in C++, two functions with the same name and signature but in different namespaces will have different mangled names.

• Name mangling is ...read more

Copy constructor creates a new object by copying the values of an existing object.

• Copy constructor is used to create a new object with the same values as an existing object.

• It is invoked when a new object is initialized with an existing object.

• It is used to avoid shallow copy and ensure deep copy of objects.

• Example: MyClass obj1; MyClass obj2 = obj1; //copy constructor called to create obj2

Print internal nodes of a binary tree (excluding left and right view nodes)

• Traverse the tree in post-order and check if the node has both left and right children

• If yes, then it is an internal node and print it

• If no, then continue traversing the tree

• Example: For the tree 1-2-4-5-3, the internal nodes are 2 and 4

Indexing in DBMS improves data retrieval speed by creating a data structure that allows quick access to records.

• Indexing creates a data structure (like B-trees) that maps keys to their corresponding records.

• It speeds up search queries, reducing the time complexity from O(n) to O(log n) in many cases.

• Types of indexes include primary, unique, composite, and full-text indexes.

• Example: A primary index on a student ID allows quick lookups of student records based on their IDs.

• Inde...read more

To fill a BST with a sorted array, we can use a recursive approach.

• Find the middle element of the array and make it the root of the BST

• Recursively construct the left subtree using the left half of the array

• Recursively construct the right subtree using the right half of the array

Memory leaks occur when allocated memory is not released, leading to resource exhaustion. Proper management is essential.

• Use smart pointers (e.g., std::unique_ptr, std::shared_ptr) in C++ to automatically manage memory.

• In Java, ensure that references to unused objects are set to null to allow garbage collection.

• Regularly use tools like Valgrind to detect memory leaks in C/C++ applications.

• In languages like Python, use weak references to prevent circular references that can le...read more

Smart pointers are objects that manage the memory of dynamically allocated objects, preventing memory leaks and dangling pointers.

• Smart pointers are a type of RAII (Resource Acquisition Is Initialization) technique.

• They automatically delete the object they point to when it is no longer needed.

• Examples of smart pointers include unique_ptr, shared_ptr, and weak_ptr in C++.

• They are used to prevent memory leaks and dangling pointers.

• I use Visual Studio Code as my IDE.

• Yes, I have ...read more

Virtual functions enable polymorphism in C++, allowing derived classes to override base class methods.

• Without virtual keyword: Base class method is called, even if derived class method exists.

• With virtual keyword: Derived class method is called, enabling dynamic binding.

• Example without virtual: Base class method 'show()' is called from a base class pointer.

• Example with virtual: Derived class method 'show()' is called from a base class pointer.

Ordered map is a map that maintains the order of its elements, while unordered map does not guarantee any specific order.

• Ordered map is implemented as a balanced binary search tree, such as Red-Black Tree or AVL Tree.

• Unordered map is implemented as a hash table, providing constant-time average complexity for search, insertion, and deletion.

• Ordered map is useful when the order of elements is important, such as maintaining a sorted list.

• Unordered map is more efficient for gener...read more

Virtual functions allow dynamic binding of functions at runtime. Vptr and Vtable are used to implement this feature.

• Virtual functions are declared in base class and can be overridden in derived classes.

• Vptr is a pointer to Vtable which contains addresses of virtual functions.

• Virtual function is needed to achieve polymorphism and to allow derived classes to have their own implementation of a function.

• Virtual functions are resolved at runtime based on the object type rather tha...read more

The height of the tree can be found by counting the number of edges from the root to the farthest leaf node.

• Count the number of edges from the root to the farthest leaf node

• This will give the height of the tree

• Example: If the farthest leaf node is 4 edges away from the root, the height of the tree is 4

Binary search in a rotated array can be done by finding the pivot point and then applying binary search on the two subarrays.

• Find the pivot point by comparing mid element with the first and last elements of the array

• Apply binary search on the two subarrays formed by the pivot point

• Repeat until the element is found or the subarray is empty

• Time complexity is O(log n)

• Example: [4,5,6,7,0,1,2], target=0. Pivot point is 3. Binary search on [4,5,6,7] and [0,1,2]

Caching is the process of storing frequently accessed data in a temporary storage to improve performance.

• Caching improves performance by reducing the need to fetch data from the original source.

• It involves storing data in a temporary storage, such as memory or disk, closer to the user or application.

• Caching can be done at various levels, including browser caching, server-side caching, and database caching.

• Examples of caching include caching web pages, caching database query r...read more