Expedia Interview Question
Software Engineer in TestsCountry: India
Interview Type: Phone Interview
void fixNode(node *head) {
if (head == nul) {
return null;
}
if (head->next == null) {
return null;
}
node *temp = head;
while (temp->next!=null) {
if (temp->value < temp->next->value) {
temp->next = null;
return;
}
temp = temp->next;
}
Your logic would fail, if the list has duplicates.
1->3->5->8->8->8->8->9
1->3->5->8->8->8->8->
^< -|
Since there are only two functions + and * , we need to take care of precedence of * first:
char[] arr = {'4','*','5','+','6','*','2','+','5'};
NodeS<int> stInt = new NodeS<int>();
int result = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] >= 48 && arr[i] <= 57)
{
stInt.Push(arr[i] - '0');
}
else if(arr[i] == '*')
{
i++;
if (arr[i] >= 48 && arr[i] <= 57)
{
int f = stInt.Pop() * (arr[i] - '0');
stInt.Push(f);
}
}
}
while (!stInt.Empty())
{
result += stInt.Pop();
}
Console.WriteLine(result);
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.");
}
if loop is there in linked list which is sorted and you want to remove it then,
- sjain May 21, 2013just check if any node whose next node value is less than current node value, if it is true then point the next pointer of current node to null.