Assignment 1 - Binary Search and Linked Lists Practice

:zap: In this assignment, you’ll apply and practice the following concepts covered during the first lesson:

  • Understand and solve a problem systematically
  • Implement linear search and analyze it
  • Optimize the solution using binary search
  • Ask questions and help others on the forum

:ledger: Assignment Notebook

Assignment 1 - Binary Search Practice

Use the starter notebook(s) to get started with the assignment. Read the problem statement, follow the instructions, add your solutions, and make a submission.

:handshake: Share your work

Share your work on the Share Your Work Category on the respective monthly threads.

Assignment1: rotated sorted array----> Can this array have duplicates?

test = {
    'input': {
        'nums': [19, 25, 29, 3, 5, 6, 7, 9, 11, 14]
    },
    'output': 4
}

I think, above output should be 3.

and

nums0 = test['input']['nums']
output0 = test['input']['nums']
result0 = count_rotations(nums0)

result0, result0 == output0

And here, in 2nd line it should be output0 = test['output'].

8 Likes

I think in problem statement, it is given to assume all elements in the list are unique. (If that you are asking)

now I got it. Thanks

1 Like

Yes, you are correct. I found that mistake also.

1 Like

We can assume that if the list is empty the it automatically means that the output should be 0 right?

There is a duplicates case in the bonus question.

1 Like

if position > 0 and ??? # How to perform the check?

what is the other condition even? I am kinda confused here.

2 Likes

You have got to add a way to create a conditional statement that verifies what is commented above that line:

# Success criteria: check whether the number at the current position is smaller than the one before it

So:
if position > 0 and (number at current position < number at previous position)

3 Likes


What does this error mean?

Your function Should be
count_rotations_linear(nums)
because you are passing the array as nums but not handling it properly in the array.

Can somebody please reply to this. Thanks in advance.

We have 2 test cases,

  1. A list that wasn’t rotated at all (0 times rotated).
  2. A list that was rotated n times, where n is the size of the list (n times rotated).

In both cases, the resulted/rotated list will be a sorted one. In that case, the expected output should be 0 or N. Isn’t it ??

3 Likes

Can someone explain why this error is occurring? It did not occur for the single test case evaluative.

Nevermind! It turns out the 2nd input ‘test’ should be ‘tests’ in evaluate_test_cases

2 Likes

Since, there should be minimum rotation to obtain the sorted list (Given in question). So, the final output will be 0.

1 Like

I am assuming 0. Let’s see what happens.

I used 0 for empty lists and it works.
But I guess using -1 makes sense because there is no possible rotation.

I think we should add the parameters