Flipkart Software Developer Interview Questions, Process, and Tips

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.