Problem 42: Length of the longest subarray where all its elements are distinct (Microsoft)
Math, Permutations, Combinatorics, Heaps, Trees
Happy Wednesday my amazing reader,
How are your summers coming along? Y’all up to anything exciting? I’ve been visiting extended family all around. I left home when I was 10, so it’s important that I try connect with family/extended cousins when I do visit home again. Today, I was driven down a couple of hours to visit my maternal grandparents (from my dad’s house). Thanks to the insane New Delhi/North Indian summers, I was sweating even though I’d come in an AC car. My grandad asked me if I wanted him to fill up the bathtub, so I could bathe the way I “loved”. The funny thing is that I am now physically too big for that tub. I guess in his mind, I’m still the 7/8 Year Old who used to splash around in the bathtub with his brother+cousin. Do you have such anecdotes from your lives? I’d love to know.
Getting back to point, I’ve got a very tricky question for you today. Don’t stress too much if you can’t do it. The purpose of this is to just expose you to another kind of question that will occasionally show up in your interviews.
Problem
This problem was asked by Microsoft.
Write a program to determine how many distinct ways there are to create a max heap from a list of N
given integers.
Examples:
Input : n = 3
Output : Assume the integers are 1, 2, 3.
Then the 2 possible max heaps are:
3
/ \
1 2
3
/ \
2 1
Input : n = 4
Output : Assume the integers are 1, 2, 3, 4.
Then the 3 possible max heaps are:
4
/ \
3 2
/
1
4
/ \
2 3
/
1
4
/ \
3 1
/
2
Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.
***Special Request***
This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.
There is a simple form in Substack that you can fill up for it. Here it is. Thank you.
https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform
To get your Substack URL, follow the following steps-
Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.
You will be redirected to your URL. Please put that in to the survey. Appreciate your help.
In the comments below, share what topic you want to focus on next. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
Happy Prep. I’ll see you at your dream job.
Go kill all you Swinging Savant,
Devansh <3
To make sure you get the most out of these questions, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75