Welcome, Guest: Register On Nairaland / LOGIN! / Trending / Recent / NewStats: 3,158,214 members, 7,836,036 topics. Date: Tuesday, 21 May 2024 at 07:32 PM |
Nairaland Forum / Science/Technology / Programming / Solve This Amazon Interview Question (2739 Views)
Can You Solve This Google Coding Interview Problem? (pics) / Chatgbt Is A Scam. It Cant Solve This Simple Thing I Ask Him / A "Senior" Software Developer Could Not Solve This Coding Challenge, Can You? (2) (3) (4)
Re: Solve This Amazon Interview Question by Nobody: 8:59am On Oct 31, 2022 |
TastyFriedPussy: Help solve it with C++ |
Re: Solve This Amazon Interview Question by Nobody: 10:09am On Oct 31, 2022 |
TastyFriedPussy:i swear you have problem |
Re: Solve This Amazon Interview Question by CyberHustle: 11:40am On Oct 31, 2022 |
Amazon has a lot of digital record keeping to do and their interview will generally relvolve around task that deals with either structuring records, creating them, reading them, updating them, and analyzing them to make sense of the records or data. This questions sound similar to when a potential buyer wants to sort search result by specific criteria like price. X is the price the user chooses and the lower or higher values are the desired/undesired values. Depending on your chosen language, sort the main list. Push all values below X into list_one, all values equals to X to list_two, and all values above into list_three. As simple as that. 2 Likes |
Re: Solve This Amazon Interview Question by LikeAking: 11:52am On Oct 31, 2022 |
Ignore dis solution.. |
Re: Solve This Amazon Interview Question by Najdorf: 12:13pm On Oct 31, 2022 |
CyberHustle:Very concise solution sir Unfortunately it doesn't satisfy the constraint of space complexity. To make it understandable for any potential future readers, the space complexity for this problem must be constant->O(1). That means you can't create any auxiliary data structure that isn't of constant size. In the case of your solution–as well as the other similar solutions posted earlier, you are creating new lists of length n, making the space complexity O(n) which doesn't meet the demands of the question. 3 Likes |
Re: Solve This Amazon Interview Question by Nobody: 12:25pm On Oct 31, 2022 |
LikeAking: . |
Re: Solve This Amazon Interview Question by CyberHustle: 8:43pm On Oct 31, 2022 |
Najdorf:If I understand the idea of the constrain you talking about, I believe it is about not creating new list with unknown length right? I am not a computer scientist nor engineer nor software engineer so I need to understand that constraint. |
Re: Solve This Amazon Interview Question by airsaylongcome: 9:24pm On Oct 31, 2022 |
LikeAking: Guru mindset |
Re: Solve This Amazon Interview Question by LikeAking: 9:32pm On Oct 31, 2022 |
airsaylongcome: Baba, every thing na prayer point.. Still hoping for the best.. U b guru... I salute! I am trying to b like u sm days.. |
Re: Solve This Amazon Interview Question by namikaze: 9:02am On Nov 01, 2022 |
It's been a while, so this my solution. The approach is to simply partition the array using quicksort's partitioning algorithm, but with the new constraint: • All elements to the left of the pivot must be less than or equal to the pivot. • All elements to the right must be greater. for example: arr = [3,2,5,7,4,5,1,10] x = 5 result would be like => [2,3,5,4,1,5,7,10]. we know the index of last pivot element in the arr, we do 2 pointer swaps from index 0 to index of the pivot, in code:
2 Likes 1 Share |
Re: Solve This Amazon Interview Question by TastyFriedPussy: 10:28am On Nov 01, 2022 |
namikaze:too you this long only to copy and paste the answer? most of you claiming programmers in the section are nothing but a bunch of jokes |
Re: Solve This Amazon Interview Question by Playermayweda(m): 10:53am On Nov 01, 2022 |
Make una no beat me oo, but what if you create three different array from the initial array containing the different values mentioned in the problem. You can filter each array based on the requirements of the problem and merge the three arrays. Is it a must it should be constant space? I also don't think my solution is O(n2) rather O(n). Na question I ask make una no beat me oo |
Re: Solve This Amazon Interview Question by CyberHustle: 11:50am On Nov 01, 2022 |
Modifying my first solution based on how I understand the constraint. Sort the main array, loop through it until you get to where values equalling X starts. Store that index minus 1 as an integer of where values below X stops. Continue looping until a value above X is encountered and store the index of that as another integer value. That leaves us with one new sorted array with size n and two int values to identify values less than and greater than X. Cc: najdorf. 1 Like |
Re: Solve This Amazon Interview Question by namikaze: 12:06pm On Nov 01, 2022 |
CyberHustle:Sorting the array only is a valid solution, only issue is the n log n runtime. |
Re: Solve This Amazon Interview Question by namikaze: 12:07pm On Nov 01, 2022 |
Playermayweda:It's O(n), but this approach has been discussed many times before. |
Re: Solve This Amazon Interview Question by namikaze: 12:08pm On Nov 01, 2022 |
TastyFriedPussy:You cannot troll me boss, just don't try. |
Re: Solve This Amazon Interview Question by CyberHustle: 12:27pm On Nov 01, 2022 |
namikaze:loop thru d array, and note the index where X is greater than the value(s) stops and the index where X is less than the value(s) start. |
Re: Solve This Amazon Interview Question by LikeAking: 1:42pm On Nov 01, 2022 |
Don't be scared of the trolls, they are just guys suffering from inferiority complex.. Feel free to drop ya solution.. |
Re: Solve This Amazon Interview Question by LikeAking: 1:43pm On Nov 01, 2022 |
CyberHustle: |
Re: Solve This Amazon Interview Question by Luckydonalds(m): 2:00pm On Nov 01, 2022 |
namikaze:While your solution may get the job done ( I didn't test it, but I looked through it to understand it well enough), I hate to be the one to break it you that it doesn't satisfy the time constraint. It has a time complexity of O(n**2) but your question requested for O(n). |
Re: Solve This Amazon Interview Question by Nobody: 2:39pm On Nov 01, 2022 |
namikaze: So many nested loops and exponential increase. How does this satisfy your question which should be 0(n) |
Re: Solve This Amazon Interview Question by Najdorf: 3:33pm On Nov 01, 2022 |
GREATIGBOMAN:His code is actually O(n). Nested loops ≠ exponential increase always. But OP your code fails to some test cases e.g [9,4,10,12,10,23,5,10,90,5] with pivot of 10 |
Re: Solve This Amazon Interview Question by Nobody: 4:15pm On Nov 01, 2022 |
Najdorf: Yea... just saw where he used breaks and it seems no value increase more than one. The way he posted it it seems he's spent more than a week with the question self |
Re: Solve This Amazon Interview Question by namikaze: 4:44pm On Nov 01, 2022 |
Najdorf:Yeah just noticed, it's subtle, bug 1: apparently we should only swap while i < j in the second part. bug 2: we should stop when i and j becomes equal in the first part. |
Re: Solve This Amazon Interview Question by namikaze: 4:48pm On Nov 01, 2022 |
GREATIGBOMAN:I actually received the question yesterday around 5pm, it's from daily coding problem. |
Re: Solve This Amazon Interview Question by namikaze: 4:53pm On Nov 01, 2022 |
GREATIGBOMAN:It's actually O(n), the first part is just the normal quicksort's partitioning algorithm, the second part builds on that. |
Re: Solve This Amazon Interview Question by namikaze: 4:58pm On Nov 01, 2022 |
Luckydonalds:It's O(n), it's just two pointers all around. |
Re: Solve This Amazon Interview Question by Nobody: 5:25pm On Nov 01, 2022 |
namikaze: Yesterday? U posted the question on 30th Abi u meant u arrived at the solution yesterday @ 5pm exactly: |
Re: Solve This Amazon Interview Question by namikaze: 5:47pm On Nov 01, 2022 |
GREATIGBOMAN:Oh it's 30, I posted @ 7: 19pm, 2hrs+ is a reasonable time frame to solve these types of questions. |
Re: Solve This Amazon Interview Question by namikaze: 6:29pm On Nov 01, 2022 |
Modified and refactored solution, hard to test since there are multiple valid solutions for a testcase. def partitionHelper(arr, pivot): |
Re: Solve This Amazon Interview Question by namikaze: 6:37pm On Nov 01, 2022 |
CyberHustle:You did not get my point, "return sorted(arr)" is automatically a valid solution, no need to loop through anything. |
Re: Solve This Amazon Interview Question by CyberHustle: 7:44pm On Nov 01, 2022 |
namikaze:How will sorting alone help identify array values lesser, equal to and greater than X? My solution involves sorting it and then looping thru to identify where values lesser than, equal to and greater then X either end or start. If you are implementing the sort algorithm, you could combine both processes otherwise depend on language shipped sorting function then loop thru to know indexes of interests. |
Help On Android Studio For 1gb Ram Pc Installation Dhtml And Other Should Enter / SIWES For Computer Science Students / Coding Advice
(Go Up)
Sections: politics (1) business autos (1) jobs (1) career education (1) romance computers phones travel sports fashion health religion celebs tv-movies music-radio literature webmasters programming techmarket Links: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) Nairaland - Copyright © 2005 - 2024 Oluwaseun Osewa. All rights reserved. See How To Advertise. 66 |