Meenakshi - Searching & Sorting for Coding Interviews: With 100+ Interview questions

DEDICATION This book is dedicated to a yogi MASTER MAHA SINGH who mended relations and excelled in each role he lived Son | Brother | Friend | Husband | Father | Father-in-law | Teacher | Farmer | Citizen | Devotee the most upright, conscientious, and able man I know We miss you in every possible way Papa.

Notion Press Old No. 38, New No. 6
McNichols Road, Chetpet
Chennai - 600 031 First Published by Notion Press 2017
Copyright Meenakshi & Kamal Rawat 2017
All Rights Reserved. eISBN 978-1-947988-23-1 This book has been published with all reasonable efforts taken to make the material error-free after the consent of the author. No part of this book shall be used, reproduced in any manner whatsoever without written permission from the author, except in the case of brief quotations embodied in critical articles and reviews.

The Author of this book is solely responsible and liable for its content including but not limited to the views, representations, descriptions, statements, information, opinions and references [Content]. The Content of this book shall not constitute or be construed or deemed to reflect the opinion or expression of the Publisher or Editor. Neither the Publisher nor Editor endorse or approve the Content of this book or guarantee the reliability, accuracy or completeness of the Content published herein and do not make any representations or warranties of any kind, express or implied, including but not limited to the implied warranties of merchantability, fitness for a particular purpose. The Publisher and Editor shall not be liable whatsoever for any errors, omissions, whether such errors or omissions result from negligence, accident, or any other cause or claims for loss or damages of any kind, including without limitation, indirect or consequential loss or damage arising out of use, inability to use, or about the reliability, accuracy or sufficiency of the information contained in this book. ACKNOWLEDGMENTS
To write a book, one need to be in a certain state of mind where one is secure inside himself to work with single minded focus. A guru helps you be in that state.

We want to thank our ideological guru, Swami Ramdev Ji. Time spent on this book was stolen from the time of family and friends. Wish to thank them, for they never logged an FIR for stolen time. We also wish to thank each other, but that would be tantamount to one half of the body thanking the other half for supporting it. The body does not function that way. GET INTRODUCED TECHNICALLY!
This chapter is neither about searching nor sorting.

A book of algorithms is bound to use concepts, data structures and helper functions repeatedly. This chapter gives a brief introduction to concepts, data structures and helper functions referred to in later chapters. It is not a tutorial on data structure. If you do not know what is a linked list or a binary tree or you have never written any program in your life, you may find it difficult to comprehend this book. Ask yourself following questions and proceed only when your honest answers to all of them are YES Q1. Have you written, compiled and executed few programs in C or C++? Q2.

Can you draw linked list and binary tree on papers? Q3. Can you write basic traversal functions of array, linked list and binary tree? Concepts This section talks about concepts that are integral to our discussions. These concepts are not directly related to searching or sorting, but will come up in discussions in rest of the book. 1. Recursion In computer programming, when a function calls itself either directly or indirectly it is called a Recursive Function and the process is called Recursion. Typically, a function performs some part of overall task and rest is delegated to recursive call(s) of same function.

There are multiple instances of functions stack frame (also called Activation record) in the stack and a function may use return value of its recursive calls. Function stops calling itself when it hits a terminating condition. Writing recursive code is not difficult, in fact, in most cases it is relatively simpler because we are not solving the complete problem. It is a two-step process

1. Visualize recursion by defining larger solution in terms of smaller solutions of exact same type, and,
2. Add a terminating condition.

The solution to find sum of first n natural numbers can be defined recursively as: writing it in terms of function call: Sum(n) = n + Sum(n-1) Terminate this recursion when n = 1. Code 0.1 defines the complete recursive function int sum(unsigned int n) { // FIRST TERMINATING CONDITION if(n == 0) return 0; // SECOND TERMINATING CONDITION if(n == 1) return 1; return n + sum(n-1); } Code: 0.1 Im portant point while writing recursive code is, never miss the terminating condition(s), else your function may fall into infinite recursion. Code 0.2 is a simple non-recursive code to compute sum of first n natural numbers.

It is doing exactly the same thing as Code 0.1. int sum(int n) { int s = 0; for(int i=1; i<=n; i++) s += i; return s; } Code: 0.2 Example 0.1: Recursion to compute n th power of a number is Code 0.3 has function for this recursion: int power(int x, int n) { if(0 == n || 1 == x){ return 1; } return x * power(x, n-1); } Code: 0.3 F unction power receives two parameters. One of them remains fixed, the other change and terminates the recursion. Terminating condition for this recursion is IF (n EQUALS 0) THEN return 1 But we have used two terminating conditions, IF (n EQUALS 0) THEN return 1 IF (x EQUALS 1) THEN return 1 This is to avoid unnecessary function calls when x is . Every function call is an overhead, both in terms of time and memory. The four things that we should focus on while writing a function (in this order) are:

1. It should serve the purpose.

   For every possible parameter, our function must always return expected result. It should not be ambiguous for any input.

2. Time taken by function to execute should be minimized.
3. Extra memory used by function should be minimized.
4. Function should be easy to understand. Ideally code should be self-explanatory without any need for documentation (comments).

We should not really care about how many lines of code does particular function runs into as long as length of code is justified (you are not writing duplicate piece of code). Recursive code usually takes more time to execute and is also heavy on memory usage. Still recursion is one of the most powerful and rampant problem-solving tool, because sometime, a solution that otherwise is very complex to comprehend, can be very easily visualized recursively. We just need to solve the problem for base case and can leave rest of the problem to be solved by recursion.

Some algorithms like merge sort has a simple recursive implementation and are difficult to code non-recursively. Algorithms like binary search can be coded both recursively and non-recursively with equal ease. Algorithms like Linear search or bubble sort are better implemented and understood iteratively than recursively. There is no blanket statement that can relate ease of code with recursion. The most important tool is common sense. 2.

Next page