## moiskim

BAN USER1. sort the elements in g.

2. traverse the tree in in-order. Since in-order traverses each node from smallest to the biggest in ascending order, both g, the each node in in-order traverse should be the same.

so

int g[] = { 2,3,4,3,1,0}

quicksort( g );

and call inorder( node);

bool inorder( node* hd)

{

static int n = 0;

if ( hd->left) inorder( hd->left);

if (g[n++] != hd->data)

return false ;

if ( hd->right) inorder( hd_>right);

}

quicksort

there are two things to think about.

First, we need to generate 6 subsets(if n is 4) 1,2 1,3 1,4 2,3 2,4 3,4

For each subset, we need to make a combination for b-z.

So, if you see the code below, the first subset is 1,2 and the first character in c and d are 'b' and 'b'.

so 1. => b, b, a, a

2 = b, c, a, a

.... and so on.

void subsetperm( int n)

{

for ( int i = 0 ; i < n ; i++)

for ( int j = i; j < n ; j++)

{

for ( char c = 'b'; c <= 'z' ; c++)

for ( char d = 'b'; d <= 'z' ; d++)

{

char* sResult = malloc( n+1);

strcpy ( sResult, "aaaaaaaaaa");

sResult[i] = c;

sResult[j] = d;

printf(sResult);

}

}

}

The solution from sd should work fine and it is very creative.

Another solution can be,

1. It will create a duplicate linked list. But ->next of the original list will point equivalent node in the new linkedlist.

node* pOld = head;

node* pNew = Null;

node* pNewTail = Null;

while (pOld)

{

if (pNewTail == null)

{ pNew=pNewTail = new node; pNew->val = pOld->val; }

else

{

pNewTail->next = new node;

pNewTail->next->val = pOld->val;

pNewTail = pNewTail->next;

}

node* pCurrent = pOld;

pOld = pOld->next;

pCurrent = pNewTail;

}

2. Then update random pointer of the new linkedlist

node* pOld = head;

while (pOld)

{

pNew->random = pOld->random->next;

pNew = pNew->next;

pOld = pOld->next;

}

int GetRep( char *s)

{

char c = *s;

int n =0;

while ( c == *s)

{

s++; n++;

}

return n;

}

pair<int, int>LargestBlock( char * s)

{

int nTmpPos = 0;

int nTmpSize = GetRep( s+nTmpPos);;

int nLPos = nTmpPos;

int nLSize = nTmpSize;

while(true)

{

nTmpPos += nTmpSize;

nTmpSize = GetRep( s+nTmpPos);

if (nTmpSize > nLSize)

{

nLPos = nTmpPos ;

nLSize = nTmpSize;

}

if (!s[nTmpPos + nTmpSize])

{

pair<int , int> pRtn;

pRtn.first = nLPos;

pRtn.second = nTmpSize;

return pRtn;

}

};

pair<int,int> FindMinMax( int* ary)

{

int nMin = *ary;

int nMax = *ary;

while(true)

{

if (!*ary)

break;

if ( nMin > *ary)

{

nMin = *ary;

}

ary++;

if (!*ary)

break;

if ( nMax < *ary)

{

nMax = *ary;

}

ary++;

}

pair<int,int> nRet;

nRet.first = nMin;

nRet.second = nMax;

return nRet;

}

// Generate all palindrom date in the form of MMDDYYYY

bool bPalindrom( char* s)

{

return s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4];

}

void genpalindromDate()

{

char date[9];

int numofMon[] = { 31, 30, 29, 30, 31, 31, 30, 31, 30, 31};

for ( int m = 1 ; m <= 12 ; m++)

for ( int d = 1 ; d <= numofMon[m-1] ; d++)

for ( int y = 1000 ; y <= 2001 ; y++)

{

sprintf( date,"%02d%02d%04d", m, d, y);

if (bPalindrom(date) )

printf("%s :", date);

}

}

Same idea as above but way simpler.

#define NUMWIDTH 7

char sary[][5] = {"abc\0","def\0","ghi\0","jkl\0","mno\0", "pqrs", "tuv\0", "wxyz"};

char getChar(int nNum, int nPos)

{

return sary[nNum-2][ nPos];

}

char getLen(int nNum)

{

return strlen(sary[nNum-2]);

}

void telephoneword( int nPos, string s)

{

if ( nPos ==NUMWIDTH)

{

printf("\t %s", s.c_str());

}

else

for ( int i = 2 ; i < 10 ; i++)

{

for ( int j=0; j < getLen(i) ; j++)

telephoneword( nPos + 1, s + getChar(i, j));

}

}

telephoneword( 0, "");

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

- moiskim June 21, 2017