Cracking the Coding Interview Chapter 2 Solutions in PeopleCode

/* Application Package Name : CTCI_LL_AP */

class ListItem
   method ListItem(&data As any);
   method linkTo(&item As CTCI_LL_AP:ListItem);
   method next() Returns CTCI_LL_AP:ListItem;
   method getData() Returns any;
 
private
   instance CTCI_LL_AP:ListItem &nextItem_;
   instance any &data_;
end-class;

method ListItem
   /+ &data as Any +/
   %This.data_ = &data;
end-method;

method linkTo
   /+ &item as CTCI_LL_AP:ListItem +/
   &item.nextItem_ = %This;
end-method;

method next
   /+ Returns CTCI_LL_AP:ListItem +/
   Return %This.nextItem_;
end-method;

method getData
   /+ Returns Any +/
   Return %This.data_
end-method;


import CTCI_LL_AP:*;

class ListItemExt
   method ListItemExt(&data As any);
   method linkTo(&item As CTCI_LL_AP:ListItemExt);
   method next() Returns CTCI_LL_AP:ListItemExt;
   method prev() Returns CTCI_LL_AP:ListItemExt;
   method remove() Returns CTCI_LL_AP:ListItemExt;
   method getData() Returns any;
private
   instance CTCI_LL_AP:ListItemExt &nextItem_;
   instance CTCI_LL_AP:ListItemExt &prevItem_;
   instance any &data_;
end-class;

method ListItemExt
   /+ &data as Any +/
   %This.data_ = &data;
end-method;

method linkTo
   /+ &item as CTCI_LL_AP:ListItemExt +/
   REM ** manipulate previous sibling;
   &item.nextItem_ = %This;
   %This.prevItem_ = &item;
end-method;

method next
   /+ Returns CTCI_LL_AP:ListItemExt +/
   Return %This.nextItem_;
end-method;

method prev
   /+ Returns CTCI_LL_AP:ListItemExt +/
   Return %This.prevItem_;
end-method;

method remove
   /+ Returns CTCI_LL_AP:ListItemExt +/
   %This.nextItem_.linkTo(%This.prevItem_);
   REM ** Or manipulate both siblings;
   REM %This.prevItem_.nextItem_ = %This.nextItem_;
   REM %This.nextItem_.prevItem_ = %This.prevItem_;
   Return %This.prevItem_;
end-method;

method getData
   /+ Returns Any +/
   Return %This.data_;
end-method;



/* Functions represent solutions 1 to 8 in ascending order */


import CTCI_LL_AP:*;


Function removeDups(&head As CTCI_LL_AP:ListItem) Returns CTCI_LL_AP:ListItem
 
   Local CTCI_LL_AP:ListItem &leader;
   Local CTCI_LL_AP:ListItem &runner;
   Local CTCI_LL_AP:ListItem &prev;
 
   &leader = &head;
   While &leader.next() <> Null
      &prev = &leader;
      &runner = &prev.next();
      Repeat
         If &leader.getData() = &runner.getData() Then
            &runner.next().linkTo(&prev);
         End-If;
         &prev = &prev.next();
         &runner = &prev.next();
      Until All(&runner);
      &leader = &leader.next();
   End-While;
   CollectGarbage();
   Return &head;
 
End-Function;

Function k2Last(&head As CTCI_LL_AP:ListItem, &K As number) Returns CTCI_LL_AP:ListItem
 
   Local CTCI_LL_AP:ListItem &runner;
   Local number &I = 1;
   &runner = &head;
   While &runner.next() <> Null
      &runner = &runner.next();
      &I = &I + 1;
      If &I = &K Then
         Break;
      End-If;
   End-While;
   Return &runner;
 
End-Function;


Function removeMiddle(&head As CTCI_LL_AP:ListItem, &c As any)
 
 
   Local CTCI_LL_AP:ListItem &prev;
   Local CTCI_LL_AP:ListItem &runner;
   Local CTCI_LL_AP:ListItem &tail;
 
   &prev = &head;
   &runner = &prev.next();
   &tail = &runner.next();
 
   While All(&tail)
      If &runner.getData() = &c Then
         &tail.linkTo(&prev);
         Break;
      End-If;
      &prev = &runner;
      &runner = &prev.next();
      &tail = &runner.next();
   End-While;
 
   CollectGarbage();
 
End-Function;



Function partitionll(&head As CTCI_LL_AP:ListItem, &x As any) Returns CTCI_LL_AP:ListItem
 
   Local CTCI_LL_AP:ListItem &prev;
   Local CTCI_LL_AP:ListItem &runner;
   Local CTCI_LL_AP:ListItem &tail;
   Local array &prevArray, &tailArray;
   Local any &hold;
   Local number &pI, &tI, &pJ, &tJ;
 
   &runner = &head;
   &prevArray = CreateArray();
   &tailArray = CreateArray();
   &pI = 1;
   &tI = 1;
   Repeat
      &hold = &runner.getData();
      If &hold < &x Then
         &prevArray [&pI] = create CTCI_LL_AP:ListItem(&hold);
         &pI = &pI + 1;
      Else
         &tailArray [&tI] = create CTCI_LL_AP:ListItem(&hold);
         &tI = &tI + 1;
      End-If;
      &runner = &runner.next();
   Until All(&runner);
 
   &pJ = 1;
   While &prevArray.Next(&pJ)
      &prevArray [&pJ].linkto(&prevArray [&pJ - 1]);
   End-While;
 
   &tJ = 1;
   While &tailArray.Next(&pJ)
      &tailArray [&tJ].linkto(&tailArray [&tJ - 1]);
   End-While;
 
   &tailArray [1].linkto(&prevArray [&pJ - 1]);
 
   Return &prevArray [1];
 
End-Function;


Function sumList(&head As CTCI_LL_AP:ListItem, &order As string) Returns CTCI_LL_AP:ListItem
 
   Local CTCI_LL_AP:ListItem &runner;
   Local array &listArray;
   Local array of string &n2sArr;
   Local number &total, &I, &J, &K, &M, &N, &P, &Q, &temp;
   Local array of any &holder;
 
   &runner = &head;
   &holder = CreateArray();
   &listArray = CreateArray();
   &n2sArr = CreateArrayRept("", 0);
 
   Evaluate &order
   When "reverse"
      &total = &runner.getData();
      &I = 10;
      While &runner.next() <> Null
         &runner = &runner.next();
         &total = &total + Product(&runner.getData(), &I);
         &I = Product(&I, 10);
      End-While;
   
      &n2sArr = Split(NumberToString("*", &total));
   
      &N = 1;
      For &M = &n2sArr.Len To 1 Step - 1
         &listArray [&N] = create CTCI_LL_AP:ListItem(Value(&n2sArr [&M]));
         &N = &N + 1;
      End-For;
      Break;
   When "straight"
      &holder [1] = &runner.getData();
      While &runner.next() <> Null
         &runner = &runner.next();
         &holder.Push(&runner.getData());
      End-While;
   
      &K = 10;
      &total = &holder [&holder.Len];
      &temp = &holder.Len - 1;
      For &J = &temp To 1 Step - 1
         &total = &total + Product(&holder [&J], &K);
         &K = Product(&K, 10);
      End-For;
   
      &n2sArr = Split(NumberToString("*", &total));
   
      For &P = 1 To &n2sArr.Len Step 1
         &listArray [&P] = create CTCI_LL_AP:ListItem(Value(&n2sArr [&P]));
      End-For;
      Break;
   End-Evaluate;
 
   &Q = 1;
   While &listArray.Next(&Q)
      &listArray [&Q].linkto(&listArray [&Q - 1]);
   End-While;
 
   Return &listArray [1];
End-Function;


Function palindromeCheck(&head As CTCI_LL_AP:ListItemExt) Returns boolean
 
   Local CTCI_LL_AP:ListItemExt &start, &end, &runner;
   Local number &midpoint, &listLength, &P;
 
   &midpoint = 0;
   &listLength = 1;
 
   If &head.next() = Null Then
      Return True;
   Else
      &start = &head;
      &runner = &start.next();
   
      While All(&runner)
         &listLength = &listLength + 1;
         &end = &runner;
         &runner = &runner.next();
      End-While;
   
   
      &midpoint = Idiv(&listLength, 2);
   
      For &P = 1 To &midpoint Step 1
         If &start.getData() <> &end.getData() Then
            Return False;
         Else
            &start = &start.next();
            &end = &end.prev();
         End-If;
      End-For;
   End-If;
 
   Return True;
 
End-Function;

Function intersectCheck(&head1 As CTCI_LL_AP:ListItem, &head2 As CTCI_LL_AP:ListItem) Returns boolean
 
   Local CTCI_LL_AP:ListItem &runner1, &runner2;
 
   &runner1 = &head1;
   &runner2 = &head2;
 
   While All(&runner1)
      While All(&runner2)
         If &runner1 = &runner2 Then
            Return True;
         End-If;
         &runner2 = &runner2.next();
      End-While;
      &runner1 = &runner1.next();
   End-While;
   Return False;
End-Function;


Function circularCheck(&head As CTCI_LL_AP:ListItem) Returns CTCI_LL_AP:ListItem
 
   Local CTCI_LL_AP:ListItem &start, &runner;
 
   &slow = &head;
   &fast = &head;
 
   While All(&fast)
         &slow = &slow.next();
         &fast = &fast.next();
         &fast = &fast.next();
         if &slow = &fast then
              break;
         end-if;
   End-While;
 
   If None(&fast) Or None(&fast.next()) Then
         Return null;
   end-if;

  &slow = &head;

  While &slow <> &fast
         &slow = &slow.next();
         &fast = &fast.next();
  End-While;

  Return &slow;

End-Function;