Reorganize String - Tesla Interview Question - Leetcode 767 - Python
Vložit
- čas přidán 8. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
Python Code: github.com/neetcode-gh/leetco...
Java Code: github.com/ndesai15/coding-ja...
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/reorgan...
0:00 - Read the problem
4:30 - Drawing Explanation
9:10 - Coding Explanation
leetcode 767
This question was identified as a Tesla coding interview question from here: github.com/xizhengszhang/Leet...
#tesla #coding #interview
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Python Code: github.com/neetcode-gh/leetcode/blob/main/767-Reorganize-String.py
Java Code (Provided by a viewer): github.com/ndesai15/coding-java/blob/master/src/com/coding/patterns/heap/ReOrganizeString.java
Isn't the problem same as Task scheduler with cooldown period as 1 ?
Yeah exactly, a very similar problem.
@@annubaba7944 Almost, in task scheduler you can have idle cycles. Here you have to use all characters for the solution to be valid.
Conceptually simple but nuanced problems like these are my favorite
Here's an alternative way to construct a rearrangement:
1. rearrange by frequency in descending order ('abbacca' -> 'aaabbcc')
2. break into two halves and merge in alternating order ('aaabbcc' -> 'aaab' + 'bcc' -> 'abacacb')
The goal is to return a rearrangement where adjacent characters are different.
Your first alternate way doesn't achieve that.
@@DJ-vx9gl I meant for these two be two distinct steps in the same solution, the output of step 1 is just an intermediate result to be used in step 2. The final output is the output of step 2
Than how without looking into the result we will be able to find if adjacent are same or not ?.......so to check this we need to perform some extra operation?
@@negi3625 This construction guarantees that adjacent characters are not the same. We know that if a character has frequency >= 1+ len(s)/2, then no such rearrangement is possible. Now let's say this is not the case, and we sort the original string by frequency in descending order (e.g. 'abbacca' -> 'aaabbcc'). In this intermediate rearrangement (call it "s1"), the unique characters appear in chunks, and no chunk has length >= 1+ len(s)/2, i.e. s1[0] != s1[n/2+1] and s1[1] != s1[n/2+1]. When we split "s1" into two halves and merge in alternating order, we're doing something like s1[0] + s1[n/2+1] + s1[1] + s1[n/2+2] + ... . So this is guaranteed to have no adjacent characters that are the same. Here's a more detailed explanation along with my code: leetcode.com/problems/reorganize-string/discuss/1653199/python3-on-solution-without-max-heap
I will be right back I will test this, it seems that It will work but to make sure ill try
Mate, we really love your videos doing also your explanation to some of these weird question. From London I hope you keep going with these videos.
Thank you so much. I jumped straight to the solution because I don't know how to implement it after finishing reading the problem description.
congo bro on 50k i love watching your videos
I have a FAANG interview this Thursday, almost gave up this question..even though it is frequently asked during interviews. Now that you've made a video on this ..I'm relieved
Just did terrible on my Amazon interview :/ definitely nothing in the easy section of algo expert that’s for sure
@@TheTopProgrammer That hurts..I have my interview in 2hrs. Fingers crossed
@@poojabennabhaktula4883 How did your interview went?
@@sayandip8041 Flunked it. Question was reverse linked list in k groups. Managed to build brute force . The interviewer wasn't happy. Chances are slim 😐
@@poojabennabhaktula4883 good luck! I should have prepared more, but also feel like the questions they gave me seemed more challenging than other people I talked too. I will definitely continue practicing and re apply later this year when I have had time to focus in on those skills. I work in the cloud and have my aws solutions architect/azure administrator and write various automation scripts using powershell/Python but was not prepared haha. Anyway just wanted to give a backstory, I’m sure you will do great, just take your time and focus on breaking the problem down you got this!!!
Hi NeetCode, I love binging your videos! Any chance of doing any of the calculator problems in the future?
Thanks for the amazing content
Daily dose of Neetcode! 🙌
thanks for the great explanation, in just first 6 min understood how to solve problem
Just to add a trivial check, in the beginning, when reorg is not possible:
maxF = max(count.values())
if maxF > (len(s) + 1) // 2:
return ""
Then we need not do the rest of heap algo ;)
Hi Neetcode, can I use sorted dictionary by value. It will be still (nlogn) right.
bought life time sub, keep going 🏎
I love this guy for his clarity. Within 5 mins I got the hint and also, I was doing the same mistake that you showed at first. Thanks a lot, I came up with the approach of priority queue after you gave the hint in the minute.
Your videos motivate me to do leetcode , thanks 😊
Love your videos even though am not good with programming. Learning Python right now. Would love to listen to how to generate working code from plain English. Thanks
Whats the approach if they asked for minimum swaps required to make the possible string??
the goat
Congratulations on reaching 50K subscribers. We need a live session on the occasion of 100K subscribers.
That would be cool!
almost 210k right now
@@cocoatut49 641K now
Hi, thanks for the detailed explanation.
Isn't the first solution you showed (finding the max occurrence at each iteration that is not prev) is more efficient as it runs in O(26 * n) = O(n) as the hash map will be of size 26 at most?
The solution with the heap is O(nlogn) so why is it the chosen solution?
In the case that n = 26, O(n*log(n)) solution will be more efficient. O(n*log(n)) will be the more efficient solution until log(n) >= 26. This is assuming we are using the English alphabet.
I watched this video till 5:35 and was able to code it myself. Thanks.
C++ Guys:
class Solution {
public:
struct Compare{
bool operator()(paira,pairb){
return a.second0)
pq.push(top2);
pq.push(top);
}
else
return "";
}
return ans;
}
};
wow when you explain it, the solution just clicks instantly
Didn't understand why we used ''prev"? Can anyone explain it to me?
👍🏻👍🏻👍🏻 very nice
I just did it W/O seeing any video or discussion. Guess I'm good enough for Tesla 🤣🤣🤣
Heapify is O(nlog(n))
I found this solution too, but it is possible to do this in linear time (without depending on the alphabet restrictions, i.e. without a heap).
can u mention that approach
how
man ,two mistakes in my code, 1. I used even odd for holding the most previously used element
2. took reverse ie [ value ,-count] in heap 🤷♂
The second one happens to me all the time 🤣
You are God
Couldn’t you just sort it and then swap left and right pointers when you encounter duplicates.
no because that does not handle the fact that letters which occur most frequently need to be used first (as explained in the video)
how do you know this problem is from tesla
# from max heap
import heapq
lst = list(range(1,11))
heapq._heapify_max(lst)
print(lst[0])
A more readable solution
class Solution:
def reorganizeString(self, s: str) -> str:
if len(s) == 1:
return s
res = []
char_count = {}
for char in s:
char_count[char] = 1 + char_count.get(char,0)
max_heap = [] #[(char_count,char)]
for char,count in char_count.items():
heapq.heappush(max_heap,(-count,char))
while len(max_heap) >= 2:
top_most_count,top_most_char = heapq.heappop(max_heap)
next_count,next_char = heapq.heappop(max_heap)
res.append(top_most_char)
res.append(next_char)
if top_most_count + 1 != 0:
heapq.heappush(max_heap,(top_most_count+1,top_most_char))
if next_count + 1 != 0:
heapq.heappush(max_heap,(next_count+1,next_char))
# only one odd char left to get processed
if max_heap:
char_count,char = heapq.heappop(max_heap)
# not a valid case to add into result
if -1*char_count > 1 or res[-1] == char:
return ''
res.append(char)
return ''.join(res)
Similar to czcams.com/video/s8p8ukTyA2I/video.html Task Scheduler problem I guess
No need "if prev and not maxHeap". it's confusing.
just "return res if len(res)==len(s) else """.
If there are no extra letters for combining the maximum number of letter. The maximum number of letter won't push in the minheap. which means it can not fill in all letters.
Hi neetcode i think you have a mistake in the complexity time , actually you are dealing with the occurences of letters so at most you will have 26 different keys , so this o(26) you are building your heapify based on the maxHeap list() wich at most will have 26, so it is O(26) too, the same for the part of pushing and poping at most you will have 26Log(26).
So In general Ur algorithm time complexity is O(n) because of counting the number of occurences of each character and O(1) in Space Complexity. (Btw i saw your video notification yesterday and i tried to slove the problem and i followed the same approach as you)
btw you can improve your code instead of using res as a string you can start with an array and append( each character to it and use at the end "".join(res) wich is o(n).
i hope i could explain well my thoughts.
First off, O(26) is not a thing. It's O(k) where k is a constant. But this algorithm does not run in constant time because clearly a string that is 10000 characters long does not take the same time as a string that is 1 character long. You need to iterate through your HashMap to find the max occurrence for each letter as you decrement it. And you do that for each letter which means it's O(26) or O(k) multiplied by O(n) where n is the length of your string. So O(26*n) is correct
@@harrywang9375 Hi, please could you show me in my comment where i said that this algorithm run in a constant time ?
I clearly said : " So In general Ur algorithm time complexity is O(n) because of counting the number of occurences of each character and O(1) in Space Complexity. "
I think you did not read my full comment.
This is not medium 🙏😭
The if statement after the while cond cannot apply. Maxheap cannot be false and true simultaneously.
The if statement will never happen
maxheap does not need to be true to execute the loop
@@tshotblue22 nope... logical AND implies left and right conditions to be true. The IF statement after the while loop is opposite to the while statement. so if the while loop statement is false, it will not enter the loop therefore the IF statement will never happen. I guess the IF statement is useless.
@@stephanembatchou5300 did you catch where he updated the code at 16:48?
I thought the same but he corrects the "and" in the while condition to be an "or" in the last minute of the video