论坛首页 招聘求职论坛

讨论曾经被考过的一个面试题:将一个英文句子单词倒置的实现...

浏览 39183 次
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2004-09-13  
评价:
Good:
1、把delimiters 和 includeDelimiter 作为控制的参数,增加了扩展性;

Not Very Good:
1、如果把String source,String delimiters,boolean includeDelimiter都做为 private型的成员变量,似乎更加合理;
2、tokenizer不应该是StringReverser 的private attribute;
0 请登录后投票
   发表时间:2004-09-13  
derbysoft 写道

1、如果把String source,String delimiters,boolean includeDelimiter都做为 private型的成员变量,似乎更加合理;

没有把它们作为成员变量是考虑到面试的时间有限 ,有了private属性,没有getset就不太合适了
derbysoft 写道

2、tokenizer不应该是StringReverser 的private attribute;

把它作为一个属性首先是因为希望在构造对象的时候创建它,避免引入三个属性(上述的String source,String delimiters,boolean includeDelimiter)增加coding的时间。其次对象的任何属性首先都应该选用private,如果要考虑继承才开放到protected,而我把类声明成了final。另外这个tokenizer属于逻辑的实现,和外界无关的,所以就封装起来了。
这个类的用法是
StringReverser reverser = new StringReverser("this is a test String");;
String reversString = reverser.reverse();;
0 请登录后投票
   发表时间:2004-09-13  
呵呵,只是各人编程序风格不同,思路其实都差不多。
换了我,会把 tokenizer 挪到 reverse()里面去,因为 tokenizer只有在 reverse()里才被用到,封在method里它的作用域比封装在class中就更小了。
0 请登录后投票
   发表时间:2005-04-19  
要是真的遇到需要自己反转字符串的需求,肯定对性能做要求,各位老大的答案没有一个能通过。
0 请登录后投票
   发表时间:2005-04-20  
既然用来招聘考试的,肯定不是为了考string tokenizer的用法。

用split的方法,内存空间会成问题。让我们扩展一下,假若输入的是一个文本文件,长度是1G,怎么办?

还是应该从字符串尾或者文件尾逆向一个个字符去扫描,每当出现分隔符就把前面积累的字符作为单词扔到输出。
0 请登录后投票
   发表时间:2005-04-20  
我第一个想法也会是string tokenizer ,同时考虑StringBuffer存取字符串,但是具体实现还真没细想,如果面试的时候我也会去google,允许的话!
0 请登录后投票
   发表时间:2005-04-21  
package com.sweater.test;

public class TestSWT {

	public static String reverse(String str); {
		StringBuffer reverseStr = new StringBuffer(str);.reverse();;

		String regex = "[\\s\\,\\?\\'\\.\\:\\.]";
		String[] splitStr = str.split(regex);;

		for (int i = 0; i < splitStr.length; i++); {
			StringBuffer sbTemp = new StringBuffer(splitStr[i]);;

			String strTemp = reverseStr.toString();;
			strTemp = strTemp.replaceFirst(sbTemp.reverse();.toString();,
					splitStr[i]);;

			reverseStr = new StringBuffer(strTemp);;

		}

		//System.out.println(reverseStr.toString(););;

		return reverseStr.toString();;
	}

	public static void main(String[] args); {

		String s1 = "I am a student.";
		String s2 = "I am a student , yes? no";
		String s3 = " she said:'It's OK!'";
		String s4 = "I am a code? yes   ";

		System.out.println("s1=[" + s1 + "], reversed s1=["
				+ TestSWT.reverse(s1); + "]");;
		System.out.println("s2=[" + s2 + "], reversed s2=["
				+ TestSWT.reverse(s2); + "]");;
		System.out.println("s3=[" + s3 + "], reversed s3=["
				+ TestSWT.reverse(s3); + "]");;
		System.out.println("s4=[" + s4 + "], reversed s4=["
				+ TestSWT.reverse(s4); + "]");;
	}
}



结果:
s1=[I am a student.], reversed s1=[.student a am I]
s2=[I am a student , yes? no], reversed s2=[no ?yes , student a am I]
s3=[ she said:'It's OK!'], reversed s3=['OK! s'It':said she ]
s4=[I am a code? yes   ], reversed s4=[   yes ?code a am I]
0 请登录后投票
   发表时间:2005-04-22  
上个星期微软工程院的笔试题有一道就是这个题目。

关键是题目要求使用C语言,并且不能使用任何C库函数,除了IsSpace(char *).

我当时的思路是,申请一个额外动态数组,然后大循环扫描句子,再小循环扫描
每个单词,记录下每个单词在串中的开始和结束位置,最后再反方向输入到新数组中。

效率是O(N^2),还需要分配线型大小空间,哎。不是个好实现,但是时间上不允许多想啊。
0 请登录后投票
   发表时间:2005-07-27  
derbysoft 写道
to 凤舞凰扬:
     没有夸张,如果用你的办法,逗号之类的间隔符号虽然被去掉了,却没有象庄表伟要求的那样被打印出来;

to sankxuan:
    用了StringTokenizer(a,SEPARATORS,true)的三参数的构造函数,漂亮,确实是最好的实现。

------------------------------------------------------
重构了一下,下面是重构后的代码和执行结果:


import java.util.StringTokenizer;

public class Test{

    public static final String SEPARATORS = " ,\t:'';?!"; 

    public static String reverse(String input);{
    
        StringTokenizer st = new StringTokenizer(input, SEPARATORS, true);;
        StringBuffer words = new StringBuffer("");;
        while (st.hasMoreTokens();); {
            words.insert( 0, st.nextToken(); );;
        }    
        return words.toString();;
    }        
    
    public void testReverse();{
        
        String[] sentences = new String[]{
            "Hello, world!",
            "I am a student",
            "Am I a student? yes, or no",
            "Am I a student ? yes , or no",
            "Zhuang says:'It's just a coding game.'"
            };
            
        for (int i = 0; i < sentences.length; i++);
            System.out.println("Sentence[" + i + "]=[" + sentences[i]+"], " + 
                "After reversed: [" + Test.reverse(sentences[i]);+"]");;
       
    }
    
    public static void main(String[] args);{
        new Test();.testReverse();;
    }
    
        
}



--------------------------------------------------------------------------

执行结果:


引用
>ant exec

Buildfile: build.xml

exec:
     [java] Sentence[0]=[Hello, world!], After reversed: [!world ,Hello]
     [java] Sentence[1]=[I am a student], After reversed: [student a am I]
     [java] Sentence[2]=[Am I a student? yes, or no], After reversed: [no or ,yes ?student a I Am]
     [java] Sentence[3]=[Am I a student ? yes , or no], After reversed: [no or , yes ? student a I Am]
     [java] Sentence[4]=[Zhuang says:'It's just a coding game.'], After reversed: ['game. coding a just s'It':says Zhuang]


你这个实现没有考虑到性能上面的问题,怎么能够用words.insert( 0, st.nextToken() );呢?消耗太大!每次insert要修改多少reference啊!数据结构没有学好,字符串一大,性能下降的厉害,你自己试试,最好是用Stack或者LinkedList这两个性能差不多。
这个题目就考两个点:一个是遍历算法,一个是数据结构,这个遍历算法还是自己写好一些,关键题目里面没有说明delimiter的范围,那么就应该自己实现只是对character进行解析。判断字符不需要用switch case的办法,用这个方法:
	/**
	 * if char is in range of A~Z or a~z return true
	 * else return false
	 *
	 * @param c
	 * @return
	 */
	private boolean isCharacter(char c); {
		long x = 'A'; //65
		long y = 'Z'; //90
		long m = 'a'; //97
		long n = 'z'; // 122				
		return (c >= x && c <= y); || (c >= m && c <= n);;
	}
0 请登录后投票
   发表时间:2005-07-31  
这个行不行啊?
引用

/**
* @author Administrator
*
* TODO To change the template for this generated type comment go to
* Window - Preferences - Java - Code Style - Code Templates
*/
public class ReverseSentence {

    public static String doReverseSentense(final String aSentence){
        StringBuffer sb1 = new StringBuffer();
        Collection result = new Stack();
       
        char[] cArray = aSentence.trim().toCharArray();
        for (int i = 0; i &lt; cArray.length; i++) {
            if(cArray[i] &gt;= 'A' && cArray[i] &lt;= 'z'){
                sb1.append(cArray[i]);
            }
            else{
                ((Stack)result).push(sb1.toString());
                ((Stack)result).push(String.valueOf(cArray[i]));
                sb1.delete(0,sb1.length());
            }
        }
        ((Stack)result).push(sb1.toString());
        sb1.delete(0,sb1.length());
       
        while(result.size() &gt; 0){
            sb1.append(((Stack)result).pop());
        }
        return sb1.toString();
    }
   
    public static void main(String[] args) {
        String[] sentences = new String[]{
                "I think the argument was basically that ",
                "names somewhere, so why bother introducing an",
                "But I agree with Scott - I think it can add value for complex apps.",
                "sun的实现考虑了所有unicode字符,而我只考虑了英文字母。 ",
                "Alex Michael,Hu'nter?kk"
                };
        for (int i = 0; i &lt; sentences.length; i++) {
            System.out.println(doReverseSentense(sentences[i]));
        }
    }
}


输出这样:
引用

that basically was argument the think I
an introducing bother why so ,somewhere names
.apps complex for value add can it think I - Scott with agree I But
。母字文英了虑考只我而,符字unicode有所了虑考现实的sun
kk?nter'Hu,Michael Alex
0 请登录后投票
论坛首页 招聘求职版

跳转论坛:
Global site tag (gtag.js) - Google Analytics