Reverse Linked List

My Coding Questions

1. Two sorted linked lists are given. Members of list nodes are ints. Make one sorted list that aggregates both lists.
2. The array of bools are given. Write the sort algorithm
3. Find first repeated character in string. Write test cases.

Coding: Arrays

1. Given the following prototype:

int compact(int * p, int size);

write a function that will take a sorted array, possibly with duplicates, and compact the array, returning the new length of the array. That is, if p points to an array containing: 1, 3, 7, 7, 8, 9, 9, 9, 10, when the function returns, the contents of p should be: 1, 3, 7, 8, 9, 10, with a length of 5 returned.
Solution in comment.

48. Given an array of integers, find the contiguous sub-array with the largest sum.

ANS. Can be done in O(n) time and O(1) extra space. Scan array from 1 to n. Remember the best sub-array seen so far and the best sub-array ending in i.
Link to original, 48

49.Given an array of length N containing integers between 1 and N, determine if it contains any duplicates.

ANS. [Is there an O(n) time solution that uses only O(1) extra space and does not destroy the original array?]

53. An array of characters. Reverse the order of words in it.

ANS. Write a routine to reverse a character array. Now call it for the given array and for each word in it.

Coding: Linked list with cycle

Question: How could you determine if a linked list contains a cycle in it, and, at what node the cycle starts?
Source

Night bridge - crossing

There are four people who need to cross a bridge at night. The bridge is only wide enough for two people to cross at once. There is only one flashlight for the entire group. When two people cross, they must cross at the slower member's speed. All four people must cross the bridge in 17 minutes, since the bridge will collapse in exactly that amount of time. Here are the times each member takes to cross the bridge:

• Person A: 1 minute
  
• Person B: 2 minutes
  
• Person C: 5 minutes
  
• Person D: 10 minutes
  

So, if Person A and C crossed the bridge initally, 5 minutes would elapse, because Person C takes 5 minutes to cross. Then, Person A would have to come back to the other side of the bridge, taking another minue, or six minutes total. Now, if Person A and D crossed the bridge next, it would take them 10 minutes, totalling to 16 minutes. If A came back, it would take yet another minute, totally 17... the bridge would collapse with A and B on the wrong side. How can all four people get across the bridge within 17 minutes? Note: there is no trick-answer to this problem. You can't do tricky stuff like throwing the flashlight back from one end of the bridge to the other. This problem can be solved!

Eight balls

You are given a scale which you are to use to measure eight balls. Seven of these balls have the same weight: the eigth ball is heavier than the rest. The scale does not indicate the weight of a particular object; it is a scale which tells you which of the two sides being weighed is heavier (like the scale that lady of justice statue holds up). So, for example you could place one ball on each end of the scale. If ball one was heavier than ball two, it would tip in ball one's direction; if ball two were heavier, it would tip io ball three's direction; if the balls were of equal weight, the scale would not tip at all. What is the minimum number of weighs you could perform to find the heaviest of the eight balls?