Car Fleet

Medium 30 pts New · no attempts yet csharp

Topics

Company

Car Fleet — Goldman Sachs interview prep · Stack

Classic interview problem #853.

Input (stdin)

Line 1: n\nLine 2: target\nNext n lines: position speed

Output (stdout)

Number of car fleets

Your program must read from stdin and write the answer to stdout (no extra debug text).

Examples

Sample

Input

Output

Static hints

Input format: Line 1: n\nLine 2: target\nNext n lines: position speed
DSA Interview 150 — Stack
Problem #853
Frequently asked at Goldman Sachs
Stack

Toolliyo Coach

Stuck? Get a nudge — not the answer

Progressive help: Nudge → Guide → Approach. Full solution stays behind the Solution tab.

Your solution

Editor is open — no login wall to practice.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static int[] Ria(string line = null)
    {
        line ??= Console.ReadLine();
        if (string.IsNullOrWhiteSpace(line)) return Array.Empty<int>();
        return line.Trim().Split(new[] { ' ', ',', '\t' }, StringSplitOptions.RemoveEmptyEntries)
            .Select(int.Parse).ToArray();
    }
    static string[] Rsa()
    {
        int n = int.Parse(Console.ReadLine());
        var arr = new string[n];
        for (int i = 0; i < n; i++) arr[i] = Console.ReadLine();
        return arr;
    }
    static void W(params object[] parts) => Console.WriteLine(string.Join(" ", parts));
    static void Wb(bool v) => Console.WriteLine(v ? "true" : "false");
    static void Wi(int v) => Console.WriteLine(v);
    static void Ws(string v) => Console.WriteLine(v);

static void Main()
    {
        // Read from stdin (see problem statement for format)
        // Line 1: n\nLine 2: target\nNext n lines: position speed

}
}

Ready — edit the code above and click Run or Submit.

Official solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static int[] Ria(string line = null)
    {
        line ??= Console.ReadLine();
        if (string.IsNullOrWhiteSpace(line)) return Array.Empty<int>();
        return line.Trim().Split(new[] { ' ', ',', '\t' }, StringSplitOptions.RemoveEmptyEntries)
            .Select(int.Parse).ToArray();
    }
    static string[] Rsa()
    {
        int n = int.Parse(Console.ReadLine());
        var arr = new string[n];
        for (int i = 0; i < n; i++) arr[i] = Console.ReadLine();
        return arr;
    }
    static void W(params object[] parts) => Console.WriteLine(string.Join(" ", parts));
    static void Wb(bool v) => Console.WriteLine(v ? "true" : "false");
    static void Wi(int v) => Console.WriteLine(v);
    static void Ws(string v) => Console.WriteLine(v);

    static void Main()
    {
int n = int.Parse(Console.ReadLine());
int target = int.Parse(Console.ReadLine());
var cars = new List<(double pos, double speed)>();
for (int i = 0; i < n; i++) {
    var p = Ria();
    cars.Add((p[0], p[1]));
}
cars.Sort((a, b) => b.pos.CompareTo(a.pos));
int fleets = 0;
double maxTime = 0;
foreach (var (pos, speed) in cars) {
    double t = (target - pos) / speed;
    if (t > maxTime) { fleets++; maxTime = t; }
}
Wi(fleets);
    }
}

Prefer Coach (Nudge → Guide → Approach) before revealing. No forced signup.

Explanation

Step 1 / 1

Goldman Sachs interview context: Car Fleet is a Medium Stack problem — Monotonic stack or bracket matching — watch for O(n) single-pass solutions.

Use the animation above to step through each move before writing code.

Pattern: Stack

Read from stdin, write to stdout. Classic interview problem #853.

Prev Next All problems