Hey everyone! Welcome back to Code Review, a series of interview challenges released weekly that are completely free for the community. This week w...
For further actions, you may consider blocking this person and/or reporting abuse
because I'd argue that letting your language work for you, and therefore optimizing developer time, is better than optimizing execution time when not strictly necessary.
To follow up: I made three versions of this code. The first version is as above, the second version has the naive approach to finding the intersection:
and a third approach uses a map for lookup:
Performing some timed tests shows that using the built-in function consistently takes about two to three times as long as the self-built map-based function, growing at roughly
O(n)
using a random array of size 1000 and 10000. Only in exceptional cases would I not use the built-in function.The naive approach, on the other hand, grows with
O(n²)
and takes significantly longer at larger array sizes. However, with 26ms with an array size of 1000, it depends on the use case whether I would start optimizing this (if this isn't easily replaced with a built-in function).Nice work!! Always always interesting to test out a language's built in methods and know whats what when it comes to time complexity.
When the language solves the problem for you... touché
Hi! I wrote a solution that should be able to handle n-number of lines.
Also it does not care if there are duplicate numbers or they are out of order.
It just uses .map and .reduce.. probably it still could be optimized by using Set.
simplified the solution by using Sets and corrected the answer to correspond the assignment
couldn't help myself.. improved the performance by sorting sets and checking result set. Changed the api from array input to n-amount of params. Also input is filtered from not a number
Decided to have a one more improvement for performance (when one Set has size = 0, so no need to reduce other Sets. Also result from reduce is directly an array of numbers).
Also my apologies to @elisabethgross as I noticed the tag #codenewbie in the challenge and my answer isn't really for newbies.
Rust solution - works for any number of strings:
Is there any difference between
and
?
None that I'm aware of. I prefer
"".to_owned()
overString::from("")
or"".to_string()
to avoid the confusion of "why are you converting a string to a string?" that I've seen in some newbie Rust threads.this is my solution, Im no pretty good at JS but I want to be a master on it :)
ok, i have no idea to make my code look like editor
Nice job! And try surrounding your code with triple backticks to format the code ;)
thanks I made it :D i'll wait for more
also you can put javascript directly after your backticks to make it have syntax highlighting (maybe its js, dont know, also works for other languages)
Pro tip!!
This is my approach.
Nice custom parseArray function!! And I like that use of Object.entries().
Yes, I've looked up how
Set
works and you're right. Thanks for clarifying.Another cool solution (but not as readable as yours) however is this "destructive" one on SO.
I used for loop so that improve the performance
fwiw, another js option:
jsfiddle.net/4usxLhyo/1/
sorry, first post, not sure how to get the js syntax highlighting...
Edit: thanks @elisabethgross for the syntax highlighting help!
Nice! If you use the triple backticks, you can write
javascript
next to the top triple backticks. Check out this helpful markdown cheat sheet!Not a JS guy, so I decided to do it in Python.
As an interviewer, for these kind of question I'm not a fan of leveraging too much of the language built-ins (such as sets), as it masks algorithmic thinking, which I believe is an important part of the interview.
My solution uses a dictionary to count the number of occurrences for every item.
I agree about not leveraging too many language built-ins, or, making sure to talk about the time complexity of those built-ins!
In JavaScript.
Python solution, not in a nice format, and assuming the input are two integer arrays:
So idea:
You iterate over the smallest array, at each step, you are in one of 3 situations
arr1[i] == arra2[j] // you increment i and j because of the invariant, that says the arrays are sorted, so if you found a match you can safely increment.
arr1[i] < arr2[j] // since at index i we have the smallest element, we increment that one because being sorter we ca safely increment until we hit what is at index j or greater
arr1[i] < arr2[j] // same as above only for j
A simple and straightforward O(m+n) solution.
EDIT: I just checked the next article and it has the same solution listed. Sorry I did not check that before posting this here.
But
[...s1].filter(x => s2.has(x))
is still O(n²), isn't it?I'm pretty sure there is a O(s1) + O(s2) = O(n) solution.
Good answer but you lost the ordering when using sets.
coderbyte.com/results/philipgg:Fin...
I submitted a 0(2n-a) where a is the number of repetitive elements.
The idea is to use that the arrays are sorted so always increment from where we are.
if the elements are matching, save and then increment both counters.
Else increment the count of the array which has the lower number, to try to find the bigger one. (this is auto-switching between the two.)
Nice! Was waiting for someone to come up with this one!
My solution was the same.
When it comes to challenges I prefer algorithms that can be written in pseudocode and don't use many special (or language-specific) data types.
A rust solution, im quite new to rust, so this is probably quite ugly
This is my O(n) solution. We don't need to parse any of the strings to an integer.
Would be the easiest to implement (I'm on my phone so I can't check it, also, python)
// I believe key here is that both arrays are sorted
function FindIntersection (strArr) {
const inBothStrings = []
const arr1 = strArr[0].split(', ')
const arr2 = strArr[1].split(', ')
let i=0,j=0;
while (i<arr1.length&&j<arr2.length){
//casting to numbers
let a = arr1[i]|0;
let b = arr2[j]|0;
if(a==b){
inBothStrings.push(a)
i++;
j++;
}
else if(a>b){
j++;
}
else if(b>a){
i++;
}
}
return inBothStrings.join(',')
}
Bingo! Nice work!
Thank you!
Nice solution! Love your use of Sets. Very concise and clear.
I dont understand why anyone would ask you this in an interview ? A massive red flag for me.
Clarification question: can the lists have duplicate values?
Good question! Nope, the lists will not have duplicates in themselves.
Kotlin (any number of strings): pl.kotl.in/Lgfcz5KnV?theme=darcula