Anagram program implentation
Posted on January 6, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
#include using namespace std; #include "anaword.h" static const int ALPH\_SIZE = 26; Anaword::Anaword(const string & word) : myWord(word), myCounts(ALPH\_SIZE,0) // postcondition: constructed { normalize(); } Anaword::Anaword() : myWord(""), myCounts(ALPH\_SIZE,0) { } void Anaword::normalize() // postcondition: myCounts represents the letter signture of myWord { } string Anaword::toString() const // postcondition: return "bagel" or "gable", regular form of string { return myWord; } ostream & operator << (ostream & out, const Anaword & a) // postcondition: a printed t stream out, out returned { out << a.
[Read More]Finding whether 2 arrays are intersecting
Posted on January 5, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Here are 2 arrays:
**A1 1 8 7 5 6
A2 0 9 6 4 2
**
**These two are intersecting at 6.
Complexity? **
Solution:
This can be solved using Hash Tables.
Take 1 Hash Table.
Insert elements from A1 in Hast Table as key and put value in front of them
(In case elemente get repeated increment the value count).
Now traverse the second array A2 and check for element as a key.
[Read More]Convert integer into a binary number
Posted on January 5, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
This code will print the binary number for the integer num:
void generatebits(int num) { int temp; if(num!=0) { temp = num % 2; generatebits(num >>= 1); printf("%d",temp); } } int main() { int num; printf("\\nEnter a number\\n"); scanf("%d", &num); printf("\\n\\n"); generatebits(num); return(0); } Writing a function to convert integer to bits-string
For example, if input is 2, the output is “00000000000000000000000000000010” if the system is 32-bit, “0000000000000010” if the system is 16-bit and so on.
[Read More]Binary search on Array - Recursive and iterative
Posted on January 5, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
There are two basic searching algorithms used. One is the simplest technique and is discussed here.
Here we will discuss the binary search method.
The other search method is the binary search method. The binary search technique is a very fast and a more efficient technique when compared to the linear search method, and gets us the result in O(log n) where n is number of elements. The only requirement for this method is that the input array of elements must be in the sorted order.
[Read More]Euclid's Algorithm : GCD of 2 integers
Posted on January 5, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The following example solves a classic elementary problem: “Reduce a given fraction to its lowest terms”, e.g. we want to write 2/3, not 4/6. We solve this problem by finding the greatest common divisor (gcd) of the numerator and the denominator by using the famous approach called Euclid’s algorithm.
C Code
Iterative solution
// Iterative algorithm int gcd(int a, int b) { int temp; while(b) { temp = a % b; a = b; b = temp; } return(a); } Recursive solution
[Read More]Given an array of n integers from 1 to n with one integer repeated twice
Posted on January 5, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem - Given an array of n integers from 1 to n with one integer repeated twice
This can be done via normal array traversal or hash table to find duplicates. But since we are given that the integers are from 1 to n, then there are better methods available.
Approach 1 - Arithmetic sum approach
So, the efficient method to solve it calculate the sum of actual input array, and expected sum of the array.
[Read More]Data Structures Interview Questions (Theoritical)
Posted on January 4, 2010
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
1) What is the difference between Storage structure and file structure?
The representation of a particular data structure in the memory of a computer is called a storage structure whereas a storage structure representation in auxiliary memory is often called a file structure.
2) Define data structure in terms of relation?
The possible ways in which the data items or atoms are logically related define different data structures.
3) State procedure in accordance with function?
[Read More]Basic Mathematics in Algorithms
Posted on January 3, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Recurrence Relations
Recurrence relations often arise in calculating the time and space complexity of algorithms. The amount of time (or space) that a program takes, Tk, is typically a function of the size, k, of the input data. A recurrence relation arises when Tk is some function of Tk’ for k’
Logarithmic Complexity
The following recurrence
**Tk = Tk/2 + a if k!=1
= b if k=1
**
has the solution
[Read More]Given a list of n numbers from 1 to n-1, with one of the numbers repeated. Devise a method to determine which number is repeated
Posted on January 3, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The sum of the numbers 1 to n-1 is (n)(n-1)/2. Add the numbers on the list, and subtract (n)(n-1)/2. The result is the number that has been repeated.
Give a fast way to multiply a number by 7
Posted on January 3, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Multiply by 8 (left shift by 3 bits) and then subtract the number.