TastyFriedPussy:
learn C++ them no go hear, now see as them just dey naked and disgrace theirselves, doing all sorts doing all sorts of rubbish with JS, something that would have been easier with C++

TastyFriedPussy:
your own Na to rush into any coding challenge sharp sharp to go and solve rubbish, I've never seen any coding problem you solved on nairaland that is correct, never!!!!

CyberHustle:
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.

LikeAking:
var list = [9, 12, 3, 5, 14, 10, 10]

var a = ''

var b = ''

var c = ''

let result = []

function Sort(arr,target){
list.filter((info)=> {

if(info < target){
a += info
}
else if(info === target){
b += info
}
else if(info > target){
c += info
}
})
return result.concat(Number(a),Number(b),Number(c))
}
console.log(Sort(list,10))

Najdorf:

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.

LikeAking:



I don't need to work for Amazon Sir, I want to break the job hunting circle in my generation. I don't want my kids to look for jobs when they grow up, cos I know the job mkt will be over saturated by then.

My goal is to master the art of hustling and making money.. So my kids don't have to submit CVs..

I want to build my own Amazon.

airsaylongcome:


Guru mindset

def partition(arr, x):
  i, j = 0, len(arr) - 1
  while i <= j:
    while i < len(arr) and arr[i] <= x:
      i += 1
    while j >= 0 and arr[j] > x:
      j -= 1
    if i > j:
      break
    arr[i], arr[j] = arr[j], arr[i]
    i, j = i + 1, j - 1
  
  i = 0
  while i < j:
    if arr[i] == x:
      while j >= 0 and arr[j] == x:
        j -= 1
      arr[i], arr[j] = arr[j], arr[i]
      j -= 1
    i += 1
  return arr

namikaze:
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:

def partition(arr, x):
  i, j = 0, len(arr) - 1
  while i <= j:
    while i < len(arr) and arr[i] <= x:
      i += 1
    while j >= 0 and arr[j] > x:
      j -= 1
    if i > j:
      break
    arr[i], arr[j] = arr[j], arr[i]
    i, j = i + 1, j - 1
  
  i = 0
  while i < j:
    if arr[i] == x:
      while j >= 0 and arr[j] == x:
        j -= 1
      arr[i], arr[j] = arr[j], arr[i]
      j -= 1
    i += 1
  return arr

CyberHustle:
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.

Playermayweda:
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

TastyFriedPussy:
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

namikaze:

Sorting the array only is a valid solution, only issue is the n log n runtime.

CyberHustle:
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.

namikaze:

def partition(arr, x):
  i, j = 0, len(arr) - 1
  while i <= j:
    while i < len(arr) and arr[i] <= x:
      i += 1
    while j >= 0 and arr[j] > x:
      j -= 1
    if i > j:
      break
    arr[i], arr[j] = arr[j], arr[i]
    i, j = i + 1, j - 1
  
  i = 0
  while i < j:
    if arr[i] == x:
      while j >= 0 and arr[j] == x:
        j -= 1
      arr[i], arr[j] = arr[j], arr[i]
      j -= 1
    i += 1
  return arr

namikaze:
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:

def partition(arr, x):
  i, j = 0, len(arr) - 1
  while i <= j:
    while i < len(arr) and arr[i] <= x:
      i += 1
    while j >= 0 and arr[j] > x:
      j -= 1
    if i > j:
      break
    arr[i], arr[j] = arr[j], arr[i]
    i, j = i + 1, j - 1
  
  i = 0
  while i < j:
    if arr[i] == x:
      while j >= 0 and arr[j] == x:
        j -= 1
      arr[i], arr[j] = arr[j], arr[i]
      j -= 1
    i += 1
  return arr

GREATIGBOMAN:



So many nested loops and exponential increase.


How does this satisfy your question which should be 0(n)

Najdorf:

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

Najdorf:

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

GREATIGBOMAN:


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

GREATIGBOMAN:



So many nested loops and exponential increase.


How does this satisfy your question which should be 0(n)

Luckydonalds:

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).

namikaze:

I actually received the question yesterday around 5pm, it's from daily coding problem.

GREATIGBOMAN:


Yesterday?

U posted the question on 30th


Abi u meant u arrived at the solution yesterday @ 5pm exactly:

def partitionHelper(arr, pivot):
    i, j = 0, len(arr) - 1
    while i < j:
        while i < len(arr) and arr[i] <= pivot:
            i += 1
        while j >= 0 and arr[j] > pivot:
            j -= 1
        if i > j:
            break
        arr[i], arr[j] = arr[j], arr[i]
        i, j = i + 1, j - 1
    return j


def move_till_not_pivot(arr, i, j, pivot):
    while arr[j] == pivot:
        j -= 1
        if j < 0 or j <= i:
            return -1
    arr[i], arr[j] = arr[j], arr[i]
    return j - 1
    

def partition(arr, x):
    i, j = 0, partitionHelper(arr, x)
    while i < j:
        if arr[i] == x:
            j = move_till_not_pivot(arr, i, j, x)
        i += 1
    return arr

CyberHustle:
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.

namikaze:

You did not get my point, "return sorted(arr)" is automatically a valid solution, no need to loop through anything.