头像

byene

我太难了


访客:28979

离线:10小时前



byene
3天前

之前在别的网站上发过3,4月份找实习的经历,这里在Acwing再贴下,后续补上秋招的面经。

背景

  • 本科双非+末流985渣硕
  • 算法:无ACM/OI经验,leetcode 500 + (周赛平均前200名)
  • 实习:无

投递

  • 腾讯wxg ( 4轮技术+ 1轮hr + 1轮技术(hc不够内部转岗到wxg另一个组) ) 挂
  • 腾讯csig ( 3轮技术 + 1轮hr ) OC
  • 腾讯ieg ( 2轮技术 ) 拒了第二轮面试(技术栈不匹配)
  • 美团到店( 3.12第一批笔试:0.45 + 1 + 0.36 + 0.9 + 0.55 2轮技术 ) 无下文
  • 携程( 笔试:1 + 1 + 0.7 ) 无下文
  • 百度(笔试:1 + 0.7 + 1 ) 拒绝面试(北京好像不允许武汉本地人入京, 枯了)
  • 亚马逊 拒绝面试(理由同上)
  • 京东 (一面过,准备拒绝, 理由同上)
  • 招商银行信用卡中心( 笔试 1 + 1 ) 笔试挂( 2道算法题Ak都挂,感觉很卡学校 (985渣硕被刷))
  • 微软( 笔试 0 + 0 + 0 ) 笔试挂( 跟蚂蚁金服的面试冲突了,没有做 )
  • 谷歌( 笔试 kickstart19年全打,最好名次前200名,邀请去了A day with google 面试 1轮技术 ) (过了,由于疫情取消今年实习)
  • 网易云音乐( 笔试 1 + 1 + 0.6 + 1 2轮技术 + hr面 ) 等待结果
  • 华为云( 1 + 0.75 + 0.7 )等待面试
  • 蘑菇街( 2轮技术 + 1轮hr )oc
  • 阿里消息中台( 提前批2轮技术 ) 挂
  • 阿里中间件( 提前批2轮技术 ) 挂
  • 蚂蚁金服中间件( 3.20第一批笔试:0.8 + 1 2轮技术 + 1轮hr ) 等待结果(评级可能不高就没交叉面)
  • 字节跳动( 笔试:1 + 1 + 0.25 + 1 一面过 ) 等待二面
  • 微众银行( 笔试:1 + 1 + 1 ) 无下文
  • 滴滴出行( 2轮技术面 ) 无下文( 实习时间不匹配,需要长时间实习 )
  • 斗鱼( 笔试: 0.8 + 2轮技术 ) 等待结果
  • shopee( 笔试 1 + 0.6 + 0.3 ) 无下文
  • 猿辅导( 内推无下文 )
  • 虎牙( 内推无下文 )
  • 奇安信( 内推无下文 )
  • 小米( 内推无下文 )
  • paypal( 简历挂 )
  • 快手( 简历挂 )

面经

腾讯ieg

(一面)
  1. Epoll ET/LT的区别( 源码级别 )
  2. TCP关键字( reuseport reuseaddress这些 )
  3. nginx了解不(回答了accept锁)
  4. redis相关( 为什么用跳跃表不用红黑树 )
  5. C++ 内存分配,虚函数( 我是Java,基本都不会,不过好像不要紧 )
  6. 进程的内存结构( 我从JVM层面回答的,但是要从linux角度,不会,但是不要紧 )
  7. C++的内存分配( 我从Netty的pooledbytebuffer的Jemalloc来回答的,答出了伙伴分配 )
  8. 可重入锁,自旋锁,悲观锁,乐观锁,cas( 从Java角度和数据库锁来回答,面试官希望我从linux来回答 )
(二面)

技术栈不匹配,拒绝面试

腾讯csig

(一面)
  1. Netty相比NIO来说的优点( 主从Reactor模型+Mpsc队列( 核心思想是异步串行无锁化 ) + 各种组件 )
  2. Netty做了哪些优化( 空轮询bug + 重写keyset )
  3. Epoll源码,LT和ET区别( 是否需要重新放回rdlist )
  4. tomcat/Jetty这些中对兴趣集中的read/write等操作与Netty的不同之处( 这个我没听懂,后来换了个说法,为什么有的网络框架需要将read/write等事件重建线程 )
  5. 线程上下文切换对Netty线程的影响( 面试官想听的是不要把耗时任务放入Netty线程来处理的原因,从线程上下文角度来回答 )
  6. 单例模式的实现方式( 枚举模式 )
  7. Netty的内存分配原理( pooledByteBuffer的源码实现 )( Jemalloc算法的Java实现:FastThreadLocal(确保线程安全) + 伙伴分配算法实现(完全二叉树) + 位图 )
  8. Netty实现RPC的方式
  9. Eureka的原理( CAP理论的AP + 保活机制 )
  10. 从redis集群扯到了raft算法
  11. spring ioc/aop/声明式事务/springboot的自动装配
(二面)
  1. TCP三次的整个流程,从UNIX网络编程的角度来回答( Bind(),listen(),accept这些,扯了一点半连接队列 )
  2. 项目中为什么要使用disruptor框架( 主要是方便构建解密时的消费者链,面试官质疑是为了用而用,确实是= = )
  3. 分布式ID生成算法( 雪花算法,实现参考的百度的uuid-generator,问什么要参考百度开源的这个,有什么优点,有做过对比吗( 没有 ) )
  4. 场景题1:微信实现的IM的算法中,为了保证消息的顺序传递,需要使用递增的分布式ID算法,在分布式的环境下,如果保证每个用户的消息携带的ID是趋势递增的(完全不会)
  5. 场景题2:简单说下百度搜索下,输入几个关键字,后面出现的推荐是如何实现的以及排序的( 我回答说不考虑推荐系统啥的,使用trie树+redis的sortedset )
(三面)

随便聊聊

(Hr面)

随便聊聊( 等后续通知 )

网易云音乐

(一面)
  1. 自我介绍+项目
  2. 线程池相关( 回答得深一点:futuretask + worker类( state为-1的作用 ) )
  3. Java线程的安全性( 从重排序+可见性+原子性来答,尽可能深入回答 )
  4. redis分布式锁相关,在项目中是如何应用的
  5. mysql,聚集和非聚集索引,%like%,maysql的事务,默认级别,gap锁的原理, 组合索引在B+树中是如何表示的( 这块没答好 )
  6. 手撕算法,求top100 ( 快速排序稍微变变 )
(二面)
  1. UNIX网络编程中,使用线程池的情况下,主线程如何将fd传给从线程(不太会)
  2. Redis的网络模型(EPOLL LT模式)+内存分配算法(Jemalloc) + LRU如何实现( 我是从Java的LinkedHashMap回答的,红黑树+双向链表 )
  3. 聊聊对网易云音乐的认识
(Hr面)

随便聊聊

美团到店(严重怀疑被kpi了,明明笔试那么好T。T)

(一面)(18分钟)
  1. 微服务架构
  2. Java的各种锁
  3. 自己实现一个RPC框架
(二面)(15分钟)
  1. 介绍下项目,没了

京东

(一面)
  1. 聊项目
  2. Java线程的安全性,各种锁,Syn和可重入锁的区别(源码级别)
  3. SpringBott的自动装配
  4. Spring的设计模式( 单例,工程,代理,观察者 )
  5. 对比jdk的动态代理和cglib动态代理区别
  6. bean的默认级别(@scope注解,默认是单实例,可以修改为多实例)
  7. 算法题
给一个时间,设计一个算法来判断是对应一周中的哪一天。

输入为三个整数:day、month 和 year,分别表示日、月、年。

返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday",  "Thursday", "Friday", "Saturday"}。(2020.1.1是星期三)

字节

(一面)
  1. 聊项目
  2. redis的原理(数据结构,持久化原理(rdb+aof),主从通信原理(raft协议), 集群与哨兵模式的区别)
  3. 数据库索引(B+树索引,聚簇与非聚簇,组合索引(最左匹配))
  4. 数据库事务(隔离级别,各种读问题, innodb默认隔离级别)
  5. 算法题
排序二叉树第k大结点

斗鱼

(一面)
  1. 聊项目
  2. 聊JVM(垃圾回收,内存分配,有没有实际调优过(没有))
  3. 聊线程池(自带的常用3中线程池原理,参数+流程 + 源码)
  4. 聊数据库(隔离级别,事务性)
  5. 随便写个二叉树遍历
(二面)
  1. 聊项目
  2. 聊TCP在UNIX网络编程下的原理
  3. 愿不愿意转go + 闲聊

阿里消息中台

(一面)
  1. select/poll/epoll 理解, ET/LT源码区别
  2. tcp协议,setnoday配置, reset包
  3. JUC中的copyonwrite的理解
  4. 可重入锁源码(公平与非公平模式), 在唤醒过程做了哪些优化
  5. netty线程模型,write()和channel.write()的区别
(二面)
  1. 全程吊打,项目到了几百万,甚至上亿的级别如何优化,然后凉凉

其他

其他的还有的面经,其实跟上面知识点差不多,加上自己之前没有记录,忘了很多,大家将就看看

体会

  1. 一定要早投,不然后面可够你等的
  2. 基础扎实是不够的,还要有项目支撑(在项目的基础上问基础),我一般能过一面,二面就拉闸,因为没有实习经历
  3. 建议面一轮总结后就忘一轮(别在意结果),因为等得是真的难受,各位心态要好
  4. 尽量海投
  5. 多做项目,没有就上github上面找

项目建议

我自己的话没有实习经历,基本都是自学,我自己的话对Netty框架比较感兴趣,这里以Netty为基础给大家几个项目方向参考

  • 基于Netty实现RPC框架,在此基础上实现raft算法,然后继续在此基础上实现一个简单的kv存储。
  • 基于how tomcat works这本书,自己使用NIO和Netty分别实现一个简易的Http服务器
  • 使用EPOLL/POLL/SELECT 三种网络编程模式,实现一个c语言版的简易Netty,并在此基础上实现Http协议的解析,并使用webbench进行压力测试
  • 自己实现一个简易的spring 框架 支持IOC/AOP,网上资料很多,如果不满足,可以阅读blade(https://github.com/lets-blade/blade)这个开源项目的源码



byene
6天前

1. 题意看不懂(pass)

2. leetcode480

3. 最长连续1的方案数

题意

给定01字符串s,以及数k, 最多有k次操作,可以将s中的0变成1, 求使得s中连续的1的最多的方案数

eg

1010101  1
输出3

解释
最长的连续1是3, 有3种方案
1110101 1011101 1010111


题解
二分+滑动窗口先求最长的连续1的长度, 然后再滑动窗口这个最长长度判断

#include<bits/stdc++.h>
using namespace std;

string str;
int n, k;

bool Check( int m )
{
    int cnt = 0;
    for( int i = 0; i < m; i ++ )
    {
        if( str[ i ] == '0' ) cnt ++;
    }
    if( cnt <= k ) return true;
    for( int i = m; i < n; i ++ )
    {
        if( str[ i ] == '0' ) cnt ++;
        if( str[ i - m ] == '0' ) cnt --;
        if( cnt <= k ) return true;
    }
    return false;
}

int main()
{
    cin >> n >> k;
    cin >> str;
    int Maxlen = 0;
    int l = 0;
    int r = n;
    while( l <= r )
    {
        auto mid = l + r >> 1;
        if( Check(mid) )
        {
            Maxlen = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    int tot = 0;
    int cnt = 0;
    for( int i = 0; i < Maxlen; i ++ )
    {
        if( str[ i ] == '0' ) cnt ++;
    }
    if( cnt <= k ) tot ++;
    for( int i = Maxlen; i < n; i ++ )
    {
        if( str[ i ] == '0' ) cnt ++;
        if( str[ i - Maxlen ] == '0' ) cnt --;
        if( cnt <= k ) tot ++;
    }
    cout << tot << endl;
    return 0;
}



byene
6天前
重建多叉树
给出一组数对表示结点的父子关系,重建多叉树
[(1,2),(1,3),(1,4),(2,5),(2,6),(3,7),(3,8),(8,9)]

                   1
            2.     3.    4
         5.  6.  7 8
                       9
删除连续数字大于等于k的数,求剩下的数组
距离,k = 3 时,先删除3个3,合并后删除3个2,剩下[1, 4, 5, 5, 6, 5]
[1, 2, 2, 3, 3, 3, 2, 4, 5, 5, 6, 5]
[1, 2, 2, 2, 4, 5, 5, 6, 5]
[1, 4, 5, 5, 6, 5]
抽牌 (leetcode950)
假设有一堆牌,去翻牌:

1. 先翻出第一张牌

2. 假设还有牌,就把当前第一张牌放到牌堆最底下

3. 假设还有牌就回到第 1 步

给一些数字各不相同的牌出来,帮我排列这些牌,使得按照上面的规则,最终翻出来的牌是从大到小排列的。

3 5 7 2 1

output:

????? = 7 1 5 2 3

7     (5 2 3 1)

5     (3 1 2)

3     (2 1)

2     (1)

1

使得翻牌的结果序列正好是

7 5 3 2 1
最接近的值
单调数组,一分为二,交换位置,得到新的数组 arr
1 2 | 3 5 6 
3 5 6 1 2 ->arr
目标值 target
arr 中与 target 最接近的值所在的位置

eg : 输入2.5 输出0 4




byene
6天前

之前牛客网发过一次题解,感觉在acwing发更合适一点

#include "bits/stdc++.h"
using namespace std;

int a[ 1000010 ];
int n;

int main()
{
    cin >> n;
    vector< int > left;
    vector< int > right;
    for( int i = 1; i <= n; i ++ ) cin >> a[ i ];
    int deep = 0;
    int sum = 0;
    int t = 1;
    while( true )
    {
        if( sum + t > n ) break;
        deep ++;
        sum += t;
        if( deep == 1 )
        {
            left.push_back( a[ sum ] );
           // cout << "deep " << deep + " " << a[ sum ] << endl;
        }
        else
        {
            left.push_back( a[ sum - t + 1 ] );
            right.push_back( a[ sum ] );
           // cout << "deep " << deep << " " << a[ sum - t + 1 ] << " " << a[ sum ] << endl;
        }
        t *= 2;
    }
    int tot = 0;
    int cnt = 0;
    t = 1;
    while( cnt <= deep )
    {
        tot += t;
        t *= 2;
        cnt ++;
    }
    t /= 2;
    int res =  t - ( tot - n );
    //cout << res << endl;
    for( int i = n - res + 1; i <= n; i ++ ) left.push_back( a[ i ] );
    int top = ( res + 1 ) / 2;
    int topres = t / 2 - top;
    int now = n - res;
    for( int i = now - topres + 1; i < now; i ++ ) left.push_back( a[ i ] );
    reverse( right.begin(), right.end() );
    for( auto x: right )
    {
        left.push_back( x );
    }
    int sz = left.size();
    for( int i = 0; i < sz - 1; i ++ ) cout << left[ i ] << " ";
    cout << left[ sz - 1 ] << endl;
    return 0;
}

#include "bits/stdc++.h"
using namespace std;

#define  ll long long

int n, m;
ll v[ 205 ][ 2005 ];
ll sum[ 2050 ][ 205 ];
ll pre[ 2050 ];

int hh, tt;
ll q[ 2050 ], dp[ 2050 ];

int main()
{
    cin >> n >> m;
    for( int i = 1; i <= n; i ++ )
    for( int j = 1; j <= m; j ++ )
    {
        cin >> v[ i ][ j ];
        v[ i ][ j + m ] = v[ i ][ j ];
    }
    for( int i = 1; i <= m * 2; i ++ )
    {
        for( int j = 1; j <= n; j ++ )
        {
            sum[ i ][ j ] = sum[ i ][ j - 1 ] + v[ j ][ i ];
        }
    }
    ll goal = LONG_LONG_MIN;
    for( int i = 1; i <= n; i ++ )
    for( int j = i; j <= n; j ++ )
    {
        for( int k = 1; k <= m * 2; k ++ ) pre[ k ] = pre[ k - 1 ] + sum[ k ][ j ] - sum[ k ][ i - 1 ];
        ll ans = LONG_LONG_MIN;
        hh = 0;
        tt = -1;
        dp[ 0 ] = 0;
        q[ ++ tt ] = 0;
        for( int k = 1; k <= m * 2; k ++ )
        {
            if( hh <= tt && k - q[ hh ] > m ) hh ++;
            if( hh <= tt ) dp[ k ] = pre[ k ] - pre[ q[ hh ] ];
            while( hh <= tt && pre[ q[ tt ] ] >= pre[ k ] ) tt --;
            q[ ++ tt ] = k;
        }
        for( int k = 1; k <= m * 2; k ++ ) goal = max( goal, dp[ k ] );
    }
    cout << goal << endl;
    return 0;
}

  #include "bits/stdc++.h"
using namespace std;

int dp[ 305 ][ 305 ][ 21 ];
int n, k;

int main()
{
    cin >> n >> k;
    for( int i = 1; i <= n; i ++ )
    for( int j = 1; j <= n; j ++ )
    for( int x = 0; x <= k; x ++ ) dp[ i ][ j ][ x ] = 100000000;

    for( int q = 0; q <= k; q ++ )
    for( int len = 1; len  <= n; len ++ )
    {
        for( int i = 1; i + len - 1 <= n; i ++ )
        {
            int j = i + len - 1;
            if( i == j )
            {
                dp[ i ][ j ][ q ] = 0;
            } else {
                if( q != 0 )
                {
                    dp[ i ][ j ][ q ] = min(dp[ i + 1 ][ j ][ q - 1 ], dp[ i ][ j - 1 ][ q - 1 ]);
                    for( int x = i + 1; x < j; x ++ )
                    {
                        dp[ i ][ j ][ q ] = min( dp[ i ][ j ][ q ], max( dp[ i ][ x - 1 ][ q - 1 ], dp[ x + 1 ][ j ][ q - 1 ] ) );
                    }
                }
                dp[ i ][ j ][ q ] = min( dp[ i ][ j ][ q ], i + dp[ i + 1 ][ j ][ q ] );
                dp[ i ][ j ][ q ] = min( dp[ i ][ j ][ q ], j + dp[ i ][ j - 1 ][ q ] );
                for( int x = i + 1; x < j; x ++ )
                {
                    dp[ i ][ j ][ q ] = min( dp[ i ][ j ][ q ], x + max( dp[ i ][ x - 1 ][ q ], dp[ x + 1 ][ j ][ q ] ) );
                }
            }
        }
    }
    cout << dp[ 1 ][ n ][ k ] << endl;
}


新鲜事 原文

byene
25天前
AcWing《算法进阶课》拼团优惠!https://www.acwing.com/activity/content/introduction/32/group_buy/398/


活动打卡代码 AcWing 1250. 格子游戏

byene
9个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 201;

int Fa[ N * N ];

int Find( int x )
{
    return Fa[ x ] == x ? x : Fa[ x ] = Find( Fa[ x ] );
}

void Init( int n )
{
    for( int i = 1; i <= n * n; i ++ ) Fa[ i ] = i;
}

int n, m, x, y;
string dr;

int main()
{
    cin >> n >> m;
    Init( n );
    int result = -1;
    for( int i = 1; i <= m; i ++ )
    {
        cin >> x >> y >> dr;
        int hash1;
        int hash2;
        if( dr == "D" )
        {
            hash1 = n * ( x - 1 ) + y;
            hash2 = n * x + y;
        }
        else
        {
            hash1 = n * ( x - 1 ) + y;
            hash2 = n * ( x - 1 ) + y + 1;

        }
        int fa1 = Find( hash1 );
        int fa2 = Find( hash2 );
        if( fa1 == fa2 )
        {
            result = i;
            break;
        }
        Fa[ fa2 ] = fa1;
    }
    if( result == -1 ) cout << "draw" << endl;
    else               cout << result << endl;
    return 0;
}


活动打卡代码 AcWing 1116. 马走日

byene
10个月前
#include<bits/stdc++.h>
using namespace std;

const int maxn = 12;

int dx[ 8 ] = { 1, 1, -1, -1, 2, 2, -2, -2 };
int dy[ 8 ] = { 2, -2, 2, -2, 1, -1, 1, -1 };

int vis[ maxn ][ maxn ];

int n, m, t, cnt;
int sx, sy;

void dfs( int x, int y, int num )
{
    vis[ x ][ y ] = 1;
    if( num == n * m )
    {
        vis[ x ][ y ] = 0;
        cnt ++;
        return;
    }
    for( int i = 0; i < 8; i ++ )
    {
        int nx = x + dx[ i ];
        int ny = y + dy[ i ];
        if( nx < 1 || nx > n || ny < 1 || ny > m ) continue;
        if( vis[ nx ][ ny ] ) continue;
        dfs( nx, ny, num + 1 );
    }
    vis[ x ][ y ] = 0;
    return;
}

int main()
{
    cin >> t;
    while( t -- )
    {
        cin >> n >> m >> sx >> sy;
        sx ++;
        sy ++;
        cnt = 0;
        dfs( sx, sy, 1 );
        cout << cnt << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

byene
10个月前
#include<bits/stdc++.h>
using namespace std;

const int maxn = 22;

char Map[ maxn ][ maxn ];
int vis[ maxn ][ maxn ];
int w, h, sx, sy, cnt;

int dx[ 4 ] = { 1, -1, 0, 0 };
int dy[ 4 ] = { 0, 0, -1, 1 };

void dfs( int x, int y )
{
    cnt ++;
    vis[ x ][ y ] = 1;
    for( int i = 0; i < 4; i ++ )
    {
        int nx = x + dx[ i ];
        int ny = y + dy[ i ];
        if( nx < 1 || nx > h || ny < 1 || ny > w ) continue;
        if( Map[ nx ][ ny ] == '#' || vis[ nx ][ ny ] ) continue;
        dfs( nx, ny );
    }
}

int main()
{
    while( cin >> w >> h && w )
    {
        for( int i = 1; i <= h; i ++ )
        for( int j = 1; j <= w; j ++ )
        {
            cin >> Map[ i ][ j ];
            if( Map[ i ][ j ] == '@' )
            {
                sx = i;
                sy = j;
            }
        }
        cnt = 0;
        memset( vis, 0, sizeof( vis ) );
        dfs( sx, sy );
        cout << cnt << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1112. 迷宫

byene
10个月前
#include<bits/stdc++.h>
using namespace std;

const int maxn = 101;

int k, n, flag;
int ax, ay, bx, by;

char Map[ maxn ][ maxn ];
int vis[ maxn ][ maxn ];

int dx[ 4 ] = { -1, 0, 0, 1 };
int dy[ 4 ] = { 0, 1, -1, 0 };

void dfs( int x, int y )
{
    vis[ x ][ y ] = 1;
    if( Map[ x ][ y ] == '#' ) return;
    if( flag ) return;
    if( x == bx && y == by )
    {
        flag = 1;
        return;
    }
    for ( int i = 0; i < 4; i ++ )
    {
        int nx = x + dx[ i ];
        int ny = y + dy[ i ];
        if( nx < 0 || nx >= n || ny < 0 || ny >= n ||  vis[ nx ][ ny ] ) continue;
        dfs( nx, ny );
    }
    return;
}

int main()
{
    cin >> k;
    while( k -- )
    {
        cin >> n;
        for( int i = 0; i < n; i ++ )
        for( int j = 0; j < n; j ++ ) cin >> Map[ i ][ j ];
        cin >> ax >> ay >> bx >> by;
        memset( vis, 0 ,sizeof( vis ) );
        flag = 0;
        dfs( ax, ay );
        if( flag )  cout << "YES" << endl;
        else        cout << "NO" << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1098. 城堡问题

byene
10个月前
#include<bits/stdc++.h>
using namespace std;

const int maxn = 55;

int Map[ maxn ][ maxn ];
int vis[ maxn ][ maxn ];

int n, m;

int area, cnt;

int bfs( int i, int j )
{
    queue< pair< int, int > > q;
    q.push( { i, j } );
    vis[ i ][ j ] = 1;
    int sz = 1;
    while( q.size() )
    {
        auto now = q.front();
        q.pop();
        for( int i = 0; i < 4; i ++ )
        {
            int val = ( Map[ now.first ][ now.second ] >> i ) & 1;
            if( val ) continue;
            int x = now.first;
            int y = now.second;
            if( i == 0 ) y --;
            if( i == 1 ) x --;
            if( i == 2 ) y ++;
            if( i == 3 ) x ++;
            if( x < 1 || x > n || y < 1 || y > m ) continue;
            if( vis[ x ][ y ] ) continue;
            vis[ x ][ y ] = 1;
            sz ++;
            q.push( { x, y } );
        }
    }
    return sz;
}

int main()
{
    cin >> n >> m;
    for( int i = 1; i <= n; i ++ )
    for( int j = 1; j <= m; j ++ ) cin >> Map[ i ][ j ];

    area = 0;
    cnt = 0;

    for( int i = 1; i <= n; i ++ )
    for( int j = 1; j <= m; j ++ )
    {
        if( vis[ i ][ j ] ) continue;
        cnt ++;
        area = max( area, bfs( i, j ) );
    }
    cout << cnt << endl;
    cout << area << endl;
    return 0;
}