Time complexity:
Worst-case: \(O(nlog(n))\)
Best-case: \(O(nlog(n))\)
Average-case: \(O(nlog(n))\)
Merge sort divides the array in half, sorts each of those halves, and them merges them back together.
Sorting – Merge Sort
Reply
Sorting – Selection Sort
Time complexity:
Worst-case: \(O(n^2)\)
Best-case: \(O(n^2)\)
Average-case: \(O(n^2)\)
Find the smallest element and move it to the front. Then, find the second smallest and move it.
Sorting – Bubble Sort
Time complexity:
Worst-case: \(O(n^2)\)
Best-case: \(O(n)\)
Average-case: \(O(n^2)\)
Sort array elements in ascending order. If the first element is greater than the second element, swap the first two elements.
Then, we go to the “next pair” and so on.
C Pointer
Pointer Related: Array, Structure, Single Pointer (*), Double Pointer (**), Reference (&)
Common Bit Manipulation
bool getBit(int num, int shift)
{
return ( (num & (1 << shift)) != 0);
}
int setBit(int num, int shift)
{
return ( num | (1 << shift));
}
int clearBit(int num, int shift)
{
int mask = ~ (1 << shift);
return num & mask;
}
int clearBitMSBthroughShiftBit(int num, int shift)
{
int mask = (1 << (shift )) -1;
return num & mask;
}
int clearBitMSBthroughShift0(int num, int shift)
{
int mask = ~ ((1 << (shift +1 )) -1);
return num & mask;
}
int updateBit(int num, int shift, int v) //set i-th bit = v
{
int mask = ~ (1 << shift);
return (num & mask) | (v << shift);
}
Check Little Endian or Big Endian
int val = 0x0D0C0B0A;
char c = *((char *)(&val));
if (c == 0x0A)
cout<< "little endian machine"<<endl;
else if(c == 0x0D)
cout<< "big endian machine"<<endl;
CTCI: Ch. 5-3
Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.
CTCI: Ch. 5-2
Given a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with less than 32 characters, print “ERROR.”
CTCI: Ch. 5-1
You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i.
You can assume that the bits j through I have enough space to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i.
You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.
Chapter 5. Bit Manipulation
-
You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i. You can assume that the bits j through I have enough space to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.
EXAMPLE
Input: N = 10000000000, M = 10011, i = 2, j = 6
Output: N = 10001001100
Continue reading