1. check whether a string is palindrome
2. reverse words in a string

Question

1. check whether a string is palindrome
2. reverse words in a string

This implementation does not use StringBuilder or other built-in String operations, no cheating! · Accepted Answer

This implementation does not use StringBuilder or other built-in String operations

if you tell your interviewer you are going to use reverse on  a StringBuider, you are toast.


using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace AlgorithmsTests
{
    [TestClass]
    public class ReverseAndPalindrome
    {
        [TestMethod]
        public void Palindrome_Tests()
        {
            Assert.IsTrue(IsPalindrome(string.Empty));
            Assert.IsTrue(IsPalindrome("a"));
            Assert.IsTrue(IsPalindrome("aa"));
            Assert.IsTrue(IsPalindrome("aba"));
            Assert.IsTrue(IsPalindrome("abcdefghgfedcba"));
            Assert.IsFalse(IsPalindrome("ab"));
            Assert.IsFalse(IsPalindrome("abbcba"));
        }

        [TestMethod]
        public void ReverseSteing_Tests()
        {
            Assert.AreEqual("a", ReverseString("a"));
            Assert.AreEqual("ab", ReverseString("ba"));
            Assert.AreEqual("fedcba", ReverseString("abcdef"));
        }

        private string ReverseString(string o)
        {
            //switch the first half against the second half
            char[] s = o.ToCharArray();
            for (int i = 0; i < s.Length / 2; i++)
            {
                char t = s[i];
                s[i] = s[s.Length - 1 - i];
                s[s.Length - 1 - i] = t;
            }
            return new string(s);
        }

        private bool IsPalindrome(string s)
        {
            //check the fisrt half against the second half
            for (int i = 0; i < s.Length / 2; i++)
            {
                if (s[i] != s[s.Length - 1 - i])
                    return false;
            }
            return true;
        }
    }
}

Omer Ozer · Answer

I think the string won't be reversed but the words within the string will. 

Here's a O(n) solution for java:

 public static String reverse(String s){
        String reversed="";

        char[] c = s.toCharArray();

        int wordBeg=0;
        int wordEnd=0;

        for(int i = 0;i wordBeg && (c[i]==' '||i==c.length-1)){
                wordEnd=i;
                for(int j=wordEnd;j>=wordBeg;j--){
                    reversed+=c[j];
                }
                wordBeg=i;
                wordEnd=i;
                continue;
            }
            if(c[i]!=' '){
                wordEnd=i;
            }else{
                wordBeg=i;
                wordEnd=i;
                reversed+=' ';
            }
        }

        return reversed;
    }

Possible Solution · Answer

static boolean pal(String s) {
		return (s.equals(new StringBuilder(s).reverse().toString()));
	}

	// reverse the words in a string.
	static String reverseWords(String s) {
		String delims = "[ ]+"; // delimiter for space(s)
		String[] tokens = s.split(delims); // store words
		String returnString = ""; // initialize string to return
		// add words to return string, starting from last word
		for (int i = tokens.length-1; i >=0; i-- ) {
			returnString += tokens[i] + " ";
		}
		return returnString.trim(); // trim last white space and return string
	}

Meta

Meta Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches