Verifying an Alien Dictionary
Vložit
- čas přidán 3. 03. 2020
- For business inquiries email partnerships@k2.codes SOCIAL
----------------------------------------------------------------------------------------------------------------
Instagram: / kevinnaughtonjr
Twitter: / kevinnaughtonjr
Patreon: / kevinnaughtonjr
GitHub: github.com/kdn251
My Desk Setup
Desk - bit.ly/3jfY195
Chair - amzn.to/2O9TM3r
Monitor - amzn.to/3rcSHGa
Webcam - amzn.to/2NUmwgi
Desktop - amzn.to/3tiySPL
Laptops - amzn.to/3aRoN3Z
iPad - amzn.to/2LlJzzJ
Keyboard - amzn.to/3jfbxdd
Mouse - amzn.to/36ElWtT
Wrist Rest - amzn.to/3trrHF4 (pls don't buy this)
Mouse Pad - amzn.to/2Myz2lt
Microphone - amzn.to/3atNyTA
Lamp - amzn.to/3jjfZYp
Headphones - amzn.to/3tvr0KU (new model)
Headphone Hook - amzn.to/3tr8uTC
Blue Light Glasses - amzn.to/3cDVUdK
Wireless Charger - amzn.to/39LY1uu
Keyboard cable - amzn.to/2O5p2R5
Mic arm - amzn.to/3cECZj8
Audio interface - amzn.to/36HdWIi
Cloudlifter - amzn.to/36VO6kf
Laptop dock - amzn.to/2O2DsBw
Motherboard - amzn.to/3rkiWuA
Solid state - amzn.to/3rk5vuo
CPU cooler - amzn.to/3tnwwPA
CableMod - amzn.to/3tqbtM8
CPU - amzn.to/3auG1ns
Power supply - amzn.to/3trsAxo
RAM - amzn.to/39JZcuf
Designing Data-Intensive Applications - amzn.to/2YK4ek1
Clean Code - amzn.to/3txqfB5
Meditations - amzn.to/3cDa4fi
MUSIC
----------------------------------------------------------------------------------------------------------------
look at me. by ☽shinji☾
leetcode.com/problems/verifyi... - Věda a technologie
SMASH LIKE, SUBSCRIBE, AND LEAVE A COMMENT LETTING ME KNOW WHAT PROBLEM YOU WANT ME TO MAKE A VIDEO ON NEXT
instagram: instagram.com/kevinnaughtonjr/
twitter: twitter.com/kevinnaughtonjr
Its actually a bit simpler. You don't need to compare every word to every other word. Just compare your current word to the next word. If any i+1 is lexicographically before i, then they're not in the right order.
Nice!
@@KevinNaughtonJr In that case, how was your submission faster than 100% of Java submissions?
How was his submission faster than 100% of Java submissions? Are we missing something in the approach that you propose?
@@vk1618 Don't trust the speed of execution mentioned by Leetcode. It's mostly wrong.
@@vk1618 public boolean isAlienSorted(String[] words, String order) {
int [] ary = new int[26];
for(int i = 0; i < 26; i++){
ary[order.charAt(i) - 'a'] = i;
}
int j = 0, index = 0, length = words.length;
while(j + 1 < length){
if(ary[words[j].charAt(index) - 'a'] == ary[words[j + 1].charAt(index) - 'a']){
int min = (words[j].length() < words[j + 1].length()) ?
words[j].length() : words[j + 1].length();
for(index = 0; index < min; index++){
if(ary[words[j].charAt(index) - 'a'] > ary[words[j + 1].charAt(index) - 'a'])
return false;
}
}else if(ary[words[j].charAt(index) - 'a'] > ary[words[j + 1].charAt(index) - 'a'])
return false;
if(index + 1
@Kevin ..Just saw this question today for my first round at Facebook with just a tiny difference of getting a String array of alphabets as the order parameter.I would have never done this question unless I came across your video title.I feel grateful.Thank you so much.
That's awesome super happy I was able to help :) If you need help with more questions like this check out the interviewing service I created thedailybyte.dev/?ref=kevin I'd recommend joining the annual tier if you can!
Did you get the job?
Algorithm is really simple, as you found first letter not matching a letter is same position of another word then use the order table and then the task done.
Hi Kevin, there's a way that can be solved with dynamic programming? I'm trying to optimize it with some technique
Thanks to you I am getting better and better in solving these problems. Couple months ago I was merely a copy machine of your solutions. Today I am able to sort most of these problem on my own, then i am comparing our solutions ;)
Konrad Onbal that’s amazing Konrad nice work keep it up!!! :)
Hey Kevin, I just wanted to know why you compare each word with every consequent word in the dictionary. If we keep comparing i and i + 1th word lexicographically I think we can reach the ordering because in each step we make sure that i and i + 1 are correct. So we won't have to compare i with i + 2, i + 3 and so on. As going by order comparing i , i + 1 then i + 2 and i + 3 will make sure the dictionary is aligned with the previous value. What do you think?
Very useful thank you! Could you make a video on 373 please? Having trouble wrapping my head around it!
Okay one question here...
We are going with words[i] and words[i+1] and comparing lexicographically. But for words[i], we also have to compare with each letter of that word. For that another loop is used inside.
Does that complete execution in linear time? I think it will result in O(n^2). Please correct me if I'm wrong
I didn't quite get the purpose of the break statement. Why doe not traverse all throught the lengths of the ith / jth word? Wouldn't the loop break right after comparing the first characters from ith and jth words if we allow the break statement?
Oh I figured it out. When we see that the second word's current character has more value than first word's current character, we immediately know that these two are in correct places in the given list. So our next step is to break the inner for loop, so that we can compare the THIRD word with the first word.
I guess you could optimize it by comparing letter in the jth position of the ith and ith + 1 word while i is less than words.length -1, you avoid an unnecessary loop
Is there a reason why you use an array rather than a HashMap
N*N*M is not required. Just compare i and i+1 each time and do in N*M.
Edit :
Oops. Seems like lot more people pointed the same.
I had the same problem with my Interview with FB. Solved with the best optimal solution!
Just solving this problem will not be enough you need to solve the next Middle-level problem to pass Onsite interview
Excellent explanation
Amazing explanation bro!
Don't get irked by these ppl who are suggesting they have a better solution and all those things. It takes massive efforts for you to put such content for free! Appreciate it!
Sorry I'm new at this. Why we need to include the "- 'a' " part in the function?
get ASCII value for alphabets in order array
"-a" to make sure that resultant integer lies b/w the array indices (0 to 25)
I'm a little confused so "hello" "leetcode" o is coming before c right? So that should be false??
Can you please describe the time complexity over here?
Hi Kevin
Can this be solved using Trie?
Thank you again, kevin.
Anytime Arpit thank YOU for the continued support!
2:16 - you don't need to compare e's as from the first character itself we know they are lexicographically sorted. If the preceding characters are same only then you need to do the comparison of subsequent characters.
What I don't understand in the first example is that, 'o' in hello comes after 'c' in leetcode but the first example outputs true? How does that work?
Basically, the case passes/fails when you come across the first pair of distinct characters. The rest is irrelevant. Basically, the loops breaks after the first iteration since H comes before L. Not sure why Kevin kept iterating through the rest of the characters.
Can we go through the array once, create a matching int array based on the ‘weight’ of each word, and check of its sorted ?
hmmm that's an interesting idea
you rock dude !
Great video! One question though, why did you decide to use an array to store the alphabet as opposed to using a hashmap? If you used a hashmap its still O(1) lookup, and you can simply index it directly with the char value as opposed to doing (letter - 'a');
HashMap and Array Indexing has the same O(1) access time, however, Array Indexing is clean and direct, no odd cases. HashMap is not as clean, it can have collision at times. So Array Indexing is always faster though not dimensional faster.
HashMap can lookup the value with the character directly, though it is convenient, internally it is doing the math similar to (letter - 'a'). So speed wise, HashMap can only be slower if not on par with Array Indexing.
Hi Kevin!
I found this explanation really simple to understand. I myself reached to a similar solution with a hashmap instead of the array. However, I thought since the time complexity would be always greater than n^2, it would be a bad solution. I wanted to ask, how does one decide whether the brute force solution is good enough? Is there a way to do so before pressing the submit button in the coding round of the company?
If you can't think of any other solution, then you have to think that brute force is the best one. If you can think of another then just implement the other one. There is no way if knowing if you can't see the other solution
Solution summary: use a word_index to track your current word and char_index to track the current character index you are comparing with words that start with the same character(s). if order.index(words[word_index][char_index]) < order.index(words[word_index+1][char_index]) OR word_index == len(words[word_index]) -> word_index++ & char_index = 0 and keep checking while word_index is within range of the list of words
At 9:35 , How can you break whole loop by comparing the very first element buddy?
can please highlight the meaning it??
I don't know his code ran successfully and that too with "faster than 100%" when there is an O(n) algorithm to solve ths. Fake
great video man. can u please do more graph based problems?
thanks and I'll see what I can do for you :)
In case of “hello” and “leetcode” example ‘c’ comes before ‘o’ in order string. I am confused, please clarify.
Basically, the case passes/fails when you come across the first pair of distinct characters. The rest is irrelevant. Basically, the loops breaks after the first iteration since H comes before L. Not sure why Kevin kept iterating through the rest of the characters.
@thaxcutioner#1 , where does he iterate over the rest of the letters it breaks out of the inner most for loop and goes to the next word and as there is no next word, we return true.
Why would you need the i, j double loop? If word 1 is less than word 2, word 2 is less than word 3, that implies word 1 is less than word 3, right?
Yeah I think that makes sense
Please advise on facebook software engineering interview preparation.
Thanks Kevin . Please do next video no : 1192
Critical Connections in a Network
Anytime and that problem is on my list :)
Can anyone tell me "our first check".. the break in line 15.. wouldn't it just check for first characters and then break?
Yes, it means the condition satisfied, should compare next words
I have a queestion. Why does he keep substracting the character 'a' in the loops?
Whats your thoughts on learning python specifically for leetcoding?
I think that's a good call unless you feel comfortable in another language already
I don't think the if (...) break within the foor loop is necessary. Doesn't it?
Hi Kevin, great work. One little correction tho, you don't need to compare every word to every other one. It is sufficient to compare only words[i] to words[i+1], since if the array is sorted until the i'th element, we only need to check the next one. This would yield O(n*m) instead of O(n^2*m).
right!
Could you do leetcode problem 163 Missing Ranges? Thank you
I'll add it to my list
We don't need to compare all the words in the list with every other word that comes after. We can just compare 1st and 2nd, then 2nd and 3rd and so on. Wouldn't that be better than this?
Kevin, i guess here 2 loops i,j is not required, because you compare in one loop i, i+1 words comparison ?
yep you're right, nice!
I think 2 loops are required since you need to compare the letters according to their dictionary. So one loop to go through the words and the other loop to go through the letters:
Great sir
dear kevin, the 'break' statement breaks the for-loop running k times as soon as it compares the first letter. so it only verified the lexicographical order of the first k character of each word and for rest of the k-1 characters it just breaks out of the for loop. isn't this an anomally? its the first check right to break away right after the very first letter compared and found to be correct?
yes. azzzzzz always comes before baaaaa
In the first example, why u compared other characters of strings after first mismatch?
Wasn't comparison of the first character was enough?
yes it was I think I was trying to just explain the logic more
@@KevinNaughtonJr Except that follows a different logic b/c for the first example "o" (hellO) comes after c (leetCode) thus that case would fail
The - a is throwing me off big time.
Use a hashmap to store the letters and the index of them instead. I dont get the -'a' either. wont even run when i have that
What about using a trie
I just did not understand the task scheduler at all...its not the code that i did not get ...but the question itself ...i tried to read it several time ...but cannot get it
Never seen or heard of this problem. Thanks for sharing!
One question - is M the max letter count of all the words? I think it’s the min. As you take k as the min.
M (in the runtime) would be the maximum size that an individual word can be because in the worst case we'll have to run through all those M characters for each of the words
letter o comes after the letter C, so my script is saying its False on the first example.
i was confused there too. the question only cares about the first great or smaller than case to decide. So in all the examples, it decides at the first instances a greater or smaller comparison
13:51 - Memory usage could be better. No need to create an array of alphabet you can just compare using order.indexOf(words[i].charAt[j])
Shouldn't the 'break' at line 15 be a 'continue' statement?
If the kth character in the ith word is less than the kth character in the jth word then we know those two words are in lexicographical order so we can stop there
No, you already verified that iChar is < jChar so the lexicographical order is correct. You dont need to compare the rest.
Think about ""abaxy" vs "abcde". As soon as you verified that a < c on 3rd characters, you need to break.
@@MehmetSafakAlbayrak Right which is what my code is doing :)
@@MehmetSafakAlbayrak but if loop breaks after verifying a
I would translate the words from alien to English and then use the language string comparison to compare i and i + 1
Requesting for Find Max distance from closest person in a row.
I'll add it to my list!
Please solve minimum window subsequence. Thanks.
I'll put it on my list!
This is so hard
WHY MINUS 'A' ???????
please make video on Amazon Oops questions
I'll see what I can do!
How can somebody solve this in 20 minutes?
Good video but you do not need to compare every word with every other word. You just need to compare the current word with the next word (I think.) Also a hash map that stores the character index for each letter in the alien dictionary makes this a little easier. So map['h'] = 0 for example. Then you are just comparing indices not letters.
You just need to compare adjacent words to check if they are lexicographically sorted., no need to compare a word with each of the other words.
Could you make a video on Amazon's most FAQ on OOP, create api to search file in dictionary
I'll see what I can do!
please do dynamic problems
I've got some on the list!
Can you do more Facebook most asked questions pleaase?
i got you
Kevin, lexicographic comparison is transitive. You only need to compare to the next word.
The modularity of the code isn't good.
Why the "- 'a' "
I came here for the Hard version -_-
Click-baited FTW
I watch this video 3 weeks before an interview for facebook
Nice :)
@@KevinNaughtonJr i am stressed . I am a data engineer. Asides from algorihm i have to prepared for sql as well
@@iamabean If you need help preparing for your interview check out my Patreon page: www.patreon.com/KevinNaughtonJr
@@KevinNaughtonJr i am watching ur Facebook playlist and pray hahaha
lmao just realized this is an easy question
Why is this rated hard in gfg😖😖
You only need to compare i and i+1 words Don't need the inner for loop with j
I think you do cuz otherwise you can't guarantee that the current word is lexicographically sorted with respect to every other word
@@KevinNaughtonJr czcams.com/video/qSbJZWENtX4/video.html
We need to verify for every word[i] , it is lexicographically sorted with respect to word[i+1] which we can conclude that words[i] is lexicographically sorted with respect to all the remaining.
@@MehmetSafakAlbayrak ahhh gotcha :)
@@KevinNaughtonJr but if every word is sorted with respect to its next word, then definitely whole array is sorted
@@bhopalsingh4102 right
["apap","app"]
"abcdefghijklmnopqrstuvwxyz" i can't seem to understand how apap is less than app. Please explain.
Think of a dictionary.
a comes before p, so the words are technically the same up until "ap", because right after one has an "a", the other has another "p", and since a comes before p, therefore appap is the first word.
A dictionary (like a real world, alphabetical one, not a Python object) only cares about alphabetical order, not length.
I think we can solve this in O(N*M) time where N is number of words and M is average number of characters in a word , if we put the characters in order as keys and the respective position(weight) they occur on in the string in a hashmap e.g. h-> 0,l-> 1. We then iterate through the words string picking each word and adding up the weight of the word with the help of the hashmap. Then have a count variable that stores the total weight of the previous word and compares it to the weight of the current word we are looking at. If our current word is less in weight then we return false.If not, we continue the process till the end and return true.
You don't need to compare every letter mate, you keep comparing while letters are the same still in current and next word.
mapmp;
for(int i=0;i
This can be done in n*m times as others in the comments have suggested, Here is python solution for the same.
class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
alphabet = [None] * 26;
for i in range(0, len(order)):
alphabet[ord(order[i]) - ord('a')] = i;
for i in range(len(words) - 1):
word1 = words[i]
word2 = words[i + 1]
minCharLength = min(len(word1), len(word2))
for j in range(minCharLength):
word1Char = word1[j]
word2Char = word2[j]
if(alphabet[ord(word1Char) - ord('a')] < alphabet[ord(word2Char) - ord('a')]):
break
elif(alphabet[ord(word2Char) - ord('a')] < alphabet[ord(word1Char) - ord('a')]):
return False
elif(j == minCharLength - 1 and len(words[i]) > len(words[i + 1])):
return False
return True
class Solution {
public boolean isAlienSorted(String[] words, String order) {
int n = words.length;
HashMap map = new HashMap();
for (int i = 0; i < order.length(); i++) map.put(order.charAt(i), i);
for (int i = 0; i < n - 1; i++)
if (!sortedAlienly(words[i], words[i + 1], map)) return false;
return true;
}
private boolean sortedAlienly(String s, String t,
HashMap map) {
int m = s.length(), n = t.length();
int i = 0, j = 0;
while (i < m && j < n) {
char ss = s.charAt(i);
char tt = t.charAt(j);
if (ss != tt) {
return map.get(ss)
Words: ["hello", "leetcode"]
Order: "hlabcdefgijkmnopqrstuvwxyz"
Does `o` in hello comes before `c` in leetcode ? how are they sorted? Can anyone help me to understand ?
you don't need to go till c. you compare h to l -> since h < l you broke the condition check and continue