Subscribe Us

Showing posts with label python. Show all posts
Showing posts with label python. Show all posts

Cyclic Sort (First Level)

 

Cyclic Sort (easy)

Problem Statement 

We are given an array containing ‘n’ objects. Each object, when created, was assigned a unique number from 1 to ‘n’ based on their creation sequence. This means that the object with sequence number ‘3’ was created just before the object with sequence number ‘4’.

Write a function to sort the objects in-place on their creation sequence number in O(n)O(n) and without any extra space. For simplicity, let’s assume we are passed an integer array containing only the sequence numbers, though each number is actually an object.

Example 1:

Input: [3, 1, 5, 4, 2]
Output: [1, 2, 3, 4, 5]

Example 2:

Input: [2, 6, 4, 3, 1, 5]
Output: [1, 2, 3, 4, 5, 6]

Example 3:

Input: [1, 5, 6, 4, 3, 2]
Output: [1, 2, 3, 4, 5, 6]

Solution 

As we know, the input array contains numbers in the range of 1 to ‘n’. We can use this fact to devise an efficient way to sort the numbers. Since all numbers are unique, we can try placing each number at its correct place, i.e., placing ‘1’ at index ‘0’, placing ‘2’ at index ‘1’, and so on.

To place a number (or an object in general) at its correct index, we first need to find that number. If we first find a number and then place it at its correct place, it will take us O(N^2)O(N2), which is not acceptable.

Instead, what if we iterate the array one number at a time, and if the current number we are iterating is not at the correct index, we swap it with the number at its correct index. This way we will go through all numbers and place them in their correct indices, hence, sorting the whole array.

Let’s see this visually with the above-mentioned Example





Here is the code in Following Language
a) Python (Problem 4)
b) Java  (Problem 4)
c) C++ (Problem 3)
d) Javascript (Problem 2) 

Time complexity #

The time complexity of the above algorithm is O(n). Although we are not incrementing the index i when swapping the numbers, this will result in more than ‘n’ iterations of the loop, but in the worst-case scenario, the while loop will swap a total of ‘n-1’ numbers and once a number is at its correct index, we will move on to the next number by incrementing i. So overall, our algorithm will take O(n) + O(n-1) which is asymptotically equivalent to O(n).

Space complexity #

The algorithm runs in constant space O(1).




Share:

Python List

 



What is List : 

In python, list is a collection of any data type which is mutable, i.e means we can change the value of list  

list Creation

we can create list in two ways

a) Empty List : L=[]

b) With some values : L1=[1,2,3,4,5,6]

After creation of empty list we can add some number with the help of append and extend function. 

for accessing list element we can use the index of the element. i.e if we want to access 3 from above mentioned list(L1), then we have to write, x= L1[2],  where 2 is the index of 3.

if you want to access all the element, then you can use range function as follows:

for i in range (0,len(L1)):

    print(L1[i])

Here, i represents the index of individual element. 

Lists are pretty useful, but only if you can get at the things inside them. You can already go through the elements of a list in order, but what if you want, say, the fifth element? You need to know how to access the elements of a list. Here’s how you would access the first element of a list:

animals = ['bear', 'tiger', 'penguin', 'zebra']

bear = animals[0]


How do you make a two- dimensional (2D) list?

That’s a list in a list like this: [[1,2,3],[4,5,6]].

Aren’t lists and arrays the same thing?

It depends on the language and the implementation. In classic terms, lists are very different from arrays because of how they’re implemented. In Ruby, lists are referred to as arrays. In Python, they’re referred to as lists. Just call these lists for now, since that’s what Python calls them. 

How come a for- loop can use variables that aren’t defined yet?

It defines that variable, initializing it to the current element of the loop iteration, each time through. 

Why does for i in range(1, 3): only loop two times instead of three times?

The range() function only does numbers from the first to the last, not including the last. So itstops at two, not three, in the above. This turns out to be the most common way to do this kind of loop.

What does elements.append() do?

It simply appends to the end of the list. Open up the Python shell and try a few examples with a list you make. Any time you run into things like this, always try to play with them interactively in the Python shell.

What is While loop

A while- loop will keep executing the code block under it as long as a boolean expression is True. they do is simply do a test like an if- statement, but instead  of  running the code block once, they jump back to the “top” where the while is and repeat. It keeps doing this until the expression is False. Here’s the problem with while- loops: Sometimes they do not stop. This is great if your intention is to just keep looping until the end of the universe. Otherwise you almost always want your loops to end eventually. To avoid these problems, there’s some rules to follow:

1. Make sure that you use while- loops sparingly. Usually a for- loop is better.

2. Review your while statements and make sure that the thing you are testing will become False at some point.

3. When in doubt, print out your test variable at the top and bottom of the while- loop to see what it’s doing.


String Delimiters, Part I

A string in Python is a sequence of characters. For Python to recognize a sequence of characters, like hello, as a

string, it must be enclosed in quotes to delimit the string.

For this whole section on strings, continue trying each set-off line of code in the Shell. Try

"hello"

Note that the interpreter gives back the string with single quotes. Python does not care what system you use. Try

'Hi!'

Having the choice of delimiters can be handy.

Figure out how to give Python the string containing the text: I’m happy. Try it. If you got an error, try it with another type of quotes, and figure out why that one works and not the first.

There are many variations on delimiting strings and embedding special symbols. 

Note: A string can have any number of characters in it, including 0. The empty string is ’’ (two quote characters

with nothing between them). Many beginners forget that having no characters in the middle is legal. It can be useful.

Strings are a new Python type. Try

type('dog')

type('7')

type(7)

The last two lines show how easily you can get confused! Strings can include any characters, including digits. Quotes

turn even digits into strings.

String Concatenation

Strings also have operation symbols. Try in the Shell (noting the space after very):

'very ' + 'hot'

The plus operation with strings means concatenate the strings. Python looks at the type of operands before deciding

what operation is associated with the +. Think of the relation of addition and multiplication of integers, and then guess the meaning of

3*'very ' + 'hot'

Were you right? The ability to repeat yourself easily can be handy. Predict the following and then test. Remember the last section on types:

7+2

'7'+'2'

Python checks the types and interprets the plus symbol based on the type. Try

'7'+2

With mixed string and int types, Python sees an ambiguous expression, and does not guess which you want - it just gives an error! 

This is a traceback error. These occur when the code is being executed. In the last two lines of the traceback it shows the Python line where the error was found, and  then a reason for the error. Not all reasons are immediately intelligible to a starting programmer, but they are certainly worth checking out. In this case it is pretty direct. You need to make an explicit conversion, so both are strings if you mean concatenation, ’7’ + str(2), or so both are int if you mean addition, int(’7’) + 2.



Share:

Digital Library Book list







Algorithm 




Introduction to Algorithms 3rd.Edition - (CLRS)


Aptitude 




100 aptitude trick(102pgs)s


Artificial Intelligence 


Artificial Intelligence A Modern Approach Third Edition -  Stuart Russel



Assembly Language



Assembly Language for X86 Processors KIP R. Irvine


C Language

C Programming for absolute beginners 

Head First C

Pointers & Memory

C Solved Program List (Part I)

C questions and answer


C++

Effective_Modern_C++ - Scott Meyers

Modern C++ Programming Cookbook - Marius Bancila

The C ++Programming Language - Bjarne Stroustrup

OBJECT_ORIENTED_PROGRAMMING Question & Answer


Competitive Programming

Competitive Programming hand book

Competitive_programming


Company Placement Materials

Aptitude shortcut prime material


DevOps




DevOps with Kubernetes -  Hideto Saito

Digital Electronics 

Moris Mano Degital Design 3rd Edition

Drupal


Drupal 8 Module Development by Daniel Sipos


Excel

Mircrosoft_Excel_2019_Bible . M Alexander, Richard Kusleika,John


Flutter

Beginning App Development with Flutter by Rap Payne 


HTML & CSS & Javascript

HTML & CSS Design and Build Website

JavaScript Data Structures and Algorithms

HTML5 & javascript  By :- Jeanine Meyer

THE HTML AND CSS WORKSHOP


Hacking




CEH : Certified Ethical Hackers, All in one Exam Guide

Hacking: The Art of Exploitation, 2nd Edition

Web security for developers - malcolm mcdonald

Hacking The Xbox

KALI LINUX WIRELESS PENETRATION TESTING BEGINNERS GUIDE THIRD EDITION - Cameron Buchanan, Vivek Ramachandran


ICSE 

ICSE Class X Computer Application Notes

Internet Of Things 




INTERNET  OF THINGS PROJECTS WITH ESP32


Java

Introduction to Programming in Java

Java The Complete Reference Ninth Edition

Java The Complete Reference Eleventh_Edition


Jira 



Jira 8 Administration Cookbook Third Edition


Microsoft Power BI

MICROSOFT POWER  BI COOKBOOK

MongoDB

MongoDB in Action, 2nd Edition


Networking

Data_Communications and Networking 4th Ed Behrouz A Forouzan


PHP

Gunnard Engebreth PHP 8 Revealed Use Attributes the JIT Compiler


Python

Data Analysis from scratch with Python

Head First Python

Foundations of Agile Python Development (2008)

Python For Beginners Ride The Wave Of Artificial Intelligence

 Python Data Science - The Bible - Mark Solomon Brown

Full_Book_Python_Data_Structures_And_Algorithm

Cracking Codes with Python An Introduction to Building and Breaking

ADVANCED DEEP LEARNING WITH PYTHON


PostgreSQL

Thomas S.M. - PostgreSQL High Availability Cookbook - 2017

PostgreSQL

React

Pro React 16

react hooks in Action - John Larsen


SQL

SQL Learning (2nd Edition)

SQL : Introduction, Entity- relationship model, Relational Model


Unix/Linux

The-Linux-Command-Line-A-Complete-Introduction














Share:
Powered by Blogger.

Ad Code

Responsive Advertisement

Ad Code

Responsive Advertisement

Featured post

Search This Blog

Recently added book names

THE HTML AND CSS WORKSHOP   | MICROSOFT POWER BI COOKBOOK   | MongoDB in Action, 2nd Edition  | ADVANCED DEEP LEARNING WITH PYTHON   | Cracking Codes with Python An Introduction to Building and Breaking  | Moris Mano Degital Design 3rd Edition  | Beginning App Development with Flutter by Rap Payne  |react hooks in Action - John Larsen   | Artificial Intelligence A Modern Approach Third Edition Stuart Russel  | Data Structures and Algorithms - Narasimha Karumanchi   | Thomas S.M. - PostgreSQL High Availability Cookbook - 2017  | Gunnard Engebreth PHP 8 Revealed Use Attributes the JIT Compiler   | ICSE Class X Computer Application Notes   | INTERNET OF THINGS PROJECTS WITH ESP32   | 100 aptitude trick(102pgs)s   | OBJECT_ORIENTED_PROGRAMMING Question & Answer   | C questions and answer   | Full_Book_Python_Data_Structures_And_Algorithm   | Jira 8 Administration Cookbook Third Edition  | KALI LINUX WIRELESS PENETRATION TESTING BEGINNERS GUIDE THIRD EDITION - Cameron Buchanan, Vivek Ramachandran  HTML5 & javascript By :- Jeanine Meyer   | Python For Beginners Ride The Wave Of Artificial Intelligence   | HackingTheXbox   | Introduction to Algorithms 3rd.Edition - (CLRS)   | The C++ Programming Language - Bjarne Stroustrup   | Modern C++ Programming Cookbook - Marius Bancila   | Java The Complete Reference Eleventh Edition   Data_Communications and Networking 4th Ed Behrouz A Forouzan   | DevOps with Kubernetes - Hideto Saito   | The-Linux-Command-Line-A-Complete-Introduction   | Assembly Language for X86 Processors KIP R. Irvine   | Effective_Modern_C++ - Scott Meyer

Contact Form

Name

Email *

Message *

Followers

Mobile Logo Settings

Mobile Logo Settings
image

Computer Training School Regd. under Govt. of West Bengal Society Act 1961

Header Ads Widget

Responsive Advertisement

Hot Widget

random/hot-posts

Recent in Sports

Popular Posts

Most Popular

Popular Posts

Labels

Blogger templates