Google ❤️ Arrays

Welcome back!

Today’s problem is taking a coding challenge we previously covered to the next level. Let’s dive in.

Today we will cover:

• Best Time to Buy and Sell Stock II

• Column-oriented Storage

Read time: under 4 minutes

CODING CHALLENGE

Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Solve the problem here before reading the solution.

Note: We had previously solved the easier version of Best time to buy and sell stock here. We recommend to check it out as a bonus challenge this week!

PRESENTED BY DATACAMP

Datacamp Free Access Week. Unlimited Learning, Zero Cost.

No catch, no card details. The entire learning platform is free between November 4th - 10th.

Datacamp is free all week. Start now!

SOLUTION

To maximize profit, we'll iterate through the prices and buy the stock whenever the price is lower than the next day's price. Then, we'll sell it the next day.

This strategy works because we can buy and sell on the same day. We're essentially capturing all the price increases in the array.

We'll keep a running total of our profit. For each day, if the price is higher than the previous day, we add the difference to our profit.

The time complexity of this solution is O(n), where n is the length of the prices array.

SYSTEM DESIGN

Column-oriented Storage

Column-oriented storage is a clever way to organize data that can make analytics and reporting much faster.

In traditional row-oriented storage, all information about a single employee (name, department, salary, hire date) is stored together. This makes sense when you need complete employee profiles, like when HR needs to view all details about one person.

Column-oriented storage flips this approach. Instead of keeping all information about one employee together, it stores all the data from a single column together. For example, all salaries would be stored in one file, all names in another, and all departments in a third file.

This approach really shines when you're doing HR analytics. Want to find the average salary across departments? With column storage, all salary data is already grouped together, making calculations much faster.

Here are a few advantages of using Column-oriented storage:

Less data needs to be read: If you only need salary data for analysis, you only load the salary file, ignoring names, departments, and other information.

Better compression: Data in a single column often has similar values or patterns, making it easier to compress. For example, a "department" column might only contain a few dozen unique values that can be compressed efficiently.

There are some trade-offs though. When new employee data comes in, multiple files need to be updated for each column which makes the writes slower. To solve this problem, we can use LSM trees where data is first stored in memory using a special tree structure. Once enough data accumulates, it's written to disk in bulk.

Column storage works best when you're analyzing specific fields across many employees, but it's slower when you need to reconstruct complete employee profiles. Also, all columns must maintain the same sort order to keep data consistent.

Here's a comparison of Row vs. Column Oriented Storage:

NEWS

This Week in the Tech World

Amazon RTO Mandate Sparks Tension: Amazon CEO Andy Jassy denies that the new 5-day office mandate is a "backdoor layoff." The policy, starting January 2025, faces employee backlash with over 37,000 workers joining a Slack channel opposing the change.

OpenAI Expands Into Robotics: OpenAI hires Meta's former AR glasses head, Caitlin Kalinowski, to lead robotics efforts. The move comes as OpenAI invests $400 million in robot startup Physical Intelligence, signaling expansion into physical AI.

Perplexity AI's Massive Funding: AI search startup Perplexity AI is finalizing a $500 million funding round at a $9 billion valuation, led by IVP. The company, which competes with Google and OpenAI, has seen its valuation surge from $500 million earlier this year.

Google's Internal Tension: Google executives faced concerned employees at a Halloween all-hands meeting following hints of more cost cuts. VP of recruiting confirms reduced hiring, while employees worry about potential layoffs after year-end.

Nvidia Takes Market Crown: Nvidia surpassed Apple to become the world's most valuable public company, reaching a market cap of $3.43 trillion. The AI chip maker's shares have nearly tripled in 2024, reflecting its dominance in AI hardware.

Meta's Mixed Quarter: Meta reports weaker-than-expected user growth with 3.29 billion daily active users. The company warns of significant AI infrastructure spending increase in 2025, despite 19% revenue growth.

Block’s Restructuring: Block-owned Tidal announces major layoffs as Jack Dorsey pushes for "startup" mentality. Company eliminates product management and marketing roles, potentially affecting 25% of staff. Block plans additional layoffs into December.

HELP US

👋 Hi there! We are on a mission to provide as much value as possible for free. If you want this newsletter to remain free, please help us grow by referring your friends:

📌 Share your referral link on LinkedIn or directly with your friends.
📌 Check your referrals status here.

BONUS

Just for laughs 😏

YOUR FEEDBACK

Until next time, take care! 🚀

Cheers,

Sahil + Sarra