Dream11 Sdet Interview Questions and Answers

Identify data structure based on insertion and deletion order

• If insertion and deletion follow LIFO order, it is a stack

• If insertion follows FIFO order and deletion follows LIFO order, it is a queue

• If insertion and deletion follow priority order, it is a priority queue

Find maximum element in an array in less than O(N)

• Use divide and conquer approach

• Compare maximum of left and right subarrays

• Recursively find maximum element

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