Working on machines without understanding them ? Then you should be here..
Geographical location should not become a barrier to Share our knowledge.
Puzzles and Interview question are intended to be discussed here.We encounter cycle stealing in the context of Direct Memory Access (DMA). Either the DMA controller can use the data bus when the CPU does not need it, or it may force the CPU to temporarily suspend operation. The latter technique is called cycle stealing. Note that cycle stealing can be done only at specific break points in an instruction cycle.!--google_ad_client = "pub-7615364552369508";google_ad_host = "pub-1556223355139109";google_ad_host_channel="00000+00013+00005+00032";/*...
Saturday, February 27, 2010
If the number of frames allocated to a low-priority process falls below the minimum number required by the computer architecture, we must suspend that process' execution. We should then page out its remaining pages, freeing all its allocated frames. This provision introduces a swap-in, swap-out level of intermediate CPU scheduling.!--google_ad_client = "pub-7615364552369508";google_ad_host = "pub-1556223355139109";google_ad_host_channel="00000";/*...
Usually, on increasing the number of frames allocated to a process' virtual memory, the process execution is faster, because fewer page faults occur. Sometimes, the reverse happens, i.e., the execution time increases even when more frames are allocated to the process. This is known as the Belady's Anomaly. This is true for certain page reference patterns. This is also called the FIFO anomaly....
AVL trees are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has O(log n) height and hence O(log n) worst case search and insertion times. However, ordinary binary search trees have a bad worst case. When sorted data is inserted, the binary search tree is very unbalanced, essentially more of a linear list, with O(n) height and thus O(n) worst case insertion...
Before looking at the answer, try writing a simple C program (with a for loop) to do this. Quite a few people get this wrong.This is the wrong way to do itstruct list *listptr, *nextptr;for(listptr = head; listptr != NULL; listptr = listptr->next){ free(listptr);}If you are thinking why the above piece of code is wrong, note that once you free the listptr node, you cannot do something like listptr = listptr->next!. Since listptr is already...
One way is to reverse the data in the nodes without changing the pointers themselves. One can also create a new linked list which is the reverse of the original linked list. A simple C program can do that for you. Please note that you would still use the "next" pointer fields to traverse through the linked list (So in effect, you are using the pointers, but you are not changing them when reversing the linked list)....
Thursday, February 25, 2010
You have 25 horses. You have 5 tracks to race on. We need to find 3 fastest horses. How many minimum races required to find that ? We have no stop-watch. Horses run at same speed. Now this puzzle is deceptive if you are not careful enough. Solution : Divide the set of 25 horses into 5 non-overlapping sets of 5 horses each.Have a race each for all the horses in eachset.This makes it a total of 5 races, one for each set. Now, have a race for the winners...
Find if the sum of two elements in an array sum up to b (a number) with complexity of O(n)? Input – Array : 1,2,3,4,5,6,7,8 and the sum is : 6 Output would be : {1,5} {2,4} Solution : Here is the idea is to start from the first element of the array and keep a hashtable to store the potential pairs. We will check if sum – (a[i]) already exists in the Hashtable. If yes, we have a pair (a[i], value from hashtable) as the pair with the sum. If no,...
Given an array of m+n elements in the range 1 to n ie(m elements are repeated). Find the duplicate elements. Time Complexity: O(m+n) Space Complexity: O(m) Solution : Since we know there are 1 to n elements, we can sort the array in O(n). The first n elements will be the unique values and n to m will be the duplicates. This is O(n+m) && no extra space required. for (int i = 0; i < array.Length; i++) { if (array[i]...
Write an algorithm to find whether a given number is a multiple of 3 or not without using modulo or division operation. Ans: Convert the number to a string, thereby getting the decimal digits separately. Read those digits once by one and add all of them. If the sum is more than 10, repeat the procedure. Once the sum is less than 10, if it is 0, 3, 6 or 9, then the original number is divisible by...
In an integer array all numbers occur exactly twice except for a single number which occurs exactly once..give an O(n) algorithm to find the number occurring only once. Ans: Do bitwise XOR of all numbers. The result will be the number that occurs only once. The result in each position is the different number if the two bits are different, and 0 if they are the same. public class Xor { public static void main(String args[]) { ...
You have a [n * n] array which is sorted both row wise and column wise. How do you find an element in this array in O(n) time ? Solution: 1 1. Start from left bottom most cell. 2. If query is larger move right . 3. If query is smaller move up. 4. If you can’t move right or up and haven’t found the query yet, it means that the query does not exist.Applying binary search for Rows and column may furthur reduce the complexity...
Question : Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.Eg.i) 3 2 7 10 should return 13 (sum of 3 and 10)ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)The idea is to use Dynamic Programming and store the intermediate “good” sums in an auxiliary array. The right way is to define an array B[n] whose j-th element...
This problem is called Maximum contiguous sub sequence sum problem.
Given an array which can contain both positive and negative numbers, find the maximum contiguous sub sequence sum.
For example in an array = {2, -3, 4, -5, 6, -3, 8}, it should return 11.
Algo :
Take the array, {2, -3, 4, -5, 6, -3, 8}
Compute the partial sums up to place i for all i, {2, -1, 3, -2, 4, 1, 9}
Subtract from each element the minimum that occurs earlier (or 0), {2,...
Implement N stacks using constant sized array(space). Until the array is completely filled, I should be able to push elements to any one of the N stacks.(i.e.)Do not reserve space for the stacks. And I should also be able to pop elements from any stack. Sounds very tricky. The idea is : Keep an array S of N pointer, where each Si.top will point to the top of the corresponding stack. And one global pointer gptr, which points to the next free location...
This is one of the nasty ones, if you don’t fully understand what “Inorder successor” is. The inorder successor is the next value in an inorder traversal of a binary search tree. So how do you find the inorder successor for the node U ? Algorithm : If node U has a right sub-tree, then the successor is the left most descendent of the right sub-tree....
There are four dogs, each at a corner of a large square. Each of the dogs begins chasing the dog clockwise from it. All of the dogs run at the same speed. All continuously adjust their direction so that they are always heading straight toward their clockwise neighbor. How long does it take for the dogs...
You are given an Array of N size. It contains 0 and 1 only. You have to arrange all 0s before all 1s (In the program you can’t travel more than once. Minimum complexity desired).Idea : Move a pointer left, from the front, until it encounters a 1Move a pointer right, from the end, until it encounters a 0Swap the elements at the two pointers (if they haven’t crossed)Repeat this for entire array – this is inplace and single pass.Code :public class swap01{...
Given a string of ASCII characters, write the write a program to remove the duplicate elements present in them. For example, if the given string is "Potato", then, the output has to be "Pota". Additional constraint is, the algorithm has to be in-place( no extra data structures allowed) Idea for an O(n) solution : Let’s start with ['a','b','a','c','a','a','d','b','c']
[i:j:'a','b','a','c','a','a','d','b','c'] – [0,0,0,0] (character map for a,b,c,d)...
I am sure you must know answer to this by now. Nevertheless, its very easy to miss the most valid answers to this which is the lesser known “Tortoise and Hare Algorithm” Solution with – O(n) time complexity Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single...
Given the values of two nodes in a binary search tree, we need to find the lowest common ancestor. You may assume that both values already exist in the tree.
I/P : 4 and 14 O/P : 8 (Here the common ancestors of 4 and 14, are {8,20}. Of {8,20}, the lowest one is 8). Algorithm:
The main idea of the solution is — While traversing Binary Search Tree from...
Problem : There are two sorted arrays A1 and A2. Array A1 is full where as array A2 is partially empty and number of empty slots are just enough to accommodate all elements of A1. Write a program to merge the two sorted arrays to fill the array A2. You cannot use any additional memory and expected run time is O(n). Solution: The trick to solving this...
Given two sorted Linked Lists, we need to merge them into the third list in sorted order. Complexity – O(n) Solution : public Node mergeList(Node a, Node b){ Node result = null; if(a==null) return b; if(b==null) return a; if(a.data <= b.data){ result =a; result.next = mergeList(a.next,b); } else { result =b; result.next = mergeList(b.next,a);...
Sometimes a code-segment is worth a thousand words. Understanding the MaxHeap and MinHeaps using Java code is very easy. Here is an implementation of both. MaxHeap : package bst;
import java.util.ArrayList;
import java.util.List;
public class BinaryHeap {
//ArrayList to hold the heap
List h = new ArrayList();
public BinaryHeap(){
}
//Constructs the heap - heapify
public BinaryHeap(int[] e) {
for(int i=0; i<e.length;i++)
...
Ah, this question has bugged me a lot. Finally I have found an answer to this. Actually there are two standard ways of doing this : a. Do a Euler Walk on the tree and get the RMQ algorithm to calculate the LCA – cool, but for Ph,D. Students. b. Create two array/linked list/queue and store DFS path to both the nodes and store them in these arrays. The...
You are given a number (either 32 or 64 bit)containing some bit pattern (or numeric value). You have to place all the 0s in even position and 1s in odd position and if suppose number of 0s exceed the number of 1s or vice versa then keep them untouched. Generalize your solution for an N bit number.
It has to be done in O(n) time, without several single loops (only one pass) and O(1)space.
For e.g.
Input Number: 0 1 1 0 1 0 1 0 1 1 1 0 0 1...
We have two linked lists which are merged at some point. We need to find the intersection.This shape is popularly known as Y-Shape intersection also.Finding of intersection can be done by several methods. Some of them are listed in this excellent article.We will discuss a simpler approach which works by getting the difference of the counts of elements...
The list shows above is a palindrome and we need to check if it is indeed a palindrome. Among several approaches, the following is a simple and easy to understand method. Algorithm: 1. Get the middle of the linked list. 2. Reverse the second half of the linked list. 3. Compare the first half and second half. 4. Construct the...
The list shown above contains a loop – from 5 its connected to 2. There are several incorrect and inefficient methods of finding a loop. The most efficient method is discussed here. Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as...
Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 Algorithm: 1. Create a temp string and store concatenation of str1 to str1 in temp. temp = str1+str1 2. If str2 is a substring of temp then str1 and str2 are rotations of each other. Example: str1 = "ABACD" str2 = "CDABA" temp = str1.str1 = "ABACDABACD"...
A very famous Microsoft Interview question : You have two candles. Each burn for 60 minutes. How can you measure 45 minutes using this ? Solution : lay both the candles together on a horizontal surface, next to each other, but both pointing in opposite direction as shown…. <======= =======> now light both the candles…. when both the flames on both candles meet , exactly half an hour would hav passed… now the candles should look like…...
Subscribe to:
Posts (Atom)