Microsoft Loves This Coding Question! | Reverse Words in a String - Leetcode 151

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[@GregHogg]

Sorry, it should be "the sky is blue" -> "blue is sky the"!

[@abdelrhmankamal1370]

You're still doing great! I really like all your videos; they keep helping me learn more about code interview questions.

[@GregHogg]

​@@abdelrhmankamal1370Thank you so much, I really do appreciate it!! ❤

[@yogeshvanzara5553]

Hey can you give us where can we learn DSA?

[@tomasruzicka9835]

I would have used bash sed replace ` +` for ` ` everywhere, another sed delete `(^ )|( $)` then rev then xargs

[@The-KP]

​@@tomasruzicka9835 , or \s ?

[@danielhaveman5675]

That code is waaaay too complicated. You only need to do 4 steps: - split on spaces - reverse the array - filter the array for any empty strings (the null between the two spaces, at the beginning and at the end) - join the array with a space again so: " hi there ".split(" ").reverse().filter(a=>a).join(" "); no need to trim separately, or to track things manually in a loop

[@shapelessed]

The point there was to make it as little CPU-intensive as possible. It does technically achieve this, since built-in methods hook in to pure C++ code, but the side effect is that you end up allocating memory for 5 different copies of that string before you reach the results.

[@danielhaveman5675]

@@shapelessed then that sounds like you have a severe case of premature optimization there. Sure you should understand what happens so you can write optimized code if there's a case for it. But there are many cases where legibility, simplicity, using native C++ optimized code, maintainability, preventing possibility of memory-leaks, etc. etc. is worth more than a slightly optimized memory-footprint that wasn't asked for in the initial question

[@shapelessed]

@@danielhaveman5675 That's literally exactly not what I said.

[@pantherdddjvdgx]

You got to love the noobs making videos while being unemployed

[@gustavo9758]

​​@@shapelessed how would you make it more performant? Regex to get the words? Individual trimming?

[@AngryEgg6942]

Bro is taking 3 left turns instead of 1 right

[@merveillevaneck5906]

Dude. Strip + reverse loop + character buffer using a stack + store resulting words in the buffer in an array every time you find a whitespace. Then join the array at the end. 2n runtime

[@salism2]

Thanks. This is an accepted answer in Python: ' '.join(s.split()[::-1])

[@Jahnvi-z8q]

yeah, even i put this directly in return statement and this solution passed all leetcode test case. I do not understand why go long when it can be done in a shorter way or probably with just one-line code.

[@edudictivecoder464]

​@@Jahnvi-z8q well you can but remember the single line would not help you track your Intermediates thus right multiple line is good in many cases where you might have to read the intermediates it can be for other func or debugging for your own with print func

[@AverageSensei]

Bro the type of guy to park the furthest from the grocery store

[@Eknoma]

You don't need a custom for loop to do a super common operation... "...".split() does exactly what you would expect, removing all whitespace, so e.g. " this is a \t string ".split() Gives you ["this", "is", "a", "string"] So the way to do this task in Python is just " ".join(reversed(inp.split()))

[@Eknoma]

Or of course if you want to use an actual programming language instead, you could just do solution :: String -> String solution = unwords . reverse . words

[@Torbeng]

@@Eknoma Boo no one wants haskell, but looks nice actually

[@Phrozends]

Without using so much memory for large inputs, we could use a the regular stack tecnique that gets flushed on spaces. You do it in O(n) time too.

If you use .split() or .split(None) instead of .split(' ') then you don't need for-loop nor .strip(' ') def rev(txt): return ' '.join(txt.split()[::-1]) And if you really need to use space (or other char) in .split(' ') then you may use filter(None, list) to remove empty strings from list def rev(txt): return ' '.join(filter(None, txt.split(' ')[::-1]))

[@musicb5202]

Right? I swear this guy seems to go at each of these challenges in the most beginner way possible, cause split is like the most trivial of functions. Yet he somehow can't understand how it works. Maybe like finish a python course first before doing leetcodes lol.

[@niaei]

@musicb5202 it's a codding challenge. You must have a logic that work on all languages. Split in all languages does not have the same functionality as it has in python. If it was a python codding challenge. Then you would be right.

[@prodmatze]

thats only for python tho, most languages dont have that many pre built functions

[@madghostek3026]

​@@prodmatzethe solution is in python so you should know and utilise the language, writing C calque in python is always possible but will be inefficient

[@jeansimonlavoie]

@@niaeiim a c# dev . And when I have to solve problems in a interview they usually forbid us to use any LINQ

[@FakeDumbDummy]

the sky is blue blue is the sky bro failed test cases in dry run

[@GregHogg]

Yeah ikr

[@sedletzkiivan3340]

javascript ftw : s.trim().split(/\s+/).reverse().join(' ')

[@your_-_mom]

Booo

[@corbinfonville1012]

I think the for loop is overkill. Just: str.split(' ').filter(s => !!s).reverse().join(' ')

[@pknepps]

Even better, string.split("//s+")

[@Keyakina]

what is s => !! s?

[@norbertkis-szabo5053]

This oneliner does everything that is needed for the solution. Although its in javascript I believe. S => !!s is checking the truthiness of the string and its only False if the string is ‘’. Code should be something like this in python, but I didn’t check it, wrote it from phone: “ “.join(reversed(filter(lambda s: s, text.split(‘ ‘))))

[@mathe42]

Using .filter(Boolean) is more readable

[@MadpolygonDEV]

And what do you think those functions do under the hood 😂

[@davidgillies620]

Run it through a whitespace-contraction regex before split/reverse/join.

[@babatundetaiwo5184]

I got asked a question similar to this 2 weeks ago

[@kartirnium]

Or just use split(' ') with the option to remove empty strings. Then iterate backwards while adding a space in between .

[@borisv7357]

when using split without any parameters, so just .split() it remoces all whitespaces, which means that for this solution you dont need to iterate in anyway, just not use the split.(' ') and the strip(' '). Which leaves new_s = ' '.join(s.split()[::-1])

[@briandavis6898]

Can you use split and join? Then maybe a trim instead of all that parsing

[@BitbenderM]

if you are gonna use python, then maybe actually use python? def reverseWords(words: str) -> str: return ' '.join([word for word in words.split(' ') if word != ''][::-1]) can change to r.split() if you want to split by regex to split better or to split easier with multiple types of delimiters but this one line requires no imports

[@GregHogg]

Sounds good to me haha

[@kumarashutosh-p3n]

we can solve via stringstream as well

[@GregHogg]

What's that

[@kumarashutosh-p3n]

@@GregHogg it breaks words into tokens.

[@henryjubeda7617]

Spaces are characters too

[@MartinBarker]

one line and no manual loops: String.Join(" ", s.Split(' ').Where(x => !string.IsNullOrEmpty(x)).ToArray().Reverse()); This is MS use C# they built it. if you can't you can do the same thing is most langs including VB since it has all of .Net inside it

[@mykevelli]

Or just add StringSplitOptions.RemoveEmptyEntries to your Split and you don't need the Where()

[@wong_tai_ming]

Can be solved with two pointers as well

[@oferron4894]

SHOULD be solved with two pointers is more accurate.. This dude didn't get what coding interviews are all about

[@Eknoma]

What would you need two pointers for?

[@tgr5588]

@@Eknomaone points to the beginning of the current word, and the other one to the end of it. You can then reverse the word in-place

[@Eknoma]

@@tgr5588 You are not asked to reverse each word... you are asked to reverse the order of the words. "I am a human" -> "human a am I". And why would you every write out an algorithm like reverse by hand, instead of using a library?

[@Tldr205]

​@@Eknomain coding interview the goal is often to make or show your own implementation and solution and optimize it. You need to know a library really well, to be sure it's not doing something funky.

[@daa82]

Just use a stack, put all elements in and pop them out. Voila!!

[@RemoteAccessGG]

Split, reverse, join - Wise Man And if you’re a nerd, you should do list(filter(lambda a: a != “”, splitted_list))

[@midophriya3657]

in Php implode(‘ ‘, array_reverse(array_filter(explode(‘ ‘, $str))))

[@jjferman2587]

This runtime is terrible. You can propose this solution but at what cost? Follow up, can you do it without using as much memory or time?

[@keyboardbasher5769]

def reverseWords(self, s: str) -> str: # Split the string into words s_split = s.split() # Reverse the order of words reversed_words = s_split[::-1] # Join the reversed words with a single space return ' '.join(reversed_words)

[@theabshow7318]

Bro can't we use just trim function

[@balavikashkandukuri6139]

return " ".join(reverse(s.split()))

[@pcriged]

Why not strip the spaces. Split on space into an array and then move any non space elements in to a new concatenated string. Seems like less code and less processor cycles.

[@alexjenkins8026]

Or just don't specify a single space in your split: ' '.join(s.split()[::-1])

[@SelvaKarthik07]

Just use .split() ?

[@KejriwalBhakt]

Do it using C. Using python is itself a hack.

[@GregHogg]

Haha fair, it's a hack that's usually allowed in coding interviews, and I feel we deserve all the help we can get 😂

[@chandings]

sir what about , or . or any other punctuation. ususally there is no space between words n punctuation

[@ankitroy8567]

L=s.split() L=l.sort(reverse=True)

[@AkshatPandey]

w=s.split() w.reverse return ' '.join(w)

[@muhammad.hameem]

Do this using C language without including sny library

[@Imbalanxd]

does anyone notice that the questions that rely on knowing long established decades old algorithms are classed as easy, and anything requiring even the slightest amount of nuance and original thinking is medium or hard?

[@1010-w4d]

Do it in c

[@AbhishekGupta-qv7ig]

They will rejext it or fail you , they want a DSA answer always

[@nabilfannane7217]

return s.split(' ').reverse().join(' ')

[@mufasum]

a cool one-liner I came up with, although I'm not sure if it's the most memory-efficient. return ' '.join(s.split()[::-1])

[@pound9799]

can you use the split function ? btw I love your content!

[@antoniong4380]

``....=my_string.trim().split(' ').rev().collect();`` this should be about right, right?

[@aziz0x00]

Hey thanks!, why is the "i += 1" in the for loop

[@StripesOO7]

Its totally useless since its this is python and „i“ gets overwritten nonetheless each loop.

[@madmarchy5176]

JS version message.split(" ").filter(val => val).reverse().join(" ") If you'd like to also capitalize the first word of the new sentence, message.toLowerCase().split(" ").filter(val => val).reverse().join(" ").replace(/^\w/, c => c.toUpperCase());

[@Triplicata]

"I solved it right away" >Everyone in the comments talks about how shit the code is

[@davidahgren9037]

Que?

[@TUSHARKHANDELWAL-i8s]

Now do it in C++

[@GregHogg]

Nah

[@TUSHARKHANDELWAL-i8s]

@@GregHogg hehe , I did this in C++ it was much line of code

[@rahuldwivedi4758]

This is not the kind of logic they’d be looking for though. They’d be looking for the logic. How about this? var newStr = ‘’; str=str.trim(); temp=‘’; for(var i=str.length-1; i>0; i-){ if(str[i]==“”){ newStr += temp.revers(); temp = “”; } temp +=str[i]; }

[@srki22]

Solution in Java: return Pattern.compile("[ ]+").splitAsStream("the sky is blue").reduce("",(x, y)-> String.join(" ", y, x));

[@AkellaBosch]

return " ".join([word for word in string.strip().split()[::-1] if len(word) > 0)

[@salism2]

This is accepted, split takes care of strip and empty words: ' '.join(s.split()[::-1])

[@DrCognitive]

What practical use could this knowledge bring to the table? When are you going to do this in a real program?

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@NOKIA5593]

Damn thats a bad solution... I would not hire you with this.

[@MadpolygonDEV]

Shocking how many people here over engineer this a simple problem

[@kenzostaelens1688]

' '.join(s.strip().split()[::-1)) should just work tho

[@bxshaped27_79]

Now do it in C

[@lootusmaximus9776]

even i could probably do that

[@abhinavmishra9323]

Don't know why people solve coding problems in python. Its so stupid

[@17ashishemmanuel]

Does python not support regex?

[@PavankumarPattar-bs5lv]

The Python "re" module provides regular expression support.

[@17ashishemmanuel]

@@PavankumarPattar-bs5lv ah I see

[@AngryEgg6942]

It does but you don’t need it

[@MumujiBirb-d2l]

regex moment

[@sharjeelfaiq16]

Better approach let s = "Blue Is Sky"; s = s.split(" "); s = s.reverse(); s = s.join(" "); console.log(s); \\ Sky Is Blue

[@juriansan]

Well I can stop listening.

[@maervo4179]

Dude just iterate, collect word as long there is not " " and put it on stack. O(n) congrats 😂

[@shapelessed]

string.split(" ").reverse().join(" ") Done. Have a happy day.

[@HanaShirosaki-c4f]

js oneliner from someone who gets rejected by every company in germany written in 20secs of my lifetime: const reverse = (s) => s.split(' ').map(w => w.trim()).filter(n => n !== '').reverse().join(' '); Dont know the idea of the video? such tasks is daily routine and do not need any brain at all lol

[@AngryEgg6942]

Guys don’t listen to this guy. This is the better way: ret = ‘ ‘.join(s.split()[::-1])

[@thescientist4668]

normal people: Just use split() or the equivalent in your language... solved in one minute. me with arm assembly without any libraries : "this little maneuver is gonna cost us 51 years!!" ya ik using asm is stoopid for coding interviews.

[@NishitMishra96]

Reversing the array and finding a word Using two pointers and then reversing the word makes it a medium category of problem. Using library functions is easy. But coming up with a solutions without using them is the actual skill.

[@sophiophile]

I think a more elegant (and memory efficient) solution is to iterate over the chars backward and while char != ' ', add the chars to a string rev_word. Each time the loop breaks, ans += ' ' + rev_word[::-1] and rev_word = '' (also, add on the termination of the for loop if rev_word isn't empty). Same time complexity, but lower memory complexity. Plus no extra logic necessary to handle weird extra whitespaces. Memory complexity for your solution is O(k) where k is the number of words, this is O(1).

[@shapelessed]

Memory is plenty in modern systems, while the CPU might be more of a bottleneck, and since it's probably either node or chromium, it's generally better to use builtin methods as they offload all the logic to much faster, lower-level underlying C++ code. So while splitting and joining is more memory-intensive, GC will generally get rid of it right away and might just as well be faster. That's why it's generally better to use builtin methods and only optimise and write your own helpers when truly needed.

[@darknight3613]

It wouldnt be smart to look at k as the number of words, if i have only 4 words but each of them is 10,000 chars long then it's around 40,000 iterations while you are saying O(4). And going through each letter in a word and keeping it will cost you the length of the longest word in the string, which is potentially the length of the string so O(n) memory

[@sophiophile]

@@darknight3613 I agree with you about calling it O(k). It was just to help make clear that he was duplicating the entire string *and* creating a list structure that stores the entire thing piece-wise, when you could just have a variable hold a single word at a time, while making a solution that didn't need to create any extra logic to handle extra/weirdly placed white spaces. Both solutions need to iterate over the whole string once (the split and join is iterating over each character in the word). The absolute best solution memory complexity wise, is to just do the whole thing in-place on the input string, and not create any extra variables whatsoever. But that makes for some really hard to read code when you handle the whitespace problem. This struck a balance between the two.

[@RockuHD]

​@sophiophile yeah but doing it in place is scary. In real life (not a code interview) they might be using that string for something else and then you just changed it on them... some languages string are immutable and for good reason... 100% agree though, looping backwards and added each char to a char buffer pre sized to the original string length +1 (for the null terminator) is the best way to go about this one.

[@sophiophile]

@@RockuHD 100%

[@MasterQuestMaster]

This language doesn’t have a „remove empty entries“ option for split? Damn…

[@antonivanov1351]

You can do it with no additional memory by just reversing the whole string first and then reversing each word(using two pointers technic)

[@SAL404w]

Me with my reg expression: 🗿

[@DZX5000]

if your getting asked to code in an interview, your being looked at as a clown. find something else.

[@jjpaq]

Regex replace all `\s.*?` matches with ` ` and then trim() would work for the spacing issues, no?

[@chacelow2438]

Or \s+ might work too

[@jjpaq]

@@chacelow2438 you're right.

[@The-KP]

`\s.*?` would replace all chars following a space, the dot star matches everything

[@jjpaq]

@@The-KP yeah, he's right, I was zonked when I wrote that lol.

[@gregbugaj]

just because you solved does not mean it is good. However you did get the job.done

[@raphaelamorim]

too complicated, the problem is much easier

[@darkoplax7688]

.trim.split(" ").reverse().join("")

[@gvenkatesh8935]

We can do this in one loop by using two pointers

[@mohammedfarookabdul3387]

heck to use regex pattern that's pro do

[@usemayonaise]

I doubt microsoft would hire you if you gave that as a solution

[@aniketmahangare8333]

I don’t think you’re allowed to use split and all here.

[@GregHogg]

You might, you could ask the interviewer! I try to use built ins where possible to simplify things

[@n_fan329]

Ret = s.split(‘ ‘).reverse().join(‘’)

[@GregHogg]

Beauty

[@RalfNieuwenhuijsen]

You are joking right? str => str.trim().split(/\s+/g).reverse().join(' ')

[@opaligodzilla417]

it should not be "blue is the sky" it should be "blue is sky the"

[@GregHogg]

Yes sorry about that

[@opaligodzilla417]

@@GregHogg 👍

[@arsenypogosov7206]

You are supposed to solve it in O(1) space...

[@GregHogg]

You'll have to generate a new (immutable) string so I'm not sure if this is completely possible

[@arsenypogosov7206]

@@GregHogg You are allowed to do it "inplace". You need to reverse the whole string and then each word individually. "hello world" -> "dlrow olleh" -> "world hello". Also sometimes people exclude the space needed for the answer from space complexity (like with the space for the input), but it's really depends on the interviewer. It's always better to ask him directly.

[@ajgamerpro1356]

c# remove empty entries

[@GregHogg]

Lol yeah built in functions are great

[@low-key-gamer6117]

Do it in C

[@prangbod]

‘ ‘.join([word for word in string.split(‘ ‘) if word != ‘’].reverse())

[@prasadsawant7]

Even though if we don't provide the separator to split, still it splits the string as expected without including those spaces in the list. I did it in one line: return " ".join(s.split()[::-1]).strip()

[@GeroldH]

This isn't quite the right problem. The constraint making this interesting is to do it in place, you can't allocate memory. Then you get the classic Microsoft question :)

[@GregHogg]

In many languages strings are immutable though?

[@lucnguyen5553]

​@@GregHoggNot in all languages. If you were to do this interview question in a language where strings are immutable (e.g. Java or Python), then imagine the input was an array of chars instead, similarly to low-level languages like C where strings are just pointers to sequences of chars. So "hi there" would be ['h', 'i', ' ', 't', 'h', 'e', 'r', 'e']. The goal is to reverse the order of the words without allocating any extra memory. The trick is to reverse the whole array, and then reverse each word individually, all in-place. For example: ['h', 'i', ' ', 't', 'h', 'e', 'r', 'e'] -> ['e', 'r', 'e', 'h', 't', ' ', 'i', 'h'] -> ['t', 'h', 'e', 'r', 'e', ' ', 'h', 'i'] Note: I agree that the solution in your video is cleaner and would usually be better in an actual code base. But that's just how coding interviews go, they force harsh constraints because they want to see a particular clever solution. In this case, the pretext is that this is a low mem device and so allocating memory is a no-no, which can be a real constraint, but most of the time your solution is easier for everyone to read and understand.

[@masomahboob]

Why don’t you write a lambda function inside the filter function to filter out any whitespaces. In the end, you could join the words back into a string with a space. Or, you could use regex as well. Using regex: import re # Original string with multiple whitespaces original_string = "This is an example string" # Step 1: Use re.findall() to find all non-whitespace sequences words = re.findall(r'\S+', original_string) # Step 2: Reverse the list of words reversed_words = words[::-1] # Step 3: Join the reversed list back into a string with single spaces reversed_string = " ".join(reversed_words) print(reversed_string)

[@Gennys]

Can't you pass in a regex to split by instead of splitting by single space? Split by greedy white space character in regex. Or you can sanitize the string before doing the standard method.

[@alexwolters1164]

In python its easy, try doing it in c with pointers and dynamic memory allocation.

[@TonyFarley-gi2cv]

Honey even the conversation to the wording is mathematically aligned together

[@jackpaice]

I hate this kind of test, cause irl I’d just use lodash

[@MytvvvMovies]

We can use space as a delimmetter in that case

[@vigneshreddy1213]

java 3 steps StringTokenizer deli=" " call recursively till no more tokens add the token to stringBuilder before returning from function and return

[@strategistaow3520]

How did you do blue is the sky? When it should be blue is sky the?

[@salism2]

He corrected it at the pinned comment above

[@Nikhil-ty3rk]

This is literally 3 lines in C#

[@casperhansen826]

A one liner i C#: return string Join(" ", input.Split(' ', StringSplitOptions.RemoveEmptyEntries).Reverse());

[@MadpolygonDEV]

The point of these is to show how you come up with your own algorithms and problem solving.