Computer Scientist Interview Questions and Answers

Given an array of integers, find if a subarray exists whose sum equals to k.

• Use a hashmap to store the prefix sum and its frequency.

• Iterate through the array and check if the difference between current prefix sum and k exists in the hashmap.

• If it exists, then a subarray with sum k exists.

• Time complexity: O(n), Space complexity: O(n).

To break a linked list into two lists, we can traverse the list and add nodes to respective lists based on their value.

• Traverse the linked list and add nodes to positive or negative list based on their value

• Create two empty lists for positive and negative nodes

• Iterate through the linked list and add nodes to respective lists

• Join the two lists at the end to get the final result

Merge K-Sorted Linked List

• Create a min heap of size k

• Insert the first element of each linked list into the heap

• Pop the minimum element from the heap and add it to the result list

• Insert the next element from the linked list of the popped element into the heap

• Repeat until all elements are processed

BFS (Breadth-First Search) is a graph traversal algorithm that explores all the vertices of a graph in breadth-first order.

• Create a queue to store the visited vertices

• Start with the initial vertex and enqueue it

• While the queue is not empty, dequeue a vertex and mark it as visited

• Enqueue all the adjacent vertices of the dequeued vertex that are not yet visited

• Repeat until the queue is empty

Left view of a binary tree is the set of nodes visible when the tree is viewed from the left side.

• Traverse the binary tree level by level using BFS or DFS.

• Keep track of the first node encountered at each level (leftmost node).

• Store the leftmost nodes in an array to get the left view of the binary tree.