Bạn sẽ "viết 1 hàm tìm số có giá trị lớn thứ 2 trong dãy số cho trước" như thế nào?


(Lê Trần Đạt) #1

Sáng nay Đạt thấy topic này trên Voz, mới tới trưa mà đã lên 15 trang.

Tóm tắt nội dung:

Một bạn, có vẻ như đang cay cú, đăng câu hỏi này và nói rằng “thằng em” ở dãy trọ không làm được bài này nhưng lại deal được lương 8tr.

https://vozforums.com/showthread.php?t=4971101

Nếu là các bạn, với đề “viết 1 hàm tìm số có giá trị lớn thứ 2 trong dãy số cho trước” thì bạn sẽ giải như thế nào?

Chú ý là đề chỉ bao gồm viết 1 hàm tìm số có giá trị lớn thứ 2 trong dãy số cho trước, không có yêu cầu gì khác.


Đạt có 2 cách giải bài này. Một cách lúc còn đi học và một cách lúc đã đi làm. Đạt sẽ chia sẻ sau.

Update, đã chia sẻ ở đây. Gạch đá nào :slight_smile:


(Nguyen Ca) #2

Cái bài này phỏng vấn bên capegini có nè :D. Và yêu cầu là 1 vòng for.


(cescnghia) #3

1 vòng lập for, mình ko có xử lý trường hợp mảng chỉ có 1 phần tử.

#include <stdio.h>
#include <limits.h>

int function(int* tab, size_t length);

int main(void){
	int tab[] = {1, -123, 80, 8, 2, 10, 9, 18, -1000, 200, 1, 4};
	int result = function(tab, 12);
	printf("Second max in this array : %d\n", result);

        return 0;
}


int function(int* tab, size_t length){
	int max1 = INT_MIN;
	int max2 = INT_MIN;
	int i;
	for(i = 0; i < length; i++){
		if (max1 < tab[i]){
			max2 = max1;
			max1 = tab[i];
		} else if (max1 > tab[i] && max2 < tab[i]){
			max2 = tab[i];
		}
	}
	return max2;
}

(...) #4

Nếu tất cả các phần tử bằng nhau và bằng luôn INT_MIN thì sao


(Lê Trần Đạt) #5

Đề không yêu cầu dùng 1 vòng lặp. Đạt đưa ra câu hỏi để giải quyết vấn đề thực tế ta gặp

viết 1 hàm tìm số có giá trị lớn thứ 2 trong dãy số cho trước

Chứ không đưa ra bất cứ một giới hạn nào.


(Itachi Citus) #6

Lúc đầu mình cũng nghĩ bài này giống bạn, đọc lại trên voz mới thấy còn nhiều lỗ hổng :smile::

  • Trường hợp length < 2 chưa xử lý.
  • Trường hợp toàn bộ mảng bằng nhau không được xử lý.
  • Thuật toán không tổng quát cho trường hợp mảng không phải số nguyên (INT_MIN).
  • Thuật toán không tổng quát cho trường hợp tìm số lớn thứ n.

Nhìn vậy mà phức tạp hơn tưởng tượng ban đầu :sweat_smile:.


(Kiều Dũng) #7

Hi. Mình không xy ly truong hop mang co 1 phan tu nhe.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    //int arr_a[17] = {19, 0, 5, 7, 13, 15, 11, 6, 4, 5, 102, 11, 15, 15, 16, 18, 19};
    int arr_a[7] = {0,0,0,0,0,0,0};
    int max = arr_a[0];
    int max2 = 0;
    int i;
    //printf("%d", length_array);
    for (i = 0; i < 7; ++i) {
        printf("%d ", arr_a[i]);
    }
    printf("\n");
    for (i = 1; i < 7; ++i) {
        if ( arr_a[i] > max) {
            max = arr_a[i];
            max2 = arr_a[i-1];
        }
        else {
            if (max2 < arr_a[i]) {
                max2 = arr_a[i];
            }

        }
    }

    printf("\n");
    if (max2 == max)
        printf("tat ca phan tu trong mang = nhau");
    else
        printf("%d", max2);
    return 0;
}

(cescnghia) #8

Ok, đồng ý với bạn. Cần phải giải quyết tất cả các exception !


#9

Nếu hàng dùng 1 lần thì :joy:

for (i = 0; i < sophantu; i++){
		if(a[i] > Smax_denhat){
			Smax_denhi = Smax_denhat;
			Smax_denhat = a[i];
		}
	}
if (Smax_denhi == Smax_denhat)
	printf("Mang nay co van de ma tui hong biet van de gi.");

Bookmark topic lại để dành :kissing:


(...) #10

Đề không yêu cầu dùng vòng lặp gì thì em dùng vòng lặp while vậy :sweat_smile:

Sắp xếp mảng giảm dần, xong rồi tìm phần tử khác phần tử thứ nhất đầu tiên thứ nhất.
Phải vậy không anh @ltd :sweat_smile:

#include <iostream>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <random>
using namespace std;

void find_max2(vector<double> &v)	{

	if (v.empty() || v.size() == 1)	{
		cout << "Non-sense input!" << endl;
		return;
	}

	std::sort(v.begin(), v.end(), [](double a, double b)	{ return a > b; });
	
	int i = 0, after_i = i + 1;
	while (i < v.size() - 1 && v[after_i] == v[i])	{
		i = after_i;
		after_i++;
	}

	if (v[after_i] == v[i])
		cout << "All elements have the same value" << endl;
	else
		cout << "Result: " << v[after_i] << endl;
}

int main()	
{
	vector<double> vec;

	int n;
	cout << "Enter number of elements: ";
	cin >> n;
	for (int i = 0; i < n; i++)	{
		vec.push_back(rand());
		cout << vec[i] << " ";
	}
	cout << endl;

	find_max2(vec);

	system("pause");
	return 0;
}

(Hai) #11

Đề bài không giới hạn gì, nên em sẽ dùng cách bình thường nhất :

  • Tìm max
  • Duyệt mảng, tìm phần tử lớn thứ 2

(Lê Trần Đạt) #12

Cách đó cũng ổn, nhưng có cách tốt hơn, cũng không khó mấy. Ví dụ như cách của @nguyenchiemminhvu


Vì Đã có câu trả lời của @nguyenchiemminhvu nên Đạt chia sẻ thế này.

Khi mình đi làm, không có chuyện giới hạn sẽ phải làm trong 1 vòng lặp hay hai vòng lặp. Nhớ một điều là hw thì rẻ mà developer thì mắc.

Nếu mình mắc thì nên đáng giá của nó. Mình có giá thì người khác cũng vậy, tức là viết code làm sao để người sau đọc hiểu và code theo nhanh nhất có thể.

Lúc đi học có ta có thể viết một hàm với rất nhiều if else loạn xạ. Giúp cho chương trình chạy nhanh hơn vài phần triệu giây. Nhưng làm cho developer khác tốn vài phút hoặc 1 ngày hoặc vài ngày chỉ để debug. Vậy có đáng không?


  • Solution lúc Đạt đi học sẽ là một vòng lặp với nhiều if else, cuối cùng chạy được. Nhưng rất khó hiểu và khó debug.

  • Solution lúc Đạt đi làm sẽ là xem thử ngôn ngữ có hỗ trợ hàm sort không, vì dụ như C++ STL hỗ trợ std::sort. Hoặc C hỗ trợ qsort. Hãy sử dụng nó, các hàm này là các hàm tối ưu tốt hơn hàm mình tự viết nhiều. Đừng reinvent the wheel.

Các bước thực hiện như sau:

    1. Sắp sếp giảm dần mảng đã cho
    • hàm sort của thư viện sẽ cho ra kết quả tối ưu nhất có thể trong khi ta tốn 1 phút để code dòng code này.
    1. kiểm tra từ 1 tới n của mảng, nếu thấy số nhỏ hơn mang[0] thì đó chính là số max thứ 2

Ưu điểm:

Code nhanh, hàm sort tối ưu, logic đơn giản dễ debug.

Nhược điểm

Có thể chậm hơn chương trình if else tá lả vài phần triệu giây

Code C

#include <stdio.h>
 
int get_second_max(int * array, int len);
 
int main() {
    int array[10] = {1,2,9,9,9,3,4,5,7,0};
    printf("get_second_max: %d\n", get_second_max(array, 10));
}
 
int cmp_int (const void * a, const void * b)
{
    return ( *(int*)b - *(int*)a );
}
 
int get_second_max(int * array, int size) {
    int max;
    int second_max;
    int i;
 
    qsort (array, size, sizeof (int), cmp_int);
    max = second_max = array[0];
 
    for(i = 1; i < size; ++i) {
        if ( max > array[i] ) {
            second_max = array[i];
            break;
        }
    }
 
    return second_max;
}

Code ++ có thể xem bài của Vũ:


(cescnghia) #13

Em ko đồng ý cách làm của @ltd cho lắm. code của a rất dễ hiểu nhưng qsort có time complexity avg là nlogn (worst case O(n^2 )). Thuật toán của e sẽ nhanh hơn a nếu n lớn.


(Lê Trần Đạt) #14

OK, đó là lý thuyết. Nhưng Đạt hỏi Nghĩa là khi n lớn cỡ như thế nào thì mới xảy ra trường hợp này? Thực tế một chút, khi nào thì mình sẽ làm những công việc xử lý dữ liệu lớn thế này?

Requirements lúc đó sẽ khác rất nhiều, thời gian dành cho việc viết một thuật toán if-else loạn xạ nên dành ra để xem thử sort nào phù hợp với data của mình.

Ví dụ: dựa vào input của mình, tức là cái mảng nhận vào, mình sẽ tìm ra được thuật toán có best case. Gọi thư viện để sử dụng thuật toán phù hợp, sort, làm lại tương tự.

Tức là ta sẽ viết một cái interface nữa, dựa vào loại input, ta sẽ gọi thuật toán sort phù hợp. Code vẫn nhanh, logic vẫn dễ hiểu. Nên nhớ là thời gian code ngắn hơn thời gian debug và fix lỗi.


(cescnghia) #15

Em đồng ý với anh, em chưa đi làm nhưng sẽ tiếp thu ý kiến của anh về việc code đơn giản, dễ hiểu còn hơn là if else tá lả để rồi debug. Anh nghĩ nếu 1 ngày nào đó em đi phỏng vấn và anh là người phỏng vấn em thì anh thích được nghe câu trả lời nào hơn ( qsort hay if else tá lả) ?


(...) #16

Cứ trả lời hết cả 2 trường hợp luôn cho chắc :sweat_smile:


(Gió) #17

Dùng cái set hoặc hàm unique trong c++ cho tiện

template<class T>
T * findmax_k(vector<T> & v,int k){
      sort(v.begin(),v.end());
      auto it=unique(v.begin(),v.end());
      int size=distance(v.begin(),it);
      if(size<k) return NULL;
      return new T(*(it-k));
}


(Nguyễn Hải Đăng) #18

Bạn biết cả 2 và chỉ ra được cái hay cái dở của cả 2 cái thì ai chả thích.


(Lê Trần Đạt) #19

@nghia, anh sẽ tuyển @Gio :joy:@Gio sử dụng đúng công cụ cho đúng vấn đề.

@nghia cái quan trọng là cách em trình bày, em có thể nói rằng em thích làm cái này bởi vì …

Chỉ cần em thuyết phục được người phỏng vấn là được. Anh có đọc được ở đâu đó thì khả năng thuyết phục quan trọng hơn, làm sao em thuyết phục được khách hàng mua hoặc sử dụng sản phẩm của mình rất quan trọng.

Em đi phỏng vấn tức là đi “bán thân”, phải marketing sản phẩm thiệt ngon người ta mới “mua” lận.


(Chế Tiệp Chân Khoa) #20

em đã đọc đi đọc lại đề của anh đạt và trên voz rùi và em chắc chắn không thấy chỗ nào kêu phải dùng C hay C++ cả, vậy check nhanh cái máy có high-level language nào dùng cho tiện :stuck_out_tongue_winking_eye:

def f(l):
    l1 = l
    m = max(l)
    l1 = [x for x in l if x!=m] 
    return max(l1)

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?