Coding Interview | Software Engineer @ Bloomberg (Part 2)

Data structures website: keeponcoding.io
Part 1: • Coding Interview | Sof...
-----------------------------------
/ keep_on_coding

[@pawlstothewall]

The problem doesn't say that the input string will only have the characters in the array. This could be a problem for your hash function, because "abe" (1+2+5) would be identical to "acd" (1+3+4), for example. So, if the array was ['a', 'b', 'e'], but the string was "acdbe", it would return "acd" as a valid substring. Of course, the function will work fine if the string will only have the characters in the array.

[@JoseVargas-dx7wz]

Cool video! I got a lot of worst experiences than this you show! First. The interviers where much toffer! they provided me with no help. expt when I was five minute left of the time asigned to the interview, at that point I knew I was doomed!. You give her some very good pointers on how to deal with this types of interviews. The first one is that you show the way you are thinking the problems. Analysing edge cases and trying to show how you would solve it "by hand", confirming with the intervier that you are on the right path by writing down the steps in common languaje 8this is seen on the part 1 video). The second one is that you always should own the mistakes you make, like the hash function there, No matter what the error is you could alwys state "let me contiue assuming that it's correct" that's a superb way of getting some presure off, because in the real situation you know that you'll have a lot more time or the help of others to unstuck you and also yuo would be able to debug the damm thing!

[@ehsanhadid1260]

I liked the mocked interview and it helps me a lot. but about the code, you wrote, the getHash will return the same number for (a,c,e) and (b,c,d). a= 1 , c = 3 , e = 5 == 9 b = 2 , c = 3 , d = 4 == 9 we can't make a unique hash in this way and also you didn't consider this situation (xyxyz) in your code and you just checked if the 'y' is at the end.

[@cristianoo2]

I would solve it by sliding a window, then counting for each char in the window how many times it appears. Then check if any has zero, if so, it's invalid. If not, it's valid. If invalid, slide the window to the right 1 pos and repeat it. Cache it in a list of start pos -missing char. If you reach the end of the string and nothing was found, start it over with a +1 bigger window. For each new try, look for start pos + window size -1 and check if the char there is equal to the stored missing char. If not, continue sliding right. The caching system provides dynamic programming features that will make it run as fast as nlogn in the worst case

[@sanishtj]

Nice job. I have another idea not sure whether a valid one. Make an ArrayList, add all unique items to list, Loop through each char in the string, keep removing whatever char comes first. if we can't find a char, [when something repeating] stop and reset the ArrayList back to start one. Repeat. Time complexity O(Nk) I guess with ArrayList operations. And space complexity may be O(k) for the new ArrayList. Please let me know what you think.

[@dhwajsharma]

Please do more of these type of videos.

[@truthprevailer8531]

Map a Number for each character and sum up the number in each location. e.g. x=1,y=2,z=2 so str = 12577876.. so 6 means its perfect addition of x+y+z.. just output the from 9-2

[@freakycandies]

You should multiply the character value to prime number while calculating the hash to ensure uniqueness.

[@roryboyes2307]

I didn't consider prime numbers. I was thinking of multiplying each character value by a value which would make the smallest valid string character value greater than the largest valid string character value

[@HarisKhan-bh6uj]

learn so much watching these videos !!

[@saads9915]

Firt i will split the string then get every 3 characters from the first position and check if it has all the characters, if not then move to position 2 and take the next 3 (array lenght) ...

[@wiktorliszkiewicz354]

Get all the unique chars from string then count it length, then loop over the string starting from 0 to length of the query minus the length of the string and do the regular expression comparison to each search string if is null then add one to search space of the string and loop again, if search string length is same as string length and no match then return null... ?

[@evitaemort]

Wow thanks. Totally Do abl. Great Relief to know I will find a job after uni.

[@chashtag2336]

I think given some assumptions on this question theres a much faster way of solving it. If all characters in the String match characters in the array, all characters in the array are unique, and the smallest substring is the size of the given array, you dont ever need to compare the characters to eachother. All you really need to test is that any substring of length of the array has unique characters. So if array has 4 chars, read substrings in groups of 4. Solution: Create a HashSet. Add each character to it in groups of 4 from the string. Check its size. If size = 4, you found the string

[@lvisyt]

it asking for smallest substring that has all characters given in the arr. It might be possible that answer has size more than that of arr size. example -> arr = {a , b, c} and strr = "abdc".

[@yti]

Yup, this guy’s answer is like minimizing heart surgery into playing candy crush.

[@chreezy8276]

I'm new to programming but couldn't you write it like this in python or am i missing something: def getShortestUniqueSubstring(arr,string): substring="" for i in string: if i not in substring and i in arr: substring+=i return substring

[@jaagup]

@@chreezy8276 Going to ask couple questions that might help you learn more of the computer science side of the thing. Whats the time complexity of line "if i not in substring and i in arr:", when n = len(arr) and m = len(string)? And then whats the time complexity of the whole function?

[@chreezy8276]

@@jaagup I guess it would be O(n*logm) for the line and O(n^2*log(m)) for the whole function. So pretty slow overall

[@DansHobbies]

A better way would be to have 2 pointers and an int (uniqeChar) that counts the amount of unique chars seen. For each new char we see we will increase the counter. 1) The first pointer will increment and for each char it sees - if exists in the hashmap increase its count, otherwise increase unique count by 1 and and add to the hashmap, stop when uniqueChar=arr.size. 2) Now start moving the left pointer, for each char if its value in the hashmap is greater then 1 decrease it, and continue, otherwise remove the char from hashmap, reduce uniqueChar index, save the number as shortest string, and return to 1). 3) stop when the rightmost pointer reaches the bounds of the string. 4) return the smallest string index. o(n) with 2 pointers and easy to code.

[@pritamkumarpattanayak1497]

KMP OR RABIN KARP ALGOTIHM CAN BE USED ?

[@DragonPigAdventures]

might be a crazy simple and wrong answer, get the length of the array (this will be the smallest length of the output), then move through the substring with a for loop and just check each letter? find x if the next one is x go back to the search using the position of the last x as the start position? and so on? but it wouldn't account for more than one match or use the array to make a matrix of different strings of possible patterns xyz xzy etc then just search through the substring?

[@samgord4669]

idk about time and space But, i think if you wanna use JavaScript to do it, the function will be something like : const res = (arr,str) => { let unique = [...new Set(str.split(''))] let sharedChars = [] unique.forEach(char => { arr.forEach(el => { if (char == el) { sharedChars.push(char) } }) }) return sharedChars.join('') } plz correct me if i'm wrong 😅

[@sravanthi_anumak]

All your videos are very informative. Thanks for your effors. :) I have interview with bloomberg in NYC coming up... can you share your thoughts on this.. Many thanks.

[@maxou95210]

Would the use of a ternary search tree be a good solution here? We create a TST from the input string "str" and loop over arr to see if we can find a subtree containing the sequence of characters defining the substring. Complexity would be at worst O(N²) if arr.size == str.size (e.g. the substring is the whole str) Average complexity would be O(log(str_length) x arr_length)

[@kamertonaudiophileplayer847]

It would be interesting to see a coding interview in machine learning.

[@iftekharniloy913]

They ask the same things, with some additional things about your ML experience.

[@chiranthsanketh562]

@@iftekharniloy913 Wouldn't they concentrate more on real-time examples?

[@wanderlustfunk]

My friend gave one ML interview, got asked to convert BST to doubly linked list in o(n) time and o(n) space

[@kamertonaudiophileplayer847]

@@wanderlustfunk Thanks, it is kind of obvious.

[@rishabsharma8298]

Well it can be done in log n if we start iterating from both sides, so whenever you find the the string you keep adding it to an array, so here will be two arrays at the end. Now your only have to check both arrays and find shortest string that will keep the complexity to n (small size of array strings). Now if shortest string of both the arrays is equal in length give priority to array one since it’s the first ordered string, otherwise you can display the reversed string in reverse from the second array. Assuming string length can be 500 it can in worst case be linear but in most of the cases will be O(log n)

[@jpmorallo]

with this video I need probably 2-3 years hard coding C# and Java to be skilled once again at age 47.

[@boblewis1287]

You need data structures

[@DevvratSingh007]

We all need Lord.

[@-r0mus5]

no you just need to grind leetcode

[@johngreen256]

Could this problem have been solved with the window slider algo? Like basically just a for loop with pointers that keep track of the window size and returns the minimum window size that contains all 3 of those required characters? Not sure if this is optimal solution but what I would have tried.

[@badmusadeyinka1662]

My thoughts exactly. I think you are correct.

[@jameshuh8362]

Yes, this is a sliding window problem. When you have all 3 of the required characters, you decrement the window size until you don’t, then you start moving your end pointer forward again.

[@melihtopcu97]

it would work, but Regular Expressions are the way to go for this problem. Just let it build the expression given the Arr of characters to get each possible, valid combination (like this: xyz|xzy|yzx|yxz|zxy|zyx) and return null if no match or match.Value. Can be done in 3 lines of code.

[@ooboontoo]

@@melihtopcu97 Yes, and what will be complexity of this regexp ?

[@melihtopcu97]

@@ooboontoo pretty simple, xyz|xzy|yzx|yxz|zxy|zyx for 3 characters. x^2 - (x) should equate to the number of characters. Using 20 characters it would take 380 combinations. If you were to take many more characters, a better algorithm would be needed. But I think up to 20 should be fine. Using logical OR's is not very computationally expensive and quite fast.

[@alexcruz8024]

Wow this looks easy… I need to start applying for internships…

[@RebornAc3]

Can use rabin karp algorithm to solve this in worst case O(n*m) but if implemented properly should fetch you O(n+m), with constant space.

[@a_llama]

that assumes the characters are contiguous

[@joshuaaroke]

Ok, I guess the interview is for the two of you and in pair. Please let me know if the other guy is an interviewer or is also taking the interview

[@TopsideXP]

MORE!!!!

[@Gzzzzzz111]

I'm kind of confused here. Were you the interviewer or interviewee?

[@sciencenerd6623]

It’s a mock interview, so they both took turn interviewing each other

[@Gzzzzzz111]

@@sciencenerd6623 Uhhh makes sense now. Thanks for the clarification.

[@laptrinhcungngan]

very good

[@deamonoid85]

create lookup of arr: char->int where k-th element from arr is 2^k. take n elements (length of arr) of str, and move by one (circular buff) each time calculate sum of lookup vals of chars (can just add new one and subtract oldest one) until you get 2^n-1. quite fast

[@GoodGuy374]

both part 1 and part 2 are very similar to questions I had on my recent interview. honestly, i can't understand the question fully as these questions are not even remotely close to codes i have been working at my current company. they are just useless technical questions and unnecessarily hard. :(

[@xymadison]

It is hard to tell who the interviewer is and who the interviewee is.

[@irfansari_]

I also deserve this type of interviewer Aisa interviewer Mai bhi deserve karta hu

[@12jeron09]

😂

[@mp29940]

Aren't they interviewing eachother?

[@SimplyMartin]

They both are interviewees basically. Read the text in green above

[@mlzqq189]

Hey, I am doing a video essay on AI and job displacement for a school project. Is it alright for me to take a screenshot from your video as an example of a software engineer coding interview? Appreciate your videos, by the way!

[@Basicguy1798]

I would just freeze in such interviews. At least for me, I need to be alone while actually writing the code. Yes, maybe discuss/plan the hell out when you are discussing the feature/product but thats it. COme back, code, test, then discuss again later. Not stand over my shoulders

[@rudraprasad3615]

Bro 😭I feel you.. same dude. I just can't code while someone is staring at my code. I can discuss the logic and possible flaws but Coding, nah never. That's why I never do good in Interview. My life kinda sucks ☹️😔

[@sloppyprogrammer4373]

I can just say one thing: you both lack proper work experience. In your next interview take this in mind: it is just a giant filter, I can do this. Just pretend they are not there or think out loudly, so they can hear your train of thoughts. It will surprise you how beneficial this can be to both you and your colleagues (I work in offices, I have giant dislike for working from home because mostly people are less productive, while they claim they are more productive).. If they hear what you are thinking, they can steer you often in a better direction or give you hints when you are stuck. If you are just a mole sitting there and be in your own world, it's not going to be the best productive experience (neither for you or your team). All interviews require you: is to ask enough questions to see if you are a teamplayer or not, most IT/Tech companies don't want people that perform best when they are left alone, they want someone that can communicate and is a teamplayer. Hence why interviews like this will make you freeze, because you lack the experience to behave in the way they want you to behave. Mostly you will work alone anyway, but they setup interviews like this to figure out if you have the competence to ask questions while you are in the process of solving problems. That's really the whole ideology about such interviews. It's just a giant filter, nothing more.

[@Basicguy1798]

@@sloppyprogrammer4373 well I don't know what experience you are talking about but I am happily working for the I&D department of a German mnc in Germany and have been doing pretty good. So yeah, this mode of interview doesn't work for me, maybe works for others. So yeah that's about it.

[@sloppyprogrammer4373]

@@Basicguy1798 Well I prefer small 4-8hr taking projects as an assessment because that gives a better idea of what someone is able to do. But I see why large techcompanies need a filter like this. Sorry, my reaction was a bit dickish now I read through it again.

[@Basicguy1798]

@@sloppyprogrammer4373 all good no worries. I have also worked on assignments/mini-projects that a tech lead or recruiting manager would give with a week's time to do and then the interview would commence on a specified date, majorly focussing on that project. That's logical and I am fine with that. But this thing doesn't work for me. But then, whatever works for a person

[@moogleking]

Good mock interview

[@CodingInterviewTV]

There are apps like Coding Interview Champ that people use to solve these LeetCode interview problems during the coding interview

[@shilpachowdhury8860]

For to practice coding part which site it is to run the code

[@MrHamsterbacke756]

Never analyzed for space complexity in college. Is it useful? It seems like in most cases it does not matter how much ram your program needs.

[@otalgebra4436]

what college did you go to that didnt analyze? lol it always matters especially when your code deals with large datasets.

[@MrHamsterbacke756]

​@@otalgebra4436 Maybe I was sleeping in that lecture :D

[@Gashdal]

it matters a lot for passing interviews at big tech companies to get 200k+ a year jobs. other than that? no it will almost never matter for most engineers. still good to know obviously

[@joyzzyg]

Zerkaa did pretty well in this interview.

[@mossadahmed8150]

I saw part 1 and he was helping u alot is that a thing in an interview ?!

[@dariuszwodarczyk3193]

I had to make a test. Interview version: 50min Real life version: ~10-15min (stackoverflow get_all_substrings ) But yeah thx - cool tip in case of any silly interview "You wanna silly coding or real life solving?";

[@electricshmoo]

My thoughts on the answer: Create an array of potential answers. ForEach the string characters, and concatenate them to each potential answer element and + add 1 new potential answer with just the new character. Check each potential answer by removing the remaining search characters from that answer until the answer's search array is empty. When an answer's search array is empty, it has all the characters - and should not be appended to anymore. When you get to the end of the input string, find your shortest potential answer with no missing search elements (if one exists). Not sure what the time/space dimensions are, less than factorial, more than linear. .... yup yup.

[@panda_dva2261]

I like watching these...i dont really code hardcore or anything, i knew a few things here and there (im a data analyst) but i just like to watch how the interviews are lol

[@mattiaabbondi5858]

Hello, which are needed coding skills for a data analyst?

[@panda_dva2261]

@@mattiaabbondi5858 depends. For government jobs, mainly just enough to make charts and graphs. Its not about the coding, coding is just your tool. You can use whatever your comfortable with mainly. Its all about the analyzing and wiritng reports when it comes down to it

[@foboz971]

Crazy shit that, I am not getting into coding for sure. My own processor will overheat and burn :D

[@sadathalam838]

is this linear solution for number 2 or n2 can someone please tell me? public static String getShortestUniqueSubstring(char[] arr, String str){ int i = 0; int j = 0; String string = ""; while(j

[@blix8567]

Ma la sai fare la classe rettangolo?

[@PreetiSingh-cb6gv]

BTW, who is the interview taker, and who is the giver?

[@surgeon23]

Damn that i drove me crazy.

[@rishi8413]

I try it in python ''' Question:- given an array of unique characters [arr] and a string [str] implement a funtion [getShortestUniqueSubstring] that finds the smallest substrign of [str] containing all the characters in [arr] .Return ''(enpty string) if such a substring doesn't exist. EXAMPLE : input: arr=['x','y,'z'] ,str = 'xyyzyzyx' output: 'zyx' ''' from itertools import permutations def getShortestUniqueSubstring(array,string): if len(array) == 0: # return empty array if array is empty print('array is empty') return '' elif len(array) == 1: # if array have single element return that element if it resent in string else retun empty string print('array have only one element') if array[0] in string : return array[0] else: return '' else : # permutate array : create all possible strings including all elements of array all_possible_array = [''.join(i) for i in permutations(array)] # loop over all_possible_array for i in all_possible_array : # if the str present in string if i in string: return i # can modify to get all str present in the string else : # no return or break condition # if no element is present in the string return '' if __name__ == '__main__' : # test1 array = ['x','y','z'] string = 'xyyzyzyx' # test2 # array1 = ['a','b','z'] # string1 = 'abazba' a= getShortestUniqueSubstring(array,string) print(a)

[@OmarGindia]

here is another variation in python def get_smallest_substring(uniq_chars, string): substring, substrings, used_ar = '', [], [] # get all the substrings dirty_strings = [string[i:] for i, _ in enumerate(string)] for dirty_string in dirty_strings: for char in dirty_string: if char in uniq_chars: substring += char if char not in used_ar: used_ar.append(char) if len(used_ar) == len(uniq_chars): substrings.append(substring) substring, used_ar = '', [] break # get the shortest one shortest_substring = '' for _ss in substrings: if not shortest_substring: shortest_substring = _ss elif len(_ss) < len(shortest_substring): shortest_substring = _ss return shortest_substring if __name__ == '__main__': ARR = [''.join(c) for c in input('uniqu arry (no spaces): ')] STR = input('string to get subset from :') res = get_smallest_substring(ARR, STR) print(res)

[@LotusP2]

I don't think using permutations is a good idea, you must to take into account that len(arr) can be 30. permutation(30, 30) is 2.6e32.

[@Terracraft321]

@@LotusP2 What'd be your solution then?

[@GeezUrCute]

@@Terracraft321 can use sliding window algorithm i guess. basically start with two pointers (start and end) at the beginning of the string, then move the end pointer to the right until we have found all the characters in the array. Once all the characters are found, you try to minimize the window by moving the start pointer to the right and checking if the substring still contains all the characters. Repeat this process until you find the smallest substring that contains all the characters in the array.

[@proctoscopefilms]

The interviewee has a very interesting accent. Cool mix of British and Indian.

[@eurika5433]

Yes yes visual studio is a good

[@haqoncsgo5380]

C# looks like: public static string GetShortestUniqueSubString(char[] arr, string str) { if(str.Length < arr.Length) return ""; var chars = new HashSet(arr); var currentGroup = new Dictionary(arr.Length); for(int groupEndIndex = 0; groupEndIndex < str.Length; groupEndIndex++) { if(groupEndIndex >= arr.Length) { var prevGroupFirstChar = str[groupEndIndex - arr.Length]; if(currentGroup.TryGetValue(prevGroupFirstChar, out int charCount)) { if(charCount == 1) { currentGroup.Remove(prevGroupFirstChar); } else { currentGroup[prevGroupFirstChar] = charCount - 1; } } } char c = str[groupEndIndex]; if(chars.Contains(c)) { if(currentGroup.ContainsKey(c)) { currentGroup[c]++; } else { currentGroup.Add(c, 1); } } if(currentGroup.Count == arr.Length) { var groupStartIndex = groupEndIndex - arr.Length + 1; return str.Substring(groupStartIndex, arr.Length); } } return ""; }

[@shibashisbanerjee266]

Use HashMap and then use 2pointer...left = 0 ; right = 0; if(map.containsKey(s.charAt(r))) if(map.get(s.charAt(i)) == 0) count++; r++;

[@YoungMoneyNL]

Who is the other guy?

[@javadnoruzi908]

Thank you . It was helpfull for me.I have interview with Amazon.

[@moman5382]

what was your major in university?

[@jas6744]

It was a prank

[@maiksousavital1671]

I got lost with his train of thought 😂

[@victormikhaltsevich5148]

Interesting interviews, definetely core for competitive programming I would personally run kmp but rabin Karp is easier to write out,. Part 1 bst was a nice fizz buzz for that data structure. Overall creative solutions. Thank you.

[@JJ-vj3eq]

You can solve this problem with sliding window. No need for Rabin Karp or KMP.

[@user-vn4jw3ch8w]

you are prolly trash at cp if you gonna kill a chicken with a chainsaw , you don't need any complicated pattern match algo here, simple 2 pointer do the justice

[@rallokkcaz]

It's so funny how theses companies ask these questions like you're going to use stuff like this all the time, so people remember these coding problems and their solutions instead of the intuition of why or how you'd actually use these techniques. They then put them on a team writing CRUD REST endpoints lol.

[@lvisyt]

what about this solution.. We perform a binary search from lo = 0 to hi = size of strr array. we take out mid and then see if the substring of mid length yields the answer or not. If it does we can update hi = mid -1 and if it doesnt we can make lo= mid + 1. and then return the length of smallest substring. time complexity will me O(nlogn). maybe??

[@KaranKumar-hw2bq]

checking if the substring is valid or not will take 30 iterations even if done in best efficient manner. So , its O(n*logn*30).

[@aarrynz9721]

Anyone else feel sleepy after reading the first sentence of the question?

[@amzmoney]

how do these algo's translate to everyday coding on the job?

[@93hothead]

zero, real job usually has nothing to do with algorithms

[@trashcanolives3139]

they do it to see how you will respond to a problem you don't know, how you collaborate, and tackle issues so, although not completely related to your job, it tells a lot about you, to the employer

[@tilakmadichettitheappdeveloper]

@@93hothead u have never worked a real job, did you ? (for saying zero with such certainty)

[@93hothead]

@@tilakmadichettitheappdeveloper ZERO

[@strongtheory]

It gives the employer just an idea of how you solve problems. Unless you are a researcher, all these algorithms have already been implemented in most languages and really well at that.

[@abhishekismaster]

-----------------------------------Can be implemented using Stack----------------------------------------------- public static void main(String[] args) { String str = "xyyzyzyx"; String[] arr = str.split(""); Stack st = new Stack(); StringBuilder stb = new StringBuilder(); for (int i = 0; i < arr.length; i++) { if (!st.isEmpty()) { if (st.size() == 3) { break; } if (!st.peek().equals(arr[i])) { if (st.firstElement().equals(arr[i])) { st = null; // free up memory st = new Stack(); } st.add(arr[i]); } else { st = null; // free up memory st = new Stack(); } } else { st.add(arr[i]); } } st.forEach(val -> stb.append(val)); System.out.println(stb.toString()); }

[@markadriantamayo6039]

I used java and came up with this static String getShortestUniqueSubstring(char[] arr, String str) { String output = ""; for (int x = str.length(); x > 0; x--) if (!(output.contains(str.substring(x-1, (x)))) && Arrays.toString(arr).contains(str.substring(x-1, (x)))) output = str.substring(x-1, (x)) + output; return output; }

[@remodiekabouter]

Did he get the job?

[@abduallahmohamedfarouk686]

good job man :D but i want to ask a stupid question .. Is ur peer is an Egyptian ? If yes send me his accounts :D

[@KeepOnCoding]

No idea. It was an anonymous interview.

[@abduallahmohamedfarouk686]

@@KeepOnCoding thanks alot.. Keep on.. We have a big benefits here ❤

[@KeepOnCoding]

@@abduallahmohamedfarouk686 Thanks bro!

[@Rohitsurthi7]

@@KeepOnCoding He is Indian

[@mato77]

@@KeepOnCoding have you asked for that person’s consent to record and publish the interview?

[@TheBullGangGeneral]

Such an easy problem, why does it take 35 mins.

[@lolerdielolol]

had some fun making this one in python array = ["x" , "y" , "z" , "u" ] string = "xyyzyzyux" def get_shortest_unique_substring(array, string): needed = len(array) counter = 0 succes = 0 returner = "" for letter in string: for i in range(0, len(array)): if (i+counter) < len(string): if string[counter + i] in array and string[counter + i] not in returner: succes += 1 returner += string[counter + i] else: succes = 0 break counter += 1 if succes == needed: break else: returner = "" return returner print(get_shortest_unique_substring(array, string))

[@thiagooliveira6147]

I guess your code will not work if the string doesn't exist if you try with this array = ["x" , "y" , "z"] string = "xyyzyzy" I am not a Python developer but made my own version of it. array = ["x" , "y" , "z"] string = "xyyzyzyx" def get_shortest_unique_substring(array, string): arraySize = len(array) # reduce overcalculation for i in range(0, len(string) - arraySize + 1): substring = string[i:i+arraySize] match = [value for value in array if value in list(substring)] if len(match) == arraySize: return substring return '' print(get_shortest_unique_substring(array, string))

[@t_kon]

A in operation for a list is O(n) by itself. Doing it in a loop will cost you O(n^2).

[@thiagooliveira6147]

@@t_kon how we could get rid of that?

[@t_kon]

@@thiagooliveira6147 By changing the algorithm. One viable solution that I can think of is using a sliding window with double pointer.

[@lupuclaudiu4887]

memory leak at line 10!

[@lightyagami2169]

4:22

[@thisisbrian6635]

Not sure how I end up here, but here is my solution of Java version, it uses slide widow and the time complexity is O(N) static String getShortestUniqueSubString(char[] arr, String str) { if (arr == null || arr.length == 0) { return ""; } Set characters = new HashSet(); for (char c : arr) { characters.add(c); } int start = 0; int end = str.length() - 1; int i = start; int j = start; boolean isFound = false; Map charIndex = new HashMap(); while (j < str.length()) { if (charIndex.size() < characters.size() && characters.contains(str.charAt(j))) { charIndex.put(str.charAt(j), j); } if (charIndex.size() == characters.size()) { isFound = true; if (j - i < end - start) { start = i; end = j; } if (i == charIndex.get(str.charAt(i))) { charIndex.remove(str.charAt(i)); } i++; } else { j++; } } return isFound ? str.substring(start, end + 1) : ""; }

[@t_kon]

The idea was good but...what about this test case? char list = ['x', 'y', 'z'] and the given string is ['xyyz']. In this case the size of char and given string could not be the same.

[@felixtube71]

I solved this pretty quick with just a hash table and then running thru the array and appending the character if it existed in the hash table. This one seems pretty straight forward or am I missing something? in Swift import Foundation func smallestSubstring(stringArray: [String], inputString: String) -> String { var substringHash = [String: String]() for char in inputString { substringHash[String(char)] = String(char) } var subString = "" for string in stringArray { if substringHash[string] != nil { subString += string } } return subString } //returns xy for the answer smallestSubstring(stringArray: ["x","y","z"], inputString: "xyxyxyxyxx") //returns "" for answer smallestSubstring(stringArray: ["x","y","z"], inputString: "aaaa") O(n)?

[@superemzone]

It's incorrect. Try the test case they have in the video... your solution is actually just adding the characters of the string array that are present in the inputString. You are just printing overlapping characters. You aren't checking if 1) You found a valid substring (meaning the string is consecutive within the input string) 2) The substring you found is the shortest one within the string. Sometimes its helpful to just write test cases to see if you understand the question. E.g. stringArray: ["x","y","z"], inputString: "xyxyxyxyxx" --> Should return "" because "z" not in input string. stringArray: ["x","y","z"], inputString: "xyyyzyxyxx" --> Should return "zyx" stringArray: ["x","y","z"], inputString: "xyyyzyyyy" --> Should return "xyyyz"

[@vinoth4167]

@@superemzone didn’t understand the last scenario. There is a duplicate y. How that could even be called as substring..

[@t_kon]

@@vinoth4167 a substring is a string within a string....having y or not does not have any relation with it being a substring.

[@56BAK]

Instead, you can change the array to string and then get the sum of the chars' Unicodes => then check if you can find the same result with the given string

[@BapeRuLLZ]

My idea might be too slow and it seems too simple to work, but here we go: 1. Sort 'arr' in an ascending order. 2. If 'arr's size is 'n' than take the first n characters from 'str' as a substring 3. Sort the substring (while storing their original order) and check if they match. 4. If they match then return the original order of the given substring, if not then check if the given substring even contains the first character from 'arr', if it does, then make your new substring from that index and if it doesnt, then you can make your new substring with the index of 'n'. Continue until done. If 'arr' it small, then you might be needing more checks, but the sorting would be faster in return. if 'arr' is big, then vica versa.

[@z-root8955]

i just started learning python and i tried solve it with python i'm a beginner arr = ['a','b','c'] st = 'achaaaacccafgsdbfg' output = "" for i in st: for j in arr: if (i == j): if(j not in output): output += i print(output)

[@Essepti2229]

i coded this in 20 minutes in python within 2 days of starting to learn python im not saying im a genius , im still trash but the problem is worse

[@manoelramon8283]

and then, the hired candidate does not know how to run a simple webserver because lost great time studying to pass on interviews with stupid and unpractical questions.

[@CorporaMedicina]

this is like Netflix movie...

[@venkatasivavarmasirivuri231]

😂😂😂

[@curtkeeling]

Ive been in S/W - IT for over 3 decades. When in the F would this ever be relevant?????

[@KaranKumar-hw2bq]

He gave wrong and non optimal solution and nobody recognizes it . Most software engineers and interviewers are like this only, I suppose ?

[@baynaraoa921]

Well i was able to come up with this, no idea if its faster or slower then the one in the video, but i did see in the comments solutions with a better time complexity then my solution #include int GetAsciiSum(char arr[], int size) { int sum = 0; for (int x = 0; x < size; x++) { sum += (int)arr[x]; } return sum; } std::string getShortestUniqueSubstring(char arr[], std::string input) { int size = strlen(arr); if (input.size() < size) return std::string(); std::string result; int sumOfArray = GetAsciiSum(arr, size); for (int i = 0; i < input.size(); i++) { result = input.substr(i, size); int sumOftmp = GetAsciiSum((char*)result.c_str(), result.size()); if (sumOfArray == sumOftmp) { int uniquecounter = 0; for (int x = 0; x < size; x++) { for (int y = 0; y < result.size(); y++) { if (arr[x] == result.at(y)) { uniquecounter++; break; } } if (uniquecounter == size) return result; } } } return std::string(); } int main() { char arr[] = "xyz"; std::string input = "xyyzyzyx"; std::cout

[@guardrover]

getHash was not necessary

[@ThugLifeModafocah]

I don't even remember what Asymptotically means... Jesus...

[@liontalha7383]

use z algorithm.

[@umarasghar7209]

Hi sir, thanks for sharing that. Did you get hired in Bloomberg? As much I could see most of the code is written by the interviewer. So I am really got confused what is that? Does it really work that way the interviewer will write the code for you.

[@AB-fc8io]

This is not bloomberg interview. The are practicing on preparation site.

[@Dagnabit888]

I'll just stick to delivering pizza

[@ShadOBahn]

for this implementation, you're using canned data structures (map->subsets), i consider that poor spirit of this exercise, and a map is not required for this anyway

[@punnadigunarathna1791]

public static void main(String[] args) { String[] ar = {"x", "y", "z"}; String s = "xyayzxyzyx"; List smallest = new ArrayList(); for (int i = 0; i < s.length(); i++) { String elem = s.substring(i,i+1); if(Arrays.stream(ar).anyMatch(s1 -> s1.equalsIgnoreCase(elem))) { if (smallest.contains(elem)) { smallest = smallest.subList(smallest.indexOf(elem) + 1, smallest.size()); } smallest.add(elem); }else{ smallest.clear(); } if(smallest.size()==ar.length) break; } System.out.println(smallest); }

[@user.1743]

…. okey? …. okey? - no it is not ok.

[@Black_hacker-mj2ro]

What are you doing guys both are looking confused 😂

[@zb3485]

THESE PROGRAMMERS DONT KNOW WHAT THEY'RE DOING!!!!!!!

[@jeanrodrigues6249]

Floppy

[@osamamohammed8275]

char [] arr = {'o','s', 'k','m','a'}; String str = "kaatksoamaao"; int counter = 0; boolean [] finded = new boolean[arr.length] ; // String ss = str.substring(0,3); // System.out.println(ss); for (int w3 = 0 ; w3 < arr.length; w3++) { for (int w = 0; w < arr.length; w++) { if (arr.length + w3

[@osamamohammed8275]

sorry I missed some lines char [] arr = {'o','s', 'k','m','a'}; String str = "kaatksoamaao"; int counter = 0; boolean [] finded = new boolean[arr.length] ; // String ss = str.substring(0,3); // System.out.println(ss); for (int w3 = 0 ; w3 < arr.length; w3++) { for (int w = 0; w < arr.length; w++) { if (arr.length + w3

[@justicearthur8613]

private static String getUniqueSubstrings(char[] arr, String str){ if(str.length() < arr.length)return ""; int count = 0; while (count < str.length() - arr.length + 1){ String sub = str.substring(count, arr.length + count); if(containsAllWords(sub,arr)) return sub; count++; } return ""; } public static boolean containsAllWords(String word, char [] keywords) { for (char k : keywords) if (!word.contains(String.valueOf(k))) return false; return true; } //my solution

[@lewisholmes4594]

I don't belong here...

[@mdadnanullah497]

We have to permute the arr, then check all permuted string with STR. Example : Permuted possibility strings of [x, y, z] are [x,y,z], [x,z,y], [y,z,x],[y,x,z],[z,x,y],[z,y,x]... NOW CONVERT Evey to string then check the string to STR...if found return the string...

[@Kay8B]

@@neevalkumar108 Yeah this was my first thought but I think its O(n2) is there solution faster?

[@t_kon]

Permutation is O(n!). Bad time complexity.

[@JJ-vj3eq]

This doesn't work if the smallest string contains duplicate characters. Input: [x, y, z], xyyz Output: xyyz xyzz is not a permutation of the input array.

[@martincerveny2284]

That's bad way - it will with array size like max 5. But array size can be up to 30. So 30! is very very big number of possibilities. And what's more - we are looking for shortest answer, but it can be still larger than size of array.

[@timk8513]

ugly solution

[@gergokocsis1099]

didn"t have time to test it, but this one should work even if the input contains multiple instances of the same character. fun getSubstring(input: Array, string: String): String { // val input = arrayOf('y', 'z', 'z') // val string = "abcdzzabcdzzzyzz" var currentResult = "" val charDict = mutableMapOf('*' to 0) val charLastIndex = mutableMapOf('*' to 0) input.forEach { if (charDict.containsKey(it)) { charDict.replace(it, (charDict[it]!! + 1)) } else { charDict[it] = 1 } } string.forEach { stringItem -> if (input.any { it == stringItem }) { currentResult += stringItem if (currentResult.count { it == stringItem } == charDict[stringItem]!!) { charLastIndex[stringItem] = currentResult.lastIndex } if (currentResult.count { it == stringItem } > charDict[stringItem]!!) { currentResult = currentResult[charLastIndex[stringItem]!!] + stringItem.toString() } } else { currentResult = "" } if (currentResult.toList().containsAll(input.toList())) return currentResult } return "" }

[@Majinblackex]

i would do it this way def get_shortest_unique_substring(arr, str): aSTr=list(str) curCountr=collection.defaultdict(int) target=collection.Counter(arr) mineLenPossible=len(arr) ans=´´ ´´ shortestLen=float (´inf´) def includesALL(big,smll): return all(big[x]>=smll[x] for x in smll) R, L =0,0 while R

[@Iceman-gm1fu]

easy. add the values to a hashset, return the values to a stringbuilder. stringbuilder.tostring for the answer.

[@blang1]

This one is easy. return "zyx";