logic

• Sorting

1. Alternating sort

Given a list of pairwise distinct integers, sort it in alternating order: The second number is larger than the first, the third is smaller than the second, the fourth is larger than the third etc. (This order is not unique.) E.g., `5 7 3 4 2 9 1` would be valid output.

Solution

You can do this in O(n) by placing each element in turn at the end, or at the penultimate position based on a comparison with the current last element.

For example,

``````1,4,9,2,7,5,3,8,6
Place 1 at end, current list [1]
4>1 true so place 4 at end, current list [1,4]
9<4 false so place 9 at penultimate position [1,9,4]
2>4 false so place 2 at penultimate [1,9,2,4]
7<4 false so place 7 at penultimate [1,9,2,7,4]
5>4 true so place 5 at end [1,9,2,7,4,5]
3<5 true so place 3 at end [1,9,2,7,4,5,3]
8>3 true so place 8 at end [1,9,2,7,4,5,3,8]
6<8 true so place 6 at end [1,9,2,7,4,5,3,8,6]
``````

Note that the equality tests alternate, and that we place at the end if the equality is true, or at the penultimate position if it is not true.

2. Turning Number in an Array

Turning number is the maximum number in an array which increases and then decreases. This kind of array is also named unimodal array. Please write a function which gets the index of the turning number in such an array.

For example, the turning number in array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 10, so its index 5 is the expected output.

3. Sum Of Three

Given three sets A, B, and C of at most N integers each, determine whether this is a triple a in A, b in B,
and c in C such that a + b + c = 0.

Solution

Sort B in increasing order; sort C in decreasing order; for each a in A, scan B and C for a pair that sums to – a
(when the sum is too small, advance in B, when the sum is too large, advance in C).

4. Expensive exchange

A clerk at a shipping company is charged with the task of rearranging a number of large crates in order of the time they are to be shipped out.
Thus, the cost of compares is very low (just look at the labels) relative to the cost of exchanges (move the crates). The warehouse is nearly full—there is extra space sufficient to hold any one of the crates, but not two. What sorting method should the clerk use?

5. Nuts and bolts(G. J. E. Rawlins)

You have a mixed pile of N nuts and N bolts and need to quickly find the corresponding pairs of nuts and bolts. Each nut matches exactly one bolt, and each bolt matches exactly one nut. By fitting a nut and bolt together, you can see which is bigger, but it is not possible to directly compare two nuts or two bolts. Give an efficient method for solving the problem.

Solution

Since we can’t compare a nut with other nuts and a bolt with other bolts, we can’t sort them. So current best possibility seems to pick nuts one-by-one and find matching bolts for them. In this manner, we will match all the pairs in O(n^2) time complexity.
But though we can’t compare a nut with other nuts and so for bolts, we can compare a nut with bolts and vice-versa. Also keep in mind that if a Nut(N) is smaller than a Bolt(B) than N is fit only for bolts smaller than B. Similarly if a Bolt(B’) is smaller than a Nut(N’) than N is fit only for bolts smaller than B’. So we can go like following in solving this problem.
• Take a nut from the nuts pile
• Divide bolts around it in 2 parts, which are smaller and larger than this.
• Find a matching bolt to this nut.
• Divide nuts in 2 parts, which are smaller and larger than matching bolt.
Now we have 2 subsets of Nuts and Bolts. If we pick a nut from small size nuts pile, we will get a corresponding bolt in smaller size bolts pile and similarly for large size piles. At every step, we will be able to divide these piles in 2 halves and reduce complexity by a factor of 2 in average case. In this case time complexity will be O(nlogn).

In worst case we might have choose the smallest/largest nut/bolt as reference and our one pile will have zero nut/bolt and another pile will have all the remaining. In this case time complexity will be O(n^2).
Algorithm:
Take a nut; partition the bolts with respect to this nut. We will find the matching bolt for this nut. Now take the bolt; partition the nuts.
In this manner, we have divided the Original problems into 2 sub-problems.
T(n) = T( i ) + T(n-i ) + O(n)
Where we have chosen the ith largest nut from a particular pile.
Average time complexity = O(nlogn).
Worst time complexity = O(n^2).
6. The way a card game player arranges his card as he pick them up 1 by 1 is an example of :
Solution
insertion sort
7. Which sorting algorithm should not be used in below case :
1) data is already sorted in same order.
2) data is already sorted in reverse order.
3) All elements are same (special case of case 1 and 2)
Solution
Quicksort
7. Minimum Difference between Two Arrays
Given two arrays x[1], …, x[m] and y[1], …, y[n], design an algorithm to find two elements x[i] and y[j] such that the absolute value |x[i] – y[j]| is minimized over all posibble pairs of x and yelements. A brute force algorithm needs O($n^2$) time. Your algorithm should be far more efficient than that. Analyze the time complexity of your algorithm.

Solution

First, sort array x. Then, for each element in y, use Binary Search method to find the element with the closest value in array x. In this way, we can find the pair with the minimum absolute value of the difference. Sorting the array takes O(m lg m) time and binary search takes O(n lg m) time.

8. Pancake Sorting

Jeremy is a waiter working in a restaurant. The chef there is sloppy; when he prepares a stack of pancakes, they come out all different sizes. When Jeremy delivers the pancakes to the customer, he wants to rearrange them by grabbing several from the top and flipping them over on the way. After repeating this for several times, the smallest pancake is on top, and so on, down to the largest at the bottom. If there are n pancakes, how many flips are required? Design an algorithm to help Jeremy, and analyze its time complexity.

Solution

This problem is called pancake sorting. For a stack of pancakes, we first locate the largest pancakes. Then we flip the largest pancakes to the top by using one flip and use another flip to move the largest pancaked to the bottom. Then, we recursively sort the top n-1 pancakes. Since every pancake except the smallest one needs at most two flips to move to the correct position, the number of flips is 2(n – 1).

Arrays

2. Jolly Jumpers

A sequence of n integers is called a jolly jumper if the absolute values of the differences between successive elements take on all possible values 1 through n − 1.Where n > 0.

For instance, 1 4 2 3 is a jolly jumper, because the absolute diﬀerences are 3, 2, and 1, respectively. The deﬁnition implies that any sequence of a single integer is a jolly jumper. Write a program to determine whether each of a number of sequences is a jolly jumper.

3. Given an array of n integers, where one element appears more than n/2 times, find that element in linear time and constant extra space.

Solution

There is a beautiful algorithm for solving this that works in two passes (total time O(N)) using only constant external space (O(1)).

The intuition behind the algorithm is actually quite beautiful. Suppose that you were to have a roomful of people each holding one element of the array. Whenever two people find each other where neither is holding the same array element as the other, the two of them sit down. Eventually, at the very end, if anyone is left standing, there’s a chance that they’re in the majority, and you can just check that element. As long as one element occurs with frequency at least N/2, you can guarantee that this approach will always find the majority element.

To actually implement the algorithm, you make a linear scan over the array and keep track of your current guess as to what the majority element is, along with the number of times that you’ve seen it so far. Initially, this guess is undefined and the number of repeats is zero. As you walk across the array, if the current element matches your guess, you increment the counter. If the current element doesn’t match your guess, you decrement the counter. If the counter ever hits zero, then you reset it to the next element you encounter. You can think about this implementation as a concrete realization of the above “standing around in a room” algorithm. Whenever two people meet with different elements, they cancel out (dropping the counter). Whenever two people have the same element, then they don’t interact with each other.

items = [1, 2, 3, 4, 5, 5, 5, 5, 5 ]

# shuffle the items

random.shuffle(items)

print(“shuffled items: “, items)

majority_elem = items[0]

count = 1

for i in range(1,len(items)):

if items[i] == majority_elem:

count += 1

else:

count -= 1

if count == 0:

majority_elem = items[i]

count = 1

print(“majority element : %d” % majority_elem )

4. Given an array of size N that contains values between 1 and N-1, find the duplicate element (assuming there is only one). If it contains values between 1 and N+1, how would you find the missing element (again assuming there is only one missing)? Do each in O(N).

Solution

For the first partcompute the sum of the numbers from 1 to N-1. Then sum the values in the array. The duplicate number is the difference between these sums.

For the second part, compute the sum of the numbers from 1 to N+1. Then sum the values in the array. The missing number is again the difference between these sums.

knockoutjs : valueHasMutated

Explicitly Triggering the Evaluation of Observables with ValueHasMutated

In certain scenarios, you will want to be able to notify the subscribers with the latest value of an observable, You can achieve this by using the valueHasMutated function for any observable.
valueHasMutated is what is used internally to notify when the value has actually changed. However, it can be used to trigger subscribers with the same value.

```
<button data-bind="click: handleClick">Click me</button>

```
```
var viewmodel = function () {
self.projectsVisible = ko.observable(false);
self.handleClick = function () {
self.projectsVisible.valueHasMutated();
};
}

ko.applyBindings(viewmodel);

```

knockoutjs : components

Components are a powerful, clean way of organizing your UI code into self-contained, reusable chunks. This feature allows developer to build some custom UI components that will have it’s own view and logic. You can register a component using ko.components.register (technically, registration is optional, but it’s the easiest way to get started). A component definition specifies a viewModel and template.

• viewModel is optional
• template is required

REGISTRATION

```ko.components.register('mywidget', {
viewModel: function(params) {
//Define view model here
this.title = ko.observable("I am a Widget");
},
template: '</pre>
<div></div>
<pre>'
});
```

USE

```
<mywidget></mywidget>

```

OR

```</pre>
<div data-bind="component: {
name: &quot;mywidget&quot;
}"></div>
<pre>
```

Example with Backbone

```
<!DOCTYPE html>
<html>
<meta charset="utf-8" />
<script type="text/javascript" src="../lib/knockout-3.2.0.debug.js"></script>
<script type="text/javascript" src="../lib/underscore.js"></script>
<script type="text/javascript"
src="http://cdnjs.cloudflare.com/ajax/libs/jquery/1.7.1/jquery.min.js"></script>
<script type="text/javascript"
src="http://cdnjs.cloudflare.com/ajax/libs/backbone.js/1.1.0/backbone-min.js"></script>
<script type="text/javascript" src="../js/demo.js"></script>
<body>
<div id="start-div">
<div id="title-div"></div>
<div id="my-widget"></div>
</div>
</body>
</html>

```

demo.js

```
var MyView = Backbone.View.extend({
el : '#start-div',
render : function() {
this.\$el.find("#title-div").html('Hello Knockout');
this.koStart();
},

koStart : function() {
this.initKOComponent();
this.\$el.find("#my-widget").append("<mywidget params='titleText: title'></mywidget>");

var viewModel = {
title : "I am a custom Widget"
};

ko.applyBindings(viewModel);
},
initKOComponent : function() {
ko.components.register('mywidget', {
viewModel : function(params) {
this.widgetTitle = ko.observable(params.titleText);
},
template : '<div data-bind="text: widgetTitle"></div>'
});
}

});
var myView = new MyView();
myView.render();

});

```

knockoutjs : “template” binding

• Rendering a named template
• If you want to, you can factor out templates into a separate element and then reference them by name:

```
<h2>Participants</h2>
Here are the participants:
<div data-bind="template: { name: 'person-template', data: buyer }"></div>
<div data-bind="template: { name: 'person-template', data: seller }"></div>

<script type="text/html" id="person-template">
<h3 data-bind="text: name"></h3>
<p>Credits: <span data-bind="text: credits"></span></p>
</script>

<script type="text/javascript">
function MyViewModel() {
this.buyer = { name: 'Franklin', credits: 250 };
this.seller = { name: 'Mario', credits: 5800 };
}
ko.applyBindings(new MyViewModel());
</script>

```

In this example, the person-template markup is used twice: once for buyer, and once for seller. Notice that the template markup is wrapped in a — the dummy type attribute is necessary to ensure that the markup is not executed as JavaScript, and Knockout does not attempt to apply bindings to that markup except when it is being used as a template.

knockoutjs : Two way data binding with Observables

• Two way data binding with Observables
• Change in data will be reflected in change in template
• ```<!DOCTYPE html>
<html>
<meta charset="utf-8" />
<script src="../lib/knockout-3.2.0.debug.js" type="text/javascript"></script>
<body>
<label>Hello </label>
<input type="text" data-bind="value: name" />
<script type="text/javascript">
// Here's my data model
var viewModel = {
name : ko.observable("Shiv")
};
ko.applyBindings(viewModel); // This makes Knockout get to work

setTimeout(function(){ viewModel.name("Shivanshu"); }, 3000);// change data after 3 seconds

</script>
</body>
</html>
```

After 3 seconds…..

RequireJs “map” configuration

map:

For the given module prefix, instead of loading the module with the given ID, substitute a different module ID.
This sort of capability is really important for larger projects which may have two sets of modules that need to use two different versions of ‘foo’, but they still need to cooperate with each other.
This is not possible with the context-backed multiversion support. In addition, the paths config is only for setting up root paths for module IDs, not for mapping one module ID to another one.
map example:

```requirejs.config({
map: {
'some/newmodule': {
'foo': 'foo1.2'
},
'some/oldmodule': {
'foo': 'foo1.0'
}
}
});
```

If the modules are laid out on disk like this:
• foo1.0.js
• foo1.2.js
• some/
• newmodule.js
• oldmodule.js
When ‘some/newmodule’ does `require(‘foo’)` it will get the foo1.2.js file, and when ‘some/oldmodule’ does `require(‘foo’)` it will get the foo1.0.js file.
This feature only works well for scripts that are real AMD modules that call define() and register as anonymous modules. Also, only use absolute module IDs for map config. Relative IDs (like ‘../some/thing’) do not work.
There is also support for a “*” map value which means “for all modules loaded, use this map config”. If there is a more specific map config, that one will take precedence over the star config. Example:

```requirejs.config({
map: {
'*': {
'foo': 'foo1.2'
},
'some/oldmodule': {
'foo': 'foo1.0'
}
}
});
```

Means that for any module except “some/oldmodule”, when “foo” is wanted, use “foo1.2” instead. For “some/oldmodule” only, use “foo1.0” when it asks for “foo”.
Note: when doing builds with map config, the map config needs to be fed to the optimizer, and the build output must still contain a requirejs config call that sets up the map config. The optimizer does not do ID renaming during the build, because some dependency references in a project could depend on runtime variable state. So the optimizer does not invalidate the need for a map config after the build.

Learning RequireJS

Why requirejs?

Why are we using requirejs? I’ve even asked it of myself. For me, organizing large javascript projects and managing dependencies led to it. There are lots of great posts about how to use requirejs but I wanted to focus on WHY.

Explicit Dependency Specifications :
Open up any significant sized javascript file with 100+ lines of code, even 50, and tell me, within 5 seconds, what dependencies it has. Can’t do it? You can with modules and requirejs.

```function View() {
this.name = ko.observable('bob');
this.age = ko.observable(20);
...
}
var view = new View();
ko.applyBindings(view, \$('viewPlaceHolder')[0]);
```

versus

```require(['jquery', 'knockout'], function(\$, ko) {
// who knows whats in here, but I do know what it needs
});
```

How often do you use this information as a developer? Think about the value in not spending 5 minutes everytime you need to know, or more likely, the value in not creating a bug because you didn’t take the time to find them all or you missed one.

Explicit Export Specifications :

Along with explicit dependencies, modules have an explicit mechanism to define what they export. We can quickly read a module and know what it provides by looking at the return statement, instead of wondering what globals to access. define makes explicit that it is providing an interface to consumers.

```define('math', ['dependencyA', 'dependencyB'], function(dependencyA, dependencyB) {
// horrible things to local scope
return {
min: min,
max: max,
average: average
};
});
```

Avoid Script Tag Soup :

```<script src="scripts/utils.js">
<script src="scripts/numbers.js">
<script src="scripts/common.js">
<script src="scripts/formatting.js">
<script src="scripts/thing.js">
<script src="scripts/other.js">
<script src="scripts/site.js">
```

Using RequireJS :

Application Structure :

├── app.js
├── index.html
├── lib
│ ├── modules
│ │ └── template.js
│ ├── require.js
│ └── underscore.js

The data-main Attribute

Once you downloaded RequireJS, the first thing to do after you put its script in your solution is to understand how RequireJS starts working. Once RequireJS is loaded, it search for a script with data-main attribute (it should be the same script with the src attribute set to load RequireJS). The data-main should be set to the base Url for all the scripts. From the base Url, RequireJS will start loading all the relevant modules. Here is an example of a script tag with the data-main attribute:

```<script data-main="app.js" src="lib/require.js"></script>
```

Configuring RequireJS

Another way to define the base Url is using the config function.

Now, let’s take a look at app.js.

```require.config({
//By default load any module IDs from scripts/app
baseUrl: 'scripts/app',
//except, if the module ID starts with "lib"
paths: {
lib: '../lib',
jquery: "jquery-1.11.0.min"
},
// load backbone as a shim
shim: {
'backbone': {
deps: ['underscore'],
// use the global 'Backbone' as the module name.
exports: 'Backbone'
}
}
});
```
• The config Function :
• If you want to change the default RequireJS configuration values with your own configurations, you can do that using the requirejs.config function. The config function receives an options object that can include a lot of configurations options. Here are some of the configurations that you can use:
paths – path mapping for modules that don’t exists in under the baseUrl
shim – configuration for dependencies, exports and initialization function to wrap scripts/modules that don’t use the RequireJS define function. For example, if underscore library doesn’t use the RequireJS define function and you still want to use it with RequireJS, you will have to define it as a shim in the config function.

// Sets the configuration for your third party scripts that are not AMD compatible( that do not use define() to declare the dependencies and set a module value)

```  shim: {

"backbone": {
deps: ["underscore", "jquery"],
exports: "Backbone"  //attaches "Backbone" to the window object
}

} // end Shim Configuration
```

The Shim configuration can also be used to make sure that that certain scripts executed in a particular order.
http://requirejs.org/docs/api.html#config-shim
deps – array of dependencies to load.

Defining Modules Using RequireJS :
Modules are just well-scoped objects that expose an API and encapsulate their internals. In order to define a module, RequireJS exposes the define function. There should be only one call for define in each JavaScript file by convention. The define function receives an array of dependencies and a function which is going to hold all the module definitions. By conventions the module definition function receives as parameters all the previous dependencies and in the order they were supplied in the array. For example, here is a simple module definition:

```define(["logger"], function(logger) {
return {
firstName: “John",
lastName: “Black“,
sayHello: function () {
logger.log(‘hello’);
}
}
}
);
```

Using The require Function :

Another useful function in RequireJS is the require function. The require function is used to load dependencies without the creation of a module. For example, here is a usage of the require function which defines a function that require jQuery to work:

```require(['jquery'], function (\$) {
//jQuery was loaded and can be used now
});
```

```define(function ( require ) {

// note the inline require within our module definition
require(["foo", "bar"], function ( foo, bar ) {
foobar = foo() + bar();
});

// we can still return a module
return {
foobar: foobar
};
});
```

you can use a synchronous require() as long as the module was already registered for that context:

```define(['require', 'lorem/ipsum'], function(require){
// since 'lorem/ipsum' is on the dependency list it will be registered
// before calling the definition function, so the synchronous require will
// also work
var ipsum = require('lorem/ipsum')
console.log(ipsum.doSth());
});
```

But this would fail if the module dolor/amet wasn’t registered yet:

```define(['require'], function(require){
var ipsum = require('lorem/ipsum')
console.log(ipsum.doSth());
});
```

Some Tricks for Troubleshooting :

You can use these API calls in your code if you need to, but I’ve actually found them quite useful when on the console in Chrome:
require.defined(moduleId) – returns true if your moduleId has been defined and is ready for use.
require.specified(moduleId) – returns true if your moduleId has been listed as a dependency by another defined module. Note that just because this returns true doesn’t mean your moduleId is ready to use (don’t you just love asynchrony?).
Get module Url
If you ever need to find the path to a given module, just use the following…

```var path = require.toUrl("./style.css");
```

requirejs.s.contexts._.config – I learned about this from Vernon Kesner. This is technically a “back door/undocumented” call – so it could change or disappear without warning. However it returns a very useful object full of configuration info, see below:

This is the result of calling requirejs.s.contexts._.config inside a sample gif-generation app I used to demo Web Workers at Devlink. You can see all the relevant configuration data: the base URL, the paths we’ve mapped, the shim configuration, etc.
Two other key items to know about when it comes to troubleshooting RequireJS are ‘errbacks’ and the requirejs.onError method.

RequireJS “errbacks” :

When you make a require call, you can include a third argument – a callback that receives an error argument, allowing you to react to the error, instead of ultimately generating an uncaught exception. The method signature, when using “errbacks” looks like this:

```require(
[ "backbone" ],
function ( Backbone ) {
return Backbone.View.extend({ /* your magic here */ });
},
function (err) {
/*
err has err.requireType (timeout, nodefine, scripterror)
and err.requireModules (an array of module Ids/paths)

Inside here you could requirejs.undef('backbone') to clear
the module from require locally - and you could even redefine
it here or fetch it from a different location (though the
fallback approach earlier takes care of this use-case more succinctly)
*/
}
);
```

requirejs.onError :

RequireJS has a global onError handler that will catch any errors not already handled by “errbacks”. To use it, simply set it like this:

```requirejs.onError = function (err) {
/*
err has the same info as the errback callback:
err.requireType & err.requireModules
*/
console.log(err.requireType);
// Be sure to rethrow if you don't want to
// blindly swallow exceptions here!!!
};
```