Niklaus Wirth, a Swiss computer scientist, wrote a book in 1976 titled:
Algorithms + Data Structures = Programs
40+ years later, that equation ...
For further actions, you may consider blocking this person and/or reporting abuse
Oh man, I would never want to work in a company that believes my understanding of the internals of arrays, hash tables, trees, graphs, etc. matter. They clearly have the focus on some nonsense that helps not at all in performing the actual job of a programmer, which is implementing good enough things in a timely manner.
I would literally walk out on the interview if they started asking me nonsense like this.
The worst job I ever took I should've passed on immediately when they seriously asked me to write SQL on a piece of paper. I should've walked out at that very moment. I didn't have the sense to do that then, but now I do.
It's like the post from a few days ago about how bubblesort works - literally basically nobody needs to ever know that. What the average programmer needs to know is how to use the
sort()-function of the language in question and that's it, whatever algorithm is behind it matters so incredibly rarely that you can basically say it's never.It really depends where you’re working. Companies like FB, Google, and Amazon need to test programmers on data structures because certain structures work better in certain situations, and when their software engineers know which tools to use to optimize a process to run in 5μs instead of 10μs... well, let’s just say for a company running tens or hundreds of thousands of servers, every microsecond saved means less servers the company needs running. And less servers = more $$$.
But for most startups or mid sized companies it’s way more important that developers know how to get shit up and running, and less important the actual code they write to get there.
The problem is a lot of smaller tech companies look up to companies like Google and try to copy they’re interview process because hey, it’s Google. And these companies never consider that just maybe an app with billions of users has a slightly different set of requirements than their app with 500 users.
No heaps? I'm sure they deserve some love too.
Yes, I should add them to the list as well.
There is list of offers and it's criteria, which looks like this.
Each offer will have list of product ids, if a cart has all these products, then the corresponding discount would be applicable.
Now for a given cart, multiple offers may be applicable. In that case, offer which returns the max discount should be returned.
Example
Lets say the Cart contains these products [1,2,3,5,7,6,9]
List of offers are:
Offer 1- Product I'd [1,3,8] 10%
Offer 2 product ids [1,2,5,9] 15%
Offer 3 product ids [2,5,6] 25%
Offer 4 product ids [1,2,3,4] 30%
Output : 25%
For the cart, offer1 is not applicable as product I'd 8 is not there in the cart.
Offer2 is applicable as product I'd 1,25,9 all are available in the cart.
Offer3 is also applicable
Offer 4 is not applicable as product I'd 4 is not present in the cart.
Thus output would max discount from offer 2 and offer 3.
Which is 25%
Question is how should we store these offers so that we should get the offer amount with minimum time.
Assume this is for a big retail company, where the request comes in large number.
Can anyone please let me know the right data structures for this?
Hi,
You can use two different data structure to maintain the time complexity.
Hash Map
Hash-Map to put all the products for efficient lookup
Go through all the offers and check whether their elements exist in Hash-map.
If yes , put them in heap.
Max-Heap will contain discounts in descending order but before inserting into heap you need to check that the list of order with id's belongs to product like Product I'd [1,3,8] doesn't belong to original list of these : This is step 1
products [1,2,3,5,7,6,9]
After Insertion you can get Max discount in o(1) in max-heap.
Awesome! Thank you.
Thanks a lot! ❤️
thanks) remember that book (studied at the institute ))
next step - methods of sorting?
Nice! Thanks a lot for this.
Awesome list! Well laid out and super useful. Thanks so much for your time in writing this!
What a great great post! Your interview questions have been added (and answered) on fullstack.cafe portal and back-linked!
Very well explained sir.
Very helpful.