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.
Given a pointer to a node in a singly linked list, how do you delete the node ?
A simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires pointer to the head node which contradicts the problem statement.
Fast solution is to copy the data from the next node to the node to be deleted and delete the next node. Something like following.
struct node *temp = node_ptr->next;
...
Wednesday, June 30, 2010
Find vertical sum of given binary tree. Example: Code: 1 / \ 2 3/ \ / \4 5 6 7 The tree has 5 vertical linesVertical-1: nodes-4 => vertical sum is 4Vertical-2: nodes-2 => vertical sum is 2Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12Vertical-4: nodes-3 => vertical sum is 3Vertical-5: nodes-7 => vertical sum is 7We need to output: 4 2 12 3 7 We can do an inorder traversal and hash the column....
Write a program to shuffle an pack of cards in the most efficient way. This question can be asked in several flavors.
Knuth Shuffle / Fisher-Yates Shuffle(Modified version by Durstenfeld) algorithm is the answer to all the trick questions. So how does this algorithm work ?
Fisher and Yates’ original method was designed to be implemented using pencil and paper, with a precomputed table of random numbers as the source of randomness. Modern...
Saturday, May 8, 2010
I got this tutorial from one site its very helpful hence shared here..... :)This tutorial show coding how to connect with a database in C++….This are actual guidesNote:QuoteBefore I start just to introduce some SQL commands and stuff. For starter you had some back grounds on it….SQL (Structured Query Language) is a fourth-generation language (4GL) that is used to define, manipulate, and control an RDBMS (relational database management system).DML...
Thursday, April 8, 2010
This is a well known problem where given any two traversals of a tree such as inorder & preorder or inorder & postorder or inorder & levelorder traversals we need to rebuild the tree. The following procedure demonstrates on how to rebuild tree from given inorder and preorder traversals of a binary tree: Preorder traversal visits...
Design a datastructure to implement a stack such that ALL of push(), pop() and getMax() functions work in O(1) time. You have infinite memory at your disposal. Also note that function getMax() just returns the element with maximum value in the stack and NOT delete it from the stack like what pop() does. Insight : compress the information using diffPUSH :if stack emptypush(elem)push(elem)elsemin = pop()push(elem-min)push(min)POP :min =...
Sunday, March 28, 2010
In file1.cwe have static int i = 5;and int *ptr = &i;now value of ptr is written in some file say abc.txtnow file2.c (another program) opens abc.txtread the valueand print the value loacted at dat adress saywhat will be the o/p????example i = 5;ptr = &i; ptr has now 0xABFF0xABFF is written in abc.txtfile2.c opens the abc.txt and read the value 0xABFFnow print the value present at this addresswaht it will print????ANSWER:A program has nothing...
The solution is to iterate down the list looking for the correct place to insert the new node. That could be the end of the list, or a point just before a node which is larger than the new node.Note that we assume the memory for the new node has already been allocated and a pointer to that memory is being passed to this function.// Special case code for the head endvoid linkedListInsertSorted(struct node** headReference, struct node* newNode){...
When a program is loaded into memory, it is organized into three areas of memory, called segments: the text segment, stack segment, and the heap segment. The text segment (sometimes also called the code segment) is where the compiled code of the program itself resides. This is the machine language representation of the program steps to be carried out, including all functions making up the program, both user defined and system.The remaining...
Most compilers recognized the file type by looking at the file extension.You might also be able to force the compiler to ignore the file type by supplying compiler switch. In MS VC++ 6, for example, the MSCRT defines a macro, __cplusplus. If you undefine that macro, then the compiler will treat your code as C code. You don't define the __cplusplus macro. It is defined by the compiler when compiling a C++ source. In MSVC6 there's a switch for the...
Linkage is used to determine what makes the same name declared in different scopes refer to the same thing. An object only ever has one name, but in many cases we would like to be able to refer to the same object from different scopes. A typical example is the wish to be able to call printf() from several different places in a program, even if those places are not all in the same source file.The Standard warns that declarations which refer to the...
This questions is asked almost always in every interview.The best way to swap two variables is to use a temporary variable.int a,b,t;t = a;a = b;b = t;There is no way better than this as you will find out soon. There are a few slick expressions that do swap variables without using temporary storage. But they come with their own set of problems.Method1 (The XOR trick)a ^= b ^= a ^= b;Although the code above works fine for most of the cases, it tries...
A sorting program that sorts items that are on secondary storage (disk or tape) rather than primary storage (memory) is called an external sort. Exactly how to sort large data depends on what is meant by ?too large to fit in memory.? If the items to be sorted are themselves too large to fit in memory (such as images), but there aren?t many items, you can keep in memory only the sort key and a value indicating the data?s location on disk. After the...
Both Merge-sort and Quick-sort have same time complexity i.e. O(nlogn). In merge sort the file a[1:n] was divided at its midpoint into sub-arrays which are independently sorted and later merged. Whereas, in quick sort the division into two sub-arrays is made so that the sorted sub-arrays do not need to be merged latter....
A Heap is an almost complete binary tree.In this tree, if the maximum level is i, then, upto the (i-1)th level should be complete. At level i, the number of nodes can be less than or equal to 2^i. If the number of nodes is less than 2^i, then the nodes in that level should be completely filled, only from left to right.The property of an ascending heap is that, the root is the lowest and given any other node i, that node should be less than...
Great C datastructure question!The answer is ofcourse, you can write a C program to do this. But, the question is, do you really think it will be as efficient as a C program which does a binary search on an array?Think hard, real hard.Do you know what exactly makes the binary search on an array so fast and efficient? Its the ability to access any element in the array in constant time. This is what makes it so fast. You can get to the middle...
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)....
A SQL JOIN clause combines records from two or more tables in a database. It creates a set that can be saved as a table or used as is. A JOIN is a means for combining fields from two tables by using values common to each. ANSI standard SQL specifies four types of JOINs: INNER, OUTER, LEFT, and RIGHT. In special cases, a table (base table, view,...
Wednesday, March 17, 2010
A majority element in an array A, of size N is an element that appears more than N/2 times (and hence there is atmostone such element)Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:I/P : 3 3 4 2 4 4 2 4 4O/P : 4I/P : 3 3 4 2 4 4 2 4O/P : NONEObvious answer is create a binary search tree. When you get one element insert it. If the element exists increase count by one in the node....
Saturday, February 27, 2010
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";/*...
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++)
...
Subscribe to:
Posts (Atom)