What is R's PlacePrep?

R's PlacePrep is a free, open-source placement preparation platform for engineering students. It provides company-wise previous year questions with detailed solutions, timed mock exams, university PYQs, and aptitude & coding practice for TCS NQT, Infosys IRT, Accenture, and more.

Is R's PlacePrep free to use?

Yes! R's PlacePrep is 100% free and open-source. All placement papers, mock exams, university PYQs, and solutions are accessible without any payment or subscription.

Which companies are covered on PlacePrep?

PlacePrep covers placement papers from TCS (NQT), Infosys (IRT), Accenture, Wipro, Cognizant (GenC), Capgemini, and more. Papers are organized by year and exam type with detailed solutions.

Does PlacePrep have mock exams?

Yes! PlacePrep offers timed mock exams that simulate real placement test conditions with fullscreen mode, anti-cheat measures, auto-submission, and instant evaluation with detailed performance reports.

Goldman Sachs

Coding

Display Mode

Jump to Section

Practice Questions10

Export

Back to Goldman Sachs

Goldman Sachs coding

1 sections, 10 questions

Practice All (10)Sign in required

Practice Questions

Practice10 questions

Question 1

Search in a Row-Wise and Column-Wise Sorted Matrix

Problem

Given a matrix where each row is sorted in ascending order and each column is sorted in ascending order, find whether a given number exists in the matrix.

Example:

Input:
matrix = [
  [1,  4,  7,  11],
  [2,  5,  8,  12],
  [3,  6,  9,  16],
  [10, 13, 14, 17]
], target = 5
Output: true

Solution

— Staircase Search:

Code

Java

public class SearchSortedMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int row = 0;
        int col = matrix[0].length - 1;

        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == target) return true;
            else if (matrix[row][col] > target) col--;
            else row++;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 4, 7, 11},
            {2, 5, 8, 12},
            {3, 6, 9, 16},
            {10, 13, 14, 17}
        };
        System.out.println(searchMatrix(matrix, 5));
    }
}

Python

def search_matrix(matrix, target):
    row = 0
    col = len(matrix[0]) - 1

    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False

matrix = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]]
print(search_matrix(matrix, 5))

Time: O(M+N)Space: O(1)

Question 2

Implement a Max Stack Using One Stack

Problem

Design a stack that supports push, pop, and getMax in O(1) amortized time, using only one stack (not two).

Solution

— Store Encoded Max Value:

Code

Java

import java.util.Stack;

public class MaxStack {
    private Stack<Long> stack = new Stack<>();
    private long max;

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push((long) x);
            max = x;
        } else if (x <= max) {
            stack.push((long) x);
        } else {
            // Encode a value greater than max to recover the previous max on pop
            stack.push(2L * x - max);
            max = x;
        }
    }

    public int pop() {
        long top = stack.pop();
        if (top <= max) {
            return (int) top;
        } else {
            int oldMax = (int) max;
            max = 2 * max - top;
            return oldMax;
        }
    }

    public int getMax() {
        return (int) max;
    }
}

Time: O(1) for all operationsSpace: O(N)

Question 3

Intersection Point of Two Linked Lists

Problem

Given the heads of two singly linked lists, find the node where the two lists intersect. Return null if they do not intersect.

Code

Java

public class IntersectionOfLinkedLists {
    static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }

    public static Node getIntersectionNode(Node headA, Node headB) {
        if (headA == null || headB == null) return null;

        Node a = headA, b = headB;
        while (a != b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        return a;
    }
}

Time: O(M+N)Space: O(1)

Question 4

Reverse a String

Problem

Write code to reverse a given string in place.

Code

Java

public class ReverseString {
    public static String reverse(String s) {
        char[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
        return new String(chars);
    }

    public static void main(String[] args) {
        System.out.println(reverse("GoldmanSachs"));
    }
}

Time: O(N)Space: O(N) for the output string (O(1) extra for the swap)

Question 5

Two Sum

Problem

Given an array of integers and a target, return the indices of the two numbers that add up to the target.

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

Code

Java

import java.util.*;
public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[]{seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));
    }
}

Time: O(N)Space: O(N)

Question 6

Maximum Subarray Sum (Kadane's Algorithm)

Problem

Find the contiguous subarray with the largest sum in an array of integers.

Example:

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

Code

Java

public class MaximumSubarray {
    public static int maxSubArray(int[] nums) {
        int maxSoFar = nums[0], maxEndingHere = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

    public static void main(String[] args) {
        System.out.println(maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }
}

Time: O(N)Space: O(1)

Question 7

Number of Islands

Problem

Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Example:

Input:
11110
11010
11000
00000
Output: 1

Solution

— DFS:

Code

Java

public class NumberOfIslands {
    public static int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    private static void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return;
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

Time: O(M×N)Space: O(M×N) recursion stack in worst case

Question 8

Detect Cycle in a Linked List

Problem

Given the head of a linked list, determine if it contains a cycle.

Solution

— Floyd's Cycle Detection:

Code

Java

public class LinkedListCycle {
    static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }

    public static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

Time: O(N)Space: O(1)

Question 9

Valid Parentheses

Problem

Given a string containing just (, ), {, }, [, ], determine if the input string has valid matching and nesting of brackets.

Example:

Input: "()[]{}"
Output: true

Input: "(]"
Output: false

Code

Java

import java.util.*;
public class ValidParentheses {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = Map.of(')', '(', '}', '{', ']', '[');
        for (char c : s.toCharArray()) {
            if (map.containsValue(c)) {
                stack.push(c);
            } else if (map.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != map.get(c)) return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValid("()[]{}"));
    }
}

Time: O(N)Space: O(N)

Question 10

Kth Largest Element in an Array

Problem

Find the kth largest element in an unsorted array.

Example:

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Solution

— Min-Heap:

Code

Java

import java.util.PriorityQueue;
public class KthLargestElement {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.add(num);
            if (minHeap.size() > k) minHeap.poll();
        }
        return minHeap.peek();
    }

    public static void main(String[] args) {
        System.out.println(findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
    }
}

Time: O(N log K)Space: O(K)

public class SearchSortedMatrix { public static boolean searchMatrix(int[][] matrix, int target) { int row = 0; int col = matrix[0].length - 1; while (row < matrix.length && col >= 0) { if (matrix[row][col] == target) return true; else if (matrix[row][col] > target) col--; else row++; } return false; } public static void main(String[] args) { int[][] matrix = { {1, 4, 7, 11}, {2, 5, 8, 12}, {3, 6, 9, 16}, {10, 13, 14, 17} }; System.out.println(searchMatrix(matrix, 5)); } }

def search_matrix(matrix, target): row = 0 col = len(matrix[0]) - 1 while row < len(matrix) and col >= 0: if matrix[row][col] == target: return True elif matrix[row][col] > target: col -= 1 else: row += 1 return False matrix = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]] print(search_matrix(matrix, 5))

import java.util.Stack; public class MaxStack { private Stack<Long> stack = new Stack<>(); private long max; public void push(int x) { if (stack.isEmpty()) { stack.push((long) x); max = x; } else if (x <= max) { stack.push((long) x); } else { // Encode a value greater than max to recover the previous max on pop stack.push(2L * x - max); max = x; } } public int pop() { long top = stack.pop(); if (top <= max) { return (int) top; } else { int oldMax = (int) max; max = 2 * max - top; return oldMax; } } public int getMax() { return (int) max; } }

public class IntersectionOfLinkedLists { static class Node { int val; Node next; Node(int val) { this.val = val; } } public static Node getIntersectionNode(Node headA, Node headB) { if (headA == null || headB == null) return null; Node a = headA, b = headB; while (a != b) { a = (a == null) ? headB : a.next; b = (b == null) ? headA : b.next; } return a; } }

public class ReverseString { public static String reverse(String s) { char[] chars = s.toCharArray(); int left = 0, right = chars.length - 1; while (left < right) { char temp = chars[left]; chars[left] = chars[right]; chars[right] = temp; left++; right--; } return new String(chars); } public static void main(String[] args) { System.out.println(reverse("GoldmanSachs")); } }

import java.util.*; public class TwoSum { public static int[] twoSum(int[] nums, int target) { Map<Integer, Integer> seen = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (seen.containsKey(complement)) { return new int[]{seen.get(complement), i}; } seen.put(nums[i], i); } return new int[]{-1, -1}; } public static void main(String[] args) { System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9))); } }

public class MaximumSubarray { public static int maxSubArray(int[] nums) { int maxSoFar = nums[0], maxEndingHere = nums[0]; for (int i = 1; i < nums.length; i++) { maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]); maxSoFar = Math.max(maxSoFar, maxEndingHere); } return maxSoFar; } public static void main(String[] args) { System.out.println(maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4})); } }

public class NumberOfIslands { public static int numIslands(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1') { count++; dfs(grid, i, j); } } } return count; } private static void dfs(char[][] grid, int i, int j) { if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return; grid[i][j] = '0'; dfs(grid, i + 1, j); dfs(grid, i - 1, j); dfs(grid, i, j + 1); dfs(grid, i, j - 1); } }

public class LinkedListCycle { static class Node { int val; Node next; Node(int val) { this.val = val; } } public static boolean hasCycle(Node head) { Node slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } return false; } }

import java.util.*; public class ValidParentheses { public static boolean isValid(String s) { Stack<Character> stack = new Stack<>(); Map<Character, Character> map = Map.of(')', '(', '}', '{', ']', '['); for (char c : s.toCharArray()) { if (map.containsValue(c)) { stack.push(c); } else if (map.containsKey(c)) { if (stack.isEmpty() || stack.pop() != map.get(c)) return false; } } return stack.isEmpty(); } public static void main(String[] args) { System.out.println(isValid("()[]{}")); } }

import java.util.PriorityQueue; public class KthLargestElement { public static int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : nums) { minHeap.add(num); if (minHeap.size() > k) minHeap.poll(); } return minHeap.peek(); } public static void main(String[] args) { System.out.println(findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2)); } }

Goldman Sachs

Display Mode

Jump to Section

Other Content

Export

Goldman Sachs coding

Practice Questions

Search in a Row-Wise and Column-Wise Sorted Matrix

Problem

Solution

Code

Implement a Max Stack Using One Stack

Problem

Solution

Code

Intersection Point of Two Linked Lists

Problem

Code

Reverse a String

Problem

Code

Two Sum

Problem

Code

Maximum Subarray Sum (Kadane's Algorithm)

Problem

Code

Number of Islands

Problem

Solution

Code

Detect Cycle in a Linked List

Problem

Solution

Code

Valid Parentheses

Problem

Code

Kth Largest Element in an Array

Problem

Solution

Code

Goldman Sachs

Display Mode

Jump to Section

Other Content

Export

Goldman Sachs coding

Practice Questions

Search in a Row-Wise and Column-Wise Sorted Matrix

Problem

Solution

Code

Implement a Max Stack Using One Stack

Problem

Solution

Code

Intersection Point of Two Linked Lists

Problem

Code

Reverse a String

Problem

Code

Two Sum

Problem

Code

Maximum Subarray Sum (Kadane's Algorithm)

Problem

Code

Number of Islands

Problem

Solution

Code

Detect Cycle in a Linked List

Problem

Solution

Code

Valid Parentheses

Problem

Code