Microsoft Interview Question for Interns


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

Singly linked list, so you use auxiliary data store, a stack works, better, a string works with a special character for separator, like "#".
You simply traverse the linked list and push to the stack, or to the string with "#" , e.g

1 -> 2 -> 3 -> 42 -> 3 -> 2 -> 1

will be encoded as :

1#2#3#42#3#2#1

Now, traverse from left ( head ) again, pop the stack, and match the values.
In case you are using a String, then split the string and then traverse from right.
In case they match always, we have a solution.

Error out in case there is no match.
We can try to be clever and use some x,2x pointer to reach to the middle. But, as of now, that pointer game is pointless.

- NoOne December 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution 1: O(n) ops, O(1) memory

public class ListPalindrome {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null) {
            slow = slow.next;
        }

        ListNode tail = reverse(slow);
        ListNode forward = head;
        ListNode backward = tail;

        boolean result = true;
        while (backward != null){
            if (forward.payload != backward.payload) {
                result = false;
                break;
            }
            forward = forward.next;
            backward = backward.next;
        }
        // restore list
        reverse(tail);
        return result;
    }

    private ListNode reverse(ListNode start) {
        ListNode tmp, prev = null;
        ListNode run = start;
        while (run != null) {
            tmp = run;
            run = run.next;
            tmp.next = prev;
            prev = tmp;
        }
        return prev;
    }

    public static void main() {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        head.next = second;
        ListNode third = new ListNode(3);
        second.next = third;
        ListNode fourth = new ListNode(2);
        third.next = fourth;
        ListNode fifth = new ListNode(1);
        fourth.next = fifth;
        System.out.println(new ListPalindrome().isPalindrome(head));
    }
}

Solution 2: O(n) ops, O(n) memory, 1 pass

import java.util.Stack;

public class ListPalindrome2 {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        Stack<Integer> s = new Stack<Integer>();

        while (fast != null && fast.next != null) {
            s.push(slow.payload);
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null) {
            slow = slow.next;
        }

        while (slow != null){
            if (slow.payload != s.pop()) {
                return false;
            }
            slow = slow.next;
        }
        return true;
    }

    public static void main() {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        head.next = second;
        ListNode third = new ListNode(3);
        second.next = third;
        ListNode fourth = new ListNode(2);
        third.next = fourth;
        ListNode fifth = new ListNode(1);
        fourth.next = fifth;
        System.out.println(new ListPalindrome2().isPalindrome(head));
    }
}

- minya December 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

module.exports = function (L) {
  var A = [];
  var ptr = L;
  while (ptr.next) {
    ptr = ptr.next;
    A.push(ptr.value)
  }
  for (var i = A.length - 1, ptr = L.next; i > -1; --i, ptr = ptr.next) {
    if (A[i] !== ptr.value) {
      return false
    }
  }
  return true

}

var ans = module.exports({
  next: {
    value: 1,
    next: {
      value: 2,
      next: {
        value: 3,
        next: null
      }
    }
  }
});

console.log(ans);

- srterpe December 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isPalindrom (LinkedList str)
	{
		if(str == null || str.isEmpty())
			return false;
		else
		{
			int n = str.size();
			for(int i =0; i<n/2;i++)
			{
				if(str.get(i)!=str.get((n-1)-i))
				{
					return false;
				}
			}
			return true;
		}
	}

- mkl December 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time O(n)

public class Node
    {
        public int Value { get; set; }
        public Node Next { get; set; }
    }

    public class  SinglyLinkedList
    {
        public Node Head { get; set; }
        public Node Tail { get; set; }
        public int Count { get; set; }
    }

public static bool IsPolindrom(SinglyLinkedList list)
        {
            Stack<int> store = new Stack<int>();
            Node current = list.Head;
            for (int i = 0; i < list.Count; i++)
            {
                if (i <= list.Count / 2)
                    store.Push(current.Value);
                else
                {
                    int tmp = store.Pop();
                    if (tmp != current.Value)
                        return false;
                }
                current = current.Next;
            }

            return true;
        }

- vh.vahan January 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

. Take fast and slow pointers.
. Find the middle of the linked list. O(n)
/// say Midj
. Then reverse first part of the linked list O(n)
/// say Revj
. Then just compare one by one Midj and Revj. if not matched, just bell out.

- vips January 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void palindromeElements()
{

LinkedList<int> lln = new LinkedList<int>(new[] { 1,2,3,2,1 });
var head = lln.First;
var last = lln.Last;
while (head!= null && last!=null)
{
if(head.Value==last.Value)
{
head = head.Next;
last = last.Previous;
}
else
{
Console.WriteLine("Not palindrome");
break;
}

}
if(head==null &&last==null)
{
Console.WriteLine("it is palindrome");
}
foreach (var item in lln)
{
Console.Write(item + "\t");
}
Console.ReadKey();

}

- Anonymous February 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) with no extra memory and no need to reverse list
have two pointers pointing at the head
using recursion locate the last element and point one pointer to it
then move the two pointers in opposite direction (with the help of recursion return) checking for equality
Forward pointer has to be a ref pointer for this to work

public class Node
{
    public int data;
    public Node next;
}
public static Boolean isPalindrome(Node list)
{
    Node listCopy = list;
    if (list != null)
    {
        return isPalindrome(ref listCopy, list);
    }
    return false;
}

private static Boolean isPalindrome(ref Node l1, Node l2)
{
    if (l2.next == null)
    {
        return l2.data == l1.data;
    }
    else
    {
        Boolean p = isPalindrome(ref l1, l2.next);
        l1 = l1.next;
        if ((l1 == l2) || (l1 == l2.next))

        {
            return p;
        }

        return (l2.data == l1.data) && p;
    }
}

- IC March 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static boolean isPalindrom (LinkedList str)
	{
		if(str == null || str.isEmpty())
			return false;
		else
		{
			int n = str.size();
			for(int i =0; i<n/2;i++)
			{
				if(str.get(i)!=str.get((n-1)-i))
				{
					return false;
				}
			}
			return true;
		}
	}

- Anonymous December 20, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More