Info Edge SDE Interview Questions and Answers

Find the second largest element in an array.

• Sort the array and return the second last element

• Iterate through the array and keep track of the two largest elements

• Use a priority queue to find the second largest element

Given a sorted array with repeated elements, find the occurrence of a given element using binary search.

• Use binary search to find the first occurrence of the element

• Use binary search to find the last occurrence of the element

• Calculate the occurrence by subtracting the indices of the last and first occurrences and adding 1

Implement a data structure and algorithm to print all files in a directory, including sub-directories.

• Use an n-ary tree or stack to represent the directory structure

• Implement a BFS or DFS algorithm to traverse the directory and print files

• Handle sub-directories recursively

• Consider using a queue or stack to keep track of directories to visit

Print a matrix diagonally.

• Start from the top left corner and print the diagonal elements

• Move down and right to print the next diagonal

• Repeat until all diagonals are printed

DFS is a traversal algorithm used to visit all nodes of a tree or graph. It can be applied to binary as well as n-ary trees.

• DFS stands for Depth First Search.

• In DFS, we start from the root node and visit its children recursively until we reach a leaf node.

• There are two types of DFS: Preorder (root, left, right) and Postorder (left, right, root).

• DFS can be implemented using recursion or a stack data structure.

• Example: I...read more

Find total possible valid unique combinations of given number of pairs of parenthesis without duplicity.

• Use recursion to generate all possible combinations

• Check for validity of each combination using a stack

• Use a set to avoid duplicity

Construct a binary tree from in-order traversal with nodes greater than left and right child.

• The root node will be the maximum value in the in-order traversal

• Recursively construct the left and right subtrees using the left and right portions of the in-order traversal

• Repeat until all nodes are added to the tree

An algorithm to find top 10 trending words inserted by users in sites like Twitter.

• Collect a large dataset of tweets

• Tokenize the tweets into individual words

• Remove stop words and punctuation

• Count the frequency of each word

• Sort the words by frequency in descending order

• Select the top 10 words

Find the first occurrence of 1 in a sorted binary array.

• Use binary search to find the first occurrence of 1.

• If the mid element is 1, check if it's the first occurrence or if the element before it is 0.

• If the mid element is 0, search in the right half of the array.

• If the mid element is 1 and the element before it is also 1, search in the left half of the array.

Remove duplicates from a string in O(n) without using hash

• Use an array of boolean values to keep track of characters already seen

• Iterate through the string and mark characters as seen in the array

• If a character has already been seen, remove it from the string

Find the first occurrence of 1 in a sorted infinite binary tree.

• Use binary search to traverse the tree.

• If the current node is 1, check if its left child is also 1. If yes, move to the left subtree, else return the current node.

• If the current node is 0, move to the right subtree.

• Repeat until the first occurrence of 1 is found or the tree is exhausted.

Heaps allow efficient insertion and deletion of elements, unlike arrays.

• Heaps are useful for implementing priority queues.

• Insertion and deletion of elements in a heap take O(log n) time, while in an array it takes O(n) time.

• Heaps are dynamically resizable, unlike arrays which have a fixed size.

• Heaps can be used to efficiently find the kth largest/smallest element in an array.

• Examples of heap data structures include bin

Find the 2nd minimum element from an array.

• Sort the array and return the second element.

• Use a loop to find the minimum and second minimum elements.

• Initialize two variables to store the minimum and second minimum elements.

Construct a mirror tree from a given tree and return the root of the mirror tree.

• Traverse the given tree in a recursive manner.

• Swap the left and right child of each node.

• Return the root of the mirror tree.

Level order traversal of a tree is a method to visit all the nodes of a tree level by level.

• Use a queue to store the nodes of the tree

• Start with the root node and enqueue it

• While the queue is not empty, dequeue a node and visit it

• Enqueue the left and right child of the visited node if they exist

• Repeat until all nodes are visited

Sort a stack using recursion.

• Pop the top element from the stack and recursively sort the remaining stack.

• Insert the popped element in the correct position in the sorted stack.

• Repeat until the entire stack is sorted.

• Use a helper function to insert the element in the correct position.

• Time complexity: O(n^2), space complexity: O(n) due to recursion.

• Example: Input stack - [5, 2, 7, 1], Output stack - [1, 2, 5, 7]

Populate sibling of a tree node with next node in same level with O(1) space complexity.

• Traverse the tree level by level using BFS.

• For each node, check if it has a sibling to its right.

• If yes, populate the sibling pointer of the current node with the right sibling.

• If no, move to the next level.

• Repeat until all levels are traversed.

When you type amazon.com in a browser, it sends a request to the Amazon servers, which then respond by sending back the website's content to be displayed on your screen.

• Browser sends a DNS request to resolve the domain name 'amazon.com' to an IP address

• Browser establishes a TCP connection with the Amazon servers

• Browser sends an HTTP request to the Amazon servers for the website content

• Amazon servers process the request...read more