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

given x = 10 and lst = [9, 12, 3, 5, 14, 10, 10],
sorting lst would yield: [3, 5, 9, 10, 10, 12, 14].
This satisfies the constraints, no need for further processing.

namikaze:
This problem was asked by Amazon.

Given a pivot x, and a list lst, partition the list into three parts.
* The first part contains all elements in lst that are less than x
* The second part contains all elements in lst that are equal to x
* The third part contains all elements in lst that are larger than x
Ordering within a part can be arbitrary.
For example, given x = 10 and lst = [9, 12, 3, 5, 14, 10, 10],
one partition may
be [9, 3, 5, 10, 10, 12, 14].

Can you solve it in strictly O(n) time and O(1) space complexity?
I'd like to see what you come up with.

namikaze:

given x = 10 and lst = [9, 12, 3, 5, 14, 10, 10],
sorting lst would yield: [3, 5, 9, 10, 10, 12, 14].
This satisfies the constraints, no need for further processing.

Please compare the challenge and your solution. Where are the three parts of the original list? That's is less than X, X, and greater than X?

CyberHustle:



Please compare the challenge and your solution. Where are the three parts of the original list? That's is less than X, X, and greater than X?

The three parts should be in the original list, i.e lower than x the first section, equal to x next and greater than x last.

namikaze:

The three parts should be in the original list, i.e lower than x the first section, equal to x next and greater than x last.

you mean the sorted version of the original list?
It makes no sense to me because I don't know where to start looking at I need just values greater than X.
If really want to obtain values greater than X alone, I need to know where the first value greater than X is then go until I reach the end.
That can be achieves by either looping through one extra time or noting those indexes during sorting(within sorting algorithm).

namikaze:

The three parts should be in the original list, i.e lower than x the first section, equal to x next and greater than x last.

If sorting alone is a valid solution then your question is senseless and pointless. Sounds a lot like you looking for clout.

If I need the values less than, equals to, and greater than X, I just loop through and pick the values if it matches my interest. To have three different list within a list. You must know where the less than X values end and note that index in a variable(x_starts for example) then know where greater than X starts(x_ends) in another variable. Any value between is X.

Using extra space would have made it easy. Cause then you can use 3 for loops but the space complexity would be o(n). It would look something like this

CyberHustle:
If sorting alone is a valid solution then your question is senseless and pointless. Sounds a lot like you looking for clout.

If I need the values less than, equals to, and greater than X, I just loop through and pick the values if it matches my interest. To have three different list within a list. You must know where the less than X values end and note that index in a variable(x_starts for example) then know where greater than X starts(x_ends) in another variable. Any value between is X.

Calm down, you're the only saying the question is pointless, it justs means you probably don't understand it yet.
Think of it as quicksort's partitioning algorithm, every item smaller than or equal to the pivot goes left of the pivot, greater than or equal goes to right.
for example;
piv = 5, arr = [2,5,1,4,7,3,6]
some valid solutions include:
1. [2,4,3,1,5,7,6].
2. [1,2,3,4,5,6,7].
note that 2 is just the array sorted.

The same goes for the question but with the new constraint that all items equal to the pivot stays at the middle, together with the pivot.
for example;
piv = 5, arr = [5,2,5,1,4,5,7,3,6]
some valid solutions include:
1. [2,4,3,1,5,5,5,7,6].
2. [1,2,3,4,5,5,5,6,7].
note that 2 is also just the array sorted.
sigh.

Deicide:
Using extra space would have made it easy. Cause then you can use 3 for loops but the space complexity would be o(n). It would look something like this

This is correct, but space to beat is O(1), which is actually the tricky part.

CyberHustle:
If sorting alone is a valid solution then your question is senseless and pointless. Sounds a lot like you looking for clout.

If I need the values less than, equals to, and greater than X, I just loop through and pick the values if it matches my interest. To have three different list within a list. You must know where the less than X values end and note that index in a variable(x_starts for example) then know where greater than X starts(x_ends) in another variable. Any value between is X.

We have explained this thing multiple times in different ways...

I'm even tired sef

namikaze:

This is correct, but space to beat is O(1), which is actually the tricky part.

Space is cheap

Najdorf:
We have explained this thing multiple times in different ways...
I'm even tired sef

I dey tell you, he really should look at it from a different perspective.

Deicide:
Space is cheap

Not until you have 5 billion records to process.

namikaze:

Calm down, you're the only saying the question is pointless, it justs means you probably don't understand it yet.
Think of it as quicksort's partitioning algorithm, every item smaller than or equal to the pivot goes left of the pivot, greater than or equal goes to right.
for example;
piv = 5, arr = [2,5,1,4,7,3,6]
some valid solutions include:
1. [2,4,3,1,5,7,6].
2. [1,2,3,4,5,6,7].
note that 2 is just the array sorted.

The same goes for the question but with the new constraint that all items equal to the pivot stays at the middle, together with the pivot.
for example;
piv = 5, arr = [5,2,5,1,4,5,7,3,6]
some valid solutions include:
1. [2,4,3,1,5,5,5,7,6].
2. [1,2,3,4,5,5,5,6,7].
note that 2 is also just the array sorted.
sigh.

If I reply you the way I ought to, this thread will derail.
Your own question say we need three new lists. But your solution shows only one list and therefore is incomplete. What you have there is a human readable solution and not a computer readable one.

Lastly, any moniker accepting your clearly incomplete solution is your alternate.

Najdorf:

We have explained this thing multiple times in different ways...

I'm even tired sef

Instead of playing games, show me the three different lists in your solution.
That rubbish you are calling a solution with three list is one sorted list that leaves no room for where list one ends and where list two starts.

You should be practicing and not wasting peoples time.

.

CyberHustle:
If I reply you the way I ought to, this thread will derail.
Your own question say we need three new lists. But your solution shows only one list and therefore is incomplete. What you have there is a human readable solution and not a computer readable one.

Lastly, any moniker accepting your clearly incomplete solution is your alternate.

Three parts! not three lists, you just don't understand the problem, admit it.

namikaze:
This problem was asked by Amazon.

Given a pivot x, and a list lst, partition the list into three parts.
* The first part contains all elements in lst that are less than x
* The second part contains all elements in lst that are equal to x
* The third part contains all elements in lst that are larger than x
Ordering within a part can be arbitrary.
For example, given x = 10 and lst = [9, 12, 3, 5, 14, 10, 10],
one partition may
be [9, 3, 5, 10, 10, 12, 14].

Can you solve it in strictly O(n) time and O(1) space complexity?
I'd like to see what you come up with.

I cannot find any use of this coding test on Amazon shopping site. Their site only has these types of sorting: Price: Low to high, Price High to low, Avg. Customer review and Newest arrivals. None of these requires this type of coding test. All that is needed for these are to use the sorting provided by the programming language to achieve these basic kinds of sorting.

This kind of coding test is only useful when it comes to games programming as you'll have to store data in arrays and manually check and retrieve them using the quickest logic possible.

It is not possible to accomplish this coding test in O(1) as you cannot accomplish this task without a nested loop.

O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.

bool IsFirstElementNull(IList<string> elements)
{
return elements[0] == null; //Source: https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
}

CodingSoft:


I cannot find any use of this coding test on Amazon shopping site. Their site only has these types of sorting: Price: Low to high, Price High to low, Avg. Customer review and Newest arrivals. None of these requires this type of coding test. All that is needed for these are to use the sorting provided by the programming language to achieve these basic kinds of sorting.

This kind of coding test is only useful when it comes to games programming as you'll have to store data in arrays and manually check and retrieve them using the quickest logic possible.

It is not possible to accomplish this coding test in O(1) as you cannot accomplish this task without a nested loop.

O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.

bool IsFirstElementNull(IList<string> elements)
{
return elements[0] == null; //Source: https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
}

1. loop nesting does not affect space complexity by it self.
2. Time and space are measured differently, there is no "time or space", there's only "time and space"
3. O(1) for time differs from the O(1) for space.
4. The problem is solvable in O(n) time, not O(1).

Deicide:
Using extra space would have made it easy. Cause then you can use 3 for loops but the space complexity would be o(n). It would look something like this

Recommend a Linux distro….I’ve used Ubuntu 20.04 or so and I didn’t like it…

Kvngfrosh:
Recommend a Linux distro….I’ve used Ubuntu 20.04 or so and I didn’t like it…

Try Elementary Os or manjaro or if you wanna go light , Linux mint

namikaze:

1. loop nesting does not affect space complexity by it self.
2. Time and space are measured differently, there is no "time or space", there's only "time and space"
3. O(1) for time differs from the O(1) for space.
4. The problem is solvable in O(n) time, not O(1).

I am still waiting for the three parts you talked about. The is a useless question if sorting will automatically break down a list into three parts.

CyberHustle:

I am still waiting for the three parts you talked about. The is a useless question if sorting will automatically break down a list into three parts.

sigh just forget it.

namikaze:

sigh just forget it.

Abeg no bring this kind question again

Let us just stick to the WordPress wey everyone go sabi

Najdorf:
Abeg no bring this kind question again
Let us just stick to the WordPress wey everyone go sabi

lol, I hear you.

Deicide:
Try Elementary Os or manjaro or if you wanna go light , Linux mint

Nahhh I don’t think I want elementary os, it looks like Mac OS. Maybe I’ll try Manjaro… thanks

namikaze:

1. loop nesting does not affect space complexity by it self.
2. Time and space are measured differently, there is no "time or space", there's only "time and space"
3. O(1) for time differs from the O(1) for space.
4. The problem is solvable in O(n) time, not O(1).

Found out more about O(1) space complexity
What is O(1) space complexity?
"To answer your question, if you have a traversal algorithm for traversing the list which allocate a single pointer to do so, the traversal algorithms is considered to be of O(1) space complexity. Additionally, let's say that traversal algorithm needs not 1 but 1000 pointers, the space complexity is still considered to be O(1).

However, if let's say for some reason the algorithm needs to allocate 'N' pointers when traversing a list of size N, i.e., it needs to allocate 3 pointers for traversing a list of 3 elements, 10 pointers for a list of 10 elements, 1000 pointers for a list of 1000 elements and so on, then the algorithm is considered to have a space complexity of O(N). This is true even when 'N' is very small, eg., N=1.

To summarise the two examples above, O(1) denotes constant space use: the algorithm allocates the same number of pointers irrespective to the list size. In contrast, O(N) denotes linear space use: the algorithm space use grows together with respect to the input size."

Source: https://stackoverflow.com/questions/43260889/what-is-o1-space-complexity#:~:text=To%20summarise%20the%20two%20examples,respect%20to%20the%20input%20size.