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 differences are 3, 2, and 1, respectively. The definition 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.

Advertisements

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();
    };
    self.projectsVisible.subscribe(function (newValue) { alert(newValue); });
}

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>
<head>
<meta charset="utf-8" />
<title>Home Page</title>
<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>
</head>
<body>
	<div id="start-div">
		<div id="title-div"></div>
		<div id="my-widget"></div>
	</div>
</body>
</html>

demo.js


$(document).ready(function() {
	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 : Computed Observables

  • COMPUTED OBSERVABLES – FUNCTIONS DEPENDENT ON ONE OR MORE OTHER OBSERVABLES.
  • What if you’ve got an observable for firstName, and another for lastName, and you want to display the full
    name? That’s where computed observables come in – these are functions that are dependent on one or
    more other observables, and will automatically update whenever any of these dependencies change.
    Your evaluator function will be called once each time any of its dependencies change, and whatever value you return will be passed on to the observers such as UI elements or other computed observables.

    
    <!DOCTYPE html>
    <html>
    <head>
    <meta charset="utf-8" />
    <title>Home Page</title>
    <script src="../lib/knockout-3.2.0.debug.js" type="text/javascript"></script>
    </head>
    <body>
    	<label>Hello </label>
    	<input type="text" data-bind="value: fullName" />
    	<script type="text/javascript">
    		// Here's my data model
    		var viewModel = {
                firstName: ko.observable("Shiv"),
                lastName: ko.observable("Yadav")
            };
            viewModel.fullName = ko.dependentObservable(function () {
                // Knockout tracks dependencies automatically. It knows that fullName depends on firstName and lastName, because these get called when evaluating fullName.
                return viewModel.firstName() + " " + viewModel.lastName();
            });
    		ko.applyBindings(viewModel); // This makes Knockout get to work
    		
    		setTimeout(function(){ viewModel.firstName("Shivanshu"); }, 3000);// change data after 3 seconds
    		
    	</script>
    </body>
    </html>
    

    ang4

    After 3 seconds….

    ang5

    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>
    <head>
    <meta charset="utf-8" />
    <title>Home Page</title>
    <script src="../lib/knockout-3.2.0.debug.js" type="text/javascript"></script>
    </head>
    <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>
    

    ang2

    After 3 seconds…..

    ang3

    knockoutjs : Simple data binding

  • Simple binding with “applyBindings” method.
  • Bind data to template by calling “applyBindings” method.
    Note that it is only one time binding.After that data and template are detached.
    Any change in template or data will not affect each other.
    it’s not really a data binding. Works like template parsing.

    <!DOCTYPE html>
    <html>
    <head>
    <meta charset="utf-8" />
    <title>Home Page</title>
    <script src="../lib/knockout-3.2.0.debug.js" type="text/javascript"></script>
    </head>
    <body>
    	<label>Hello </label>
    	<input type="text" data-bind="value: name" />
    	<script type="text/javascript">
    		// Here's my data model
    		var viewModel = {
    			name : "Shiv"
    		};
    		ko.applyBindings(viewModel); // This makes Knockout get to work
    	</script>
    </body>
    </html>
    

    ang1