Housing.com Interview Questions and Answers

Identify and correct two swapped nodes in a Binary Search Tree (BST) to restore its properties.

• In a BST, for any node, left children are smaller and right children are larger.

• Perform an in-order traversal to identify the two swapped nodes.

• During traversal, keep track of the previous node to find violations.

• Example: For BST [4, 2, 6, 1, 3, 5, 7], if 1 and 6 are swapped, in-order gives [6, 2, 4, 1, 3, 5, 7].

• Swap the iden...read more

Design a seat booking system that locks seats until payment is confirmed, handling failures and timeouts effectively.

• Implement a state machine with states: Available, Locked, Paid, and Cancelled.

• When a user selects seats, transition from Available to Locked state.

• Set a timer for the payment process; if payment is not completed in time, transition to Available.

• Handle payment failures by transitioning from Locked to Avai...read more

The number of ways to reach the nth step using 1 or 2 steps at a time.

• Use dynamic programming to solve this problem

• Create an array to store the number of ways to reach each step

• Initialize the first two elements of the array as 1, since there is only one way to reach the first and second steps

• For each subsequent step, the number of ways to reach it is the sum of the number of ways to reach the previous two steps

• Return t...read more

Find all pairs (i, j) in an array where ai > aj and i < j using an efficient nlogn approach.

• Use a modified merge sort to count inversions while sorting the array.

• During the merge step, count how many elements from the right half are less than the current element from the left half.

• Example: For array [3, 1, 2], pairs are (3, 1), (3, 2), (2, 1).

• The algorithm runs in O(n log n) time complexity.

Find the maximum interval that intersects the maximum number of intervals.

• Sort the intervals based on their start times.

• Iterate through the sorted intervals and keep track of the current interval with the maximum number of intersections.

• Update the maximum interval whenever a new interval intersects more intervals than the current maximum interval.

Check if a path exists from a word to a single letter by removing one letter at a time, ensuring all intermediate words are valid.

• Use a recursive function to explore all possible paths by removing one letter at a time.

• Utilize a set for the dictionary for O(1) lookups.

• Base case: If the current word is a single letter and exists in the dictionary, return true.

• Example: For 'alpha', valid path could be 'alpha' -> 'plha'...read more

Implementing an auto-suggest feature for search engines to enhance user experience by predicting search queries.

• Use a trie data structure for efficient prefix searching.

• Store a list of common queries and their frequencies to prioritize suggestions.

• Implement a backend service that queries the database for suggestions based on user input.

• Consider using machine learning models to improve suggestion accuracy over time.

• Exam...read more

Create a linked list from a number by storing each digit as a node in sequence.

• Define a Node class with properties for value and next node.

• Convert the number to a string to iterate through each digit.

• Create the head of the linked list with the first digit.

• Iterate through the remaining digits, creating new nodes and linking them.

• Example: For number 12345, nodes will be created as 1 -> 2 -> 3 -> 4 -> 5.

Implement a ctlr+f (find) functionality in a file using a data structure.

• Create a data structure to store the file content, such as an array of strings.

• Implement a function that takes a search query and returns the matching lines from the file.

• Use string matching algorithms like Knuth-Morris-Pratt or Boyer-Moore for efficient searching.

• Consider optimizing the data structure for faster search operations, like using a tr...read more

Merge two sorted arrays with empty spaces at the end in a single pass.

• Initialize two pointers at the end of each array

• Compare the elements at the pointers and place the larger element at the end of the merged array

• Decrement the pointer of the array from which the larger element was taken

• Repeat until all elements are merged

The code should traverse the binary tree level by level and update the next pointers accordingly.

• Use a queue to perform level order traversal of the binary tree.

• For each node, update its next pointer to point to the next node in the queue.

• If the current node is the last node in the level, update its next pointer to NULL.

The set of all nodes that can occur in any path from a source to a destination in both directed and undirected graphs.

• Perform a depth-first search (DFS) or breadth-first search (BFS) from the source node to the destination node.

• During the search, keep track of all visited nodes.

• Add each visited node to the set of nodes that can occur in any path.

• Repeat the search for both directed and undirected graphs.

• The resulting se...read more

The maximum number of bridges that can be connected between two sides of a river without crossing each other.

• This is a dynamic programming problem.

• Create a 2D array to store the maximum number of bridges that can be connected at each position.

• Initialize the first row and column of the array with 0.

• Iterate through the sides of the river and compare the labels.

• If the labels match, update the value in the array by adding ...read more