Yahoo Interview Experience

Problems in Round: 2

Problem: Subset Sum

You are given an array 'nums' of ‘n’ integers. Return all subset sums of 'nums' in a non-decreasing order. Note: Here subset sum means sum of all elements of a subset of 'nums'. A subset of 'nums' is an array formed by removing some (possibly zero or all) elements of 'nums'. For example Input: 'nums' = [1,2] Output: 0 1 2 3 Explanation: Following are the subset sums: 0 (by considering empty subset) 1 2 1+2 = 3 So, subset sum are [0,1,2,3]. Input Format : The first line of input contains a single integer ‘n’, denoting the size of the array 'nums'. The second line of input contains ‘n’ space-separated integers denoting elements of the array 'nums'. Output Format : Return the sum of all the subsets of 'nums' in non-decreasing order. Note : You do not need to print anything, it has already been taken care of. Just implement the given function.

This can be solved using recursion (a brute-force approach). However, I identified it as a DP problem where each element can either be chosen or not chosen (pick / not pick). A 2D array (DP table) is defined to track whether a target sum can be formed using the first n elements, using pick and not-pick choices.

Problem Metadata

Problem Type: CODE

Maximum Score: 40

Practice Topics: Recursion, Bit Manipulation

Test Cases: 15

Default Language: cpp

Problem: Coding Questions

The other two coding questions were of medium difficulty—one based on strings and the other on linked lists. They tested basic operations and problem-solving skills, but I do not recall the exact problem statements.

Problems in Round: 2

Problem: Add Two Numbers

You are given two non-negative numbers 'num1' and 'num2' represented in the form of linked lists. The digits in the linked lists are stored in reverse order, i.e. starting from least significant digit (LSD) to the most significant digit (MSD), and each of their nodes contains a single digit. Calculate the sum of the two numbers and return the head of the sum list. Example : Input: 'num1' : 1 -> 2 -> 3 -> NULL 'num2' : 4 -> 5 -> 6 -> NULL Output: 5 -> 7 -> 9 -> NULL Explanation: 'num1' represents the number 321 and 'num2' represents 654. Their sum is 975. Input Format: The first line contains a single integer 'm', the number of elements in 'num1'. The second line contains 'm' integers, the elements of the first singly linked list / digits of 'num1'. The third line contains a single integer 'n', the number of elements in 'num2'. The fourth line contains 'n' integers, the elements of the second singly linked list / digits of 'num2'. Output Format: Return the sum linked list. Note : You do not need to print anything; it has already been taken care of. Just implement the given function.

I used a dummy node to start the result list and maintained a carry variable. I traversed both linked lists together, added the values along with the carry, and created new nodes for the sum digits. Finally, I returned the list formed after the dummy node. I was also asked about the time and space complexities of the approach I followed.

Problem Metadata

Problem Type: CODE

Average Solve Time: 20 minutes

Success Rate: 80%

Maximum Score: 80

Practice Topics: Linked List

Test Cases: 25

Default Language: js

Problem: Reverse Linked List

Given a singly linked list of integers. Your task is to return the head of the reversed linked list. For example: The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse linked list is 4 -> 3 -> 2 -> 1 -> NULL and the head of the reversed linked list will be 4. Follow Up : Can you solve this problem in O(N) time and O(1) space complexity? Input Format : The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Then the test case follows. The only line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element. Output Format : For each test case, print the given linked list in reverse order in a separate line. Note : You do not need to print anything, it has already been taken care of. Just implement the given function. Constraints : 1 <= T <= 5 0 <= L <= 10^5 1 <= data <= 10^9 and data != -1 Time Limit: 1 sec

I initialized three pointers—previous, current, and next—to help reverse the links. Then, I traversed the linked list, updating the next pointer of each node to point to the previous node while moving the pointers accordingly until the end of the linked list, and returned the previous node as the new head.

Problem Metadata

Problem Type: CODE

Average Solve Time: 15 minutes

Success Rate: 85%

Maximum Score: 80

Practice Topics: Linked List, Two Pointers, Recursion, Stacks & Queues

Test Cases: 3

Default Language: js

Problems in Round: 2

Problem: Longest Common Subsequence

Given two strings, 'S' and 'T' with lengths 'M' and 'N', find the length of the 'Longest Common Subsequence'. For a string 'str'(per se) of length K, the subsequences are the strings containing characters in the same relative order as they are present in 'str,' but not necessarily contiguous. Subsequences contain all the strings of length varying from 0 to K. Example : Subsequences of string "abc" are: ""(empty string), a, b, c, ab, bc, ac, abc. Input format : The first line of input contains the string 'S' of length 'M'. The second line of the input contains the string 'T' of length 'N'. Output format : Return the length of the Longest Common Subsequence. Constraints : 0 <= M <= 10 ^ 3 0 <= N <= 10 ^ 3 Time Limit: 1 sec

Brute Force Approach: All possible subsequences of both strings are generated and compared to find the longest common subsequence. This approach is inefficient. Recursive & Memoization Approach: I then explained a recursive solution that compares characters from both strings step by step. To optimize it, I introduced memoization by storing the results of overlapping subproblems in a DP table. I wrote the code snippets on paper and also explained the time and space complexity to the interviewer.

Problem Metadata

Problem Type: CODE

Average Solve Time: 39 minutes

Maximum Score: 80

Practice Topics: Strings, Dynamic Programming

Test Cases: 3

Default Language: js

Problem: Remove duplicates from a sorted Doubly Linked List

A doubly-linked list is a data structure that consists of sequentially linked nodes, and the nodes have reference to both the previous and the next nodes in the sequence of nodes. You are given a sorted doubly linked list of size 'n'. Remove all the duplicate nodes present in the linked list. Example : Input: Linked List: 1 <-> 2 <-> 2 <-> 2 <-> 3 Output: Modified Linked List: 1 <-> 2 <-> 3 Explanation: We will delete the duplicate values ‘2’ present in the linked list. Input Format : The first line contains an integer 'n', the number of elements in the linked list. The second line contains 'n' integers, the elements of the linked list separated by a single space. Output Format : Print a single line, the final linked list. Note : You are not required to print anything; it has already been taken care of. Just implement the function.

I first explained the brute-force approach by writing code snippets on paper, where duplicate values are tracked using an extra data structure (a set) to ensure uniqueness. This approach works but uses extra space. Then, I moved to an optimized approach using pointers, where I traversed the sorted linked list and removed duplicates in place by comparing the current node with the next node, without using extra space. I was also asked about the time and space complexity of the approaches I followed. After the DSA problems, I was also asked about React fundamentals, Java exception handling, and operating system basics.

Problem Metadata

Problem Type: CODE

Maximum Score: 40

Practice Topics: Linked List

Test Cases: 25

Default Language: cpp