m********7
发帖数: 1368 | 1 面试让用iterative method写一个 in place insertion sort with singly linked
list..哎好久没有练，写了半小时还有BUG。。一般大家写这样难度的多久可以写到BUG
FREE？ |
d**********x
发帖数: 4083 | 2 1 day
remember what is the INVARIANT in your loop. maintain it and you will win
BUG
【在 m********7 的大作中提到】
: 面试让用iterative method写一个 in place insertion sort with singly linked
: list..哎好久没有练，写了半小时还有BUG。。一般大家写这样难度的多久可以写到BUG
: FREE？
|
c********p
发帖数: 1969 | |
m********7
发帖数: 1368 | 4 我也觉得这不是几十分钟能搞定的吧。。
thanks for the tip!!
【在 d**********x 的大作中提到】
: 1 day
: remember what is the INVARIANT in your loop. maintain it and you will win
:
: BUG
|
l********n
发帖数: 1038 | 5 这里循环不变量 是什么，大牛讲讲循环不变量怎么找。我怎么感觉循环不变量这个概
念更像是验证程序对不对用的 |
d**********x
发帖数: 4083 | 6 think about one implementation for partition in quick sort.
keeping one pointer to point to the end of the numbers which are smaller
than the pivot is the key to write correct algorithm
【在 l********n 的大作中提到】
: 这里循环不变量 是什么，大牛讲讲循环不变量怎么找。我怎么感觉循环不变量这个概
: 念更像是验证程序对不对用的
|
l********n
发帖数: 1038 | 7 多问一句，那这道题的invariant是什么
【在 d**********x 的大作中提到】
: think about one implementation for partition in quick sort.
: keeping one pointer to point to the end of the numbers which are smaller
: than the pivot is the key to write correct algorithm
|
d**********x
发帖数: 4083 | 8 for insertion sort
keep one pointer pointing to the last sorted element. the 'invariant' is,
before and at this point, all elements are sorted.
starting with this idea i hope you can think more clear...though it looks
like not that helpful at first glance
【在 l********n 的大作中提到】
: 多问一句，那这道题的invariant是什么
|
r*******n
发帖数: 3020 | 9 这个题有点意思。
ListNode* insert(ListNode* head){
if(head==NULL)
return;
ListNode* curr=head->next;
ListNode* dummyHead= new ListNode(0);
dummyHead->next=head;
while(curr!=NULL){
ListNode* pre=dummyHead;
// Find where to insert
while(p!=curr){
if(p->val>=curr->val)
break;
pre=p;
p=p->next;
}
if(p==curr){
//curr's value is largest so far
curr=curr->next;
}else{
//detach curr node and insert it behind of node pre
ListNode* t = curr->next;
curr->next=p;
pre->next=curr;
curr=t;
}
}
ListNode* newHead=dummyHead->next;
delete dummyHead;
return newHead;
}
BUG
【在 m********7 的大作中提到】
: 面试让用iterative method写一个 in place insertion sort with singly linked
: list..哎好久没有练，写了半小时还有BUG。。一般大家写这样难度的多久可以写到BUG
: FREE？
|
m********7
发帖数: 1368 | 10 和我这个很相似。。大牛写了多久？
List * inPlaceInsertionSort(List *head){
if(!head) throw(“empty list”);
// assume head is sorted, and unsort is unsorted
List *unsort = head->next;
while(unsort){
// take the front element from unsort
List *prev = NULL;
List *iter = head;
List *key = unsort;
// iterate within sorted list
while(iter){
if(iter->data < key->data){
prev = iter;
iter = iter->next;
}
else
break;
}
// if iter reaches end of sorted list, then sort the next node
unsort = unsort->next;
if(iter==key)
continue;
// mark the place where to insert key
List *place = iter;
// move iter to the end of sorted list and connnect to new unsort
while(iter->next!=key)
iter=iter->next;
iter->next = unsort;
// insert key to place
if(prev==NULL)
head = key;
else
prev->next = key;
key->next = place;
}
return head;
} |
e*******s
发帖数: 1979 | 11 一两个礼拜吧
BUG
【在 m********7 的大作中提到】
: 面试让用iterative method写一个 in place insertion sort with singly linked
: list..哎好久没有练，写了半小时还有BUG。。一般大家写这样难度的多久可以写到BUG
: FREE？
|
