CareerCup

Haroud, Mostly you will find the answer to 999. But I feel the intent here is to check for the possibility rather than finding the answer. Probably the guy wanted to check what you think of this code, so its kind of open-ended question.

Hi Florian

Can sleep prohibit the compiler from optimizing. I have seen code like :

while(true) { sleep(0); }

to prevent compiler from removing the while loop completely.

But in this case I am curious if the compiler can optimize the code to something like :


void SomeRunningFunction()
{
for(int i = 1; i < 1000; ++i)
{
sleep(2000);
}
}

and setting *sharedmemoryaddress to 999 at compiler time.

#include <iostream>

using namespace std;

struct List
{
    List(const string &str) 
    : mStr(str), mpNext(NULL) {}
    string mStr;
    List *mpNext;
};
  
int GetListLen(List *pCur)
{
    int count = 0;
    while(pCur)
    {
        count += pCur->mStr.size();
        pCur = pCur->mpNext;
    }
    return count;
}
    
bool IsPalindrome(List *pHead)
{
    if(pHead == NULL)
    {
        return false;
    }
    
    int len = GetListLen(pHead);
    
    List *pCur = pHead;
    List *pPrev = NULL;
    
    for(int i = 0; i < len;)
    {
        List *pNext = pCur->mpNext;
        int newLen = i + pCur->mStr.size();
        if(newLen > (len / 2)) /* Start reversing the list after len/2 + 1 */
        {
            pCur->mpNext = pPrev;           
        }
        
        i = newLen;
        pPrev = pCur;
        pCur = pNext;
    }
    if(pPrev == NULL)
    {
        return false;
    }
    
    List *pLeft = pHead;
    List *pRight = pPrev;
    
    int leftIndex = 0;
    int rightIndex = pPrev->mStr.size() - 1;
      
    bool isPalin = true;
    for(int i = 1; i <= len / 2; ++i)
    {
        if(pLeft->mStr[leftIndex] != pRight->mStr[rightIndex])
        {
            isPalin = false;
            break;
        }
        leftIndex++;
        rightIndex--;
        
        if(leftIndex == pLeft->mStr.size())
        {
            pLeft = pLeft->mpNext;
            leftIndex = 0;
        }
        
        if(rightIndex == -1)
        {
            pRight = pRight->mpNext;
            rightIndex = pRight->mStr.size() - 1;
        }
    }
    return isPalin;
    
}

int main()
{
    List *pHead = NULL;
    List *pCur = NULL;
    string str[] = {"ab", "c", "de", "eee", "dcb", "a"};
    
    for(int i = 0; i < 6; ++i)
    {
        List *pNew = new List(str[i]);
        if(pCur == NULL)
        {
            pHead = pNew;
        }
        else
        {
            pCur->mpNext = pNew;
        }
        pCur = pNew;
    }
    
    cout << IsPalindrome(pHead) << endl;
    getchar();
    return 0;
}

#include <iostream>

using namespace std;

struct LinkList
{
    LinkList(char ch) : mCh(ch), mpNext(NULL) {}
    char mCh;
    LinkList *mpNext;
};

int Count(LinkList *p1, LinkList *p2)
{
    int count = 0;
    while((p1 && p2) && (p1->mCh == p2->mCh))
    {
        count++;
        p1 = p1->mpNext;
        p2 = p2->mpNext;
    }
    return count;
}

int GetMaxPalindrome(LinkList *pHead)
{
    if(pHead == NULL)
    {
        return 0;
    }
    
    int count = 0;
    LinkList *p1 = pHead;
    LinkList *pPrev = NULL;
    while(p1)
    {
        LinkList *p2 = p1->mpNext;
        p1->mpNext = pPrev;
        count = max(count, max(Count(p1, p2) * 2 , 
                    Count(p1->mpNext, p2) * 2 + 1));
        pPrev = p1;
        p1 = p2;
    }

    p1 = pPrev;
    pPrev = NULL;
    while(p1)
    {
        LinkList *p2 = p1->mpNext;
        p1->mpNext = pPrev;
        pPrev = p1;
        p1 = p2;
    }
   
    return count;
}

int main()
{
    string sample = "12121213";
    LinkList *pHead = NULL;
    LinkList *pCur = NULL;
    
    for(int i = 0; i < sample.size(); ++i)
    {
        LinkList *pTemp = new LinkList(sample[i]);
        if(pCur != NULL)
        {
            pCur->mpNext = pTemp;
        }
        else
        {
            pHead = pTemp;
        }
        pCur = pTemp;
    }
    
    
    cout << GetMaxPalindrome(pHead);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int GetCount(vector<int> &file, int start, int end, const int val)
{
    if((start > end) || (file[start] > val) || (file[end] < val))
    {
        return 0;
    }
    
    if(file[start] == file[end] && file[end] == val)
    {
        return end - start + 1;
    }
    
    int mid = (start + end) / 2;
    return GetCount(file, start, mid - 1, val) 
        + GetCount(file, mid + 1, end, val) 
        + (file[mid] == val ?  1 : 0);
}
    

int GetCount(vector<int> &file, int memLimit, const int val)
{
    int sum = 0;
    for(int offset = 0; offset < file.size(); offset += memLimit)
    {
        sum += GetCount(file, 
                                     offset, min(offset + memLimit, 
                                     (int)file.size()) - 1, 
                                      val);
    }
    return sum;
}

int main()
{
    vector<int> file;
    
    for(int i = 0; i <= 20; ++i)
    {
        file.push_back(i);
    }
    
    file[10] = 10;
    file[11] = 10;
    file[12] = 10;
    file[13] = 10;
    
    for(int i = 0; i <= 20; ++i)
    {
        cout << file[i] << " " ;
    }
    
    cout << endl << "Count = " << GetCount(file, 7, 10);
    getchar();
    return 0;
}

#include <iostream>

using namespace std;

int Tokenize(const string &str, int idx, const char ch, int &val)
{
    int i = idx;
    int v = 0;
    while(i < str.size() && str[i] != ch)
    {
        v = v * 10 + str[i] - '0';
        i++;
    }
    val = v;
    return i;
}

int Sum(const string &str)
{
    int maxSum = 0;
    int i = -1;
    int len = 0;
    int size = str.size();
    
    while(i < size)
    {
        ++len;
        int count = len;
        int localMax = 0;
        bool isInvalid = false;
        while((count != 0) && (++i < size))
        {
            int val = 0;
            int idx = Tokenize(str, i, '#', val);
            if(idx == i)
            {
                isInvalid = true;
                break;
            }
            
            localMax = max(localMax, val);
            count--;
            i = idx;
        }
        
        if(count == 0)
        {
            maxSum += localMax;
        }
        else
        {
            throw "Invalid";
        }
    }
    return maxSum;
}

int main()
{
    try
    {
        cout << Sum("15#9#6#4#6#8#0#7#1#5");
    }
    catch(const char *pEx)
    {
        cout << pEx;
    }
    getchar();
    return 0;
}

Provided before executing Next() or Peek(), you will check HasNext()

class CPeekIterator : CIterator
{
    public:
	   CPeekIterator() : nextVal(false)
	   {
	   }
       virtual int Next()
       {
		if(hasNext)	
		{	
			hasNext = false;
			return nextVal;
		}
		return CIterator::Next();
        }		
        virtual int peek()
        {
		if(!hasNext)
		{
			hasNext = true;
			nextVal = CIterator::next();
		}		
		return nextVal;
	}   
	virtual int HasNext() const
	{
		return hasNext ? true : CIterator::HasNext();
	}		 		 	
    private:
	int nextVal;
	bool hasNext;
};

You are not taking into account points per minute.

Also "thisTask" has been wrongly computed.

#include <iostream>
using namespace std;

struct node {
	int val;
	node *left, *right;
};

node *createnode(int val) {
	node *n = new node;
	n->val = val;
	n->left = n->right = nullptr;
	return n;
}

node* findsib(node *root, int lev) {
	if(root == nullptr)
		return nullptr;
	if(lev == 0)
		return root;
	node *ret = findsib(root->left, lev - 1);
	if(ret == nullptr)
		ret = findsib(root->right, lev - 1);
	return ret;
}

int util(node *root, node *target, node* (&sib)) {
	if(root == nullptr)
		return -1;
	if(root == target) {
		return 1;
	}
	int ret = util(root->left, target, sib);
	if(ret != -1) {
		if(sib == nullptr) {
			sib = findsib(root->right, ret- 1);
		}
		return ret + 1;
	}
 	ret = util(root->right, target, sib);
 	if(ret != -1) {
 		if(sib == nullptr) {
 			sib = findsib(root->left, ret - 1);
 		}
 		ret + 1;
 	}
 	return -1;
}

node *Find(node *root, node* target) {
	if(target == nullptr)
		return nullptr;
	node *sib = nullptr;
	util(root, target, sib);
	return sib;
}


int main() {
	// your code goes here
	node *root = createnode(1);
	root->left = createnode(2);
	root->right = createnode(3);
	root->right->right = createnode(10);
	root->left->left = createnode(4);
	//root->left->right = createnode(5);
	node *target = root->left->left;
	node *sib = Find(root, target);
	if(sib)
		cout << "Target node = " << sib->val;
	else cout << "Not found";
	return 0;
}

Solution using queues

#include <iostream>
#include <queue>

using namespace std;

#define SIZE 5

int GetMax(int arr[SIZE][SIZE]) {
	queue<int> s1, s2;
	queue<int> *p1 = nullptr, *p2 = nullptr;
	int mx = 0;
	s1.push(arr[0][0]);
	for(int i = 1; i < SIZE; ++i) {
		p1 = &s1;
		p2 = &s2;
		int count = p1->size();
		if(count == 0)
			swap(p1, p2);
		count = p1->size();
		for(int j = 0; j < count; ++j) {
			int val = p1->front();
			p1->pop();
			int tmp;
			tmp = val + arr[i][j];
			mx = max(mx, tmp);
			p2->push(tmp);
			tmp = val + arr[i][j + 1];
			mx = max(mx, tmp);
			p2->push(tmp);
		}
	}
	return mx;
}

int main() {
	int arr[SIZE][SIZE] = {
		{1,  0,  0,  0, 0},
		{2,  1,  0,  0, 0}, 
		{1,  3,  5,  0, 0},
		{6,  10, 8,  4, 0},
		{3,  5,  7,  1, 9}
	};
	
	cout << GetMax(arr);
	return 0;
}

Please rply if it failing in any scenario:

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

bool EditDistance(const string &s1, const string &s2){
	int diff = s1.size() - s2.size();
	if(abs(diff) > 1)
		return false;
	int i = 0, j = 0, count = 0;
	while((i < s1.size()) && (j < s2.size())) {
		if(s1[i] == s2[j]) {
			i++, j++;
		}
		else if(s1.size() == s2.size()) {
			i++, j++, count++;
		}
		else if(s1.size() > s2.size()) {
			i++, count++;
		}
		else {
			j++, count++;
		}
		if(count > 1)
			return false;
	}
	count += s1.size() - i + s2.size() - j;
	return (count == 1);
}
int main() {
	cout << boolalpha << EditDistance("d", "a");
	return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int EditDistance(const string &s1, const string &s2){
	vector<vector<int> > dp(s1.size() + 1, vector<int>(s2.size() + 1));
	
	for(int i = 0; i < dp[i].size(); ++i) {
		dp[0][i] = i;
	}
	
	for(int i = 0; i < dp.size(); ++i) {
		dp[i][0] = i;
	}
	
	for(int i = 1; i < dp.size(); ++i){
		for(int j = 1; j < dp[i].size(); ++j){
			int del = dp[i][j - 1] + 1;
			int ins = dp[i - 1][j] + 1;
			int rpl = dp[i - 1][j - 1] + (s1[i - 1] != s2[j - 1]);
			dp[i][j] = min(del, ins);
			dp[i][j] = min(dp[i][j], rpl);
		}
	}
	return dp[dp.size() - 1][dp[0].size() - 1];
}

int main() {
	cout << boolalpha << (EditDistance("abc", "afgr") == 1);
	return 0;
}

#include <iostream>
#include <string.h>
using namespace std;

bool isValid(const char *str) {

	int len = strlen(str);
	bool valid = true;
	int numCount = 0, dotCount = 0;

	for(int i = 0; i < len;) {
		
		int j = i;
		
		int num = 0;

		if(numCount == 4) {
			valid = false;
			break;
		}

		for(; j < len; ++j) {
			if(str[j] < '0' || str[j] > '9')
				break;
			num = num * 10 + (str[j] - '0');
		}
		if((j == i) || (num < 0) || (num > 255)) {
			valid = false;
			break;
		}
		
		numCount++;
		
		if(j < len) {
			if((str[j] != '.') || ((str[j] == '.') && (dotCount == 3))) {
				valid = false;
				break;
			}
			else 
				dotCount++;
			j++;
		}
		
		i = j;
	}
	if((numCount != 4) && (dotCount != 3))
		valid = false;
	return valid;
}

int main() {
	cout << boolalpha << isValid("255...") << endl;
	cout << boolalpha << isValid("255.255.255. 255") << endl;
	cout << boolalpha << isValid(".") << endl;
	cout << boolalpha << isValid(".255.255.t") << endl;
	return 0;
}

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;


void Merge(vector<int> &v1, vector<int> &v2, vector<int> &v3, vector<int> &output) {
	
	int tsize = v1.size() + v2.size() + v3.size();
	output.resize(tsize);
	
	vector<int> indices;
	indices.push_back(v1.size() - 1);
	indices.push_back(v2.size() - 1);
	indices.push_back(v3.size() - 1);
	
	int oi = tsize - 1;
	while(indices[0] >= 0 || indices[1] >= 0 || indices[2] >= 0) {
		int mx = -1;
		int i = -1;
		if(indices[0] >= 0) {
			i = 0;
			mx = v1[indices[i]];
		}
		if((indices[1] >= 0) && (mx < v2[indices[1]])) {
			i = 1;
			mx = v2[indices[i]];
		}
		if((indices[2] >= 0) && (mx < v3[indices[2]])) {
			i = 2;
			mx = v3[indices[i]];
		}
		output[oi--] = mx;
		//cout << "mx = " << mx << endl;
		indices[i]--;
	}
	
}

int main() {
	vector<int> v1 = {3, 6, 9, 10, 14, 16, 18, 29};
	vector<int> v2 = {1, 5, 7, 11, 14, 19, 23};
	vector<int> v3 = {2, 3, 4, 5};
	vector<int> output;
	Merge(v1, v2, v3, output);
	for(auto i : output)
		cout << i <<  " ";
	return 0;
}