渥太华IT面试编程试题

[闲得慌]

这些试题应该可以全世界通用，但是为了响应几个大佬的号召，只谈与渥太华有关的问题，所以特地在标题里加上“渥太华"。

答案要求考虑edge cases, 要估算时间和空间的Big O. 语言不限， 但鼓励用Java。

先来个经典的：
试题1： Write code to reverse a string.

 

[苦逼热狗]

需要考虑unicode string吗

 

[闲得慌]

需要考虑unicode string吗

当然

 

[旭日阳刚]

是存储在数组中吗？如果知道长度，找到中间点，然后直接对换，应该是个比较快的算法？

 

[月下独酌]

#!/bin/sh
# the next line restarts using tclsh \
exec tclsh "$0" "$@"

string reverse [lindex $argv 0]

 

[闲得慌]

#!/bin/sh
# the next line restarts using tclsh
exec tclsh "$0" "$@"

string reverse [lindex 0]

当题目可能有争议的时候，很重要的一点就是询问面试官，弄清楚出题人的真实意图。 切忌自以为是，否则会惨败

 

[闲得慌]

是存储在数组中吗？如果知道长度，找到中间点，然后直接对换，应该是个比较快的算法？

你写出来看看吧

 

[heureux]

支持！

 

[苦逼热狗]

我来个小儿科的答案吧

public class ReverseString {
    
    public static void reverse(String sSource) {
        try{
            byte[] bSource = sSource.getBytes("UTF-8");
            String sUTFSource = new String(bSource,"UTF-8");
            bSource  = null;
                
            StringBuilder sbRet = new StringBuilder();
            int nSize = sUTFSource.length() - 1;
            for (int i=nSize; i>=0; i--) {
                sbRet.append(sUTFSource.charAt(i));
            }
            System.out.println("source :" + sUTFSource);
            System.out.println("result :" + sbRet.toString());
            sbRet = null;
        }catch(Exception e){
            e.printStackTrace();
        }
    }
    
    public static void main(String[] args) {
        if (args != null && args.length > 0) {
            String sSource = args[0];
            ReverseString.reverse(sSource);
        }
    }
}

 

[旭日阳刚]

假设数组A长度为n
m=int(n/2);
for i=1 to m;
{
k=n-i+1;
temp=a[k];
a[k]=a;
a=temp;
}

大概就是这样，语法忘了。
这个怎么样？

你写出来看看吧

 

[月下独酌]

当题目可能有争议的时候，很重要的一点就是询问面试官，弄清楚出题人的真实意图。 切忌自以为是，否则会惨败

直接call function不就行了～

咩哈哈哈哈哈

 

[闲得慌]

假设数组A长度为n
m=int(n/2);
for i=1 to m;
{
k=n-i+1;
temp=a[k];
a[k]=a;
a=temp;
}

大概就是这样，语法忘了。
这个怎么样？

思路是对的，但是犯了个常识性的错误： 数组的index是从0开始的。这种致命的错误肯定让你失去Offer.

 

[旭日阳刚]

我的字符串是从1开始存贮。：）
面试的时候，写程序是在纸上写吗？还是在电脑上？

思路是对的，但是犯了个常识性的错误： 数组的index是从0开始的。这种致命的错误肯定让你失去Offer.

 

[苦逼热狗]

改改再交一个

    public static String reverse2(String sSource) throws Throwable {
        int nSize = sSource.length();
        if (nSize <= 1) {
            return sSource;
        }
        int nMidPoint = nSize >> 1;
        String left = sSource.substring(0, nMidPoint);
        String right = sSource.substring(nMidPoint, nSize);
        return reverse2(right) + reverse2(left);
    }

 

[该出手时就出手]

存储空间无限制，不会高于线性时间复杂度。