Datafortune Interview Questions and Answers

Given an array and an integer, return all subsets that sum to the given integer.

• Use backtracking to generate all possible subsets of the array.

• For each subset, check if the sum equals the given integer 'K'.

• Print the subsets that satisfy the condition.

• Example: For input [1, 2, 3] and K=3, subsets [1, 2] and [3] have sum 3.

Find the length of the longest strictly increasing subsequence in an array of integers.

• Use dynamic programming to keep track of the longest increasing subsequence ending at each element.

• Initialize an array to store the length of the longest increasing subsequence ending at each index.

• Iterate through the array and update the length of the longest increasing subsequence for each element.

• Return the maximum value in the array as the length of the longest increasing subsequence.

Count the total number of inversions in an integer array.

• Iterate through the array and for each pair of elements, check if the conditions for inversion are met.

• Use a nested loop to compare each element with all elements to its right.

• Keep a count of the inversions found and return the total count at the end.

Check if a given graph is bipartite by dividing vertices into two independent sets.

• Use BFS or DFS to traverse the graph and assign colors to vertices to check for bipartiteness.

• If an edge connects vertices of the same color, the graph is not bipartite.

• Return true if all edges connect vertices of different colors, else return false.

Boundary traversal of a binary tree in anti-clockwise direction starting from the root node.

• Implement a function to calculate the boundary traversal of a binary tree

• Include nodes from left boundary, leaf nodes, and right boundary in sequence

• Ensure only unique nodes are included in the output

• Print the boundary nodes separated by single spaces for each test case