Are your preparing for SDE? Here is what may ask

Here’s a list of 30 most asked interview questions at Google for Software Development Engineer (SDE) positions, including topics on Data Structures and Algorithms (DSA), Algorithms, C++, Java, and Object-Oriented Programming (OOP).

Data Structures & Algorithms (DSA)

1. What is the difference between an array and a linked list?
   • Answer: An array is a collection of elements stored in contiguous memory locations, whereas a linked list is a collection of nodes where each node contains data and a reference to the next node in memory. Arrays allow fast random access, but linked lists allow efficient insertion and deletion.
2. Explain how a stack works.
   • Answer: A stack follows Last In First Out (LIFO) principle. The two main operations are push (adding an element) and pop (removing an element). You can only access the top element of the stack at any given time.
3. What is the difference between a queue and a stack?
   • Answer: A stack follows LIFO, while a queue follows First In First Out (FIFO). In a stack, the last element added is the first to be removed, whereas in a queue, the first element added is the first to be removed.
4. How would you implement a queue using two stacks?
   • Answer: To implement a queue using two stacks, one stack (stack1) is used to enqueue elements, and the other stack (stack2) is used to dequeue elements. When dequeue is called, we move all elements from stack1 to stack2 and pop from stack2.
5. Explain the difference between a binary tree and a binary search tree (BST).
   • Answer: A binary tree is a tree data structure where each node has at most two children. A binary search tree (BST) is a type of binary tree where the left child is smaller than the parent node, and the right child is larger than the parent node, providing efficient searching, insertion, and deletion operations.
6. What is a heap? Explain the difference between a max-heap and a min-heap.
   • Answer: A heap is a binary tree where each parent node satisfies the heap property (either max or min). In a max-heap, the value of each parent node is greater than or equal to its children, while in a min-heap, the value of each parent node is less than or equal to its children.
7. What is the time complexity of searching in a binary search tree?
   • Answer: The time complexity for searching in a binary search tree is O(h), where h is the height of the tree. In the worst case (unbalanced tree), the height can be O(n). In a balanced BST, it is O(log n).
8. Explain the concept of dynamic programming.
   • Answer: Dynamic programming (DP) is an optimization technique for solving problems by breaking them down into simpler subproblems and solving each subproblem only once, storing the results to avoid redundant computations. DP is used when the problem has overlapping subproblems and optimal substructure.
9. What is the difference between Depth-First Search (DFS) and Breadth-First Search (BFS)?
   • Answer: DFS explores a graph or tree by going deep into a branch before backtracking, while BFS explores level by level, visiting all neighbors of a node before moving to the next level. DFS uses a stack, and BFS uses a queue.
10. Explain the time complexity of quicksort.
    • Answer: The average time complexity of quicksort is O(n log n), but the worst-case time complexity is O(n²), which occurs when the pivot selection is poor. QuickSort’s worst-case can be avoided with techniques like random pivoting.

Algorithms

11. What is the difference between merge sort and quicksort?
    • Answer: Merge sort is a divide-and-conquer algorithm that divides the array into halves, sorts them, and then merges the sorted halves. QuickSort, also divide-and-conquer, partitions the array around a pivot element, and recursively sorts the subarrays. MergeSort is stable and has O(n log n) time complexity in all cases, whereas QuickSort has O(n log n) on average but can degrade to O(n²) in the worst case.
12. How do you find the nth Fibonacci number using dynamic programming?
    • Answer: Using dynamic programming, we can calculate the Fibonacci sequence in O(n) time by storing previously calculated Fibonacci numbers in a table (either iteratively or recursively with memoization) to avoid redundant calculations.
13. What is the time complexity of binary search?
    • Answer: The time complexity of binary search is O(log n), as the search space is halved at each step.
14. Explain Dijkstra’s algorithm.
    • Answer: Dijkstra’s algorithm finds the shortest path between two nodes in a graph with non-negative edge weights. It maintains a set of visited nodes and iteratively selects the unvisited node with the smallest known distance, updating the distances of its neighbors.
15. What is the traveling salesman problem?
    • Answer: The traveling salesman problem (TSP) asks for the shortest possible route that visits a set of cities and returns to the origin city. It is a classic NP-hard problem, meaning there is no known efficient solution for large datasets.
16. What is a greedy algorithm?
    • Answer: A greedy algorithm makes the locally optimal choice at each step with the hope of finding the global optimum. It doesn’t guarantee the optimal solution for all problems but works well for problems like Huffman coding or coin change problem when the problem has optimal substructure.
17. Explain the Knapsack problem.
    • Answer: The 0/1 knapsack problem involves selecting items with given weights and values to maximize the total value in a knapsack, without exceeding its weight capacity. It is typically solved using dynamic programming.
18. What is the time complexity of merge sort?
    • Answer: The time complexity of merge sort is O(n log n) for the average and worst case. It is more efficient than bubble sort and insertion sort, which have O(n²) complexity.
19. How do you detect a cycle in a directed graph?
    • Answer: To detect a cycle in a directed graph, you can use Depth-First Search (DFS). During DFS, if you encounter a node that is already in the current recursion stack, it indicates a cycle.
20. What is the difference between a brute force approach and an optimized approach in algorithms?
    • Answer: A brute force approach solves the problem by trying all possible solutions, often inefficiently, while an optimized approach uses techniques like dynamic programming, greedy algorithms, or data structures to reduce the time complexity and find a more efficient solution.

C++

21. Explain the difference between a pointer and a reference in C++.
    • Answer: A pointer holds the memory address of a variable, and it can be reassigned to point to different variables. A reference is an alias for another variable and cannot be reassigned once initialized.
22. What are the advantages of using STL (Standard Template Library) in C++?
    • Answer: The STL provides pre-built, optimized data structures and algorithms (like vectors, lists, sets, maps, etc.) that help improve productivity, reduce the need to write custom code, and provide efficient solutions to common problems.
23. Explain the concept of RAII (Resource Acquisition Is Initialization).
    • Answer: RAII is a C++ programming idiom where resources (memory, file handles, etc.) are acquired during object creation and released during object destruction. This ensures resources are automatically freed, preventing memory leaks.
24. What are virtual functions in C++?
    • Answer: Virtual functions allow you to define functions in a base class that can be overridden in derived classes. The correct function is called according to the type of the object, ensuring dynamic dispatch (polymorphism).
25. What is the difference between new and malloc() in C++?
    • Answer: new is an operator in C++ that allocates memory and calls the constructor for objects, while malloc() is a C library function that only allocates memory but does not initialize objects. new also throws exceptions if memory allocation fails, while malloc() returns NULL.

Java and Object-Oriented Programming (OOP)

26. What are the four pillars of Object-Oriented Programming (OOP)?
    • Answer: The four pillars of OOP are:
      • Encapsulation: Bundling data and methods that operate on the data within a single unit (class).
      • Abstraction: Hiding the implementation details and showing only the necessary features.
      • Inheritance: A mechanism to create a new class by inheriting properties and behaviors from an existing class.
      • Polymorphism: The ability of different objects to respond to the same method call in different ways.
27. What is the difference between == and equals() in Java?
    • Answer: == compares the reference (memory address) of two objects, while equals() compares the actual contents or state of the objects, assuming it’s overridden in the class to provide meaningful comparison.
28. What is the difference between ArrayList and LinkedList in Java?
    • Answer: ArrayList is backed by an array, offering fast random access but slower insertions and deletions, while LinkedList is backed by a doubly linked list, offering faster insertions and deletions but slower random access.
29. What are Java interfaces and how are they different from abstract classes?
    • Answer: An interface defines a contract for classes that implement it, while an abstract class can provide some method implementations and leave others abstract. A class can implement multiple interfaces but can only inherit from one abstract class.
30. Explain the concept of garbage collection in Java.
    • Answer: Garbage collection in Java is the process by which the JVM automatically frees memory by removing objects that are no longer reachable. It helps prevent memory leaks and simplifies memory management.