Interview Questions

Goldman Sachs CoderPad - Technical Screen

Binary Tree to String Serialization (Custom Format)

Write a function to convert a binary tree into a specific string representation using pre-order traversal. The format must follow a nested parenthesis structure: (root, left_subtree, right_subtree). If a node is a leaf (or if a child is missing), the format should adapt accordingly based on the provided examples.

DSATreeRecursionString

Given the following binary tree structure:

      1
    /   \
   2     3
  /     / \
 4     5   6
      /
     7

Input: root = [1, 2, 3, 4, null, 5, 6, null, null, 7]
Expected Output: "(1,(2,4,),(3,(5,7,),6))"

Explanation based on structure:

Node 2’s subtree is (2,4,) where 4 is the left child and the right child is empty.
Node 5’s subtree is (5,7,).
Node 3’s subtree is (3,(5,7,),6).
The entire tree wraps into the root 1.

Reconstructed from interview notes.

Goldman Sachs CoderPad - Technical Screen

Cloud Kitchen (Optimal Delivery Assignment)

A cloud kitchen has N orders and N delivery partners. You are given an N x N cost matrix where matrix[i][j] represents the cost/distance for Delivery Partner i to deliver Order j. Find the optimal assignment of orders to delivery partners such that exactly one order is assigned to each partner and the total delivery cost is minimized.

DSADynamic ProgrammingBitmaskingGraph

Input: N = 3

Costs Matrix:      O1  O2  O3
D1              [ 10, 20,  5 ]
D2              [  6,  7,  8 ]
D3              [  9, 10,  2 ]

Output (as recorded in notes): 21

Explanation of optimal paths (Approach 1):

Delivery Partner 2 takes Order 1 (Cost: 6)
Delivery Partner 3 takes Order 2 (Cost: 10)
Delivery Partner 1 takes Order 3 (Cost: 5)
Total Minimum Cost = 6 + 10 + 5 = 21

Correction note: for this matrix, 21 is not the true minimum. The assignment D1 to O1 (10), D2 to O2 (7), D3 to O3 (2) totals 19, which is the optimal answer. Either the matrix or the expected output was likely mis-recorded in the notes; a correct solution to the matrix as written returns 19.

Goldman Sachs CoderPad - Technical Screen

Best Average Grade

Given a list of student test scores, find the best average grade. Each student may have more than one test score in the list.

Complete the bestAverageGrade function. It has one parameter, scores, which is an array of student test scores. Each element in the array is a two-element array of the form [student name, test score] (e.g. ["Bobby", "87"]). Test scores may be positive or negative integers.

If you end up with an average grade that is not an integer, use a floor function to return the largest integer less than or equal to the average. Return 0 for an empty input.

DSAHash TableMathArray

Input:

[["Bobby", "87"],
 ["Charles", "100"],
 ["Eric", "64"],
 ["Charles", "22"]]

Expected Output: 87

Explanation: the average scores are 87, 61, and 64 for Bobby, Charles, and Eric, respectively. 87 is the highest.

Extracted from the interview prompt (heavily tested question).

LeetCode 1086 - High Five (closest conceptual match)

Goldman Sachs CoderPad - Technical Screen

Compute Snowpack (Trapping Rain Water)

Given an array of non-negative integers representing the elevations from the vertical cross-section of a range of hills, determine how many units of snow could be captured between the hills.

DSAArrayTwo PointersDynamic Programming

Input Array: {0, 1, 3, 0, 1, 2, 0, 4, 2, 0, 3, 0}

Elevation map:

                               ___
           ___                |   |        ___
          |   |        ___    |   |___    |   |
       ___|   |    ___|   |   |   |   |   |   |
   ___|___|___|___|___|___|___|___|___|___|___|___
   {0,  1,  3,  0,  1,  2,  0,  4,  2,  0,  3,  0}

Captured snow (*):

                               ___
           ___                |   |        ___
          |   | *   *  _*_  * |   |_*_  * |   |
       ___|   | *  _*_|   | * |   |   | * |   |
   ___|___|___|_*_|___|___|_*_|___|___|_*_|___|___
   {0,  1,  3,  0,  1,  2,  0,  4,  2,  0,  3,  0}

Expected Output: 13 (13 units of snow could be captured).

Extracted from the interview prompt (heavily tested question).

LeetCode 42 - Trapping Rain Water (exact algorithm match)