Carwale SDE (Software Development Engineer) Interview Questions and Answers

Prims and Kruskal's algorithms are used to find the minimum spanning tree in a graph.

• Prims algorithm starts with a single vertex and adds the minimum weight edge to the tree until all vertices are included.

• Kruskal's algorithm starts with all vertices as separate trees and merges them by adding the minimum weight edge until all vertices are included.

• Both algorithms have a time complexity of O(E log V) where E is the num...read more

Delete nodes in a linked list which have greater value on right side

• Traverse the linked list and compare each node with its right side node

• If the current node's value is less than its right side node, delete the current node

• Repeat the process until the end of the linked list is reached

Code for reversing a linked list

• Create a new empty linked list

• Traverse the original linked list and insert each node at the beginning of the new list

• Return the new list

Methods are functions that perform a specific task, while constructors are special methods that initialize objects.

• Constructors have the same name as the class they belong to.

• Constructors are called automatically when an object is created.

• Constructors can be overloaded with different parameters.

• Methods can be called multiple times with different arguments.

• Methods can have a return type, while constructors do not.

Find all permutations of a given string.

• Use recursion to swap each character with every other character in the string.

• Repeat the process for each substring.

• Add the permutation to an array.

Given an array of size 98 with natural numbers from 1-100 but 2 numbers are missing, find them.

• Calculate the sum of all numbers from 1-100 using the formula n(n+1)/2

• Calculate the sum of all numbers in the array

• Subtract the sum of array from the sum of all numbers to get the sum of missing numbers

• Find the missing numbers by iterating through the array and checking which numbers are not present

Check if a binary tree is a binary search tree or not.

• Traverse the tree in-order and check if the elements are in sorted order.

• Check if the left child is less than the parent and the right child is greater than the parent.

• Use recursion to check if all the subtrees are BSTs.

• Maintain a range for each node and check if the node value is within that range.

Detect and remove cycle in a linked list

• Use two pointers, one slow and one fast, to detect a cycle

• Once a cycle is detected, move one pointer to the head and iterate both pointers until they meet again

• Set the next node of the last node in the cycle to null to remove the cycle

Convert a number to its hexadecimal form

• Use the built-in function to convert the number to hexadecimal

• Alternatively, use the algorithm to convert the number to hexadecimal manually

• Ensure to handle negative numbers appropriately

Priority scheduling is a scheduling algorithm where processes are assigned priorities and executed based on their priority level.

• Preemptive priority scheduling allows a higher priority process to interrupt a lower priority process that is currently running.

• Non-preemptive priority scheduling allows a higher priority process to wait until the lower priority process finishes executing.

• A low priority process can preempt a ...read more

Singleton class is a class that can only have one instance at a time.

• Singleton pattern is used when we need to ensure that only one instance of a class is created and that instance can be accessed globally.

• The constructor of a singleton class is always private to prevent direct instantiation.

• A static method is used to access the singleton instance.

• Example: public class Singleton { private static Singleton instance = ne...read more

Develop tic-tac-toe game using OOPS concepts in CPP.

• Create a class for the game board

• Create a class for the players

• Create a class for the game logic

• Use inheritance and polymorphism for game objects

• Implement functions for checking win/lose/draw conditions

Delete nodes in linkedlist with greater value on right side

• Traverse the linked list from right to left

• Compare each node with the maximum value seen so far

• If the current node has a greater value, delete it

• Update the maximum value seen so far

Check if given tree is BST or not

• A binary tree is a BST if the value of each node is greater than all the values in its left subtree and less than all the values in its right subtree

• Perform an in-order traversal of the tree and check if the values are in ascending order

• Alternatively, for each node, check if its value is within the range defined by its left and right subtrees

Adhoc string questions often test manipulation, searching, or pattern recognition skills in programming.

• String reversal: Reverse a string using slicing. Example: 'hello' -> 'olleh'.

• Palindrome check: Determine if a string reads the same forwards and backwards. Example: 'racecar' is a palindrome.

• Substring search: Find if one string is a substring of another. Example: 'cat' in 'concatenation' returns True.

• Character fre...read more

OOP is a programming paradigm that organizes code into objects with properties and behaviors.

• OOP stands for Object-Oriented Programming.

• It focuses on creating reusable code by organizing it into objects.

• Objects have properties (attributes) and behaviors (methods).

• Encapsulation, inheritance, and polymorphism are key principles of OOP.

• Example: In Java, a class represents an object with its properties and methods.

Runtime polymorphism is when the method to be executed is determined at runtime, while compile-time polymorphism is determined at compile-time.

• Runtime polymorphism is achieved through method overriding.

• Compile-time polymorphism is achieved through method overloading.

• Runtime polymorphism is also known as dynamic polymorphism.

• Compile-time polymorphism is also known as static polymorphism.

• Runtime polymorphism is associate...read more

Virtual functions are functions in a base class that can be overridden by derived classes to provide different implementations.

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

• They allow polymorphism, where a pointer to a base class can invoke different derived class implementations.

• Virtual functions are resolved at runtime based on the actual object type.

• They are used to achieve ...read more

An abstract class is a class that cannot be instantiated and is meant to be subclassed.

• An abstract class can have both abstract and non-abstract methods.

• It can provide a common interface for its subclasses.

• Subclasses of an abstract class must implement all the abstract methods.

• Abstract classes can have constructors.

• An abstract class cannot be instantiated directly, but its subclasses can be.

Inheritance is a mechanism in object-oriented programming where a class inherits properties and behaviors from another class.

• Inheritance allows code reuse and promotes code organization.

• There are different types of inheritance: single inheritance, multiple inheritance, multilevel inheritance, hierarchical inheritance, and hybrid inheritance.

• Single inheritance involves a class inheriting from a single base class.

• Multipl...read more

Print Fibonacci series less than or equal to 1000.

• Start with two variables, a and b, initialized to 0 and 1 respectively.

• Print a and update a to the value of b, and b to the sum of the previous a and b.

• Repeat until a exceeds 1000.

The sum of even numbers in the Fibonacci series is calculated.

• Generate the Fibonacci series up to a given limit

• Iterate through the series and check if each number is even

• If the number is even, add it to the sum

• Return the sum of the even numbers

Explore unconventional methods to achieve sub-linear time complexity for the given problem.

• Use hashing to store previously computed results, allowing O(1) lookups.

• Implement a divide-and-conquer strategy to reduce problem size recursively.

• Consider using a probabilistic approach, like Bloom filters, for approximate results.

• Utilize parallel processing to handle multiple data segments simultaneously.

Stacks are a data structure that follows the Last-In-First-Out (LIFO) principle.

• Stacks have two main operations: push (adds an element to the top) and pop (removes the top element).

• Stacks can be implemented using arrays or linked lists.

• Common applications of stacks include function call stack, undo/redo operations, and expression evaluation.

• Example: A stack of books, where the last book placed is the first one to be re...read more

Implement max() function to find the maximum element in a stack with optimized time and space complexity.

• Use an additional stack to keep track of the maximum element at each step.

• When pushing an element onto the stack, compare it with the top element of the maximum stack and push the larger one.

• When popping an element from the stack, also pop the top element from the maximum stack if they are equal.

• The top element of t...read more