Elements of Programming Interviews: The Insiders' Guide by Adnan Aziz & Tsung-Hsien Lee & Amit Prakash

Author:Adnan Aziz & Tsung-Hsien Lee & Amit Prakash [Aziz, Adnan]
Language: eng
Format: epub
Publisher: UNKNOWN
Published: 2018-07-01T23:00:00+00:00

The time complexity of any reasonable library sort isO(nlogn) for an array with n entries. Most library sorting functions are based on quicksort, which hasO(1) space complexity. Sorting problems come in two flavors: (1.) use sorting to make subsequent steps in an algorithm simpler, and (2.) design a custom sorting routine. For the former, it’s fine to use a library sort function, possibly with a custom comparator. For the latter, use a data structure like a BST, heap, or array indexed by values.

Certain problems become easier to understand, as well as solve, when the input is sorted. The most natural reason to sort is if the inputs have a natural ordering, and sorting can be used as a preprocessing step to speed up searching.

For specialized input, e.g., a very small range of values, or a small number of values, it’s possible to sort inO(n) time rather thanO(nlogn) time.

It’s often the case that sorting can be implemented in less space than required by a brute-force approach.

Sometimes it is not obvious what to sort on, e.g., should a collection of intervals be sorted on starting points or endpoints? (Problem 10.2 on Page 51)

Table 10.1: Top Tips for Sorting

Know your sorting libraries

To sort a list in-place, use thesort() method; to sort an iterable, use the functionsorted(). • The sort() method implements a stable in-place sort for list objects. It returns None— the calling list itself is updated. It takes two arguments, both optional: key=None, and reverse=False Ifkey is notNone, it is assumed to be a function which takes list elements and maps them to objects which are comparable—this function defines the sort order. For example, if a=[1, 2, 4, 3, 5, 0, 11, 21, 100] then a.sort(key=lambda x: str(x)) maps integers to strings, anda is updated to[0, 1, 100, 11, 2, 21, 3, 4, 5], i.e., the entries are sorted according to the lexicographical ordering of their string representation. If reverse is set toTrue, the sort is in descending order; otherwise it is in ascending order.

• Thesorted function takes an iterable and return a new list containing all items from the iterable in ascending order. The original list is unchanged. For example, b = sorted(a, key=lambda x: str(x)) leavesa unchanged, and assignsb to[0, 1, 100, 11, 2, 21, 3, 4, 5]. The optional argumentskey andreverse work identically tosort.

10.1 Compute the intersection of two sorted arrays A natural implementation for a search engine is to retrieve documents that match the set of words in a query by maintaining an inverted index. Each page is assigned an integer identifier, its documentID. An inverted index is a mapping that takes a word w and returns a sorted array of page-ids which contain w—the sort order could be, for example, the page rank in descending order. When a query contains multiple words, the search engine finds the sorted array for each word and then computes the intersection of these arrays—these are the pages containing all the words in the query. The most computationally intensive step of doing this is finding the intersection of the sorted arrays.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.