swapnilsj
BAN USERint maxConsecutiveLen(vector<int>& arr){
map<int,int> pos;
for(int i = 0; i < arr.size(); i++){
pos[arr[i]] = i;
}
int maxcount(0), count(0);
auto p = pos.begin();
for(auto i = pos.begin(); i != pos.end(); i++){
if(i->first - p->first == 1){
count++;
}
else{
maxcount = max(maxcount, count);
count = 0;
}
p = i;
}
return maxcount+1;
}
Node* rearrangeLinkedList(Node* head){
Node* slow = head;
Node* fast = head;
// find the middle node
while(fast and fast->next and fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
// Reverse the second half
Node *prev = NULL, *nxt = NULL, *curr = slow->next;
while(curr){
nxt = curr->next;
curr->next = prev;
prev = curr;
curr = nxt;
}
// prev is pointing to the first node of reversed half part of
// original linked list
slow->next = NULL; // terminate first half
Node *odd = head, *even = prev, *oNext = *eNext = NULL;
while(odd and even){
oNext = odd->next;
eNext = even->next;
odd->next = even;
even->next = oNext;
odd = oNext;
even = eNext;
}
return head;
}
Size of ordering string = m
Size of input string = n
Time Complexity = O(n) + O(m) == O(n+m)
Space complexity = O(min(n, 26))
bool checkOrder(string in, string order) {
unordered_map<char, int> pos;
for(int i = 0; i < in.size(); i++){
pos[in[i]] = i;
}
for(int i = 1; i < order.size(); i++){
if(pos[order[i]] - pos[order[i-1]] < 0){
return false;
}
}
return true;
}
Size of ordering string = m
Size of input string = n
Time Complexity = O(n) + O(m) == O(n+m)
Space complexity = O(min(n, 26))
bool checkOrder(string in, string order) {
unordered_map<char, int> pos;
for(int i = 0; i < in.size(); i++){
pos[in[i]] = i;
}
for(int i = 1; i < order.size(); i++){
if(pos[order[i]] - pos[order[i-1]] < 0){
return false;
}
}
return true;
}
unsigned int reverseBits(unsigned int x){
x = ((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1);
x = ((x & 0xCCCCCCCC) >> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xF0F0F0F0) >> 4) | ((x & 0x0F0F0F0F) << 4);
x = ((x & 0xFF00FF00) >> 8) | ((x & 0x00FF00FF) << 8);
x = (x << 16) | (x >> 16);
return x;
}
// Write a function void DrawRectangle(char *Screen, int x1, int y1, int
// x2, int y2). Height and width of the monitor is known. To set a pixel,
// you need to set that particular bit of the screen.
// Pixels for 1080p (FULL HD screen) -- 1920x1080
#define WIDTH 1920
#define HEIGHT 1080
void DrawRectangle(char *Screen, int x1, int y1, int x2, int y2){
for (size_t i = x1; i <= x2; i++) {
for (size_t j = y1; j <= y2; j++) {
if(j == y1 || j == y2 || i == x1 || i == x2){
Screen[WIDTH * j + i] = 0xFF;
}
}
}
}
O(n) solution (ignoring sorting)
int maxLenConsNums(vector<int>& arr){
if(arr.size() <= 1) return arr.size();
sort(arr.begin(), arr.end());
int maxLen = 0, currLen = 0;
int i = 1;
while(i < arr.size()){
int diff = arr[i] - arr[i-1];
if(diff == 1){
currLen++;
}
else if(diff != 1){
maxLen = max(maxLen, currLen);
currLen = 0;
}
i++;
}
return maxLen+1;
}
The way you are accessing the derived class objects in the display function makes you get "1" instead "0". This is because you are incrementing the pointer to the derived class object(8 bytes) in steps of size of base class object(4 bytes). Hence when pointer to derived class object is incremented second time, it is pointing to variable b of first element of array of derived class object.
when der arrd[i] is called, below is memory footprint of this array:
arrd[0].a = 0 (offset 0 bytes)
arrd[0].b = 1 (offset 4 bytes)
arrd[1].a = 0 (offset 8 bytes)
arrd[1].b = 1 (offset 12 bytes)
arrd[2].a = 0 (offset 16 bytes)
arrd[2].b = 1 (offset 20 bytes)
The solution is to declare the getA function as virtual forcing the increment of derived class object by size of derived class object.
- swapnilsj July 13, 2016
- swapnilsj August 21, 2016