Reorganize String - Tesla Interview Question - Leetcode 767

Reorganize String - Tesla Interview Question - Leetcode 767 - Python

Рет қаралды 40,272

Күн бұрын

🚀 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.

Пікірлер: 81

@NeetCode 2 жыл бұрын

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

@annubaba7944 2 жыл бұрын

Isn't the problem same as Task scheduler with cooldown period as 1 ?

@NeetCode 2 жыл бұрын

Yeah exactly, a very similar problem.

@micahhutchens7942 2 жыл бұрын

@@annubaba7944 Almost, in task scheduler you can have idle cycles. Here you have to use all characters for the solution to be valid.

@TheElementFive 2 жыл бұрын

Conceptually simple but nuanced problems like these are my favorite

@cnknd2005 2 жыл бұрын

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')

@DJ-vx9gl 2 жыл бұрын

The goal is to return a rearrangement where adjacent characters are different. Your first alternate way doesn't achieve that.

@cnknd2005 2 жыл бұрын

@@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

@negi3625 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?

@cnknd2005 2 жыл бұрын

@@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

@spsc07 3 ай бұрын

I will be right back I will test this, it seems that It will work but to make sure ill try

@saranshthukral4021 2 жыл бұрын

Thanks for the amazing content

@BootBoot-rl1kv 10 ай бұрын

thanks for the great explanation, in just first 6 min understood how to solve problem

@curesnow6493 Жыл бұрын

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.

@gracepal1 10 ай бұрын

Daily dose of Neetcode! 🙌

@nathann4291 7 ай бұрын

bought life time sub, keep going 🏎

@BieberTaylorLove 4 ай бұрын

Your videos motivate me to do leetcode , thanks 😊

@punnarahul4068 2 жыл бұрын

congo bro on 50k i love watching your videos

@osmanmusse9432 2 жыл бұрын

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.

@devaliskedits3290 8 ай бұрын

the goat

@Mahmoudai 6 ай бұрын

Heapify is O(nlog(n))

@eeee8677 2 жыл бұрын

Hi NeetCode, I love binging your videos! Any chance of doing any of the calculator problems in the future?

@abhishekrbhat8919 5 ай бұрын

wow when you explain it, the solution just clicks instantly

@poojabennabhaktula4883 2 жыл бұрын

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

@TheTopProgrammer 2 жыл бұрын

Just did terrible on my Amazon interview :/ definitely nothing in the easy section of algo expert that’s for sure

@poojabennabhaktula4883 2 жыл бұрын

@@TheTopProgrammer That hurts..I have my interview in 2hrs. Fingers crossed

@sayandip8041 2 жыл бұрын

@@poojabennabhaktula4883 How did your interview went?

@poojabennabhaktula4883 2 жыл бұрын

@@sayandip8041 Flunked it. Question was reverse linked list in k groups. Managed to build brute force . The interviewer wasn't happy. Chances are slim 😐

@TheTopProgrammer 2 жыл бұрын

@@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!!!

@VarunMittal-viralmutant 2 жыл бұрын

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 ;)

@sleepypanda7172 2 жыл бұрын

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.

@oliesting4921 2 жыл бұрын

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

@ekanshsharma1309 10 ай бұрын

Whats the approach if they asked for minimum swaps required to make the possible string??

@eknathyadav8744 2 жыл бұрын

Hi Neetcode, can I use sorted dictionary by value. It will be still (nlogn) right.

@rct4750 2 жыл бұрын

👍🏻👍🏻👍🏻 very nice

@jonaskhanwald566 2 жыл бұрын

Congratulations on reaching 50K subscribers. We need a live session on the occasion of 100K subscribers.

@NeetCode 2 жыл бұрын

That would be cool!

@cocoatut49 Жыл бұрын

almost 210k right now

@mohamedkaba406 5 ай бұрын

@@cocoatut49 641K now

@varunshrivastava2706 2 жыл бұрын

Didn't understand why we used ''prev"? Can anyone explain it to me?

@ghazanferwahab5673 Жыл бұрын

I just did it W/O seeing any video or discussion. Guess I'm good enough for Tesla 🤣🤣🤣

@rushabhlegion2560 10 ай бұрын

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; } };

@114london Жыл бұрын

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?

@hassanaliamjad9403 10 ай бұрын

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.

@andrepinto7895 2 жыл бұрын

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).

@arjunrai4937 Жыл бұрын

can u mention that approach

@dmwhite6735 7 ай бұрын

how

@hacksbsb Жыл бұрын

how do you know this problem is from tesla

@sidazhong2019 8 ай бұрын

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.

@alf8988 2 жыл бұрын

Couldn’t you just sort it and then swap left and right pointers when you encounter duplicates.

@vikkalkat4523 Жыл бұрын

no because that does not handle the fact that letters which occur most frequently need to be used first (as explained in the video)

@amitupadhyay6511 2 жыл бұрын

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 🤷‍♂

@NeetCode 2 жыл бұрын

The second one happens to me all the time 🤣

@Hi_kartik Жыл бұрын

# from max heap import heapq lst = list(range(1,11)) heapq._heapify_max(lst) print(lst[0])

@geekydanish5990 Жыл бұрын

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)

@Yue27s 2 ай бұрын

This is not medium 🙏😭

@scchouhansanjay 2 жыл бұрын

Similar to kzfaq.info/get/bejne/qZ6ga9icud-lYn0.html Task Scheduler problem I guess

@ayoubalem865 2 жыл бұрын

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.

@harrywang9375 2 жыл бұрын

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

@ayoubalem865 2 жыл бұрын

@@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.

@frankyvarun 2 жыл бұрын

You are God

@stephanembatchou5300 2 жыл бұрын

The if statement after the while cond cannot apply. Maxheap cannot be false and true simultaneously. The if statement will never happen

@tshotblue22 2 жыл бұрын

maxheap does not need to be true to execute the loop

@stephanembatchou5300 2 жыл бұрын

@@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.

@ffrankk1234 2 жыл бұрын

@@stephanembatchou5300 did you catch where he updated the code at 16:48?

@nofluffagain 10 ай бұрын

I thought the same but he corrects the "and" in the while condition to be an "or" in the last minute of the video