## peng

BAN USERMy name is Peng Liu

I am a master student major in Computer Science in Syracuse University, Syracuse, NY. I am looking for a full time job in 2013

My email : pengliu1989@gmail.com

My email : pengliu1989@gmail.com

Set a flag to do the reverse and traverse recursively

Node * rever(Node *n, int k, int m,int flag)

{

if(n==NULL)

return NULL;

if(flag==0) // do the reverse

{

Node *pre=n;

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

{

if(pre->next !=NUL)

{

Node *tmp=pre->next;

tmp->next=pre;

pre=tmp;

}

else

{

n->next=NULL;

return pre;

}

}

flag=1;

n->next=rever(pre->next,k,m,flag);

return pre;

}

else // do the traverse

{

Node *head=n;

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

{

if(n!=NULL)

n=n->next;

}

flag=0;

n->next=rever(n->next,k,m,flag);

return head;

}

}

an implementation of Cyrus's idea

bool findIt( queue<Node *> qu. Node *head, Node *n)

{

if(head==NULL)

return false;

if(head==n)

return true;

if(findIt(qu,head->left,n))

{

st.push(head->left);

return true;

}

if(findIt(qu,head->right,n))

{

st.push(head->right);

return true;

}

return false;

}

void search(Node *head, int num, int k)

{

if(head==NULL)

return NULL;

if(num==k)

cout<<head<<endl;

while(num<k)

{

search(head->left,num+1,k);

search(head->right,num+1,k);

}

}

void find(Node *head, Node *n, int k)

{

queue<Node *> qu;

bool check=findIt(st,head,n);

if(!check)

return ;

Node *pre=n;

for(int i=1; i<=k;i++)

{

Node *tmp= qu.front();

qu.pop();

if(i==k)

{

count<<*tmp<<endl;

return;

}

if(pre==tmp->left)

{

pre=tmp;

search(tmp->left,i+1);

}

if(pre==tmp->right)

{

pre=tmp;

search(tmp->right,i+1);

}

}

}

If the number of integers are not too large. I will make an hash table to record every integer is contained by which sets.

for example :

s1 {1,2,3,4}

s2 {3,4,5,6,7}

s3 {7,8,9}

s4 {6,11}

The hash table will be like

integer : 1-------2-------3-------4-------5-------6-------7-----------8-------9-------11

sets: ----s1-----s1---s1,s2 ---s1,s2----s2-----s2,s4--s2,s3-----s3-----s3-----s4

integer : 3-------4----------6-------7

sets: --s1,s2---s1,s2---s2,s4---s2,s3

(forget the dash here )

Whenever an integer has more then one set , there is a connection between the nodes.

So I keep deleting the set with the most frequency, until every integer has no more then one set

s1 : twice s2 : 4 times s3 : once s4: once

So I delete s2 here. After that , every integer has no more then one set .

Maybe I name the variable in the wrong way.

head is the previous Node of the sorted linked list

first , I choose the right node which is ptr1 here.

Then , make the previous node's next (head->next) to ptr1

Third, update the previous node (head=ptr1)

at last, update ptr1.

There is some bugs in my previous code . Here is tested code

Node * merge(Node *n)

{

if(n==NULL)

return NULL;

Node * ptr1=n;

Node * ptr1End=NULL;

Node * ptr2=n;

Node * head=NULL;

Node * m=head;

while(ptr2->next !=NULL)

{

if(ptr2->next->data < ptr2->data)

{

Node *tmp=ptr2->next;

ptr2->next=NULL;

ptr2=tmp;

break;

}

ptr2=ptr2->next;

}

while(ptr1!=NULL && ptr2!=NULL)

{

if(ptr1->data < ptr2->data)

{

if(head==NULL)

{

head=ptr1;

m=head;

ptr1=ptr1->next;

}

else

{

head->next=ptr1;

head=ptr1;

ptr1=ptr1->next;

}

}

else

{

if(head==NULL)

{

head=ptr2;

m=head;

ptr2=ptr2->next;

}

else

{

head->next=ptr2;

head=ptr2;

ptr2=ptr2->next;

}

}

}

if(ptr1==NULL)

{

head->next=ptr2;

}

if(ptr2==NULL)

{

head->next=ptr1;

}

return m;

}

Just an implementation of Matt's algo

Node * merge(Node *n)

{

if(n==NULL)

return NULL;

Node * ptr1=n;

Node * ptr1End=NULL;

Node * ptr2=n;

Node * head=NULL;

Node * m=head;

while(ptr2->next !=NULL)

{

if(ptr2->next->data < ptr2->data)

{

Node *tmp=ptr2->next;

ptr2->next=NULL;

ptr2=tmp;

break;

}

}

while(ptr1->next!=NULL && ptr2->next!=NULL)

{

if(ptr1->data < ptr2->data)

{

if(head==NULL)

{

head=ptr1;

m=head;

ptr1=ptr1->next;

}

else

{

head->next=ptr1;

head=ptr1;

ptr1=ptr1->next;

}

}

else

{

if(head==NULL)

{

head=ptr2;

m=head;

ptr1=ptr2->next;

}

else

{

head->next=ptr2;

head=ptr2;

ptr2=ptr2->next;

}

}

}

if(ptr1->next==NULL)

{

ptr1->next=ptr2;

}

if(ptr2->next==NULL)

{

ptr2->next=ptr1;

}

return m;

}

I think about make two array of size 256, one to record the order of characters, and the other is to record the number each character appears

char getUniqueCharacter()

{

int counter[256]={0};

char order[256]={0};

int i=0;

while(hasNext())

{

char tmp=getNext();

if(counter[tmp]==0)

order[i++]=tmp;

counter[tmp]++;

}

for(int j=0;j<256;j++)

{

char tmp=order[j];

if(tmp!='#')

{

if(counter[tmp]==1)

return tmp;

}

}

return '#';

}

O(n) runtime

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

Open Chat in New Window

Do not need to consider so many cases

- peng February 07, 2013suppose a1<a2 , b1<b2

void findDiff(int a1, int a2, int b1, int b2)

{

if(a1<b1)

{

while(a1!=b1)

{

cout<<a1<<endl;

a1++;

}

}

if(b2<a2)

{

while(b2!=a2)

{

cout<<a2<<endl;

a2--;

}

}

}