📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: 1guangnian
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft on-compus 面试题一道

🔗
流浪旧金山 2013-10-19 12:52:13 | 只看该作者
全局:
牺牲一下空间,可以达到nlogn。不过,大赞我大骏神威武霸气。哈哈
回复

使用道具 举报

🔗
流浪旧金山 2013-10-19 12:52:19 | 只看该作者
全局:
牺牲一下空间,可以达到nlogn。不过,大赞我大骏神威武霸气。哈哈
回复

使用道具 举报

🔗
austurela 2013-10-19 13:22:31 | 只看该作者
全局:
tangxukai 发表于 2013-10-19 12:52
牺牲一下空间,可以达到nlogn。不过,大赞我大骏神威武霸气。哈哈

能具体讲讲怎么implement的吗?
回复

使用道具 举报

🔗
flyaway25 2013-10-19 13:38:15 | 只看该作者
全局:
1guangnian 发表于 2013-10-19 12:32
yep, the worst case

如果按他说的每个点左右都各扫一次的worst case应该是O(n*m)吧
回复

使用道具 举报

🔗
austurela 2013-10-19 14:00:56 | 只看该作者
全局:
import java.util.Hashtable;

//Implement double LinkedList
class DoubleNode{
       
        DoubleNode next;
        DoubleNode previous;
        DoubleNode tail;
        double data;
       
        DoubleNode(double data){
                this.data = data;
                next = null;
                previous = null;
                tail = this;
        }
       
        public void addNode(double inputData){

                DoubleNode temp = new DoubleNode(inputData);
                tail.next = temp;
                temp.previous = tail;
                tail = tail.next;
        }
       
        public String toString(){
               
                StringBuffer toReturn = new StringBuffer();
               
                //pointer
                DoubleNode current = this;
               
                while(current != null){
                        //if it is the end node, append "data" to the buffer
                        if(current.next == null){
                                toReturn.append(current.data);
                        }
                        //if it is not the end, append "data - " to the buffer
                        else{
                                toReturn.append(current.data + " <-> ");
                        }
                       
                        current = current.next;
                }
               
                return toReturn.toString();
        }
}

/**
* Given a double LinkedList, you return the head of a new double
* LinkedList where all the node that is not repeated is deleted
*
* Sample input:
* 1.1<->2.5<->1.1<->3.1<->4.10<->2.50
*
* Sample output:
* 1.1<->2.5<->1.1<->2.50
*
* @author Ziliang Zhu
*
*/
public class DoubleLinkedlistRepetitionSift {

        Hashtable<Double, Boolean> myHash;

        public DoubleLinkedlistRepetitionSift(){
                myHash = new Hashtable<Double, Boolean>();
        }
       
        public DoubleNode onlyKeepRepeated(DoubleNode myHead){

                DoubleNode current = myHead;
                DoubleNode toReturn = null;
               
                //Read through the list the first time
                while(current != null){
                       
                        //There is no such node, put it in, set false
                        if(myHash.get(current.data) == null){
                                myHash.put(current.data, false);
                        }
                        //There is already such a node, remove it, put it in, set true
                        else if(myHash.get(current.data) == false){
                                myHash.remove(current.data);
                                myHash.put(current.data, true);
                        }

                        //update current
                        current = current.next;
                }

                //Reset current
                current = myHead;
                //Read through the list the second time
                while(current != null){
                       
                        //When the node is repeated, add it to the double LinkedList
                        //Use hashtable to determine is the node is needed
                        if(myHash.get(current.data) == true){

                                //copy and paste nodes
                               
                                if(toReturn != null){
                                        toReturn.addNode(current.data);
                                }
                                else{
                                        toReturn = new DoubleNode(current.data);
                                }
                               
                        }
                       
                        //update current
                        current = current.next;
                }
               
                return toReturn;
        }
       
       
}


补充内容 (2013-10-19 14:03):
我把地下室楼层的想法试着用java写了一下,主要是想请哪位有耐心读的提出些建议,各位见笑
回复

使用道具 举报

🔗
流浪旧金山 2013-10-19 14:19:11 | 只看该作者
全局:
austurela 发表于 2013-10-19 13:22
能具体讲讲怎么implement的吗?

给定一个新的数组按照data快排nlogn,数组里面的是节点,node{data,pos};从前往后找,只要前后紧挨着的一样就输出O(n)。当然如果最后是要按照原来的顺序输出,用pos再来排序就可以了。所以,应该是多一个数组就可以达到nlogn了吧?

评分

参与人数 1大米 +1 收起 理由
austurela + 1 谢谢分享

查看全部评分

回复

使用道具 举报

🔗
ac/dc 2013-10-19 19:45:27 | 只看该作者
全局:
不需要额外数组空间,因为是doubly linked list,可以直接在这个上做partition进而做quick sort, O(nlogn). 然后两两比较即可O(n). Overall O(nlogn)

补充内容 (2013-10-19 19:50):
当然in-place quick sort的recursion理论上也是要O(logn) Space的
回复

使用道具 举报

🔗
 楼主| 1guangnian 2013-10-19 23:49:17 | 只看该作者
全局:
tangxukai 发表于 2013-10-19 14:19
给定一个新的数组按照data快排nlogn,数组里面的是节点,node{data,pos};从前往后找,只要前后紧挨着的一 ...

如果允许开额外数组,输出顺序又没要求的话,这方法也不错
回复

使用道具 举报

🔗
 楼主| 1guangnian 2013-10-19 23:49:29 | 只看该作者
全局:
ac/dc 发表于 2013-10-19 19:45
不需要额外数组空间,因为是doubly linked list,可以直接在这个上做partition进而做quick sort, O(nlogn). ...

又学到新知识了。。
回复

使用道具 举报

🔗
 楼主| 1guangnian 2013-10-19 23:59:27 | 只看该作者
全局:
我觉得面试时候尽量多问问题,把各种要求,限制条件问清楚,如果跟你的实现方法有关的话,这一点昨天我还是没有做很好,在满足条件要求的情况下,选一个好实现的就行,bug-free也是很重要的
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表