### Why do we conduct an Entrance Test ?

The main objective behind conducting the entrance test is to assess the basic knowledge of Data Structures and Algorithms.

To make you ready for FAANG, the 6-month immersive online program by Scaler Academy assumes that you already have some prerequisite knowledge of basic programming.

The questions in the entrance test are designed in such a way that not only test your Data Structures and Algorithmic Skills, but the aptitude and mathematical knowledge as well. We look for candidates who can beautifully pen down their basic thoughts and logic in the form of code. The test is not just a means to assess students but a good metric for Scaler Academy as well to decide how much effort needs to be put in from our side as well to give you the best mentorship and experience throughout your journey with Scaler Academy.

## What to expect in the entrance test ?

Specifically, we assume that you already know the basics including

- How to write a Loop and if-else constructs
- What an Array is
- Simple algorithms like Searching, Sorting, …
- Some basic Maths like

- How many permutations does the string “Google” have?

- How many bits will be needed to represent the number 1 Million.

You can expect easy to easy/medium level questions on any of the above topics.

We never ask questions related to specific Data Structures like stacks / queues, trees, since we believe that your success is determined more by how consistently and passionately you are willing to follow the curriculum, and less by your current knowledge of CSE concepts.

Following topics are not going to be a part of the entrance test.

❌ Dynamic Programming

❌ Greedy Algorithms

❌ Backtracking

❌ Graphs

## Which coding language(s) are allowed in the entrance test?

Feel free to code in your preferred language, be it Python, C++, Java, Haskell, Ruby, Javascript etc. We, at Scaler Academy believe that Programming language is no barrier to express your thoughts and logic for any problem statement.

Your knowledge of a particular language does not limit your potential as a Software Engineer. Therefore, we never put a constraint on the programming language.

## How to prepare for entrance test

Let’s understand the best way to prepare for the entrance test through a sample problem.

## Problem Statement

Riya is a software Engineer at InterviewBit and is really fond of chocolates. Her friend, Sarthak gifts her a box full of chocolates containing both white and dark chocolates. Now, she being a very organised person, wants to arrange the chocolates in some order such that white chocolates are placed before the dark chocolates in a sequence. But she is currently very busy mentoring the students in the academy, so your task is to help her in arranging the chocolates.

Note: All the white chocolates are identical and dark ones as well.

## Input Format

All white chocolates are denoted by 0 and all the dark chocolates are denoted by 1.

First line contains an integer N denoting the total no. of chocolates.

Second line contains N integers denoting the shuffled order of the chocolates.

## Output Format

Output the N integers in sorted in the correct sequence.

## Sample Input

5

0 1 1 0 1

## Sample Output

0 0 1 1 1

## Constraints

## How to Approach the Problem?

- The first task is to find the underlying question behind the story.

Once you do that, you will realise that the gist of the problem statement is to sort an array containing 0s and 1s. Seems like a trivial problem, right? - You simply have to rearrange all the 0’s and 1’s in such a way that all the 0’s come in the front followed by the 1’s.

And if it looks like a rearrangement problem, don’t you think Permutation can come to your rescue? - But wait, take a minute to think if this approach is feasible under the given constraints or not?
- For an array of size , what could be the total number of permutation?

Yes you guessed it right. It’s going to be And here if you will carefully analyze, then you will observe that can be as large as (give importance to the constraints given in the problem as well).

So here will be a very huge number and it will be computationally expensive. - Can we do better than this?

As you observed earlier, this is a rearrangement problem and the final sequence is going to be a sorted one as well. So can we map this problem to sorting a given array? - Now think of the best way to perform this sorting operation. Try to recall all the sorting algorithms you have learnt so far and think which one of them can solve the problem in the optimal way.
- Among them you will figure out that QuickSort should be the way to go. But still the time complexity in order to sort the array remains . Which is again computationally expensive if is as large as .

- Now, another observation to be made at this point is that there are only 0’s and 1’s and in the end, all the 0’s will be present to the left of all the 1’s. So why not just count all the 0’s and 1’s in one go from the given array. This can be done in one traversal.
- After that, let's say the count of 0’s is CZ and count of 1’s is CO. Then replace the first CZ integers from the array with 0 and the rest of the elements by 1. This will need another traversal of the array. This approach, in asymptotic notation, takes time of linear time which is acceptable for the given constraints.
- Now there is still one issue that, we are traversing the whole array twice!
- Can we do this in single traversal?
- Now for any index let’s suppose all the numbers from index 0 to are having values as 0’s. So, do we need to shift or replace these numbers? No. Similarly for any index , suppose all elements from index to index are all 1’s. We again don’t need to do anything for these elements. Only the rest of the elements from index to needs to be updated.
- So basically we have divided our input into three parts where the leftmost part is all zeroes, the rightmost is all 1’s and in between we have random shuffling.
- So we can simply check the middle part, and if the current number is 0, we can shift it to the left part of the sequence and if it’s 1, then simply shift to the right part, and keep on doing this till the length of the middle part becomes zero.
- So what will we do to solve this? We will keep 2 pointers, ‘left’ and ‘right’. Left will segregate all 0’s to left, and right will do the same for 1’s in the right.
- Start left from 0 and right from
- At any time, when you see that the left pointer is pointing to a 0, we do nothing and increment further but if it is pointing to 1, Swap it with the value pointed by the right pointer. Now, since we have included a new 1 in the right part, we decrease the right pointer as well. And repeat the above process till the left pointer becomes greater than right.
- Voila! After one iteration, the whole array will be sorted, in a single traversal of the array and this approach also takes just time and space.

To practice similar questions like these, follow the below simple steps:

- Go to the link. https://www.interviewbit.com/courses/programming/
- Try Completing questions at least till Level 2 on the IB platform.
- Once you are done with all the questions in these levels, feel free to practice questions in next levels to brush up your skills.

Self evaluation is very important. To help you with that, the following are the links to some of the problems that have already been asked in our previous entrance tests. Through these questions, you will not only understand the types of questions asked in our entrance test, but will also get an idea of how exactly you should approach each question.

## FAQ’s

#### 1. Typically how much time is needed to prepare?

This is a relative question and completely depends on your learning speed. The more you focus on developing intuition, the better you become at problem solving skills. Clearing the entrance test should not be a big task, if your basics are clear. Try to code on a daily basis and solve as many questions as you can because that will increase your problem solving speed as well. If you are a beginner willing to sharpen your DS/Algo skills, set daily goals on the InterviewBit platform and solve at least 2-3 problems everyday. But, If you feel confident in Data structures and Algorithms, you can start practising advanced questions on the platform as well. Make sure you manage your schedule well and keep revisiting already studied concepts as well.

#### 2. Do these during your preparation

- Create a Complete Study Schedule - and Stick to it.
- Choose your study environment carefully.
- Focus more on enhancing problem solving skills.
- Try to develop intuition for every question that you solve.
- Don’t take stress before the test.
- Keep your basics clear because you will be judged on that only.

#### 3. Avoid these during your preparation

- Don't adapt to rote learning. Memorising the code is not going to help you in any way.
- Don't develop the intuition first and then try writing the code and not the other way round.
- Don't pull all-nighters.

#### 4. How to use streaks effectively?

One of the main reasons why many students prefer practising on InterviewBit is because you can set daily goals on the platform based on the time you can devote each day. We calculate streak as the continuous number of days when you hit your daily goal. If you do not meet your goal for a day, your streak is reduced to half.

Streaks are a very effective way to motivate yourself as they encourage you to solve more and more problems everyday. Make sure you put this feature to good use and make it a daily habit to solve as many problems as you can everyday.

Your performance in the entrance test will be the major stakeholder regarding your selection. So, make sure to put your best foot forward.