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 a point is inside or outside a circle

• Calculate the distance between the center of the circle and the given point using the distance formula

• If the distance is less than the radius of the circle, the point is inside the circle

• If the distance is equal to the radius of the circle, the point is on the circle

• If the distance is greater than the radius of the circle, the point is outside the circle

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

Negative elements in array won't affect binary search. Time complexity remains O(log n).

• Binary search works by dividing the array into two halves and comparing the middle element with the target element.

• If the middle element is greater than the target, search in the left half, else search in the right half.

• Negative elements won't affect this process as long as the array is sorted.

• Time complexity remains O(log n) as the search space is halved in each iteration.

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

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

Explaining page replacement algorithms like FIFO and LRU using a given page access sequence.

• FIFO (First-In-First-Out): Replaces the oldest page in memory.

• Example: Access sequence [1, 2, 3, 1, 2, 4] with 3 frames results in [1, 2, 4].

• LRU (Least Recently Used): Replaces the page that hasn't been used for the longest time.

• Example: Access sequence [1, 2, 3, 1, 2, 4] with 3 frames results in [2, 3, 4].

• Optimal: Replaces the page that will not be used for the longest time in the fut...read more

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 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 search conditions or join operations.

• Maintaining an index i...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 maintains the order of insertion while unordered map does not.

• Ordered map is implemented using a balanced binary search tree while unordered map is implemented using a hash table.

• Ordered map is useful when we need to maintain the order of insertion while unordered map is useful when we need faster access to elements.

• Example of ordered map: std::map in C++, Example of unordered map: std::unordered_map in C++

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

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) for search, insertion, and deletion.

• Example: Inserting 5, ...read more

Printing Fibonacci numbers using recursion only

• Define a recursive function that takes two arguments, n and a list to store the Fibonacci sequence

• Base case: if n is 0 or 1, return the list

• Recursive case: append the sum of the last two elements in the list to the list and call the function with n-1

• Call the function with n and an empty list to start the sequence

• Print the list of Fibonacci numbers

C++ program to find absolute difference between sum of diagonal elements

• Create a 2D array

• Calculate sum of diagonal elements

• Calculate absolute difference

• Print the result

Answering two puzzles - Plane and Fuel, and Two Wires Burned

• For the Plane and Fuel puzzle, calculate the amount of fuel needed for half the journey and then double it

• For the Two Wires Burned puzzle, light one wire at both ends and the other wire at one end only after the first wire has burned out halfway

• Both puzzles require creative thinking and problem-solving skills