Nagesh Agastya
BAN USERSr. SDE, (Vendor) Microsoft Corporation
public static void FixFaultyNodesInSortedLinkedList()
{
//Prepare the mock list
var head = new SingleLinkedList<int>() { Value = 1 };
var cur = head;
for (int i = 0; i < 5; i++)
{
cur.Next = new SingleLinkedList<int> { Value = i + 2 };
cur = cur.Next;
}
cur.Next = head;
//***************************************************
if (head == null || head.Next == null)
return; //return head;
cur = head;
while (cur.Next != null)
{
if (cur.Value > cur.Next.Value)
cur.Next = null; //fix by setting the next value null. ignore the rest of list for now.
else
cur = cur.Next;
}
Console.WriteLine("Print head to tail.");
}
public static void PrintFirstRepeatedCharacterApproach1()
{
Console.Write("Enter the string to find first repeated character: ");
string input = Console.ReadLine();
if (string.IsNullOrEmpty(input) || input.Length <= 1)
{
Console.WriteLine("Input string cannot be null and length should be greater than 1.");
return;
}
char highestRepeatedChar = input[0];
int[] counts = new int[256];
int[] charOrder = new int[256];
for (int i = 0; i < charOrder.Length; i++)
charOrder[i] = -1;
int co = 0;
for (int i =0; i <input.Length; i++)
{
char c = input[i];
if (charOrder[c] == -1)
charOrder[c] = co++;
counts[c]++;
if (counts[highestRepeatedChar] < counts[c])
{
highestRepeatedChar = c;
}
}
char firstRepChar = highestRepeatedChar;
for (int i = 0; i < 256; i++)
{
if ((int)highestRepeatedChar != i && counts[highestRepeatedChar] == counts[i] && charOrder[i] < charOrder[highestRepeatedChar])
{
firstRepChar = (char)i;
break;
}
}
Console.WriteLine("First repeated character '{0}' and count: {1}", firstRepChar, counts[firstRepChar]);
}
...its cost is o(3n), which is o(n).
Cannot rely on hashtable keys, as they are not returned in the order of insertion.
Assuming the type of data stored in linked list is int value, above solution fits the bill.
- Nagesh Agastya April 02, 2014