Implement in Python three tasks. 1) Movie Ratings (DP): Given an integer array ratings of length n, return both (a) the length of the longest strictly increasing subsequence (LIS) and (b) one valid LIS as a list of 1-based indices. Explain your DP formulation (state, transition) and provide code. Constraints: 1 ≤ n ≤ 200000; ratings[i] can be any 32-bit signed integer. Target complexity: O(n log n) time, O (n) memory. 2) Array Challenge (optimize with a tree structure): You are given n and an initial array a[1..n], followed by q operations of two types: (i) "add i x" — add integer x to a[i]; (ii) "sum l r" — output the sum of a[l..r], inclusive. Constraints: 1 ≤ n, q ≤ 200000. A naive O (n) per query will time out; implement an O(log n) per-operation solution using a Fenwick tree or segment tree. 3) Update Release Scheduler (sort and compare two lists): You receive two unsorted lists of integers: releases[0..n-1] (timestamps when builds become available) and windows[0..m-1] (deployment windows). Produce an array schedule[0..m-1] where schedule[j] is the timestamp of the latest release ≤ windows[j] that has not been assigned to any earlier window; if no release is available, set schedule[j] = -1. If multiple releases qualify for a window, choose the one with the greatest timestamp. Approach should sort both lists and scan with two pointers. Target complexity: O((n + m) log(n + m)) time, O( 1) extra space aside from outputs.

This question evaluates proficiency in dynamic programming, range-query data structures (Fenwick/segment tree), sorting and two-pointer techniques, and algorithmic complexity analysis within the Coding & Algorithms domain for Python-based implementation.

How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at DRW.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at DRW during technical interviews.

Solve three algorithmic tasks in Python

Implement in Python three tasks.

Movie Ratings (DP): Given an integer array ratings of length n, return both (a) the length of the longest strictly increasing subsequence (LIS) and (b) one valid LIS as a list of 1-based indices. Explain your DP formulation (state, transition) and provide code. Constraints: 1 ≤ n ≤ 200000; ratings[i] can be any 32-bit signed integer. Target complexity: O(n log n) time, O (n) memory.
Array Challenge (optimize with a tree structure): You are given n and an initial array a[1..n], followed by q operations of two types: (i) "add i x" — add integer x to a[i]; (ii) "sum l r" — output the sum of a[l..r], inclusive. Constraints: 1 ≤ n, q ≤ 200000. A naive O (n) per query will time out; implement an O(log n) per-operation solution using a Fenwick tree or segment tree.
Update Release Scheduler (sort and compare two lists): You receive two unsorted lists of integers: releases[0..n-1] (timestamps when builds become available) and windows[0..m-1] (deployment windows). Produce an array schedule[0..m-1] where schedule[j] is the timestamp of the latest release ≤ windows[j] that has not been assigned to any earlier window; if no release is available, set schedule[j] = -1. If multiple releases qualify for a window, choose the one with the greatest timestamp. Approach should sort both lists and scan with two pointers. Target complexity: O((n + m) log(n + m)) time, O(
extra space aside from outputs.

Implement in Python three tasks.

Movie Ratings (DP): Given an integer array ratings of length n, return both (a) the length of the longest strictly increasing subsequence (LIS) and (b) one valid LIS as a list of 1-based indices. Explain your DP formulation (state, transition) and provide code. Constraints: 1 ≤ n ≤ 200000; ratings[i] can be any 32-bit signed integer. Target complexity: O(n log n) time, O (n) memory.
Array Challenge (optimize with a tree structure): You are given n and an initial array a[1..n], followed by q operations of two types: (i) "add i x" — add integer x to a[i]; (ii) "sum l r" — output the sum of a[l..r], inclusive. Constraints: 1 ≤ n, q ≤ 200000. A naive O (n) per query will time out; implement an O(log n) per-operation solution using a Fenwick tree or segment tree.
Update Release Scheduler (sort and compare two lists): You receive two unsorted lists of integers: releases[0..n-1] (timestamps when builds become available) and windows[0..m-1] (deployment windows). Produce an array schedule[0..m-1] where schedule[j] is the timestamp of the latest release ≤ windows[j] that has not been assigned to any earlier window; if no release is available, set schedule[j] = -1. If multiple releases qualify for a window, choose the one with the greatest timestamp. Approach should sort both lists and scan with two pointers. Target complexity: O((n + m) log(n + m)) time, O(
extra space aside from outputs.

Solve three algorithmic tasks in Python

Quick Overview

Comments (0)

Solve three algorithmic tasks in Python

Quick Overview

Comments (0)