Flipkart Software Developer Interview Questions, Process, and Tips

Check if a Binary Tree is a Binary Search Tree

• Inorder traversal of BST should be in ascending order

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

• Recursively check left and right subtrees

• Use min and max values to check if nodes are within valid range

Sort a large file of numbers with limited memory

• Use external sorting algorithms like merge sort or quick sort

• Divide the file into smaller chunks that can fit into memory

• Sort each chunk and merge them together using a priority queue

• Consider using disk-based sorting techniques like replacement selection

• Optimize I/O operations to minimize disk access

Implement a phone book with search by name or phone number and prefix.

• Create an array of strings to store contacts

• Implement a function to add contacts to the array

• Implement a function to search by name or phone number

• Implement a function to search by prefix

• Use regular expressions to match prefixes

Find Pythagorean triplets in an array of integers.

• Loop through the array and pick two numbers at a time.

• Calculate the sum of squares of the two numbers.

• Check if the sum is a perfect square.

• If yes, then it is a Pythagorean triplet.

• Repeat until all possible combinations are checked.

Compute the nearest palindrome number greater than given number.

• Convert the given number to string and reverse it.

• Add the reversed string to the original number and check if it's a palindrome.

• If not, repeat the process until a palindrome is found.

• If the original number is already a palindrome, add 1 to it and repeat the process.

Find minimum window in a string which contains all characters from another string.

• Use a sliding window approach

• Create a frequency map of characters in pat

• Iterate through str and update frequency map

• Keep track of minimum window that contains all characters

• Return minimum window

Arrange balls in 4 jars to maximize probability of user losing money when drawing a red ball.

• Place all red balls in one jar and the rest in the other jars

• Ensure that the jar with red balls has the highest probability of being chosen

• Randomize the placement of the jars to add an element of chance

Code to check if a tree is BST or not

• Check if left subtree is BST

• Check if right subtree is BST

• Check if max value in left subtree is less than root

• Check if min value in right subtree is greater than root

Modify code to find maximum BST subtree and maximum BST tree in a given tree.

• Create a function to check if a given tree is a BST

• Traverse the tree and check if each subtree is a BST

• Keep track of the maximum BST subtree found so far

• To find maximum BST tree, check if each node can be the root of a BST

• Keep track of the maximum BST tree found so far

Algorithm to determine valid variables on a given line of code.

• Create a stack to keep track of variable declarations

• Traverse the code line by line

• When encountering a variable declaration, push it onto the stack

• When encountering a closing brace, pop all variables declared within that scope

• Return all variables still on the stack when reaching the given line number

Implement LRU cache with put, get, and remove operations.

• LRU stands for Least Recently Used.

• The cache should have a maximum capacity.

• When the cache is full, the least recently used item should be removed.

• When an item is accessed, it should be moved to the front of the cache.

• Use a doubly linked list and a hash map to implement the cache efficiently.

next_permutation function generates the next greater lexicographic permutation of a sequence

• The function modifies the sequence to its next permutation if possible

• If the sequence is already the largest permutation, it rearranges it to the smallest permutation

• The function returns true if a next permutation exists, else false

• The sequence must be sorted in non-descending order before calling the function

Given n sequences with start, stop and score, find maximum subset of non-overlapping sequences with maximum total score.

• Sort the sequences by their end points.

• Use dynamic programming to find the maximum sum of non-overlapping sequences.

• Keep track of the previous non-overlapping sequence with maximum sum.

• Return the maximum sum and the corresponding non-overlapping sequences.