Carwale SDE (Software Development Engineer) Interview Questions, Process, and Tips

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

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

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

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

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

Find minimum number of weighings required to find the heavier coin out of 100 coins with a balance.

• Divide the coins into 3 groups of 33 each and weigh 2 groups against each other.

• If one group is heavier, divide it into 3 groups of 11 each and weigh 2 groups against each other.

• Repeat the process until the heavier coin is found.

• Minimum number of weighings required is 4.

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

Function to check if a string has all lowercase letters appearing at least once without extra space in O(N) time.

• Create a boolean array of size 26 to keep track of the occurrence of each letter.

• Iterate through the string and mark the corresponding index in the array as true.

• Check if all the elements in the array are true and return yes if so.

• Alternatively, use a bit vector to keep track of the occurrence of each letter

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