Technical Interview with a Software Engineer - Algorithms & Data Structures
HTML-код
- Опубликовано: 1 окт 2024
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering 
Наука
I HOPE I GET CALLED BACK FOR THE ONSITE KINDA NERVOUS
Kevin you amazing, what a quick solution in 10 mins, neat and clean 😃
kumaran sg thanks!
HR will get back to you
My interviewer would have grilled me for a O(2N + 64lg64) time and O(64) space solution.
@@swagatochatterjee7104 what type of roles are you trying to get into?
The content you two put out literally changed my life ❤ I'm glad people like you exist.
Same dude. I've been doing leetcode for a month and whenever I'm stuck, I look for videos from them.
Nope, run time is not n log n where n is the number of unique characters.
The complexity is O(n + m log m) where n js the length of string and m is the number if unique chars.
Agreed, and if, lets say all characters are English letters, then the mlogm part could be considered constant, thus the total run time is really just On. That makes O(nlogn) sounds sub-optimal.
biggest crossover after infinity war
Please Like the video (it helps my channel a lot) and also
Subscribe To Kevin's Channel! - ruclips.net/channel/UCKvwPt6BifPP54yzH99ff1g
Both of you are awesome
Our inspiration
Thanks Nick thanks Kevin
I've watched both of you while I was preparing for my interviews. Will do again probably when I get back to coding leetcode.
I wonder if you could have not bothered with the heap and just sorted the array using the the same comparator and a built-in sort function.
Yeah a int[64]; would have just done the trick
this is such an easy coding problem in Python. from collections import Counter Counter(string).most_common() -> [("a", 3), ("b",2), ("c",1)] -> for k,v in Counter(string).most_common(): newstring += k*v -> return newstring
Can someone please explain me how the PriorityQueue override for compare works in Java??
Should time complexity is O(n + klogk) & memory is O(k) k is number of characters from a-Z?
Maybe I'm not the best one to tell you that, but it would be better to start with brute solution. Thank you so much.
two of the best programmers on RUclips in one place! Cool
Cool lesson Thank you so much both of you !
Is NLogN correct or is it O(N)? If we assume that alphabet has 52 characters, the construction of MaxHeap and iteration is constant time correct?
I believe it's O(N). Or specifically O(N + K log K) because:
1. Counting the characters takes O(N) time
2. When you're iterating over distinct characters constructed by a Hashmap to build the Priority Queue. Let's say K represents distinct chars, the runtime will be K log K time .
Credit to Logan Drone who commented this earlier
The size of the heap is upper bounded by the number of characters in your character set, which is constant. Wouldn't this mean that the time complexity is actually O(N) ?
No, modifying the heap is log n and you do it n times, giving you n long n
@@Qrzychu92 But, when he builds the heap, he is iterating over the hashmap, which is not size N, but size K, where K is the number of distinct characters (the character set). So if only a - Z are used, K == 52, or 128 in the case of ASCII. This is done in a separate loop, so the overall runtime would be O(N + K log K), which reduces to O(N).
@@loogtoob holy crap, you are right! What's more, simply counting the letters, sorting by count would also be O(n) because the max number of elements to sort of constant. Nice :D
return new string(toSort.ToCharArray().ToLookup(x => x, x => x).OrderByDescending(x => x.Count()).SelectMany(x => x).ToArray());
man, you gotta love C# :)
@@loogtoob Good catch! Thank you for explaining :)
And then there is me doing this in one line with the power of c# and linq:
public static string FrequencySort(string word) => new string(word.GroupBy(c => c).OrderByDescending(c => c.Count()).ThenBy(c => c.Key).SelectMany(c => c).ToArray());
Do you guys mind explaining why the runtime is O(nlogn)? To build the map, it'd be O(n). Then to add elements to the heap, it'd be O(logn). To remove would be O(logn). Therefore, the total runtime would be O(n + 2logn) which would be O(n)? Sorry, I'm a newbie.
StockDC2 in the worst case, you’re adding and removing n elements from the heap. Since each takes log n time to remove, the whole heap procedure takes nlogn time
@@SnorriDevTeam Ahhh, understood. Thanks so much for the reply.
This could be improved to O(n).
Hi, shouldn't the time complexity be o(NlogN+n) where N is the size of the alphabet and n the length of the input?
use a LinkedHashMap and you get the "cccaaa" output.
So I used Java's streams to do this in a one liner and my timing out show it to execute faster (not sure how this will format):
input.chars()
.parallel()
.mapToObj(i -> (char) i)
.collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()))
.entrySet()
.stream()
.parallel()
.sorted(Comparator.comparing(Entry::getValue, (s1, s2) -> {
return s2.compareTo(s1);
}))
.map(e -> IntStream.range(0, e.getValue().intValue())
.mapToObj(i -> e.getKey().toString())
.collect(Collectors.joining()))
.collect(Collectors.joining());
My two favourite youtubers for algorithms in one video! fire.
enjoyed so much..now going for nick's interview
Did he mess up the heap on purpose? 😂
In ThE DeScRiPtIoN
Hi Nick, i have a short Question: Is the Steem Account "iwudah" belongs to you and do you have recently published this Video here on the Steem Platform? Thanks in Advance - greetings, louis
Great collaboration ! Thanks for such a good content !
I created a map with counts and then split input string to array and finally quicksort string array using map counts.
Hi there. I need a help. I just started competitive programming and I'm not sure about which programming should I go with ??? Java , C++ or python ?? What do you think ????
This is my solution which sorts same frequency characters in alphabetical order. The interviewer may want this if this question comes up in the actual interview
public String frequencySort(String s)
{
Map map = new HashMap();
for (int i = 0; i < s.length(); i++)
{
map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
}
PriorityQueue pq = new PriorityQueue((a, b) -> a.getValue() != b.getValue() ? b.getValue() - a.getValue() : a.getKey().compareTo(b.getKey()));
pq.addAll(map.entrySet());
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty())
{
Map.Entry e = pq.poll();
for (int i = 0; i < (int)e.getValue(); i++)
{
sb.append(e.getKey());
}
}
return sb.toString();
}
I read that thumbnail and realized school wasn't that bad.
Do a system design next
I actually got the right answer to the question. I'm happy :)
I'm not sure that this solution correctly handles characters in upper and lower case. I think the input strings were to simple to fully test. Picture: "abcABC". How would that be sorted?
Justin Nelson remember that the case is treated as its own frequency, so, they all only occur once, therefore any order is valid. This is a special case.
E.g:
AaaA -> aaAA or AAaa it won’t matter
the thing kevin did at 5:50 (a,b)-> ... went overrrrrrrr my head. idk how he did that
@Royal Thomas thank you for the detailed response. Can i do something like this
new PriorityQueue(Collections.reverseOrder());
?
@@hacker-7214 Following this thread on lambda Comparators
Wow.. Thanks a ton!
It was such a fun and instructive at the same time... Keep it up yo! We want more of this...
Lol I have subscribed both of your channels
now mine pls :P
@@MeggaMortous I did good luck on your content creation
@@nayemalaboni8318 Thank you thank you!
@@MeggaMortous lol you're most welcome
Can we use TreeMap instead of HashMap...? Then we dont need Priority Queue.. isn't it?
Treemap requires more computation to store elements than priority queue...PQ is nothing but a heap
Bless you for the algorithms & ds videos as always Nick
swear to God you didnt look at answer before starting video
Not to sound pretentious but this is a pretty standard way of solving problems like these. Whenever you need to keep track of occurrences, you'll most likely always use a hashmap. Min and max heaps are very efficient O(logn) for inserting and removing nodes. If you're not familiar with heaps, an inefficient way this problem could have been solved is to find the largest number in the hashmap, print the key (i.e character) associated with that number X times, and then mark it as "used" or remove it from the map.
Great Kevin and Nick
what to do sir to become a coder like you.
please give your suggestion.
At my channel I'm solving leetcode questions and explaining my thought process. Maybe that will help you :)
@@MeggaMortous thanks
2 legends collide.
frequencySort() has unnecessary memory allocation, that's enough to fail an interview. That's why it is strongly recommend to declare/or define variable close to using them (which is another rule that was violated and these are basic rules that every programmer should know.) Also, result.ToString(), if s is empty, is unnecessary, just return "".
ActiveX man just said “unnecessary memory” lol I don’t really get what was happening but it worked so who cares
@@SteezyyGG Tiko, you would of failed the interview at my software company or any other company for that very reason.
@@activex7327 ima be playing league of legends ranked in my room with the boys and out skateboarding with my friends instead
How to got a job in 13 minutes
Python developers sweating over the question
Below is the solution I could think of in Python -
def string_orderby_frequency(str1):
list_of_char = [x for x in str1]
Char_mapset = set(list_of_char)
result_array = []
freq_of_char = []
freq_of_char_list_ordered = []
for c in Char_mapset:
freq_of_char.append(list_of_char.count(c))
freq_of_char_hashmap = dict(zip(Char_mapset,freq_of_char))
for key,value in sorted(freq_of_char_hashmap.iteritems(), key=lambda (k,v): (v,k),reverse = True):
freq_of_char_list_ordered.append ((key,value))
for (key, value) in freq_of_char_list_ordered:
result_array.append(key * value)
return "".join(result_array)
basura de codigo xD