100+ SDE (Software Development Engineer) Interview Questions and Answers

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.

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.

Given a binary search tree, print the path with sum k and minimum hops.

• Traverse the tree using DFS and keep track of the current path and its sum.

• If the current sum equals k, compare the current path with the minimum path found so far.

• If the current sum is greater than k, backtrack to the previous node and continue traversal.

• If the current sum is less than k, continue traversal.

• Return the minimum path found.

• Time complexity: O(nlogn) for balanced tree, O(n^2) for skewed tree.

Given a map with flats and their location and visibility index, show every flat with a square of 32x32.

• Create a 1024x1024 map with flats and their visibility index

• Loop through each flat and draw a 32x32 square around it

• Display the map with all the flats highlighted

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 high priority process if the high priority process is wait...read more

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 associated with inheritance.

• Compile-time polymorphism is associated...read more

Print all elements not present in a sorted array with time and space complexity.

• Iterate through array and print missing elements

• Use binary search for faster search

• Time complexity: O(n log n)

• Space complexity: O(1)

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

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 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

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 the maximum stack will always be the maximum element in the...read more

Find missing elements in a sorted array within a given range.

• Loop through the array and check if each element is within the given range.

• If an element is outside the range, add all the missing elements within the range to a list.

• Return the list of missing elements.

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.

• Multiple inheritance involves a class inheriting from multiple ba...read more

Sort characters in a string based on its frequency.

• Create a dictionary to store character frequency

• Sort the dictionary based on frequency

• Reconstruct the string using the sorted dictionary

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

Print all elements not present in an unsorted array and give time and space complexity.

• Iterate through array and use a hashset to keep track of seen elements.

• Print elements not in hashset.

• Time complexity: O(n), Space complexity: O(n)

To move the cursor 5 characters ahead of current position in an opened file.

• Use fseek() function to move the cursor to the desired position.

• Pass the current position and offset to fseek() function.

• Use SEEK_CUR as the reference point for the offset.

Agile is an iterative approach to software development that emphasizes flexibility and customer satisfaction.

• Agile involves breaking down projects into smaller, more manageable chunks called sprints.

• It prioritizes collaboration between developers, customers, and stakeholders.

• It allows for changes and adjustments to be made throughout the development process.

• It promotes continuous delivery and improvement.

• Advantages over waterfall model include faster time to market, increased...read more

Arrow functions do not have their own 'this' value, which is required in constructors.

• Arrow functions do not have a 'this' binding, so 'this' will refer to the parent scope.

• Constructors require 'this' to refer to the newly created object.

• Using arrow functions in constructors can lead to unexpected behavior and errors.

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.

Program to calculate sum of level order tree

• Traverse the tree level by level using BFS

• Add the values of each level and return the sum

• Use a queue to store the nodes at each level

• Handle edge cases like empty tree or null root

Create a linked list that contains the sum of two given linked lists representing numbers.

• Traverse both linked lists simultaneously and add the corresponding nodes' values. If the sum is greater than 9, carry over the 1 to the next node.

• If one linked list is longer than the other, add the remaining nodes to the sum.

• Create a new linked list with the sum in reverse order.

Design a chess game with backend API and project in IDE.

• Create a chess board with 64 squares and pieces

• Implement game logic for moves and captures

• Develop a RESTful API for game actions and data storage

• Use a database to store game state and player information

• Build a user interface for playing the game

• Test thoroughly to ensure functionality and security

Find the equilibrium index where the sum of all values before it is equal to the sum of all values after it.

• Iterate through the array and calculate the total sum.

• Then iterate again and keep track of the left sum and right sum.

• If they are equal at any index, return that index as the equilibrium index.

Initializer list is a syntax in C++ to initialize objects with a list of values.

• Initializer list is enclosed in curly braces {}.

• It can be used to initialize arrays, structs, and classes.

• Example: int arr[] = {1, 2, 3};

• Example: struct Point { int x, y; } p = {1, 2};

• Example: class Person { public: string name; int age; } p = {"John", 30};

Check if a string is a palindrome and can be made a palindrome by removing at most one character.

• Iterate through the string from both ends and check if the characters match.

• If the characters don't match, try removing one character from either end and check if the remaining string is a palindrome.

• If removing one character doesn't make the string a palindrome, then it's not possible to make it a palindrome by removing at most one character.

Implement 3 stacks using one array with optimized space and time complexity.

• Divide the array into three equal parts to represent each stack.

• Keep track of the top index of each stack separately.

• When pushing an element, increment the top index of the respective stack and store the element.

• When popping an element, retrieve the element from the top index of the respective stack and decrement the top index.

• Handle stack overflow and underflow conditions appropriately.

A startup is a newly established business that aims to solve a problem or meet a need using innovative technology.

• Startups are focused on growth and scalability.

• They often operate in a fast-paced and dynamic environment.

• Startups use various technologies depending on their industry and product.

• Common technologies used in startups include web and mobile development, cloud computing, data analytics, artificial intelligence, and blockchain.

• Examples of startup technologies include...read more

Waterfall model is a linear sequential approach to software development.

• Advantages: clear and well-defined stages, easy to understand and manage, suitable for small projects with stable requirements

• Disadvantages: inflexible, difficult to make changes once a stage is completed, testing is done only at the end, not suitable for large or complex projects

• Stages: requirements gathering, design, implementation, testing, deployment, maintenance

• Example: building a house, where each s...read more

Different software development models

• Waterfall model

• Agile model

• Spiral model

• V-model

• Iterative model

• RAD model

• Prototype model

• Incremental model

Dutch National Flag algorithm can be used to sort an array of 0, 1, and 2 in O(n) time complexity and O(1) space complexity.

• Initialize three pointers: low, mid, and high.

• Iterate through the array and swap elements based on their values.

• Increment low and mid pointers when encountering 0.

• Increment mid pointer when encountering 1.

• Decrement high pointer when encountering 2.

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 most common ancestor nodes of a binary tree given two integers.

• Traverse the tree to find the nodes with the given integers

• Store the path from root to each node in separate arrays

• Compare the two arrays to find the most common ancestor node

• If there are multiple common ancestors, return the one closest to the root

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.

Finding an element in a rotated array

• Identify the pivot point where the array is rotated

• Divide the array into two sub-arrays based on the pivot point

• Perform binary search on the appropriate sub-array to find the element

• Handle edge cases like when the element is at the pivot point

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 removed.

The given array needs to be flattened to a single-level array.

• Iterate through the array elements

• If an element is an array, recursively flatten it

• If an element is not an array, add it to the result array

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.

Count the number of set bits in a given number.

• Use bitwise AND operator with 1 to check if the rightmost bit is set.

• Shift the number to right by 1 bit and repeat the process until the number becomes 0.

• Keep a count of the number of set bits encountered.

• Example: For number 5 (101 in binary), the answer is 2 as there are 2 set bits.

• Example: For number 15 (1111 in binary), the answer is 4 as there are 4 set bits.

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

Sorting a list of words with a random order using an alien dictionary

• Create a graph with nodes as characters and edges as the order of characters in words

• Topologically sort the graph to get the correct order of characters

• Use the order to sort the list of words

Yes, the project directory in Django follows a specific structure.

• The main project directory contains settings.py, urls.py, and wsgi.py files.

• Each app within the project has its own directory with models.py, views.py, and urls.py files.

• Static files are stored in a 'static' directory within each app.

• Templates are stored in a 'templates' directory within each app.

• Media files are stored in a 'media' directory within the project directory.

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

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 = new Singleton(); private Singleton() {} public static Single...read more

Sort an array of 0s and 1s using O(n) solution.

• Use two pointers, one at the beginning and one at the end of the array.

• Swap the elements at the pointers if they are not in the correct order.

• Move the pointers towards each other until they meet in the middle.

• Time complexity is O(n) and space complexity is O(1).

Replace substring in a given string and print the remaining string

• Use string.replace() method to replace the substring

• Print the remaining string using string slicing

Find the maximum sum of a rectangle in a 2D matrix.

• Use Kadane's algorithm to find the maximum sum subarray in each row.

• Iterate over all possible combinations of rows and find the maximum sum rectangle.

• Keep track of the maximum sum and the coordinates of the rectangle.

Polymorphism allows for flexibility and extensibility in code by enabling objects to take on multiple forms.

• Polymorphism allows for code reuse and simplifies maintenance.

• It enables the creation of generic code that can work with objects of different classes.

• It allows for the creation of interfaces and abstract classes, which can be implemented by multiple classes.

• Examples include using a parent class to represent multiple child classes, or implementing an interface to allow f...read more